EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3662. An Exact Approach For The Time Window Assignment Traveling Salesperson Problem With Stochastic Travel Times

Invited abstract in session TD-58: MILPs for Vehicle Routing 1, stream VeRoLog - Vehicle Routing and Logistics.

Tuesday, 14:30-16:00
Room: S07 (building: 101)

Authors (first author is the speaker)

1. Francesco Cavaliere
University of Padova
2. Matteo Fischetti
DEI, University of Padua
3. Roberto Roberti
Information Engineering, University of Padova
4. Domenico Salvagnin
DEI, University of Padova

Abstract

This study centers on the Time Window Assignment Traveling Salesperson Problem with Stochastic Travel Times, marking a shift from a cost-focused strategy to a more balanced approach that considers both cost and service quality aspects in delivery operations. This research aims to address the challenge of integrating real-world uncertainties, particularly stochastic travel times, into the optimization process. When treated as a two-stage stochastic problem, the first stage involves making decisions about routing and time window assignment using binary and possibly continuous variables. This is followed by handling continuous variables associated with time window violations in the subsequent stage.

This work contributes to the ongoing exploration of vehicle routing, emphasizing the critical role of time window assignment in the optimization framework. Existing literature provides limited methodologies for this specific problem (Celik et al. 2023). In response, we introduce a novel formulation inspired by the Fox et al. three-index formulation for the Time-dependent Traveling Salesperson Problem (Fox et al. 1980). Employing Benders Decomposition as a versatile solution framework, our approach exhibits substantial advancements over prior state-of-the-art solutions for this problem.

Keywords

Status: accepted

Back to the list of papers