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

GONZALO LERA ROMERO; JUAN JOSÉ MIRANDA BRONT; SOULIGNAC, FRANCISCO J.

Virtual

Conferencia; 11th International Conference on Computational Logistics; 2020

University of Twente

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. According to different studies, one of the key factors lies in the last-mile deliveries, reaching in some cases nearly 50% of the overall parcel delivery cost. Accounting effectively for the effects of congestion at the planning level results in more accurate distributions plans.The Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW) is a variant of the well-known Traveling Salesman Problem with Time Windows (TSPTW) in which travel times are not assumed to be constant. The TDTSPTW accounts for the effects of congestion at the planning level, being particularly suited for distribution problems in large cities. In this presentation, we consider the model proposed in [2] where travel times for each arc are not constant, and instead are modeled as a continuous piecewise linear function satisfying the FIFO condition. Thus, an effective approach for the TDTSPTW must handle efficiently travel times defined by functions instead of its time-independent counterpart, where they are assumed to remain constant along the planning horizon.Our contributions are both algorithmic and methodological. Specifically: i) we propose a labeling-based algorithm for the TDTSPTW that adapts state-of-the-art features from the related (time-independent) literature (see, e.g., [4]) to the time-dependent context; ii) we propose a new relaxation specifically designed for the time-dependent context; iii) we conduct extensive computational experiments that show the effectiveness of the overall approach and the impact of the new relaxation. In particular, the results show that our approach outperforms recent ILP-based methods for the TDTSPTW proposed by [1,3,5] as well as the one developed in [4] for the Minimum Tour Duration Problem.References[1] Arigliano A, Ghiani G, Grieco A, Guerriero E, Plana I, Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm. Discr. Appl. Math.261:28–39 (2018)[2] Ichoua S, Gendreau M, Potvin J, Vehicle dispatching with time-dependent travel times. Eur. J. Oper.Res.144(2):379–396 (2003)[3] Lera-Romero G, Miranda-Bront JJ, A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints.European Journal of Operational Research 1–24 (2019)[4] Tilk C, Irnich S, Dynamic programming for the minimum tour duration problem.Transp. Sci.51(2):549–565 (2017)[5] Vu DM, Hewitt M, Boland N, Savelsbergh M, Dynamic discretization discovery for solving the time-dependent traveling salesman problem with time windows (2019). Forthcoming in Transportation Science.