What is VRP?

The Vehicle Routing Problem (VRP) (problem formulation) is a 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 for a number of geographically dispersed cities or customers. The objective of the VRP is to deliver a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a depot. In the two figures below we can see a picture of a typical input for a VRP problem and one of its possible outputs:

Figure 1. Typical input for a Vehicle Routing Problem

 

Figure 2. An output for the instance above

The VRP is a well known integer programming problem which falls into the category of NP Hard problems, meaning that the computational effort required to solve this problem increases exponentially with the problem size. For such problems it is often desirable to obtain approximate solutions, so they can be found fast enough and are sufficiently accurate for the purpose. Usually this task is accomplished by using various heuristic methods, which rely on some insight into the problem nature.

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

Hence, we can think of the first transformation as relaxing the underlying packing (BPP) structure and the second transformation 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 (i.e., the total demand along each of the k segments joining successive copies of the depot does not exceed C). Because of the interplay between the two underlying models (both of them are NP Hard problems), instances of the Vehicle Routing Problem can be extremely difficult to solve in practice.

The VRP arises naturally [Dantzing & Ramser 1959] as a central problem in the fields of transportation, distribution and logistics. In some market sectors, transportation means a high percentage of the value added to goods. Therefore, the utilization of computerized methods for transportation often results in significant savings ranging from 5% to 20% in the total costs, as reported in [Toth & Vigo 2001]. Usually, in real world VRPs, many side constraints appear. Some of the most important restrictions are: