IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v74y2019i3d10.1007_s10589-019-00132-7.html
   My bibliography  Save this article

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

Author

Listed:
  • P. Festa

    (University of Napoli Federico II)

  • F. Guerriero

    (University of Calabria)

  • A. Napoletano

    (University of Napoli Federico II)

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.

Suggested Citation

  • P. Festa & F. Guerriero & A. Napoletano, 2019. "An auction-based approach for the re-optimization shortest path tree problem," Computational Optimization and Applications, Springer, vol. 74(3), pages 851-893, December.
    • Handle: RePEc:spr:coopap:v:74:y:2019:i:3:d:10.1007_s10589-019-00132-7
    DOI: 10.1007/s10589-019-00132-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-019-00132-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-019-00132-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    2. Shi, Ning & Zhou, Shaorui & Wang, Fan & Tao, Yi & Liu, Liming, 2017. "The multi-criteria constrained shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 13-29.
    3. Luciana S. Buriol & Mauricio G. C. Resende & Mikkel Thorup, 2008. "Speeding Up Dynamic Shortest-Path Algorithms," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 191-204, May.
    4. Granat, Janusz & Guerriero, Francesca, 2003. "The interactive analysis of the multicriteria shortest path problem by the reference point method," European Journal of Operational Research, Elsevier, vol. 151(1), pages 103-118, November.
    5. Luigi Di Puglia Pugliese & Francesca Guerriero, 2012. "A computational study of solution approaches for the resource constrained elementary shortest path problem," Annals of Operations Research, Springer, vol. 201(1), pages 131-157, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Luigi Di Puglia Pugliese & Francesca Guerriero, 2016. "On the shortest path problem with negative cost cycles," Computational Optimization and Applications, Springer, vol. 63(2), pages 559-583, March.
    2. Gutierrez, Genaro J. & Kouvelis, Panagiotis & Kurawarwala, Abbas A., 1996. "A robustness approach to uncapacitated network design problems," European Journal of Operational Research, Elsevier, vol. 94(2), pages 362-376, October.
    3. Ayşegül Altın & Bernard Fortz & Mikkel Thorup & Hakan Ümit, 2013. "Intra-domain traffic engineering with shortest path routing protocols," Annals of Operations Research, Springer, vol. 204(1), pages 65-95, April.
    4. Petersen, E. R. & Taylor, A. J., 2001. "An investment planning model for a new North-Central railway in Brazil," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(9), pages 847-862, November.
    5. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    6. Cipriani, Ernesto & Fusco, Gaetano, 2004. "Combined signal setting design and traffic assignment problem," European Journal of Operational Research, Elsevier, vol. 155(3), pages 569-583, June.
    7. Wu, Dexiang & Wu, Desheng Dash, 2020. "A decision support approach for two-stage multi-objective index tracking using improved lagrangian decomposition," Omega, Elsevier, vol. 91(C).
    8. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    9. Lara, Cristiana L. & Koenemann, Jochen & Nie, Yisu & de Souza, Cid C., 2023. "Scalable timing-aware network design via lagrangian decomposition," European Journal of Operational Research, Elsevier, vol. 309(1), pages 152-169.
    10. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    11. Joseph Y. J. Chow & Amelia C. Regan, 2011. "Real Option Pricing of Network Design Investments," Transportation Science, INFORMS, vol. 45(1), pages 50-63, February.
    12. Nader Naderializadeh & Kevin A. Crowe, 2020. "Formulating the integrated forest harvest-scheduling model to reduce the cost of the road-networks," Operational Research, Springer, vol. 20(4), pages 2283-2306, December.
    13. Melkote, Sanjay & Daskin, Mark S., 2001. "Capacitated facility location/network design problems," European Journal of Operational Research, Elsevier, vol. 129(3), pages 481-495, March.
    14. Wang, Zujian & Qi, Mingyao, 2019. "Service network design considering multiple types of services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 1-14.
    15. Weckström, Christoffer & Mladenović, Miloš N. & Kujala, Rainer & Saramäki, Jari, 2021. "Navigability assessment of large-scale redesigns in nine public transport networks: Open timetable data approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 147(C), pages 212-229.
    16. Yogesh Kumar Agarwal & Prahalad Venkateshan, 2019. "New Valid Inequalities for the Optimal Communication Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 268-284, April.
    17. Zvi Drezner & Said Salhi, 2002. "Using hybrid metaheuristics for the one‐way and two‐way network design problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(5), pages 449-463, August.
    18. Ospina, Juan P. & Duque, Juan C. & Botero-Fernández, Verónica & Montoya, Alejandro, 2022. "The maximal covering bicycle network design problem," Transportation Research Part A: Policy and Practice, Elsevier, vol. 159(C), pages 222-236.
    19. David Canca & Belén Navarro-Carmona & Gabriel Villa & Alejandro Zarzo, 2023. "A Multilayer Network Approach for the Bimodal Bus–Pedestrian Line Planning Problem," Mathematics, MDPI, vol. 11(19), pages 1-36, October.
    20. Bernard Gendron & Luis Gouveia, 2017. "Reformulations by Discretization for Piecewise Linear Integer Multicommodity Network Flow Problems," Transportation Science, INFORMS, vol. 51(2), pages 629-649, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:74:y:2019:i:3:d:10.1007_s10589-019-00132-7. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.