Shortest path reoptimization vs resolution from scratch: a computational comparison

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 kth 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.