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:

• The Traveling Salesman Problem (TSP): If the capacity of the vehicles C is infinite, we can get an instance of the Multiple Traveling Salesman Problem (MTSP). An MTSP instance can be transformed into an equivalent TSP instance by adjoining to the graph k-1 (being k the number of routes) additional copies of node 0 and its incident edges (there are no edges among the k depot nodes).

• The Bin Packing Problem (BPP): The question of whether there exists a feasible solution for a given instance of the VRP 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 taken to be 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 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:

• Every vehicle has a limited capacitate (Capacitated VRP - CVRP)
• Every customer has to be supplied within a certain time window (VRP with time windows - VRPTW)
• The vendor uses many depots to supply the customers (Multiple Depot VRP - MDVRP)
• Customers may return some goods to the depot (VRP with Pick-Up and Delivering - VRPPD)
• The customers may be served by different vehicles (Split Delivery VRP - SDVRP)
• Some values (like number of customers, theirs demands, serve time or travel time) are random (Stochastic VRP - SVRP)
• The deliveries may be done in some days (Periodic VRP - PVRP)