Techreport,
Shortest Path Algorithms in Transportation models: classical and innovative aspects
(1997)
Abstract
Shortest Path Problems are among the most studied network flow optimization problems, with interesting applications in various fields. One of such field is transportation, where shortest path problems of different kinds need to be solved. Due to the nature of the application, transportation scientists need very flexible and efficient shortest path procedures, both from the running time point of view, and also for the memory requirements. Since no "best" algorithm currently exists for every kind of transportation problem, research in this field has recently moved to the design and implementation of äd hoc" shortest path procedures, which are able to capture the peculiarities of the problems under consideration. The aim of this work is to present in a unifying framework both the main algorithmic approaches that have been proposed in the past years for solving the shortest path problems arising most frequently in the transportation field, and also some important implementaion techniques which allow one to derive efficient procedures from the general algorithmic schema, in line with trends in current research. In the first part of the paper, afetr presenting the problem, we review those classical primal and dual algorithms which seem to be the most interesting in transportation. Promising reoptimization approaches are then discussed. The second part is devoted to dynamic shortest path problems, which arise very frequently in the transportation field. We analyse the main features and propose a general "chronological" algorithmic paradigm, called Chrono-SPT. We study several special cases, and investigate promising research avenues related to various extensions (time-windows. turn penalties, multicriteria and shortest hyperpaths).
