Optimization Online


Dynamic programming for the time-dependent traveling salesman problem with time windows

Gonnzalo Lera-Romero(gleraromero***at***dc.uba.ar)
Juan Jose Miranda-Bront(jmiranda***at***utdt.edu)
Francisco J. Soulignac(fsoulign***at***dc.uba.ar)

Abstract: The recent growth of direct-to-consumer deliveries has stressed the importance of last-mile logistics, becoming one of the critical factors in city planning. One of the key factors lies in the last-mile deliveries, reaching in some cases nearly 50% of the overall parcel delivery cost. Different variants of the the well-known Traveling Salesman Problem (TSP) arise naturally at the core of complex decision making processes within last mile logistics. The Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW) is one of such variants, where the travel time between two customers is not assumed to be constant. The TDTSPTW is particular suited for distribution problems in large cities, as it effectively accounts the effects of congestion at the planning level, yielding more accurate distributions plans. In this paper, we develop a labeling-based algorithm for the TDTSPTW that incorporates state-of-the-art components from the related literature. We propose a new state-space relaxation specifically designed for the time-dependent context. Extensive computational experiments show the effectiveness of the overall approach and the impact of the new relaxation, outperforming several recent algorithms proposed for the TDTSPTW. In addition, we provide evidence showing that our approach also improves the recent results reported for the Minimum Tour Duration Problem.

Keywords: Traveling salesman problem, time-dependent travel times, time windows, dynamic programming, state-space relaxation, completion bounds

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 01/07/2020
Entry Accepted: 01/07/2020
Entry Last Modified: 01/07/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society