## 4 Column Generation for \(Mtvp\)-\(Vw\)-\(Tw\)
### Solving the Pricing Subproblems
So, these branches will be:

* Left branch: \(x_{ij}=1\), which means the customer \(j\) must be visited right after customer \(i\) in all tours of \(RLMP\) and the route graph. To enforce it, all columns in the \(RLMP\) and the route graph that contains arc \((i,k)\) with \(k\
eq j\) and \((k,j)\) with \(k\
eq i\) must be deleted. Also, if \(x_{i}=\sum_{w\in\Omega^{{}^{\prime}}}a_{iw}y_{w}\), then the decision variables for vertices \(i\) and \(j\) are set to one in \(RLMP\), \(x_{i}=1\) and \(x_{j}=1\). * Right branch: \(x_{ij}=0\), which means the customer \(j\) must not follow the customer \(i\) immediately. So all tours must be removed, including the arc \((i,j)\) in \(RLMP\) and the route graph. _Branch and Price Process_

We start at the root, and if \(RLMP\) is feasible, all possible columns from three subproblems will be added to the \(RLMP\). The LP solution of the root is set as the lower bound, and also integer solution given by the CPLEX is used as the upper bound. Two branches on the number of vehicles are created, and we use a stack in implementation DFS, so nodes are added to the front of the stack. For each node, column generation is used again to find the LP- solution of \(RLMP\). We check if the node must be pruned or kept. If the node is not pruned, we update the upper bound and create two new branches. After processing all nodes, we see if the sum of the value of variables of the best bound is an integer, but variable values are not, then the branching on nodes is used to generate nodes. Then, we calculate the flows on all the arcs. In the same way, we continue with the last node added to the head of the list to see if the node must be pruned or kept after using column generation. If we keep the node, two branches are created, and the upper bound is updated. The process continues until the stack is empty. ## 6 Experimental Evaluation for \(Mtvp\)-\(Vw\)-\(Tw\)

### Mathematical Model Test

The mathematical model of MTVRP-VW-TW with the objective function of the duration of the longest route is solved with CPLEX and C++, using modified Solomon instances [46]. The algorithm is implemented in C++. The instances are a subset of [PERSON]'s set of CVRPTW test problems. They are type of \(C1,C2,R1,R2\) with 25 customers. Wemodified the number of vehicles and capacity in type \(C1\), \(R1\) to 25 vehicles, and the capacity of 200 changed to 15 vehicles, 30 wagons, 3 routes and a capacity of 150 for each wagon. For type C2, 25 vehicles and a capacity of 700 are changed to 15 vehicles, 30 wagons, 3 routes, and a capacity of 500 for each wagon. For type \(R2\) with a capacity of 1000 changed to 15 vehicles, 30 wagons, 3 routes, and a capacity of 700 for each wagon. Tables 1-3 show the results. All the instances have a large integrality gap and it takes a lot of time to solve the mathematical model. ### Branch and Price Test

[PERSON]'s (100 customers) instances [46] for Euclidean \(VRPTW\) are modified to evaluate the model. We use the first ten customers of [PERSON]'s instances to test the algorithm. The Euclidean distance between two customer locations determines the travel time for these instances. The instances of [PERSON] [46] that we consider of six different types C1, C2, \(R1\), \(R2\), \(RC1\), \(RC2\). Each data set has eight to twelve 100-node problems. Sets C1 and C2 have clustered customers whose time windows were generated based on a known solution. Problem sets \(R1\) and \(R2\) randomly generate the customer's location over a square. Sets \(RC1\) and \(RC2\) combine randomly placed and clustered customers. Sets of type \(1\) have narrow time windows and small vehicle capacity. Sets of type \(2\) have large time windows and large vehicle capacity. Therefore, the optimal solutions for type \(2\) problems have very few routes and significantly more customers per route. It must be noted that the branch and price algorithm is an exact algorithm that could not solve more than 40-50 customers so far. To use [PERSON]'s instances, we modify them.