Solving the Traveling Salesman Problem with release dates via branch and cut

Abstract

In this paper we study the Traveling Salesman Problem with release dates (TSP-rd) and completion time minimization. The TSP-rd considers a single vehicle and a set of customers that must be served exactly once with goods that arrive to the depot over time, during the planning horizon. The time at which each requested good arrives is called release date and it is known in advance. The vehicle can perform multiple routes, however, it cannot depart to serve a customer before the associated release date. Thus, the release date of the customers in each route must not be greater than the starting time of the route. The objective is to determine a set of routes for the vehicle, starting and ending at the depot, where the completion time needed to serve all customers is minimized. We propose a new Integer Linear Programming model and develop a branch and cut algorithm with tailored enhancements to improve its performance. The algorithm proved to be able to significantly reduce the computation times when compared to a compact formulation tackled using a commercial mathematical programming solver, obtaining 24 new optimal solutions on benchmark instances with up to 30 customers within one hour. We further extend the benchmark to instances with up to 50 customers where the algorithm proved to be efficient. Building upon these results, the proposed model is adapted to new TSP-rd variants (Capacitated and Prize-Collecting TSP), with different objectives: completion time minimization and traveling distance minimization. To the best of our knowledge, our work is the first in-depth study to report extensive results for the TSP-rd through a branch and cut, establishing a baseline and providing insights for future approaches. Overall, the approach proved to be very effective and gives a flexible framework for several variants, opening the discussion about formulations, algorithms and new benchmark instances.