An auction-based approach for the re-optimization shortest path tree problem

• Published in: Computational optimization and applications 2019-12, Vol.74 (3), p.851-893
• Main Authors: Festa, P., Guerriero, F., Napoletano, A.
• Format: Article
• Language: English
• Subjects: Algorithms; Convex and Discrete Geometry; Graphs; Management Science; Mathematics; Mathematics and Statistics; Nodes; Operations Research; Operations Research/Decision Theory; Optimization; Polynomials; Production planning; Shortest-path problems; Statistics
• ISSN: 0926-6003; 1573-2894
• DOI: 10.1007/s10589-019-00132-7

The shortest path tree problem is one of the most studied problems in network optimization. Given a directed weighted graph, the aim is to find a shortest path from a given origin node to any other node of the graph. When any change occurs (i.e., the origin node is changed, some nodes/arcs are added/removed to/from the graph, the cost of a subset of arcs is increased/decreased), in order to determine a (still) optimal solution, two different strategies can be followed: a re-optimization algorithm is applied starting from the current optimal solution or a new optimal solution is built from scratch. Generally speaking, the Re-optimization Shortest Path Tree Problem (R-SPTP) consists in solving a sequence of shortest path problems, where the k th problem differs only slightly from the ( k - 1 ) th one, by exploiting the useful information available after each shortest path tree computation. In this paper, we propose an exact algorithm for the R-SPTP, in the case of origin node change. The proposed strategy is based on a dual approach, which adopts a strongly polynomial auction algorithm to extend the solution under construction. The approach is evaluated on a large set of test problems. The computational results underline that it is very promising and outperforms or at least is not worse than the solution approaches reported in the literature.