Shortest path reoptimization vs resolution from scratch: a computational comparison

Abstract

The Shortest Path Problem (SPP) is among the most studied problems in Operations Research, for its theoretical aspects but also because it appears as sub-problem in many combinatorial optimization problems, e.g. Vehicle Routing and Maximum Flow-Minimum Cost problems. Given a sequence of SPPs, suppose that two subsequent instances solely differ by a slight change in the graph structure: that is the set of nodes, the set of arcs or both have changed; then, the goal of the reoptimization consists in solving the $k^{th}$ SPP of the sequence by reusing valuable information gathered in the solution of the $(k-1{)}^{th}$ one. We focused on the most general scenario, i.e. multiple changes for any subset of arcs, for which, only the description of a dual-primal approach has been proposed so far [S. Pallottino and M.G. Scutell‘a, A new algorithm for reoptimizing shortest paths when the arc costs change, Oper. Res. Lett. 31 (2003), pp. 149-160.]. We implemented this framework exploiting efficient data structures, i.e. the Multi Level Bucket. In addition, we compare the performance of our proposal with the well-known Dijkstra's algorithm, applied for solving each modified problem from scratch. In this way, we draw the line – in terms of cost, topology, and size – among the instances where the reoptimization approach is efficient from those that should be solved from scratch.

Keywords:

• Shortest path
• reoptimization
• dual approach
• computational comparison

AMS CLASSIFICATIONS:

• 68
• 90

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Figure 1 in [16] shows the hierarchy of reoptimization problems.

2 We used the maximum arc cost in the graph instance as value for C [see 24].

Additional information

Notes on contributors

Paola Festa

Paola Festa obtained her PhD degree in Operations Research in 2000 and is Full Professor in Operations Research at the University of Napoli FEDERICO II. Since 2000, Paola Festa has been teaching Operations Research and Combinatorial Optimization to undergrade and master students of both Mathematics and Computer Science courses. From 2012 to 2017, she has also taught Programming I to undergrade students of Computer Science course. She is in the scientific committee of the PhD Program in Mathematics and Computer Science (University of Napoli FEDERICO II). She has been in the scientific committee of the PhD Program in Computational Biology and Bioinformatics (University of Napoli FEDERICO II) and of the PhD Program in Operations Research (University of Calabria). Since 1999, she has been frequently and regularly Research Scholar at several national and international research institutions, including CNRs, MIT Lab. for Information and Decision Systems (USA), AT&T Labs Research (USA), and Department of Industrial and Systems Engineering of the University of Florida (USA). Paola Festa is Associate Editor of several international journals, including Journal of Global Optimization, Optimization Letters, ACM Journal on Experimental Algorithmics, and Journal of Biomedical Data Mining. She has been chair or member of the scientific committee of more than 60 international conferences and workshops and the organizer of more than 10 international scientific Workshops/conferences. She is member of the Steering Committee of the International Workshops on Hybrid Metaheuristics. She is author/co-author of more than 90 publications appeared in international journals, books, and peer-reviewed conference proceedings.

Serena Fugaro

Serena Fugaro received the Master's Degree cum laude in Applied Mathematics from the University of Napoli ‘FEDERICO II’, Italy in 2017. Since then, she is a PhD candidate in Mathematics and Applications at the same university with a PhD program in Operations Research. Her current research interests include shortest paths problems on edge-constrained graphs.

Francesca Guerriero

Francesca Guerriero graduated with honors in Management Engineering in 1993 at the University of Calabria (UNICAL), Italy. In 1997, she obtained the PhD in System Engineering and Computer Science at the same University. She was visiting research fellow at the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, MA, USA. She is Full Professor of Operation Research at the Dept. of Mechanical, Energy and Management Engineering, University of Calabria. She is currently the Vice-Dean of the Dept. of Mechanical, Energy and Management Engineering, University of Calabria and she is Vice-President of AIRO, the Italian Operations Research Society. Her main research interests are in the area of network optimization, logistics and distribution, revenue management, project management, optimization and big data. She is co-author of more than 120 papers published in prestigious journal in the Operations Research field. She has been and is a member of the scientific committee of several International Conferences. She acts as a referee for numerous international scientific journals and is a member of the editorial board of several scientific journals. She supervises master and PhD research projects.