Fundamentals of Supply Chain Theory, 2nd Edition

Chapter 11 The Vehicle Routing Problem

11.1 Introduction to the VRP

11.1.1 Overview

The vehicle routing problem (VRP) is concerned with optimizing a set of routes, all beginning and ending at a given node (called the depot ), to serve a given set of customers. The VRP was first introduced by Dantzig and Ramser (1959). It is a multi‐vehicle version of the traveling salesman problem (TSP), and is therefore more applicable in practice since most organizations with substantial delivery operations use multiple vehicles simultaneously. Of course, it is also more difficult than the TSP since it involves decisions about how to assign customers to routes, in addition to how to optimize the sequence of nodes on each route. As a result, today's “hard” VRP instances tend to involve, say, hundreds of nodes, whereas hard instances of the TSP involve thousands or tens of thousands of nodes.

Figure 11.1 shows the optimal solution to a VRP instance called eil51 from the TSPLIB data set repository (Reinelt, 1991) and originally from Christofides and Eilon (1969). The depot is near the center of the region, marked by a square, while the customers are drawn as circles. Each node has a coordinate in , and the distances between pairs of nodes are Euclidean. The demands range from 3 to 41, and the vehicle capacity is 160. Note that the optimal VRP solution involves routes that cross each other. ...