The Traveling Salesman Problem, the Vehicle Routing Problem, and Their Impact on Combinatorial Optimization

1 Introduction

The Traveling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP) are central to distribution management and have attracted the attention of researchers for more than 50 years. Their study has stimulated the emergence and the growth of some of the most important families of exact and heuristic algorithms in use today. The purpose of this paper is to provide a brief account of the evolution of the TSP and of the VRP and to show how they have contributed to shape the field of combinatorial optimization.

We first describe the two problems. The TSP is defined on a directed graph , where is the vertex set and is the arc set. With each arc is associated a non-negative cost c_ij which can also be interpreted as a length or as a travel time. The TSP consists of determining a least cost Hamiltonian tour or circuit on G. When for all , the problem is called symmetric and can be defined on an undirected graph , where is the edge set. In this case the graph is undirected and the tour is called a cycle. For simplicity, we will work with undirected graphs. In the VRP, the vertex set is , where 0 represents a depot at which are based m identical vehicles of capacity Q. The number of vehicles can be an input parameter or an output of the solution process. The vertices of are called customers, and each customer i has a non-negative demand q_i. There exist several versions of the VRP depending on the side constraints under consideration. Here we concentrate on the classical version involving capacity and route length constraints. The classical VRP consists of designing m vehicle routes of least total cost such that 1) each route starts and ends at the depot, 2) each customer appears in exactly one route, 3) the total demand of a route does not exceed Q, and 4) the length of a route does not exceed a prespecified constant L. A common variant of the VRP to which we will refer briefly is the VRP with Time Windows (VRPTW). Here a time window is associated with each customer and customer service must start within these time windows (waiting is allowed if the vehicle arrives at customer i before time a_i). In the VRPTW it is common to first minimize m and then the route length for the optimal value of m.

There exists an extensive literature on the TWP and the VRP. The reader is referred to Lawler et al. (1985) and Applegate et al. (2006) in the first case, and to Toth and Vigo (2002) and Golden, Raghavan, and Wasil (2008) in the second case.