Vehicle Routing Problem's Formulation

The VRP is a combinatorial problem whose ground set is the edges of a graph G(V,E). The notation used for this problem is as follows:

• is a vertex set, where:
• Consider a depot to be located at .
• Let be used as the set of cities.
• ij is an arc set.
• is a matrix of non-negative costs or distances between customers and .
• is a vector of the customer demands.
• is the route for vehicle .
• is the number or vehicles (all identical). One route is assigned to each vehicle.

When for all the problem is said to be symmetric and it is then common to replace with the edge set .

With each vertex in is associated a quantity of some goods to be delivered by a vehicle. The VRP thus consists of determining a set of vehicle routes of minimal total cost, starting and ending at a depot, such that every vertex in is visited exactly once by one vehicle.

For easy computation, it can be defined , an obvious lower bound on the number of trucks needed to service the customers in set V.

We will consider a service time (time needed to unload all goods), required by a vehicle to unload the quantity at . It is required that the total duration of any vehicle route (travel plus service times) may not surpass a given bound , so, in this context the cost is taken to be the travel time between the cities. The VRP defined above is NP-hard [Lenstra & Rinnooy Kan 1981].

A feasible solution is composed of:

• a partition of V;
• a permutation of specifying the order of the customers on route .

The cost of a given route (), where and (0 denotes the depot), is given by: .

A route is feasible if the vehicle stop exactly once in each customer and the total duration of the route does not exceed a prespecified bound : .

Finally, the cost of the problem solution S is: .