A Decomposition Algorithm for the Consistent Traveling Salesman Problem with Vehicle Idling

The consistent traveling salesman problem aims to identify minimum-cost routes to be followed by a single vehicle so as to provide a set of customers with service that adheres to arrival-time consistency across the multiple time periods of a planning horizon. In this paper, we address this problem via a new, exact algorithm that decomposes the problem into a sequence of single-period traveling salesman problems with time windows within a branch-and-bound search procedure. The new algorithm is highly competitive, as it is able to solve to guaranteed optimality instances with up to 100 customers requiring service over a five-period horizon, effectively doubling the size of instances that were solvable by the previous state of the art. Furthermore, and in contrast to all previous approaches, the new algorithm accounts for route duration limits, whenever applicable, as well as incorporates the flexibility for the vehicle to idle before providing service to a customer. We in fact show that, for the benchmark instances we considered, the cost of implementing consistent routes can be reduced significantly if the vehicle is allowed to idle en route, further motivating the need for algorithmic schemes to incorporate this realistic option.