Vehicle routing problem

The vehicle routing problem (VRP) is one of the most important and widely studied combinatorial problems, because it has applications in the distribution and transportation logistics1. This problem is of great importance in distribution systems, since the transport process is between 10 and 20% of the final cost of goods2. In addition, the estimated distribution costs amount to almost half of the total cost of the logistics3.

VRP can be defined as follows. There is a set of customers that are geographically distributed, who have a demand of product. There is also a depot where the product is centralized. To serve customers demand, there is a fleet of vehicles base at the depot. The problem consists of designing a set of routes with minimum cost to provide the product to customers, so that:
  • each route begins and ends at the depot,
  • each vehicle serves a route,
  • each customer is served by exactly one vehicle, and
  • the total demand of all customers is satisfied.
VRP has many variants that take into account different constraints, which can be categorized as operational and precedence. Some of these variants are:
  • Capacitated vehicle routing problem (CVRP), where a homogeneous fleet of limited capacity vehicles is considered.
  • Vehicle routing problem with time windows (VRPTW), where each customer has a predetermined time window during which it must be serviced.
  • Vehicle routing problem with backhauls (VRPB), where there are two types of customers: customers who require the product and customers who return it.
  • Vehicle routing problem with pickups and deliveries (VRPPD), also known as pickup and delivery problem (PDP), where transportation requests are considered, involving an origin customer, a destination customer and a demand to be transported. That is, this variant does not consider the product is centralized at the depot, but at some of the customers locations.

1 R. Baldacci, M. Battarra and D. Vigo. Routing a heterogeneous fleet of vehicles. In B.L. Golden, S. Raghavan y E.A. Wasil, eds., The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 3-27. Springer, 2008.
2 P. Toth and D. Vigo. An overview of vehicle routing problems. In P. Toth y D. Vigo, eds., The vehicle routing problem, pp. 1-26. SIAM, 2001.
3 B. De Backer, V. Furnon, P. Kilby, P. Prosser and P. Shaw. Local search in constraint programming: Application to the vehicle routing problem. In 1997 Workshop on Industrial Constraint Directed Scheduling, pp. 1–15. 1997.