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.
Article
View Dynamic programming for the time-dependent traveling salesman problem with time windows