An auction-based approach for the re-optimization shortest path tree problem
P. Festa (),
F. Guerriero () and
A. Napoletano ()
Additional contact information
P. Festa: University of Napoli Federico II
F. Guerriero: University of Calabria
A. Napoletano: University of Napoli Federico II
Computational Optimization and Applications, 2019, vol. 74, issue 3, No 10, 893 pages
Abstract:
Abstract 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}$$(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.
Keywords: Networks; Re-optimization; Shortest path; Auction approach (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
http://link.springer.com/10.1007/s10589-019-00132-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:74:y:2019:i:3:d:10.1007_s10589-019-00132-7
Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589
DOI: 10.1007/s10589-019-00132-7
Access Statistics for this article
Computational Optimization and Applications is currently edited by William W. Hager
More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().