Article ID: | iaor20165035 |
Volume: | 69 |
Issue: | 1 |
Start Page Number: | 23 |
End Page Number: | 32 |
Publication Date: | Jan 2017 |
Journal: | Networks |
Authors: | Pacifici Andrea, Nicosia Gaia, Di Bartolomeo Marco, Grande Enrico |
Keywords: | networks: path, combinatorial optimization, heuristics, networks: flow |
Flows over time problems relate to finding optimal flows over a capacitated network where transit times on network arcs are explicitly considered. In this article, we study the problem of determining a minimum cost origin‐destination path where the cost and the travel time of each arc depend on the time taken to travel from the origin to that particular arc along the path. We provide computational complexity results for this problem and an exact solution algorithm based on an enumeration scheme on the corresponding time expanded network. Finally, we show the efficiency of our approach through a number of experimental tests.