## 4 Column Generation for \(Mtvp\)-\(Vw\)-\(Tw\)
### Solving the Pricing Subproblems
So, the solution to \(VRPTW\) instances are routes with one trip. We need to adjust them for the multi-trip and different capacity use. We use 10 of 25 customers for the instance. Instances of type 1 that have a capacity of 200 for each vehicle now have a capacity of 50 per wagon. Instances of type 2 with a capacity of 1000 per vehicle have been modified with a capacity of 100 per wagon. The number of vehicles is limited to 10. The number of wagons is 45. A tour's maximum number of routes is limited to three for these instances. Experimental Results

The results of the branch and price algorithm are presented next. The program was implemented in the optimization programming language OPL, using ILOG CPLEX. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Instance** & **Gap (in \%)** & **CPU Time (s)** & **Objective** & **Best Bound** \\ \hline C1 & 66.4 & 14,403 & 890 & 450 \\ R1 & 67.2 & 14,402 & 665 & 292 \\ R2 & 72.5 & 14,382 & 1033 & 308 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: 25 Customers. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Instance** & **Gap (in \%)** & **CPU Time (s)** & **Objective** & **Best Bound** \\ \hline C1 & 89 & 14,339 & 569 & 408 \\ R1 & 76 & 14,420 & 680 & 408 \\ R2 & 68 & 14,059 & 1065 & 414 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: 50 Customers. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Instance** & **Gap (in \%)** & **CPU Time (s)** & **Objective** & **Best Bound** \\ \hline C1 & 66 & 14,402 & 1137 & 630 \\ R1 & 81 & 14,404 & 3340 & 630 \\ R2 & 68 & 14,402 & 1562 & 630 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: 10 Customers. CEDAR, the Compute Canada cluster, was used for experimentation, with a limit of 4 h on each solve and a maximum memory requirement of 40 GB. Our algorithm was able to find optimal solutions for \(R1\), \(R2\), \(RC1\), and \(RC2\). The results are in Table 4 where the column named Instances is the type of the instance. The gap is between the LP-relaxation value at the root and the optimal integer value in %. CPU time is calculated as differences between the time recorded at the root and the end of the algorithm in seconds. Obj is the total distance. Iter is the number of iterations used to solve \(RLMP\) by CPLEX. Cols is the number of columns generated during the branch and price algorithm. Node is the number of nodes explored in the search tree. The route is the max number of routes used in all tours. Tour is the number of tours used to visit customers. ### Analysis

The mathematical model was tested, and it can take hours, or days to give solutions with gaps of around 60%, this is why we need to use a method like a branch and a price, which is an exact method to have the optimal solution of the problem. The mathematical model is a new one in that the mathematical test confirms the validation of the model and the branch and price test shows solving the model optimally. The branch and price algorithm solves the model for the small instances, but it gives the optimal solution for these instances that the model can not provide. During experimentation, we notice that the algorithm explores more nodes if a similar capacity (one wagon) is used for all tours. Giving the algorithm the option to check more tours with two wagons and three before starting a new branch makes it faster and explores a smaller number of nodes. The number of added columns before starting a new branch increases when different capacities are used. Varying capacity can significantly affect the number of explored nodes. The upper bound that the CPLEX provides us is a good upper