A dynamic multi-source Dijkstra´s algorithm for vehicle routing

Author

Eklund, Peter W. ; Kirkby, Steve ; Pollitt, Simon

Author_Institution

Dept. of Comput. Sci., Adelaide Univ., SA, Australia

fYear

1996

fDate

18-20 Nov 1996

Firstpage

329

Lastpage

333

Abstract

This paper discusses the implementation of Dijkstra´s (1959) classic double bucket algorithm for path finding in connected networks. The work reports on a modification of the algorithm embracing both static and dynamic heuristic components and multiple source nodes. The modified algorithm is applied in a 3D spatial information system (SIS) for routing emergency service vehicles. The algorithm has been implemented as a suite of modules and integrated into a commercial SIS software environment. Genuine 3D spatial data is used to test the algorithm on the problem of vehicle routing and rerouting under simulated earthquake conditions in the Japanese city of Okayama. Coverage graphs were also produced giving contour lines joining points with identical travel times

Keywords

directed graphs; earthquakes; emergency services; heuristic programming; road vehicles; scheduling; traffic information systems; visual databases; 3D spatial data; 3D spatial information system; Japan; algorithm testing; commercial software; connected networks; contour lines; coverage graphs; double bucket algorithm; dynamic heuristics; dynamic multi-source algorithm; emergency service vehicles; multiple source nodes; path finding; simulated earthquake conditions; static heuristics; travel times; vehicle routing; Cities and towns; Earthquakes; Emergency services; Heuristic algorithms; Information systems; Routing; Software algorithms; Testing; Vehicle dynamics; Vehicles;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Information Systems, 1996., Australian and New Zealand Conference on

Conference_Location

Adelaide, SA

Print_ISBN

0-7803-3667-4

Type

conf

DOI

10.1109/ANZIIS.1996.573976

Filename

573976