Vehicle routing problemS

The vehicle routing problem (VRP) is one of the most important and widely studied combinatorial problem due to its application in delivery and transport logistics. This problem is of great importance in distribution systems, since the transportation process represents between 10 and 20% of the final cost of goods. In addition, distribution costs are estimated to be almost half the total cost of logistics.

The VRP can be defined as follows. There is a set of geographically distributed customers, who have a certain demand for the product. There is also a depot where the product is centralized. To satisfy the customers' demand, there is a fleet of vehicles whose base is the depot. The problem is to design a set of minimum cost routes to provide the product to customers, in such a way that:

• each route begins and ends at the depot,

• each vehicle is assigned a route,

• each customer is served by exactly one vehicle, and

• the demand of all customers is satisfied.

The 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 vehicles is considered, which have a limited capacity.

Vehicle routing problem with time windows (VRPTW), where each client has a predetermined time window during which they must be served.

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 orders involve an origin customer, a destination customer, and a quantity to be transported. That is, this variant does not consider that the product is in the depot, but in some of the customers.