ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows
Autor/es:
MIRANDA BRONT, JUAN J.; GONZALO LERA-ROMERO; FRANCISCO J. SOULIGNAC
Reunión:
Conferencia; International Conference on Computational Logistics 2020 (ICCL 2020); 2020
Resumen:
The recent growth of direct-to-consumer deliveries hasstressed the importance of last-mile logistics, becoming one of thecritical factors in city planning. According to different studies, oneof the key factors lies in the last-mile deliveries, reaching in somecases nearly 50% of the overall parcel delivery cost. Accountingeffectively for the effects of congestion at the planning levelresults in more accurate distributions plans.The Time-Dependent Traveling Salesman Problem with TimeWindows (TDTSPTW) is a variant of the well-known TravelingSalesman Problem with Time Windows (TSPTW) in which traveltimes are not assumed to be constant. The TDTSPTW accounts forthe effects of congestion at the planning level, being particularlysuited for distribution problems in large cities. In this presentation,we consider the model proposed in [2] where travel times for eacharc are not constant, and instead are modeled as a continuouspiecewise linear function satisfying the FIFO condition. Thus, aneffective approach for the TDTSPTW must handle efficientlytravel times defined by functions instead of its time-independentcounterpart, where they are assumed to remain constant along theplanning horizon.Our contributions are both algorithmic and methodological.Specifically: i) we propose a labeling-based algorithm for theTDTSPTW that adapts state-of-the-art features from the related(time-independent) literature (see, e.g., [4]) to the time-dependentcontext; ii) we propose a new relaxation specifically designed forthe time-dependent context; iii) we conduct extensivecomputational experiments that show the effectiveness of the overall approach and the impact of the new relaxation. Inparticular, the results show that our approach outperforms recentILP-based methods for the TDTSPTW proposed by [1,3,5] as wellas the one developed in [4] for the Minimum Tour DurationProblem.ReferencesArigliano A, Ghiani G, Grieco A, Guerriero E, Plana I, Time-dependent asymmetric traveling salesman problem with timewindows: Properties and an exact algorithm. Discr. Appl.Math.261:28?39 (2018)Ichoua S, Gendreau M, Potvin J, Vehicle dispatching with time-dependent travel times. Eur. J. Oper.Res.144(2):379?396 (2003)Lera-Romero G, Miranda-Bront JJ, A branch and cut algorithmfor the time-dependent profitable tour problem with resourceconstraints.European Journal of Operational Research 1?24(2019)Vu DM, Hewitt M, Boland N, Savelsbergh M, Dynamicdiscretization discovery for solving the time-dependent travelingsalesman problem with time windows (2019). Forthcoming inTransportation Science.