Author
Listed:
- Şifa Çelik
(School of Industrial Engineering, Eindhoven University of Technology, 5612AZ Eindhoven, Netherlands)
- Layla Martin
(School of Industrial Engineering, Eindhoven University of Technology, 5612AZ Eindhoven, Netherlands; and Eindhoven Artificial Intelligence Systems Institute, Eindhoven University of Technology, 5612AZ Eindhoven, Netherlands)
- Albert H. Schrotenboer
(School of Industrial Engineering, Eindhoven University of Technology, 5612AZ Eindhoven, Netherlands; and Eindhoven Artificial Intelligence Systems Institute, Eindhoven University of Technology, 5612AZ Eindhoven, Netherlands)
- Tom Van Woensel
(School of Industrial Engineering, Eindhoven University of Technology, 5612AZ Eindhoven, Netherlands; and Eindhoven Artificial Intelligence Systems Institute, Eindhoven University of Technology, 5612AZ Eindhoven, Netherlands)
Abstract
Next-day delivery logistics services are redefining the industry by increasingly focusing on customer service. Each logistics service provider’s challenge is jointly optimizing time window assignment and vehicle routing for such next-day delivery services. To do so in a cost-efficient and customer-centric fashion, real-life uncertainty, such as stochastic travel times, needs to be incorporated into the optimization process. This paper focuses on the canonical optimization problem within this context: the time window assignment traveling salesperson problem with stochastic travel times (TWATSP-ST). It belongs to two-stage, stochastic, mixed-integer programming problems with continuous recourse. We introduce two-step Benders decomposition with scenario clustering (TBDS) as an exact solution methodology for solving such stochastic programs. The method utilizes a new two-step decomposition along the binary and continuous first stage decisions and introduces a new scenario-retention strategy that combines and generalizes state-of-the-art Benders approaches and scenario-clustering techniques. Extensive experiments show that TBDS is superior to state-of-the-art approaches in the literature. It solves TWATSP-ST instances with up to 25 customers to optimality. It provides better lower and upper bounds that lead to faster convergence than existing state-of-the-art methods. We use TBDS to analyze the structure of the optimal solutions. By increasing routing costs only slightly, customer service can be improved tremendously driven by smartly alternating between high- and low-variance travel arcs to reduce the impact of delay propagation throughout the executed vehicle route.
Suggested Citation
Ş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.
Handle:
RePEc:inm:ortrsc:v:59:y:2025:i:2:p:210-228
DOI: 10.1287/trsc.2024.0750
Download full text from publisher
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:59:y:2025:i:2:p:210-228. 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.