Probabilistic Traveling Salesman Problem with Deadlines
Author
Abstract
Suggested Citation
DOI: 10.1287/trsc.1070.0203
Download full text from publisher
References listed on IDEAS
- Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Dimitris J. Bertsimas & Patrick Jaillet & Amedeo R. Odoni, 1990. "A Priori Optimization," Operations Research, INFORMS, vol. 38(6), pages 1019-1033, December.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Dimitris J. Bertsimas, 1992. "A Vehicle Routing Problem with Stochastic Demand," Operations Research, INFORMS, vol. 40(3), pages 574-585, June.
- 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.
- 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.
- 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.
- 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.
- 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.
- Frank A. Tillman, 1969. "The Multiple Terminal Delivery Problem with Probabilistic Demands," Transportation Science, INFORMS, vol. 3(3), pages 192-204, August.
- 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.
- 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.
- 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.
- 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.
- Dimitris Bertsimas & Philippe Chervi & Michael Peterson, 1995. "Computational Approaches to Stochastic Vehicle Routing Problems," Transportation Science, INFORMS, vol. 29(4), pages 342-352, November.
- 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.
- 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.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- 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).
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
- 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.
- 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.
- 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.
- Chuck Holland & Jack Levis & Ranganath Nuggehalli & Bob Santilli & Jeff Winters, 2017. "UPS Optimizes Delivery Routes," Interfaces, INFORMS, vol. 47(1), pages 8-23, February.
- Li, Xiang & Zhou, Jiandong & Zhao, Xiande, 2016. "Travel itinerary problem," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 332-343.
- 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.
- 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).
- 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.
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.- 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.
- 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.
- Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
- 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.
- 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.
- 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.
- 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.
- Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
- 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.
- Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
More about this item
Keywords
vehicle routing; traveling salesman problem; probabilistic; deadlines;All these keywords.
Statistics
Access and download statisticsCorrections
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.