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:
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:
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: .