IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v329y2026i1p96-111.html

Models and algorithms for the Time Window Assignment Traveling Salesperson Problem with stochastic travel times

Author

Listed:
  • Cavaliere, Francesco
  • Fischetti, Matteo
  • Roberti, Roberto
  • Salvagnin, Domenico

Abstract

We study the Time Window Assignment Traveling Salesperson Problem with Stochastic Travel Times, a two-stage stochastic problem where the first-stage decisions involve the routing aspects and the customer time window definition. Second-stage decisions follow, which integrate travel time uncertainties into the optimization process. The objective is to minimize the combined routing and time window cost, including penalties for earliness and lateness, marking a shift from a cost-focused routing strategy to a more balanced approach that considers both cost and service quality aspects in delivery operations.

Suggested Citation

  • Cavaliere, Francesco & Fischetti, Matteo & Roberti, Roberto & Salvagnin, Domenico, 2026. "Models and algorithms for the Time Window Assignment Traveling Salesperson Problem with stochastic travel times," European Journal of Operational Research, Elsevier, vol. 329(1), pages 96-111.
    • Handle: RePEc:eee:ejores:v:329:y:2026:i:1:p:96-111
    DOI: 10.1016/j.ejor.2025.07.034
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221725005600
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.07.034?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
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Magdalena A. K. Lang & Catherine Cleophas & Jan Fabian Ehmke, 2021. "Anticipative Dynamic Slotting for Attended Home Deliveries," SN Operations Research Forum, Springer, vol. 2(4), pages 1-39, December.
    2. Subramanyam, Anirudh & Wang, Akang & Gounaris, Chrysanthos E., 2018. "A scenario decomposition algorithm for strategic time window assignment vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 296-317.
    3. Kevin Dalmeijer & Guy Desaulniers, 2021. "Addressing Orientation Symmetry in the Time Window Assignment Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 495-510, May.
    4. Xinan Yang & Arne K. Strauss & Christine S. M. Currie & Richard Eglese, 2016. "Choice-Based Demand Management and Vehicle Routing in E-Fulfillment," Transportation Science, INFORMS, vol. 50(2), pages 473-488, May.
    5. Côté, Jean-François & Mansini, Renata & Raffaele, Alice, 2024. "Multi-period time window assignment for attended home delivery," European Journal of Operational Research, Elsevier, vol. 316(1), pages 295-309.
    6. Abdollahi, Mohammad & Yang, Xinan & Nasri, Moncef Ilies & Fairbank, Michael, 2023. "Demand management in time-slotted last-mile delivery via dynamic routing with forecast orders," European Journal of Operational Research, Elsevier, vol. 309(2), pages 704-718.
    7. 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.
    8. Şifa Çelik & Layla Martin & Albert H. Schrotenboer & Tom Van Woensel, 2025. "Exact Two-Step Benders Decomposition for the Time Window Assignment Traveling Salesperson Problem," Transportation Science, INFORMS, vol. 59(2), pages 210-228, March.
    9. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    10. Uchoa, Eduardo & Pecin, Diego & Pessoa, Artur & Poggi, Marcus & Vidal, Thibaut & Subramanian, Anand, 2017. "New benchmark instances for the Capacitated Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 257(3), pages 845-858.
    11. Remy Spliet & Said Dabia & Tom Van Woensel, 2018. "The Time Window Assignment Vehicle Routing Problem with Time-Dependent Travel Times," Transportation Science, INFORMS, vol. 52(2), pages 261-276, March.
    12. Neves-Moreira, Fábio & Pereira da Silva, Diogo & Guimarães, Luís & Amorim, Pedro & Almada-Lobo, Bernardo, 2018. "The time window assignment vehicle routing problem with product dependent deliveries," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 163-183.
    13. Robert Klein & Michael Neugebauer & Dimitri Ratkovitch & Claudius Steinhardt, 2019. "Differentiated Time Slot Pricing Under Routing Considerations in Attended Home Delivery," Service Science, INFORMS, vol. 53(1), pages 236-255, February.
    14. Anastasios D. Vareias & Panagiotis P. Repoussis & Panagiotis P. Repoussi, 2019. "Assessing Customer Service Reliability in Route Planning with Self-Imposed Time Windows and Stochastic Travel Times," Service Science, INFORMS, vol. 53(1), pages 256-281, February.
    15. Remy Spliet & Adriana F. Gabor, 2015. "The Time Window Assignment Vehicle Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 721-731, November.
    16. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    17. Strauss, Arne & Gülpınar, Nalan & Zheng, Yijun, 2021. "Dynamic pricing of flexible time slots for attended home delivery," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1022-1041.
    18. Lang, Magdalena A.K. & Cleophas, Catherine & Ehmke, Jan Fabian, 2021. "Multi-criteria decision making in dynamic slotting for attended home deliveries," Omega, Elsevier, vol. 102(C).
    19. Bruck, Bruno P. & Cordeau, Jean-François & Iori, Manuel, 2018. "A practical time slot management and routing problem for attended home services," Omega, Elsevier, vol. 81(C), pages 208-219.
    20. Spliet, Remy & Desaulniers, Guy, 2015. "The discrete time window assignment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 379-391.
    21. 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.
    22. Niels Agatz & Ann Campbell & Moritz Fleischmann & Martin Savelsbergh, 2011. "Time Slot Management in Attended Home Delivery," Transportation Science, INFORMS, vol. 45(3), pages 435-449, August.
    23. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    24. Fischetti, Matteo & Ljubić, Ivana & Sinnl, Markus, 2016. "Benders decomposition without separability: A computational study for capacitated facility location problems," European Journal of Operational Research, Elsevier, vol. 253(3), pages 557-569.
    Full references (including those not matched with items on IDEAS)

    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. Jean-François Cordeau & Manuel Iori & Dario Vezzali, 2024. "An updated survey of attended home delivery and service problems with a focus on applications," Annals of Operations Research, Springer, vol. 343(2), pages 885-922, December.
    2. Waßmuth, Katrin & Köhler, Charlotte & Agatz, Niels & Fleischmann, Moritz, 2023. "Demand management for attended home delivery—A literature review," European Journal of Operational Research, Elsevier, vol. 311(3), pages 801-815.
    3. Jean-François Cordeau & Manuel Iori & Dario Vezzali, 2023. "A survey of attended home delivery and service problems with a focus on applications," 4OR, Springer, vol. 21(4), pages 547-583, December.
    4. Paradiso, Rosario & Roberti, Roberto & Ulmer, Marlin, 2025. "Lookahead scenario relaxation for dynamic time window assignment in service routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    5. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    6. Koch, Sebastian & Klein, Robert, 2020. "Route-based approximate dynamic programming for dynamic pricing in attended home delivery," European Journal of Operational Research, Elsevier, vol. 287(2), pages 633-652.
    7. Côté, Jean-François & Mansini, Renata & Raffaele, Alice, 2024. "Multi-period time window assignment for attended home delivery," European Journal of Operational Research, Elsevier, vol. 316(1), pages 295-309.
    8. Şifa Çelik & Layla Martin & Albert H. Schrotenboer & Tom Van Woensel, 2025. "Exact Two-Step Benders Decomposition for the Time Window Assignment Traveling Salesperson Problem," Transportation Science, INFORMS, vol. 59(2), pages 210-228, March.
    9. Xin Wang & Okan Arslan & Erick Delage, 2024. "Crowdkeeping in Last-Mile Delivery," Transportation Science, INFORMS, vol. 58(2), pages 474-498, March.
    10. Bonomi, Valentina & Manerba, Daniele & Mansini, Renata & Zanotti, Roberto, 2025. "Optimizing Attended Home Delivery: Multiple recovery options and customer availability profiles to face synchronization failures," International Journal of Production Economics, Elsevier, vol. 279(C).
    11. Charlotte Ackva & Marlin W. Ulmer, 2024. "Consistent routing for local same-day delivery via micro-hubs," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(2), pages 375-409, June.
    12. Subramanyam, Anirudh & Wang, Akang & Gounaris, Chrysanthos E., 2018. "A scenario decomposition algorithm for strategic time window assignment vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 296-317.
    13. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    14. Fernandes, Daniela & Neves-Moreira, Fábio & Amorim, Pedro, 2025. "Fleet sizing with price-sensitive customers in Attended Home Delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 204(C).
    15. Wassmuth, K. & Köhler, C. & Agatz, N.A.H. & Fleischmann, M., 2022. "Demand Management for Attended Home Delivery – A Literature Review," ERIM Report Series Research in Management ERS-2022-002-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    16. Okazaki, Ryota & Oyama, Yuki & Imura, Naoto & Nishinari, Katsuhiro, 2025. "Evaluating choice-based demand management strategies for day-to-day home delivery planning," Research in Transportation Economics, Elsevier, vol. 113(C).
    17. Marlin W. Ulmer & Justin C. Goodson & Barrett W. Thomas, 2024. "Optimal Service Time Windows," Transportation Science, INFORMS, vol. 58(2), pages 394-411, March.
    18. Karels, Vincent C.G. & Rei, Walter & Veelenturf, Lucas P. & Van Woensel, Tom, 2024. "A vehicle routing problem with multiple service agreements," European Journal of Operational Research, Elsevier, vol. 313(1), pages 129-145.
    19. Ruidian Song & Hoong Chuin Lau & Xue Luo & Lei Zhao, 2022. "Coordinated Delivery to Shopping Malls with Limited Docking Capacity," Transportation Science, INFORMS, vol. 56(2), pages 501-527, March.
    20. van der Hagen, L. & Agatz, N.A.H. & Spliet, R. & Visser, T.R. & Kok, A.L., 2022. "Machine Learning-Based Feasibility Checks for Dynamic Time Slot Management," ERIM Report Series Research in Management ERS-2022-001-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:eee:ejores:v:329:y:2026:i:1:p:96-111. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.