Column Generation for solving VRPTW
This is the fourth and final part of the column generation tutorial series. Link to Part 1, Part 2, Part3.
A quick recap. Earlier we looked at how column generation algorithm works in Part 2. Part 3 described about the resource constrained shortest path algorithm. In this part I will put everything together and show the algorithm in action. The code is posted in github. The problem is coded in python and the RMP and final MIP problems are solved using cplex.
I use the code to solve the Solomon’s benchmark VRPTW problems with 100 customers. There are 29 problems in total in three sets: (i) C-set, (ii) R-set, and (iii) RC-set. C-set have customer that are clustered in groups. R-set have random without any cluster. RC-set consists of the mix of clustered and random customers. The CG algorithm is set to terminate after 1000 steps even if the subproblem keeps finding more solutions with negative reduced cost. Since the resource constrained shortest path problem with resource constraint can take a large amount of time to run, I heuristically solve the problem by allowing the label to be extended to 10 customers with lowest cost (C_ij — u_i) . If the subproblem cannot find any columns with reduced cost, then subproblem solution is restarted with labels allowed to be extended to 20 customers with lowest cost (at increment of 10 until all customers are allowed).
The results are presented below:
Table 1 shows the number of vehicles required, total distance traveled, number of column generation iterations required to solve the problem and the time required to get the final solution. The columns under “Best known solution” are the best known solution found in literatures for the same problem. The last column shows the ratio between the solution from my code and the best known solution. It can be observed that the code can achieve the best known solution or near best known solution for most of the problem. For some of the problems, the total distance is smaller than the best known solution. However, my solution requires greater number of vehicles than the best known solution. My code doesn’t try to minimize the number of vehicles used unlike the best known solutions. The solution time for the problems range from 7s to 397s with an average time of 90s. The total number of column generation iterations required range from 72 to 545 with average of 201 iterations. In the next section, we will look in details at the convergence pattern of some of the problems and try to address the convergence problems.
Convergence pattern
Let’s take a look at the convergence pattern of problem C103 ( as it took the largest number of iteration to terminate). It can be seen in the following figure 1 that during the initial few iterations the objective value improved but then it remained flat before it started to decrease again. Towards the end the curve remains almost flat. It indicates that the subproblem kept adding columns for several iterations without any improvement on the objective value. Such pattern is common in column generation algorithm due to the degeneracy of the RMP problems. To overcome such situations there are different stabilization methods suggested in the literatures.
In the code I have utilized the interior point stabilization procedure formulated by Rousseau et. al (2007). The main idea of the stabilization procedure presented in Rousseau et. al (2007) is to find more than one set of duals from the RMP at each iteration. Once multiple set of duals are found, they can averaged to get the final dual value which will be used to solve the sub problem. The advantage is that instead of using one extreme point dual value, the convex combination of multiple dual values will be used. Using such dual value, sub problem will find lesser number routes to be added to the RMP and help terminate the algorithm faster. Following the findings from Rousseau et al. (2007) I solve the RMP 20 times at each iteration (each run will have randomly modified RHS of the constraints). The final dual value will be the average of the 20 dual values. The stabilization method improves the solution time by an average factor of 52% (shown in Table 2). The solution time now ranges from 4s to 266s. Figure 2 shows that after using stabilization technique the problem now converges with in 90 iterations.
Conclusion
The presented column generation algorithm shows promising results to solving VRPTW with 100 customers. Next step could be scaling to problems with more than 100 customers. The shortest path problem we are using could be too restrictive when we try to scale this algorithm. We may have to try alternative and heuristics-based approach like ruin and recreate to find promising columns quickly. Using such column generation based framework instead of meta-heuristics alone can help find the optimal (or near optimal) solution relatively quicker.
