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

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

Gilbert Laporte (HEC Montréal, Canada)
Copyright: © 2010 |Pages: 11
DOI: 10.4018/jsds.2010040104

Abstract

The Traveling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP) are two of the most popular problems in the field of combinatorial optimization. Due to the study of these two problems, there has been a significant growth in families of exact and heuristic algorithms being used today. The purpose of this paper is to show how their study has fostered developments of the most popular algorithms now applied to the solution of combinatorial optimization problems. These include exact algorithms, classical heuristics and metaheuristics.
Article Preview
Top

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 jsds.2010040104.m01, where jsds.2010040104.m02 is the vertex set and jsds.2010040104.m03 is the arc set. With each arc jsds.2010040104.m04 is associated a non-negative cost jsds.2010040104.m05 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 jsds.2010040104.m06. When jsds.2010040104.m07 for all jsds.2010040104.m08, the problem is called symmetric and can be defined on an undirected graph jsds.2010040104.m09, where jsds.2010040104.m10 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 jsds.2010040104.m11, where 0 represents a depot at which are based jsds.2010040104.m12 identical vehicles of capacity jsds.2010040104.m13. The number of vehicles can be an input parameter or an output of the solution process. The vertices of jsds.2010040104.m14 are called customers, and each customer jsds.2010040104.m15 has a non-negative demand jsds.2010040104.m16. 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 jsds.2010040104.m17 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 jsds.2010040104.m18, and 4) the length of a route does not exceed a prespecified constant jsds.2010040104.m19. A common variant of the VRP to which we will refer briefly is the VRP with Time Windows (VRPTW). Here a time window jsds.2010040104.m20 is associated with each customer and customer service must start within these time windows (waiting is allowed if the vehicle arrives at customer jsds.2010040104.m21 before time jsds.2010040104.m22). In the VRPTW it is common to first minimize jsds.2010040104.m23 and then the route length for the optimal value of jsds.2010040104.m24.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing