Capacitated Vehicules Routing Problems (CVRP) are common problems in Vehicules Routing Problem (VRP). In our case, we only have one depot with many points.
The instances used for test are Christofides instances, with 50 and 75 points.
To define the problem, we can use the following mathematical model :
-
$n$ : number of clients, without the depot -
$W$ : capacity of one vehicule -
$X_i , Y_i$ : coordinates of client i -
$C_{ij}$ : distance between point i and point j (client or depot) -
$q_i$ : weight of the point
The objective is to minimize
-
$\forall i \neq 0 : \sum_{j \neq i} \sum_k x_{ijk} = 1$ ; each client i must be visited -
$\forall k : \sum_{i \neq 0} \sum_{j \neq i} q_i x_{ijk} \leq W$ : the capacity of each trip (vehicle) k is respected -
$\forall i \neq 0, \forall k : \sum_{j \neq i} x_{ijk} = \sum_{j \neq i} x_{jik}$ : continuous trip (if vehicle k arrives at client i, it leaves it) - $\forall S \subseteq { 1, 2, ...,n}, S \neq \emptyset , \forall k : \sum_{ i \in S} \sum_{ j \in S} x_{ijk} \leq |S| - 1 $ : no subtours in each trip
This mathematic model can be used to have optimal solution, based on exact method. But with big instance, like the ones we have, the calculation time will be too much to use it. It's why we use the SPLIT heuristics.
The Split heuristic is a Route First, Cluster second heuristic. It mean that we first generate a big tour, without capacities like a TSP problem, then we cluster it into the best subtour we can.
In our case, the Big Tour is done with the Nearest Neighbor heuristic and the Randomised Nearest Neighbors. When we have the big tour, the SPlit is done with this Pseudo-code (in french) :
Initialiser les 𝑉𝑖 à plus l'infini, sauf 𝑉0 = 0 (labels provisoires)
Pour 𝑖 variant de 1 à 𝑛Pour 𝑗 variant de 𝑖 à 𝑛 tant que la demande de (𝑆𝑖 , … , 𝑆𝑗) est ≤ 𝑊
Si 𝑖 = 𝑗 // Tournée à un client, simple aller-retour
- 𝑝𝑜𝑖𝑑𝑠 = 𝑞𝑖 et 𝑐𝑜𝑢𝑡 = 2 × 𝐶(0, 𝑆𝑖)
Sinon // On ajoute le client 𝑗 à la fin de la tournée précédente
- 𝑝𝑜𝑖𝑑𝑠 = 𝑝𝑜𝑖𝑑𝑠 + 𝑞𝑗
- 𝑐𝑜𝑢𝑡 = 𝑐𝑜𝑢𝑡 − 𝐶(𝑆𝑗−1, 0) + 𝐶(𝑆𝑗−1, 𝑆𝑗) + 𝐶(𝑆𝑗, 0)
Fin si
Si 𝑉𝑖−1 + 𝑐𝑜𝑢𝑡 < 𝑉𝑗
- 𝑉𝑗 = 𝑉𝑖 + 𝑐𝑜𝑢𝑡
- 𝑃𝑗 = 𝑖 − 1
Fin si
Fin pour
Fin pour
This pseudo can be used with these notations :
- S is the big tour, Si is the index of the client in the position i in the tour
- Vi is the lowest cost possible to go to the client i
- Pi is the predecessor of the client i (used to generate the subtour)
The code can be located at SPLIT Heuristic.py .
In this part, we can see the results of the heuristic. To compare, the optimal results of the CVRP problem with these instances are respectively 524,61 and 835, 26.
We can show the representation of the best tour with 5000 iterations :
What's interesting with the randomized nearest neighbors is that we can look at the result by iterations :
