Shortest path reoptimization vs resolution from scratch:a computational comparison

Festa, Paola, Fugaro, Serena and Guerriero, Francesca (2022) Shortest path reoptimization vs resolution from scratch:a computational comparison. Optimization Methods and Software, 37 (3). pp. 1122-1144. ISSN 1055-6788

Full text not available from this repository. (Request a copy)

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 (Formula presented.) SPP of the sequence by reusing valuable information gathered in the solution of the (Formula presented.) 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.

Item Type:	Article
Additional Information:	Publisher Copyright: © 2021 Informa UK Limited, trading as Taylor & Francis Group.
Uncontrolled Keywords:	68,90,computational comparison,dual approach,reoptimization,shortest path,software,control and optimization,applied mathematics ,/dk/atira/pure/subjectarea/asjc/1700/1712
Faculty \ School:	Faculty of Social Sciences > Norwich Business School
Related URLs:	https://www.scopus.com/pages/publication...
Depositing User:	LivePure Connector
Date Deposited:	28 May 2026 15:18
Last Modified:	28 May 2026 15:18
URI:	https://ueaeprints.uea.ac.uk/id/eprint/103194
DOI:	10.1080/10556788.2021.1895153

Actions (login required)

View Item