Skip to main content
Springer Nature Link
Log in

Shortest Path Tour Problems

  • Living reference work entry
  • First Online:
Encyclopedia of Optimization

  • 47 Accesses

Introduction

The shortest path problem (SPP) is one of the most studied problems in the field of operations research. Let G = (V, A) be a directed and weighted graph, where \(C \colon A \rightarrow \mathbb {R}^+ \cup \{0\}\) is a function that assigns a nonnegative length cij to each arc (i, j) ∈ A. The SPP aims at finding an elementary path from a source node s ∈ V  to a target node t ∈ V  (s ≠ t) that minimizes the cost of the path, which is defined as the sum of the costs of the arcs of the path.

In 1959, [9] proposed the Dijkstra algorithm. Since its contribution, a vast amount of variants have been addressed resulting in the family of the constrained shortest path problem (CSPP). In this class of problems, additional constraints are imposed on the path that must be found. In many cases, traversing an arc entails the consumption of a given resource, and the final path has to respect a maximum resource budget [8].

The shortest path tour problem (SPTP) has been firstly introduced in [

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

References

  1. de Andrade RC, Saraiva RD (2018) An integer linear programming model for the constrained shortest path tour problem. Electr Notes Discret Math 69:141–148. https://doi.org/10.1016/J.ENDM.2018.07.019

    Article  MathSciNet  Google Scholar 

  2. Bajaj CP (1971) Some constrained shortest-route problems. Unternehmensforschung Oper Res – Recherche Opérationnelle 15(1):287–301. https://doi.org/10.1007/bf01939836

    MathSciNet  MATH  Google Scholar 

  3. Bhat S, Rouskas GN (2017) Service-concatenation routing with applications to network functions virtualization. In: 2017 26th International Conference on Computer Communication and Networks (ICCCN), pp 1–9

    Google Scholar 

  4. Carrabs F, Cerulli R, Festa P, Laureana F (2017) On the forward shortest path tour problem. In: Sforza A, Sterle C (eds) Optimization and decision science: methodologies and applications. Springer International Publishing, Cham, pp 529–537. https://doi.org/10.1007/978-3-319-67308-0_53

    Chapter  Google Scholar 

  5. Carrabs F, D’Ambrosio C, Ferone D, Festa P, Laureana F (2021) The constrained forward shortest path tour problem: mathematical modeling and GRASP approximate solutions. Networks 78(1):17–31. https://doi.org/10.1002/net.22010

    Article  MathSciNet  Google Scholar 

  6. Di Puglia Pugliese L, Ferone D, Festa P, Guerriero F (2020) Shortest path tour problem with time windows. Eur J Oper Res 282(1):334–344. https://doi.org/10.1016/j.ejor.2019.08.052

    Article  MathSciNet  MATH  Google Scholar 

  7. Di Puglia Pugliese L, Ferone D, Festa P, Guerriero F (2022) A generalized shortest path tour problem with time windows. Comput Optim Appl 83(2):593–614. https://doi.org/10.1007/s10589-022-00405-8

    Article  MathSciNet  MATH  Google Scholar 

  8. Di Puglia Pugliese L, Guerriero F (2013) A survey of resource constrained shortest path problems: exact solution approaches. Networks 62(3):183–200. https://doi.org/10.1002/net.21511

    Article  MathSciNet  MATH  Google Scholar 

  9. Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269–271. https://doi.org/10.1007/bf01386390

    Article  MathSciNet  MATH  Google Scholar 

  10. Ferone D, Festa P, Guerriero F (2020) An efficient exact approach for the constrained shortest path tour problem. Optim Meth Softw 35(1):1–20. https://doi.org/10.1080/10556788.2018.1548015

    Article  MathSciNet  MATH  Google Scholar 

  11. Ferone D, Festa P, Guerriero F, Laganà D (2016) The constrained shortest path tour problem. Comput Oper Res 74:64–77. https://doi.org/10.1016/j.cor.2016.04.002

    Article  MathSciNet  MATH  Google Scholar 

  12. Ferone D, Festa P, Salani M (2021) Branch and bound and dynamic programming approaches for the path avoiding forbidden pairs problem. In: Cerulli R, Dell’Amico M, Guerriero F, Pacciarelli D, Sforza A (eds) Optimization and Decision Science: ODS, Virtual Conference, 19 Nov 2020. Springer International Publishing, Cham, pp 227–235. https://doi.org/10.1007/978-3-030-86841-3_19

    Chapter  Google Scholar 

  13. Festa P (2012) Complexity analysis and optimization of the shortest path tour problem. Optim Lett 6(1):163–175. https://doi.org/10.1007/s11590-010-0258-y

    Article  MathSciNet  MATH  Google Scholar 

  14. Festa P, Guerriero F, Laganà D, Musmanno R (2013) Solving the shortest path tour problem. Eur J Oper Res 230(3):464–474. https://doi.org/10.1016/J.EJOR.2013.04.029

    Article  MathSciNet  MATH  Google Scholar 

  15. Gao L, Rouskas GN (2019) On congestion minimization for service chain routing problems. In: IEEE International Conference on Communications, vol 2019. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/ICC.2019.8761660

  16. Martin S, Magnouche Y, Juvigny C, Leguay J (2022) Constrained shortest path tour problem: branch-and-price algorithm. Comput Oper Res 105819. https://doi.org/10.1016/j.cor.2022.105819

  17. Saraiva RD, de Andrade RC (2020) Constrained shortest path tour problem: models, valid inequalities, and Lagrangian heuristics. Int Trans Oper Res 12782. https://doi.org/10.1111/itor.12782

  18. Sasabe M, Hara T (2020) Shortest path tour problem based integer linear programming for service chaining in NFV networks. In: Proceedings of the 2020 IEEE Conference on Network Softwarization: Bridging the Gap Between AI and Network Softwarization, NetSoft 2020. Institute of Electrical and Electronics Engineers (IEEE), pp 114–121. https://doi.org/10.1109/NetSoft48620.2020.9165364

  19. Sasabe M, Hara T (2021) Capacitated shortest path tour problem-based integer linear programming for service chaining and function placement in NFV networks. IEEE Trans Netw Serv Manag 18(1):104–117. https://doi.org/10.1109/TNSM.2020.3044329

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Istituto di Calcolo e Reti ad Alte Prestazioni, Consiglio Nazionale delle Ricerche, Rende, Italy

    Luigi Di Puglia Pugliese

  2. Department of Mathematics and Applications, University of Naples “Federico II”, Naples, Italy

    Daniele Ferone & Paola Festa

  3. Department of Mechanical, Energy and Management Engineering, University of Calabria, Rende, Italy

    Francesca Guerriero

Authors
  1. Luigi Di Puglia Pugliese
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniele Ferone
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Paola Festa
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Francesca Guerriero
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniele Ferone .

Editor information

Editors and Affiliations

  1. Department of Industrial & Systems Engin, University of Florida, Gainesville, FL, USA

    Panos M. Pardalos

  2. Departmentl of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA, USA

    Oleg A. Prokopyev

Rights and permissions

Reprints and permissions

Copyright information

© 2023 Springer Nature Switzerland AG

About this entry

Check for updates. Verify currency and authenticity via CrossMark

Cite this entry

Di Puglia Pugliese, L., Ferone, D., Festa, P., Guerriero, F. (2023). Shortest Path Tour Problems. In: Pardalos, P.M., Prokopyev, O.A. (eds) Encyclopedia of Optimization. Springer, Cham. https://doi.org/10.1007/978-3-030-54621-2_774-1

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-54621-2_774-1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-54621-2

  • Online ISBN: 978-3-030-54621-2

  • eBook Packages: Living Reference MathematicsReference Module Computer Science and Engineering

Publish with us

Policies and ethics