IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v45y1997i3p365-377.html
   My bibliography  Save this article

Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints

Author

Listed:
  • Aristide Mingozzi

    (University of Bologna, Bologna, Italy)

  • Lucio Bianco

    (University “Tor Vergata”, Rome, Italy)

  • Salvatore Ricciardelli

    (University “Tor Vergata”, Rome, Italy)

Abstract

The Traveling Salesman Problem with Time Window and Precedence Constraints ( TSP-TWPC ) is to find an Hamiltonian tour of minimum cost in a graph G = ( X , A ) of n vertices, starting at vertex 1, visiting each vertex i ∈ X during its time window and after having visited every vertex that must precede i , and returning to vertex 1. The TSP-TWPC is known to be NP-hard and has applications in many sequencing and distribution problems. In this paper we describe an exact algorithm to solve the problem that is based on dynamic programming and makes use of bounding functions to reduce the state space graph. These functions are obtained by means of a new technique that is a generalization of the “State Space Relaxation” for dynamic programming introduced by Christofides et al. (Christofides, N., A. Mingozzi, P. Toth. 1981b. State space relaxation for the computation of bounds to routing problems. Networks 11 145–164.). Computational results are given for randomly generated test problems.

Suggested Citation

  • Aristide Mingozzi & Lucio Bianco & Salvatore Ricciardelli, 1997. "Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints," Operations Research, INFORMS, vol. 45(3), pages 365-377, June.
    • Handle: RePEc:inm:oropre:v:45:y:1997:i:3:p:365-377
    DOI: 10.1287/opre.45.3.365
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.45.3.365
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.45.3.365?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
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Anirudh Subramanyam & Chrysanthos E. Gounaris, 2018. "A Decomposition Algorithm for the Consistent Traveling Salesman Problem with Vehicle Idling," Transportation Science, INFORMS, vol. 52(2), pages 386-401, March.
    2. Vittorio Maniezzo, 1999. "Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 358-369, November.
    3. Qin, Hu & Zhang, Zizhen & Lim, Andrew & Liang, Xiaocong, 2016. "An enhanced branch-and-bound algorithm for the talent scheduling problem," European Journal of Operational Research, Elsevier, vol. 250(2), pages 412-426.
    4. Filippo Focacci & Andrea Lodi & Michela Milano, 2002. "A Hybrid Exact Algorithm for the TSPTW," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 403-417, November.
    5. Christian Tilk & Stefan Irnich, 2014. "Dynamic Programming for the Minimum Tour Duration Problem," Working Papers 1408, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 04 Aug 2014.
    6. Claudia Bode & Stefan Irnich, 2012. "In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem," Working Papers 1212, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    7. Zhang, Zizhen & Qin, Hu & Zhu, Wenbin & Lim, Andrew, 2012. "The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach," European Journal of Operational Research, Elsevier, vol. 220(2), pages 295-304.
    8. Nagih, Anass & Soumis, Francois, 2006. "Nodal aggregation of resource constraints in a shortest path problem," European Journal of Operational Research, Elsevier, vol. 172(2), pages 500-514, July.
    9. Roberti, R. & Wen, M., 2016. "The Electric Traveling Salesman Problem with Time Windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 32-52.
    10. Vicky Mak & Andreas Ernst, 2007. "New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 66(1), pages 69-98, August.
    11. Jozefczyk, Jerzy, 2001. "Scheduling tasks on moving executors to minimise the maximum lateness," European Journal of Operational Research, Elsevier, vol. 131(1), pages 171-187, May.
    12. Claudio Gambella & Joe Naoum-Sawaya & Bissan Ghaddar, 2018. "The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 554-569, August.
    13. Roberto Baldacci & Vittorio Maniezzo & Aristide Mingozzi, 2004. "An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation," Operations Research, INFORMS, vol. 52(3), pages 422-439, June.
    14. Selvaprabu Nadarajah & Andre A. Cire, 2020. "Network-Based Approximate Linear Programming for Discrete Optimization," Operations Research, INFORMS, vol. 68(6), pages 1767-1786, November.
    15. Vu, Duc Minh & Hewitt, Mike & Vu, Duc D., 2022. "Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery," European Journal of Operational Research, Elsevier, vol. 302(3), pages 831-846.
    16. Gonzalo Lera-Romero & Juan José Miranda Bront & Francisco J. Soulignac, 2022. "Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3292-3308, November.
    17. Kap Hwan Kim & Jong Wook Bae, 2004. "A Look-Ahead Dispatching Method for Automated Guided Vehicles in Automated Port Container Terminals," Transportation Science, INFORMS, vol. 38(2), pages 224-234, May.
    18. Christian Tilk & Stefan Irnich, 2017. "Dynamic Programming for the Minimum Tour Duration Problem," Transportation Science, INFORMS, vol. 51(2), pages 549-565, May.
    19. Bode, Claudia & Irnich, Stefan, 2014. "The shortest-path problem with resource constraints with (k,2)-loop elimination and its application to the capacitated arc-routing problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 415-426.
    20. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2012. "New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 356-371, August.
    21. Sanjeeb Dash & Oktay Günlük & Andrea Lodi & Andrea Tramontani, 2012. "A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 132-147, February.

    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:inm:oropre:v:45:y:1997:i:3:p:365-377. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.