## 4 Column Generation for \(Mtvp\)-\(Vw\)-\(Tw\)
### Solving the Pricing Subproblems
endfor for all\(R_{k},R_{h}\in\mathit{Routes}\)do if\(R_{k}\) and \(R_{h}\) don't have common customer and \((La-time)_{k}\leq(Ld-time)_{h}\)then  Add an edge from vertex \(R_{k}\) to vertex \(R_{h}\) in \(A^{T}\) endif endfor for all\(R_{k}\in\mathit{Routes}\)do  Add an edge from vertex \(R_{k}\) to p and from p to \(R_{k}\) endfor
```

**Algorithm 1** Generating all non-dominated tours
```
Initialization [Generate all non-dominated tours] \(H_{k}^{T}\leftarrow\{(0,...,0)\}\) for all\(\text{R}_{k}\in V^{T}-\{p\}\)do \(FT_{bh}\leftarrow\emptyset\) endfor \(E^{T}=\{p\}\) while\(E^{T}!=\emptyset\)do  Choose \(R_{k}\in E^{T}\) for all\(R_{h}\in\text{Succ}T(R_{k})\)do \(FT_{kh}\leftarrow\emptyset\) for all\(L_{k}^{T}\in H_{k}^{T}\)do if\(R_{k}^{h}=0\)then \(FT_{kh}\gets FT_{kh}\cup ExtendT(L_{k}^{T},R_{h})\) endif endfor \(H_{k}^{T}\gets DominatedT(FT_{kh}\cup H_{h}^{T})\) if\(H_{h}^{T}\) has changed then \(E^{T}\gets E^{T}\cup\{R_{h}\}\) endif endfor \(E^{T}\gets E^{T}-\{R_{k}\}\) endwhile
```

**Algorithm 1**_Cont._

All non-dominated tours will be generated using the extend and dominate function in the label-correcting algorithm. There are three subproblems based on the various capacity. All tours will be generated for these three subproblems. First, we will see if there is a new tour with a negative reduced cost in the subproblem with one wagon. If so, the column will be added to the master problem. If not, the second subproblem will be checked. Suppose a new tour with a negative reduced cost is added to the master problem. If not, we will check the third subproblem, which uses three wagons. We solve the subproblems until all tours with the negative reduced cost are found and added to the master problem. The following flowchart shows the procedure of the algorithm in Figure 2.

## 5 Branch and Price Algorithm for \(Mtvrp\)-\(Vw\)-\(Tw\)

In this section, we describe initialization, the search strategy, the branching strategy, and the upper bound that we use in our implementation of branch and price for the multi-trip VRP with variable wagons and time windows. **Initialization:** At the root of the search tree, the \(RLMP\) is initialized with tours made of a single customer visit. The number of columns thus corresponds to the number of customers. For internal nodes in the search tree, the algorithm initializes the \(RLMP\) with the set of columns in the parent node considered after removing infeasible columns due

Figure 2: Column generation procedure for various capacities. to branching [4]. The minimum capacity for all vehicles that service a single customer is one wagon. **Search Strategy:** The branch and price tree is explored using a depth-first search. **Lower and Upper Bound:** The solution to \(RLMP\) at the root node gives a lower bound for the problem. We solve the master problem using CPLEX. The integer solution of the master problem given by the CPLEX 12.8 is used as the upper bound. **Branching Strategy:** Two branching strategies are used. We branch on the number of vehicles and the arcs. **Branching on the Number of Vehicles:** We sum the value of variables of the optimal solution of \(RLMP\), so \(k=\sum_{w\in\Omega^{{}^{\prime}}}y_{w}\), where \(\Omega^{{}^{\prime}}\subseteq\Omega\). If \(k\) is fractional, two branches are created. For each branch, one additional constraint is added to the master problem. These two constraints are:

\[\sum_{w\in\Omega^{{}^{\prime}}}y_{w}\leq\lfloor k\rfloor\]

and

\[\sum_{w\in\Omega^{{}^{\prime}}}y_{w}\geq\lfloor k+1\rfloor.\]

The dual variable value corresponding to the new constraint is added to the subproblem, and the column generation is done again for this new child node. **Branching on Arcs:** The branch on an arc happens when the flow on an arc \((i,j)\) is fractional. We calculate the flow on any arc that is in some column. The sum of the \(y_{w}\), \(w\in\Omega^{{}^{\prime}}\) on the columns that include an arc \((i,j)\), will give the flow on the arc. The arc with fractional value is taken.