An Integer Programming approach for the Traveling Salesman Problem with release dates and completion time minimization

AGUSTÍN ISMAEL MONTERO; ISABEL MÉNDEZ-DÍAZ; JUAN JOSÉ MIRANDA BRONT

virtual

Conferencia; 11th International Conference on Computational Logistics; 2020

University of Twente

In this presentation, we address the Traveling Salesman Problem with release dates and completion time minimization (TSP-rd(time)) with an exact approach. The TSP-rd(time) tackles a key operational constraint within nowadays last-mile logistics, partly motivated by same-day and fast deliveries. The package requested by a customer is not necessarily available at the beginning of the planning horizon, capturing the timing of its arrival to the distribution center. Thus, the vehicle is allowed to perform multiple trips to the depot in order to serve all the customers. The TSP-rd(time) is formulated as a synchronization problem, and so far neglects the effect of the vehicle capacity. Variants of routing problems with release dates have only recently been introduced in the literature and applications arise in the context of cross-docking and same-day delivery problems [1].Formally, let G=(V,A) be a complete graph with V the set of vertices and A the set edges. A traveling time is associated with each arc (i,j) in A and it is assumed that the triangle inequality holds. The set of vertices V is composed by the vertex 0 (depot) and the set N of n customers. For each customer in N, there is an associated non-negative release date. Only one uncapacitated vehicle is available. The vehicle must wait at the depot until the latest release date of the customers it is going to serve in the next route, i.e., the next trip starting and ending at the depot and not visiting the depot in between. The objective is to serve all customers minimizing the completion time, that is, the total traveling time plus the waiting-time at the depot.In this research, we consider the mathematical formulation proposed by Archetti et al. [2] for the TSP-rd(time), which has been successful at solving instances with up to 20 customers. We propose an alternative formulation for the TSP-rd(time) and develop an exact algorithm following a branch & cut scheme, including different initial heuristics. The algorithm is able to solve instances with up to 30 customers, including several unsolved instances that have been solved to proven optimality. To the best of our knowledge, our work extends the analysis of an exact approach for the TSP-rd(time), establish a baseline for future approaches, and opens the discussion about formulations, algorithms, and benchmark instances.References[1] Mor, A., & Speranza, M. G. (2020). Vehicle routing problems over time: a survey. 4OR, 1-21.[2] Archetti, C., Feillet, D., Mor, A., & Speranza, M. G. (2018). An iterated local search for the Traveling Salesman Problem with release dates and completion time minimization. Computers & Operations Research, 98, 24-37.