## 4 Column Generation for \(Mtvp\)-\(Vw\)-\(Tw\)
### Solving the Pricing Subproblems
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multirow{2}{*}{**Gap**} & \multicolumn{2}{c}{**CPU Time**} & \multirow{2}{*}{**Obj**} & \multirow{2}{*}{**Iter**} & \multirow{2}{*}{**Cols**} & \multirow{2}{*}{**Node**} & \multirow{2}{*}{**Route**} & \multirow{2}{*}{**Tour**} \\  & & **(s)** & & & & & & & \\ \hline RC102 & 994.364 & 869.56 & 563.562 & 20 & 17 & 3 & 2 & 2 \\ RC103 & 994.364 & 899.163 & 563.562 & 20 & 17 & 3 & 2 & 2 \\ RC105 & 994.548 & 398.842 & 545.237 & 18 & 17 & 1 & 2 & 2 \\ RC106 & 993.178 & 111.626 & 682.168 & 13 & 12 & 1 & 2 & 3 \\ RC107 & 994.189 & 202.428 & 581.069 & 11 & 10 & 1 & 2 & 2 \\ RC108 & 994.121 & 670.193 & 587.86 & 17 & 14 & 3 & 2 & 2 \\ RC202 & 992.434 & 470.885 & 756.612 & 5 & 4 & 1 & 1 & 2 \\ RC203 & 992.434 & 470.885 & 756.612 & 5 & 4 & 1 & 1 & 2 \\ RC204 & 993.722 & 872.675 & 627.785 & 3 & 2 & 1 & 1 & 2 \\ RC206 & 794.258 & 139.613 & 724.979 & 8 & 7 & 1 & 2 & 1 \\ RC207 & 991.067 & 446.75 & 893.255 & 15 & 14 & 1 & 2 & 1 \\ RC208 & 797.627 & 800.939 & 388.128 & 3 & 2 & 1 & 1 & 1 \\ R102 & 993.936 & 102.048 & 606.438 & 7 & 6 & 1 & 2 & 2 \\ R103 & 993.936 & 106 & 606.438 & 7 & 6 & 1 & 2 & 2 \\ R108 & 993.326 & 1287.93 & 667.381 & 16 & 13 & 3 & 2 & 2 \\ R110 & 994.023 & 171.832 & 597.728 & 10 & 9 & 1 & 2 & 2 \\ R111 & 993.629 & 2010.17 & 637.106 & 14 & 12 & 3 & 2 & 2 \\ R202 & 991.33 & 455.858 & 867.046 & 5 & 4 & 1 & 2 & 1 \\ R203 & 991.33 & 458.102 & 867.046 & 5 & 4 & 1 & 2 & 1 \\ R204 & 993.722 & 881.522 & 627.785 & 3 & 2 & 1 & 1 & 2 \\ R205 & 992.355 & 102.946 & 764.518 & 3 & 2 & 1 & 2 & 1 \\ R206 & 993.992 & 581.478 & 600.814 & 3 & 2 & 1 & 1 & 2 \\ R207 & 993.992 & 593.218 & 600.814 & 3 & 2 & 1 & 1 & 2 \\ R208 & 993.993 & 612.737 & 600.683 & 3 & 2 & 1 & 1 & 2 \\ R209 & 992.61 & 345.444 & 739.023 & 8 & 7 & 1 & 1 & 2 \\ R210 & 993.672 & 1068.08 & 632.814 & 3 & 2 & 1 & 1 & 2 \\ R211 & 996.263 & 443.173 & 373.736 & 2 & 1 & 1 & 1 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Branch and Price for 10 Customers. bound close to the optimal solution and it helps to explore fewer nodes and have a solution faster. The algorithm solves type 2 instances where the time windows are more expansive on the horizon. It is faster and uses fewer iterations. For type C instances, branch and price could not find a solution to the time cut-off limit. All the instances listed in Table 4 were solved optimally within four hours. We need to solve two resource constraints, the shortest path problem to determine a column with a negative reduced cost, and we need also to construct a route graph. The shortest path problem is solved using dynamic programming whose run time depends on the number of non-dominated paths which can be exponential. For large instances, this type of program run out of memory to store all the non-dominated paths. That is why we cannot solve large instances using column generation, as a part of future work we will look at other methods for solving the resource constraint shortest path problem. ## 7 Conclusions and Future Work

This work defines a new type of \(VRP\), multi-trip vehicle routing problem with a variable number of wagons and time windows. The problem is serving clients' demands in a specific interval of time (time windows). At the same time, vehicles can make multiple daily trips, and the vehicle's capacity can be set at the beginning of the day by adding up to three wagons for each vehicle. First, a mathematical model of the problem is developed, and then we develop a branch and price algorithm to solve the problem. The approach to solving the problem is column generation embedded in a branch and bound algorithm. We implemented the branch and price algorithm for \(MTVRP\)-\(VW\)-\(TW\) on several [PERSON]'s instances to show the algorithm's effectiveness. It can compute the optimal integer solution for limited customers. We are interested in combining the column generation approach with metaheuristics to develop a faster solution for \(MTVRP\)-\(VW\)-\(TW\).