摘要
复杂路网模型下多客户之间最短路径的计算,直接影响市区集送货问题的求解效率。该文提出多客户间最短路径扇面Dijkstra算法。该算法首先由客户在路网的分布确定出最小扇形区域及扇面搜索区域,并将路网节点分为拓展点集、邻节点集。然后在搜索过程中通过优化到达邻节点的通行代价来确定新的拓展点集、邻节点集。算法通过限制搜索区域、减少遍历节点的数量来缩短搜索时间。100个分布于北京市的客户间最短路径的计算表明,相对于Dijkstra算法,扇面Dijkstra算法能够在保证精度的前提下,降低15%的最短路径求解时间。
The efficiency in resolving pickup and delivery routes in cities depends on directly calculating the shortest routes among customers in complex road network. A sector Dijkstra algorithm was developed to calculate the shortest routes among such delivery route customers. The minimum sector and searching area were determined from the customer location distribution in the road network, with the road node set divided into an exploiter-node set and a neighbor-node set. The two sets were generated by optimizing the cost to neighbor nodes in the search. The search time was shortened by limiting the search region and reducing the number of node traversed. Application of the algorithm to 100 customers in Beijing shows that the calculational time is reduced by 15% compared with the Dijkstra algorithm with the same precision.
出处
《清华大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2009年第11期1834-1837,共4页
Journal of Tsinghua University(Science and Technology)
基金
北京市科委科技奥运专项基金(H030630020520)
