Shortest path reoptimization vs resolution from scratch: a computational comparison. (4th May 2022)

• Record Type: Journal Article
• Authors: Festa, Paola; Fugaro, Serena; Guerriero, Francesca
• Is Part Of: Optimization methods and software. Volume 37:Number 3(2022)
• Page Start: 1122
• Page End: 1144
• Publication Date: 2022-05-04
• Subjects: Shortest path -- reoptimization -- dual approach -- computational comparison; 68 -- 90; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2021.1895153
• Languages: English
• ISSNs: 1055-6788

Abstract

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 t h SPP of the sequence by reusing valuable information gathered in the solution of the ( k − 1 ) t h 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.