Sector Dijkstra algorithm for shortest routes between customers in complex road networks
Lian Xiaomin · Journal of Tsinghua University(Science and Technology) · 2009
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.