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 $c_{ij} = c_{ji}$ for all $(v_{i}, v_{j}) \in A$ the problem is said to be symmetric and it is then common to replace $A$ with the edge set .

With each vertex $v_{i}$ in $V' $ is associated a quantity $q_{i}$ of some goods to be delivered by a vehicle. The VRP thus consists of determining a set of $m$ vehicle routes of minimal total cost, starting and ending at a depot, such that every vertex in $V' $ 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 $\delta _{i}$ (time needed to unload all goods), required by a vehicle to unload the quantity at $v_{i}$. It is required that the total duration of any vehicle route (travel plus service times) may not surpass a given bound $D$, so, in this context the cost $c_{ij}$ 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: $F(R_{i})=\sum_{i=0}^{m} c_{i,i+1} +
\sum_{i=1}^{m} \delta _{i}$.

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

Finally, the cost of the problem solution S is: $F_{VRP} =
\sum_{i=1}^{m} F(R_{i})$ .