Shortest Path

Universita di Pisa

Dipartimento di Informatica

Technical Report : TR-97-06

Shortest Path Algorithms in Transportation models: classical and innovative aspects

Stefano Pallottino, Maria Grazia Scutella'

April 14, 1997

ADDR: Corso Italia 40,56125 Pisa,Italy. TEL: +39-50-887111. FAX: +39-50-887226

Shortest Path Algorithms in Transportation models: classical and innovative aspects1

Stefano Pallottino University of Perugia, Institute of Electronics via G. Duranti 1/A1, 06131 Perugia, Italy, pallo@di.unipi.it Maria Grazia Scutellà University of Pisa, Department of Computer Science Corso Italia 40, 56125 Pisa, Italy, scut@di.unipi.it

Abstract Shortest Path Problems are among the most studied network flow optimization problems, with interesting applications in various fields. One 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 “ad 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 implementation techniques which allow one to derive efficient procedures from the general algorithmic schema, in line with trends in current research. More precisely, in the first part of the paper, after presenting the problem, we briefly review those classical primal and dual algorithms which seem to be the most interesting in transportation, either as a...