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

Probabilistic Traveling Salesman Problem with Deadlines

Author

Listed:
  • Ann M. Campbell

    (Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242)

  • Barrett W. Thomas

    (Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242)

Abstract

Time-constrained deliveries are one of the fastest growing segments of the delivery business, and yet there is surprisingly little literature that addresses time constraints in the context of stochastic customer presence. We begin to fill that void by introducing the probabilistic traveling salesman problem with deadlines (PTSPD). The PTSPD is an extension of the well-known probabilistic traveling salesman problem (PTSP) in which, in addition to stochastic presence, customers must also be visited before a known deadline. We present two recourse models and a chance constrained model for the PTSPD. Special cases are discussed for each model, and computational experiments are used to illustrate under what conditions stochastic and deterministic models lead to different solutions.

Suggested Citation

  • Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    • Handle: RePEc:inm:ortrsc:v:42:y:2008:i:1:p:1-21
    DOI: 10.1287/trsc.1070.0203
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. Michel Gendreau & Gilbert Laporte & Marius M. Solomon, 1995. "Single-Vehicle Routing and Scheduling to Minimize the Number of Delays," Transportation Science, INFORMS, vol. 29(1), pages 56-62, February.
    3. Gilles Pesant & Michel Gendreau & Jean-Yves Potvin & Jean-Marc Rousseau, 1998. "An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows," Transportation Science, INFORMS, vol. 32(1), pages 12-29, February.
    4. Dror, Moshe, 1993. "Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution," European Journal of Operational Research, Elsevier, vol. 64(3), pages 432-441, February.
    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. Dimitris J. Bertsimas & Patrick Jaillet & Amedeo R. Odoni, 1990. "A Priori Optimization," Operations Research, INFORMS, vol. 38(6), pages 1019-1033, December.
    7. 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.
    8. Patrick Jaillet, 1988. "A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited," Operations Research, INFORMS, vol. 36(6), pages 929-936, December.
    9. Gilbert Laporte & François V. Louveaux & Hélène Mercure, 1994. "A Priori Optimization of the Probabilistic Traveling Salesman Problem," Operations Research, INFORMS, vol. 42(3), pages 543-549, June.
    10. Laporte, Gilbert & Louveaux, Francois & Mercure, Helene, 1989. "Models and exact solutions for a class of stochastic location-routing problems," European Journal of Operational Research, Elsevier, vol. 39(1), pages 71-78, March.
    11. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1992. "New Insertion and Postoptimization Procedures for the Traveling Salesman Problem," Operations Research, INFORMS, vol. 40(6), pages 1086-1094, December.
    12. Dimitris J. Bertsimas & David Simchi-Levi, 1996. "A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty," Operations Research, INFORMS, vol. 44(2), pages 286-304, April.
    13. Stewart, William R. & Golden, Bruce L., 1983. "Stochastic vehicle routing: A comprehensive approach," European Journal of Operational Research, Elsevier, vol. 14(4), pages 371-385, December.
    14. 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.
    15. Dimitris J. Bertsimas, 1992. "A Vehicle Routing Problem with Stochastic Demand," Operations Research, INFORMS, vol. 40(3), pages 574-585, June.
    16. Bianchi, Leonora & Campbell, Ann Melissa, 2007. "Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 176(1), pages 131-144, January.
    17. Dror, Moshe & Trudeau, Pierre, 1986. "Stochastic vehicle routing with modified savings algorithm," European Journal of Operational Research, Elsevier, vol. 23(2), pages 228-235, February.
    18. 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.
    19. Roberto Wolfler Calvo, 2000. "A New Heuristic for the Traveling Salesman Problem with Time Windows," Transportation Science, INFORMS, vol. 34(1), pages 113-124, February.
    20. Slotnick, Susan A. & Sobel, Matthew J., 2005. "Manufacturing lead-time rules: Customer retention versus tardiness costs," European Journal of Operational Research, Elsevier, vol. 163(3), pages 825-856, June.
    21. Bastian, Cock & Rinnooy Kan, Alexander H. G., 1992. "The stochastic vehicle routing problem revisited," European Journal of Operational Research, Elsevier, vol. 56(3), pages 407-412, February.
    22. Michel Gendreau & Gilbert Laporte & René Séguin, 1995. "An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers," Transportation Science, INFORMS, vol. 29(2), pages 143-155, May.
    23. S. Y. Teng & H. L. Ong & H. C. Huang, 2004. "An Integer L-Shaped Algorithm For Time-Constrained Traveling Salesman Problem With Stochastic Travel And Service Times," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 21(02), pages 241-257.
    24. A. Charnes & W. W. Cooper, 1963. "Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints," Operations Research, INFORMS, vol. 11(1), pages 18-39, February.
    25. Pesant, Gilles & Gendreau, Michel & Potvin, Jean-Yves & Rousseau, Jean-Marc, 1999. "On the flexibility of constraint programming models: From single to multiple time windows for the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 117(2), pages 253-263, September.
    26. Wen-Huei Yang & Kamlesh Mathur & Ronald H. Ballou, 2000. "Stochastic Vehicle Routing Problem with Restocking," Transportation Science, INFORMS, vol. 34(1), pages 99-112, February.
    27. Moshe Dror & Gilbert Laporte & Pierre Trudeau, 1989. "Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks," Transportation Science, INFORMS, vol. 23(3), pages 166-176, August.
    28. Edward K. Baker, 1983. "Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem," Operations Research, INFORMS, vol. 31(5), pages 938-945, October.
    29. Frank A. Tillman, 1969. "The Multiple Terminal Delivery Problem with Probabilistic Demands," Transportation Science, INFORMS, vol. 3(3), pages 192-204, August.
    30. John J. Bartholdi & Loren K. Platzman & R. Lee Collins & William H. Warden, 1983. "A Minimal Technology Routing System for Meals on Wheels," Interfaces, INFORMS, vol. 13(3), pages 1-8, June.
    31. Bianchi, Leonora & Knowles, Joshua & Bowler, Neill, 2005. "Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms," European Journal of Operational Research, Elsevier, vol. 162(1), pages 206-219, April.
    32. Julien Bramel & Edward G. Coffman & Peter W. Shor & David Simchi-Levi, 1992. "Probabilistic Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands," Operations Research, INFORMS, vol. 40(6), pages 1095-1106, December.
    33. Dimitris Bertsimas & Philippe Chervi & Michael Peterson, 1995. "Computational Approaches to Stochastic Vehicle Routing Problems," Transportation Science, INFORMS, vol. 29(4), pages 342-352, November.
    34. Bertsimas, Dimitris & Howell, Louis H., 1993. "Further results on the probabilistic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 65(1), pages 68-95, February.
    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. Sheng Liu & Long He & Zuo-Jun Max Shen, 2021. "On-Time Last-Mile Delivery: Order Assignment with Travel-Time Predictors," Management Science, INFORMS, vol. 67(7), pages 4095-4119, July.
    2. Tengyu Wu & Lin He & Haiyan Yu, 0. "Online traveling salesman problem with time cost and non-zealous server," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-24.
    3. Ann Campbell & Michel Gendreau & Barrett Thomas, 2011. "The orienteering problem with stochastic travel and service times," Annals of Operations Research, Springer, vol. 186(1), pages 61-81, June.
    4. Maciej Rysz & Mohammad Mirghorbani & Pavlo Krokhmal & Eduardo L. Pasiliao, 2014. "On risk-averse maximum weighted subgraph problems," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 167-185, July.
    5. Chris Groër & Bruce Golden & Edward Wasil, 2009. "The Consistent Vehicle Routing Problem," Manufacturing & Service Operations Management, INFORMS, vol. 11(4), pages 630-643, February.
    6. Chuck Holland & Jack Levis & Ranganath Nuggehalli & Bob Santilli & Jeff Winters, 2017. "UPS Optimizes Delivery Routes," Interfaces, INFORMS, vol. 47(1), pages 8-23, February.
    7. Li, Xiang & Zhou, Jiandong & Zhao, Xiande, 2016. "Travel itinerary problem," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 332-343.
    8. Zhan, Yang & Wang, Zizhuo & Wan, Guohua, 2021. "Home service routing and appointment scheduling with stochastic service times," European Journal of Operational Research, Elsevier, vol. 288(1), pages 98-110.
    9. Klapp, Mathias A. & Erera, Alan L. & Toriello, Alejandro, 2020. "Request acceptance in same-day delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    10. Li Ping Gan & Will Recker, 2013. "Stochastic Preplanned Household Activity Pattern Problem with Uncertain Activity Participation (SHAPP)," Transportation Science, INFORMS, vol. 47(3), pages 439-454, August.
    11. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    12. Errico, F. & Desaulniers, G. & Gendreau, M. & Rei, W. & Rousseau, L.-M., 2016. "A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times," European Journal of Operational Research, Elsevier, vol. 249(1), pages 55-66.
    13. Si Chen & Bruce Golden & Richard Wong & Hongsheng Zhong, 2009. "Arc-Routing Models for Small-Package Local Routing," Transportation Science, INFORMS, vol. 43(1), pages 43-55, February.
    14. F. Errico & G. Desaulniers & M. Gendreau & W. Rei & L.-M. Rousseau, 2018. "The vehicle routing problem with hard time windows and stochastic service times," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 223-251, September.
    15. Tengyu Wu & Lin He & Haiyan Yu, 2022. "Online traveling salesman problem with time cost and non-zealous server," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 2143-2166, October.
    16. Klapp, Mathias A. & Erera, Alan L. & Toriello, Alejandro, 2018. "The Dynamic Dispatch Waves Problem for same-day delivery," European Journal of Operational Research, Elsevier, vol. 271(2), pages 519-534.
    17. Yossiri Adulyasak & Patrick Jaillet, 2016. "Models and Algorithms for Stochastic and Robust Vehicle Routing with Deadlines," Transportation Science, INFORMS, vol. 50(2), pages 608-626, May.
    18. Maciej Rysz & Foad Mahdavi Pajouh & Pavlo Krokhmal & Eduardo L. Pasiliao, 2018. "Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights," Annals of Operations Research, Springer, vol. 262(1), pages 89-108, March.
    19. Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
    20. Zhouchun Huang & Qipeng Phil Zheng & Eduardo Pasiliao & Vladimir Boginski & Tao Zhang, 2019. "A cutting plane method for risk-constrained traveling salesman problem with random arc costs," Journal of Global Optimization, Springer, vol. 74(4), pages 839-859, August.
    21. Alexander M. Stroh & Alan L. Erera & Alejandro Toriello, 2022. "Tactical Design of Same-Day Delivery Systems," Management Science, INFORMS, vol. 68(5), pages 3444-3463, May.

    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. Wen-Huei Yang & Kamlesh Mathur & Ronald H. Ballou, 2000. "Stochastic Vehicle Routing Problem with Restocking," Transportation Science, INFORMS, vol. 34(1), pages 99-112, February.
    2. Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
    3. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    4. Jian Yang & Patrick Jaillet & Hani Mahmassani, 2004. "Real-Time Multivehicle Truckload Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 38(2), pages 135-148, May.
    5. Gilbert Laporte & FranÇois V. Louveaux & Luc van Hamme, 2002. "An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 50(3), pages 415-423, June.
    6. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    7. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    8. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    9. Nicola Secomandi & François Margot, 2009. "Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 57(1), pages 214-230, February.
    10. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    11. Alan L. Erera & Juan C. Morales & Martin Savelsbergh, 2010. "The Vehicle Routing Problem with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 44(4), pages 474-492, November.
    12. Bertazzi, Luca & Secomandi, Nicola, 2018. "Faster rollout search for the vehicle routing problem with stochastic demands and restocking," European Journal of Operational Research, Elsevier, vol. 270(2), pages 487-497.
    13. Luo, Zhixing & Qin, Hu & Zhang, Dezhi & Lim, Andrew, 2016. "Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 69-89.
    14. Majed G. Alharbi & Ahmed Stohy & Mohammed Elhenawy & Mahmoud Masoud & Hamiden Abd El-Wahed Khalifa, 2021. "Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features," Sustainability, MDPI, vol. 13(22), pages 1-12, November.
    15. 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.
    16. Florio, Alexandre M. & Hartl, Richard F. & Minner, Stefan, 2020. "Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 285(1), pages 172-182.
    17. Aykagan Ak & Alan L. Erera, 2007. "A Paired-Vehicle Recourse Strategy for the Vehicle-Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 41(2), pages 222-237, May.
    18. Krishna Chepuri & Tito Homem-de-Mello, 2005. "Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 153-181, February.
    19. Tan, K.C. & Cheong, C.Y. & Goh, C.K., 2007. "Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation," European Journal of Operational Research, Elsevier, vol. 177(2), pages 813-839, March.
    20. Chrysanthos E. Gounaris & Wolfram Wiesemann & Christodoulos A. Floudas, 2013. "The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty," Operations Research, INFORMS, vol. 61(3), pages 677-693, June.

    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:42:y:2008:i:1:p:1-21. 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.