Formulations for Minimizing Tour Duration of the Traveling Salesman Problem with Time Windows

Abstract

Traveling Salesman Problem with Time Windows (TSPTW) serves as one of the most important variants of the Traveling Salesman Problem (TSP). The main objective functions expressed in the literature of the TSPTW consist of the following: (1) to minimize total distance travelled (or to minimize total travel time spent on the arcs), (2) to minimize total cost of traveling on the arcs and cost of waiting before services, or (3) to minimize total time passed from depot to depot (tour duration). When the unit cost of traveling and unit cost of waiting appear equal, then one may solve the problem just minimizing tour duration. According to our best knowledge, only one formulation with nonlinear constraints considers the aim of minimizing tour duration for symmetric case. However, for just minimizing tour duration, we haven't seen any linear formulation for symmetric and any general formulation for asymmetric TSPTW. In this paper, for minimizing tour duration, we propose polynomial size integer linear programming formulation for symmetric and asymmetric TSPTW separately. The performances of our proposed formulations are tested on well-known benchmark instances used to minimize total travel time spent on the arcs. For symmetric TSPTW, our proposed formulation sufficiently and capably finds optimal solutions for all instances (the biggest are with 400 customers) in an extremely short time with CPLEX 12.4. For asymmetric TSPTW, we used instances generated from a real life problem which were used for minimizing total arc cost. We used these instances for minimizing tour duration and observe that, optimal solutions of the most of the instances up to 232 nodes are obtained within seconds. In addition, the proposed formulation for asymmetric case obtained 7 new best known solutions. (C) 2015 The Authors. Published by Elsevier B.V.