Introduction

What is the VRP?

The Vehicle Routing Problem (VRP) is the generic name given to a whole class of problems in which a set of routes for a fleet of vehicles, based at one or several depots, must be determined to serve a number of geographically dispersed customers (see the problem formulation). The objective of the VRP is to serve a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a depot. The two figures below show a typical input for a VRP instance and one of its possible outputs:

A depot and a set of geographically dispersed customers — Figure 1. Typical input for a Vehicle Routing Problem

The same customers organized into vehicle routes — Figure 2. One possible output for the instance above

The VRP is a well-known integer programming problem which falls into the category of NP-hard problems: the computational effort required to solve it exactly grows exponentially with the problem size. For such problems it is often desirable to obtain approximate solutions that can be found quickly and are accurate enough for practical purposes — a task usually accomplished by heuristic and metaheuristic methods that exploit insight into the nature of the problem.

Between the TSP and Bin Packing

This difficult combinatorial problem conceptually lies at the intersection of two well-studied problems:

The Traveling Salesman Problem (TSP): if the vehicle capacity C is infinite, we get an instance of the Multiple Traveling Salesman Problem (MTSP). An MTSP instance can be transformed into an equivalent TSP instance by adding k − 1 copies of the depot node (k being the number of routes) and its incident edges — there are no edges among the k depot nodes.
The Bin Packing Problem (BPP): the question of whether a feasible solution exists for a given VRP instance is an instance of the BPP. The decision version of this problem is conceptually equivalent to a VRP model in which all edge costs are zero, so that all feasible solutions have the same cost.

Hence, we can think of the first transformation as relaxing the underlying packing (BPP) structure and the second as relaxing the underlying routing (TSP) structure. A feasible solution to the full problem is a TSP tour — in the expanded graph — that also satisfies the packing constraints: the total demand along each of the k segments joining successive copies of the depot must not exceed C. Because of the interplay between these two underlying NP-hard models, VRP instances can be extremely difficult to solve in practice.

Why it matters

The VRP arises naturally [Dantzig & Ramser 1959] as a central problem in transportation, distribution and logistics. In some market sectors, transportation accounts for a high percentage of the value added to goods, so using computerized methods for transportation often results in significant savings — reported to range from 5% to 20% of total costs in [Toth & Vigo 2001]. Six decades after its definition, the problem is more relevant than ever: parcel delivery, grocery distribution, waste collection, field services and ride sharing all generate routing problems of unprecedented size.

Side constraints: the VRP variants

Real-world routing problems usually include additional side constraints. Some of the most important ones define the classic VRP variants:

Every vehicle has a limited capacity — Capacitated VRP (CVRP)
Every customer must be supplied within a certain time window — VRP with Time Windows (VRPTW)
The vendor uses several depots to supply the customers — Multiple Depot VRP (MDVRP)
Customers may return goods to the depot — VRP with Pick-up and Delivery (VRPPD)
A customer may be served by more than one vehicle — Split Delivery VRP (SDVRP)
Some values (customer demands, service or travel times) are random — Stochastic VRP (SVRP)
Deliveries may be spread over several days — Periodic VRP (PVRP)

The full list of variants, with links to their descriptions and benchmark instances, is available on the VRP Variants page.