IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v51y2017i2p549-565.html
   My bibliography  Save this article

Dynamic Programming for the Minimum Tour Duration Problem

Author

Listed:
  • Christian Tilk

    (Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, D-55128 Mainz, Germany)

  • Stefan Irnich

    (Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, D-55128 Mainz, Germany)

Abstract

The minimum tour duration problem (MTDP) is a variant of the traveling salesman problem with time windows, which consists of finding a time window-feasible Hamiltonian path minimizing the tour duration. We present a new effective dynamic programming (DP)-based approach for the MTDP. When solving the traveling salesman problem with time windows with DP, two independent resources are propagated along partial paths, one for costs and one for earliest arrival times. For dealing with tour duration minimization, we provide a new DP formulation with three resources for which effective dominance and bounding procedures are applicable. This is a nontrivial task because in the MTDP at least two resources depend on each other in a nonadditive and nonlinear way. In particular, we define consistent resource extension functions (REFs) so that dominance is straightforward using componentwise comparison for the respective resource vectors. Moreover, one of the main advantages of the new REF definition is that the DP can be reversed consistently such that the forward DP or any of its relaxations provide bounds for the backward DP, and vice versa. Computational tests confirm the effectiveness of the proposed approach.

Suggested Citation

  • Christian Tilk & Stefan Irnich, 2017. "Dynamic Programming for the Minimum Tour Duration Problem," Transportation Science, INFORMS, vol. 51(2), pages 549-565, May.
    • Handle: RePEc:inm:ortrsc:v:51:y:2017:i:2:p:549-565
    as

    Download full text from publisher

    File URL: https://doi.org/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    2. Asvin Goel & Thibaut Vidal, 2014. "Hours of Service Regulations in Road Freight Transport: An Optimization-Based International Assessment," Transportation Science, INFORMS, vol. 48(3), pages 391-412, August.
    3. 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.
    4. Claudia Bode & Stefan Irnich, 2015. "In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem," Transportation Science, INFORMS, vol. 49(2), pages 369-383, May.
    5. Michel Gendreau & Alain Hertz & Gilbert Laporte & Mihnea Stan, 1998. "A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows," Operations Research, INFORMS, vol. 46(3), pages 330-335, June.
    6. E. Balas, 1999. "New classes of efficiently solvable generalized Traveling Salesman Problems," Annals of Operations Research, Springer, vol. 86(0), pages 529-558, January.
    7. Asvin Goel, 2009. "Vehicle Scheduling and Routing with Drivers' Working Hours," Transportation Science, INFORMS, vol. 43(1), pages 17-26, February.
    8. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    9. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    10. Yvan Dumas & Jacques Desrosiers & Eric Gelinas & Marius M. Solomon, 1995. "An Optimal Algorithm for the Traveling Salesman Problem with Time Windows," Operations Research, INFORMS, vol. 43(2), pages 367-371, April.
    11. Jeffrey W. Ohlmann & Barrett W. Thomas, 2007. "A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 80-90, February.
    12. 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.
    13. Jean-Yves Potvin & Tanguy Kervahut & Bruno-Laurent Garcia & Jean-Marc Rousseau, 1996. "The Vehicle Routing Problem with Time Windows Part I: Tabu Search," INFORMS Journal on Computing, INFORMS, vol. 8(2), pages 158-164, May.
    14. Roberto Roberti & Aristide Mingozzi, 2014. "Dynamic ng-Path Relaxation for the Delivery Man Problem," Transportation Science, INFORMS, vol. 48(3), pages 413-424, August.
    15. Egon Balas & Neil Simonetti, 2001. "Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study," INFORMS Journal on Computing, INFORMS, vol. 13(1), pages 56-75, February.
    16. Eric Prescott-Gagnon & Guy Desaulniers & Michael Drexl & Louis-Martin Rousseau, 2010. "European Driver Rules in Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 44(4), pages 455-473, November.
    17. Jean-Yves Potvin & Samy Bengio, 1996. "The Vehicle Routing Problem with Time Windows Part II: Genetic Search," INFORMS Journal on Computing, INFORMS, vol. 8(2), pages 165-172, May.
    18. 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.
    19. Martin W. P. Savelsbergh, 1992. "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 146-154, May.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Rosario Paradiso & Roberto Roberti & Demetrio Laganá & Wout Dullaert, 2020. "An Exact Solution Framework for Multitrip Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 68(1), pages 180-198, January.
    2. Ann-Kathrin Rothenbächer, 2019. "Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures," Transportation Science, INFORMS, vol. 53(3), pages 850-866, May.
    3. Jeanette Schmidt & Christian Tilk & Stefan Irnich, 2023. "Exact Solution of the Vehicle Routing Problem With Drones," Working Papers 2311, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    4. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    5. Christian Tilk & Nicola Bianchessi & Michael Drexl & Stefan Irnich & Frank Meisel, 2018. "Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem," Transportation Science, INFORMS, vol. 52(2), pages 300-319, March.
    6. Selvaprabu Nadarajah & Andre A. Cire, 2020. "Network-Based Approximate Linear Programming for Discrete Optimization," Operations Research, INFORMS, vol. 68(6), pages 1767-1786, November.
    7. 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.
    8. 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.
    9. Goel, Asvin, 2018. "Legal aspects in road transport optimization in Europe," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 144-162.
    10. Ann-Kathrin Rothenbächer, 2017. "Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures," Working Papers 1714, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    11. Fuying Liu & Chen Liu & Qi Zhao & Chenhao He, 2021. "A Hybrid Teaching-Learning-Based Optimization Algorithm for the Travel Route Optimization Problem alongside the Urban Railway Line," Sustainability, MDPI, vol. 13(3), pages 1-17, January.

    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. 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.
    2. 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.
    3. 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.
    4. Fontaine, Romain & Dibangoye, Jilles & Solnon, Christine, 2023. "Exact and anytime approach for solving the time dependent traveling salesman problem with time windows," European Journal of Operational Research, Elsevier, vol. 311(3), pages 833-844.
    5. Christian Tilk, 2016. "Branch-and-Price-and-Cut for the Vehicle Routing and Truck Driver Scheduling Problem," Working Papers 1616, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. 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.
    7. Asvin Goel & Stefan Irnich, 2017. "An Exact Method for Vehicle Routing and Truck Driver Scheduling Problems," Transportation Science, INFORMS, vol. 51(2), pages 737-754, May.
    8. 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.
    9. Tilk, Christian & Goel, Asvin, 2020. "Bidirectional labeling for solving vehicle routing and truck driver scheduling problems," European Journal of Operational Research, Elsevier, vol. 283(1), pages 108-124.
    10. Dieter, Peter & Caron, Matthew & Schryen, Guido, 2023. "Integrating driver behavior into last-mile delivery routing: Combining machine learning and optimization in a hybrid decision support framework," European Journal of Operational Research, Elsevier, vol. 311(1), pages 283-300.
    11. Christian Tilk & Asvin Goel, 2019. "Bidirectional labeling for solving vehicle routing and truck driver scheduling problems," Working Papers 1914, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    12. 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.
    13. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    14. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    15. Qie He & Stefan Irnich & Yongjia Song, 2018. "Branch-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Working Papers 1804, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    16. Ann-Kathrin Rothenbächer, 2019. "Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures," Transportation Science, INFORMS, vol. 53(3), pages 850-866, May.
    17. Asvin Goel & Thibaut Vidal, 2014. "Hours of Service Regulations in Road Freight Transport: An Optimization-Based International Assessment," Transportation Science, INFORMS, vol. 48(3), pages 391-412, August.
    18. 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.
    19. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    20. Ricardo Fukasawa & Qie He & Fernando Santos & Yongjia Song, 2018. "A Joint Vehicle Routing and Speed Optimization Problem," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 694-709, November.

    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:ortrsc:v:51:y:2017:i:2:p:549-565. 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: 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.