File(s) under permanent embargo
Dynamic multi-source Dijkstra's algorithm for vehicle routing
conference contribution
posted on 1996-01-01, 00:00 authored by Peter EklundPeter Eklund, S Kirkby, S PollittThis paper discusses the implementation of Dijkstra's 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.