The Robust Traveling Salesman Problem with Time Windows Under Knapsack-Constrained Travel Time Uncertainty

Enrico Bartolini (), Dominik Goeke (), Michael Schneider () and Mengdie Ye ()
Additional contact information
Enrico Bartolini: Deutsche Post Chair – Optimization of Distribution Networks, School of Business and Economics, Rheinisch-Westfälische Technische Hochschule (RWTH) Aachen University, 52062 Aachen, Germany;
Dominik Goeke: Lufthansa Systems GmbH & Co.KG, 65479 Raunheim, Germany
Michael Schneider: Deutsche Post Chair – Optimization of Distribution Networks, School of Business and Economics, Rheinisch-Westfälische Technische Hochschule (RWTH) Aachen University, 52062 Aachen, Germany;
Mengdie Ye: Deutsche Post Chair – Optimization of Distribution Networks, School of Business and Economics, Rheinisch-Westfälische Technische Hochschule (RWTH) Aachen University, 52062 Aachen, Germany;

Transportation Science, 2021, vol. 55, issue 2, 371-394

Abstract: We study the traveling salesman problem with time windows (TSPTW) under travel time uncertainty—modeled by means of an uncertainty set including all travel time vectors of interest. We consider a knapsack-constrained uncertainty set stipulating a nominal and a peak travel time for each arc and an upper bound Δ on the sum of all deviations from the nominal times. Viewing the difference between the peak time and its nominal value as the maximum delay possibly incurred when traversing the corresponding arc, the problem we consider is thus to find a tour that remains feasible for up to Δ units of delay. This differs from previous studies on robust routing under travel time uncertainty, which have relied on cardinality-constrained sets and only allow for an upper bound on the number of arcs with peak travel time. We propose an exact algorithm based on column generation and dynamic programming that involves effective dominance rules and an extension of the n g -tour relaxation proposed in the literature for the classical TSPTW. The algorithm is able to solve the robust TSPTW under both knapsack- and cardinality-constrained travel time uncertainty. Extensive computational experiments show that the algorithm is successful on instances with up to 80 customers. In addition, we study the impact of the two uncertainty sets on the trade-off between service quality and cost exhibited by the resulting solutions.

Keywords: traveling salesman problem; time windows; uncertain travel time; robust optimization; state space relaxation (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.1011 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:2:p:371-394

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().