Premium
Efficient modeling of travel in networks with time‐varying link speeds
Author(s) -
Horn Mark E. T.
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200009)36:2<80::aid-net2>3.0.co;2-b
Subject(s) - dijkstra's algorithm , link (geometry) , computer science , duration (music) , scheduling (production processes) , consistency (knowledge bases) , travel time , fifo (computing and electronics) , path (computing) , mathematical optimization , operations research , shortest path problem , algorithm , mathematics , theoretical computer science , artificial intelligence , graph , transport engineering , engineering , computer network , art , literature , computer hardware
This paper investigates exact and approximate methods for estimating time‐minimizing vehicular movements in road network models where link speeds vary over time. The assumptions made about network conditions recognize the intrinsic relationship between speed and travel duration and are substantiated by elementary methods to obtain link travel duration. The assumptions also imply a condition of FIFO consistency, which (as shown by work of Kaufman and Smith) justifies the use of Dijkstra's algorithm for path‐finding purposes. The paper describes several adaptations of the Dijkstra algorithm, including new variants that are addressed specifically to the dynamic conditions mentioned above. Computational tests indicate that these procedures will be useful for scheduling, modeling, and other purposes, when applied to networks of substantial size. © 2000 John Wiley & Sons, Inc.