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:

• $V = \{v_{0}, v_{1},\ldots , v_{n}\}$ is a vertex set, where:
  • Consider a depot to be located at $v_{0}$.
  • Let $V' = V \backslash \{v_{0}\}$ be used as the set of $n$ cities.
• ij is an arc set.
• $C$ is a matrix of non-negative costs or distances $c_{ij}$ between customers and .
• is a vector of the customer demands.
• $R_{i}$ is the route for vehicle $i$.
• $m$ is the number or vehicles (all identical). One route is assigned to each vehicle.

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:

• a partition ${R_{1},\ldots ,R_{m}}$ of V;
• a permutation $\sigma_{i}$ of $R_{i}\bigcup {0}$ specifying the order of the customers on route $i$.

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})$ .