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

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