## 4 Column Generation for \(Mtvp\)-\(Vw\)-\(Tw\)
### Solving the Pricing Subproblems  
For three different capacities of the vehicles, we have three route graphs. Consequently, three subproblems will be solved. The label correcting algorithm can be applied to each of them again to find the new tour with the negative reduced cost to be added to the master problem. Now, the label correcting algorithm can be implemented to determine all non-dominated tours of the route graph. The method described in [4] is used to implement the label-correcting algorithm on the route graph. Using the extend and dominate function in the label correcting algorithm, all non-dominated tours will be generated. The algorithm first generates all non-dominated routes and then generate the route graph, and finally creates all non-dominated tours. The algorithm is described next. **Description of the Algorithm:**  
The Algorithm 1 finds all non-dominated tours on the route graph from the origin node \(p\) (depot). We need the following notation to describe the algorithm:  
* \(G=(N,A)\): The input graph. * \(N\): Set of customers and vertices 0 and \(n+1\) as the depot. * \(A\): Set of all edges between vertices in \(N\)
* \(H_{i}\): List of labels on node \(v_{i}\)
* \(Succ(v_{i})\): Set of successors of node \(v_{i}\). * \(E\): List of nodes waiting to be processed. * \(Extend(L_{i},v_{j})\): Function that returns the label resulting from the extension of label \(L_{i}\), \(\in H_{i}\) towards node \(v_{j}\) when the extension is possible, nothing otherwise. * \(Dominated(A_{j})\): Procedure that removes dominated labels in the list of labels \(H_{j}\). * \(F_{ij}\): List of labels extended from \(v_{i}\) to \(v_{j}\)
* _Routes_: To save all non-dominated routes. * \((Ld-time)_{k}\): latest departure time of \(R_{k}\in Routes\). * \((La-time)_{k}\): latest arrival time of \(R_{k}\in Routes\). * \((Ed-time)_{k}\): earliest departure time of \(R_{k}\in Routes\). * \((Ea-time)_{k}\): earliest arrival time of \(R_{k}\in Routes\). * \(G^{T}=(V^{T},A^{T})\): Route graph
* \(V^{T}\): Set of all non-dominated routes which are vertices in the route graph. * \(A^{T}\): Set of edges in the route graph
* \(H_{k}^{T}\): List of labels on node \(R_{k}\)
* \(SuccT(R_{k})\): Set of successors of route \(R_{k}\). * \(E^{T}\): List of routes waiting to be processed. * \(ExtendT(L_{k}^{T},R_{k})\): Function that returns the label resulting from the extension of label \(L_{k}^{T}\in H_{i}^{T}\) towards node \(R_{h}\) when the extension is possible, nothing otherwise. * \(DominatedT(H_{h}^{T})\): Procedure that removes dominated labels in the list of labels \(H_{h}^{T}\). * \(FT_{kh}\): List of labels extended from \(R_{k}\) to \(R_{h}\)```
Input:\(G(N,A)\) {All notation used are written above}  output: all non-dominated tours  Initialization {Generate all non-dominated routes} \(H_{p}\leftarrow\{(0,..,0)\}\) for all\(v_{i}\in V-\{p\}\)do \(F_{ij}\leftarrow\emptyset\) endfor \(E=\{p\}\) while\(E!=\emptyset\)do  Choose \(v_{i}\in E\) for all\(v_{j}\in\mathit{Succ}(v_{i})\)do \(F_{ij}\leftarrow\emptyset\) for all\(L_{i}\in H_{i}\)do if\(V_{i}^{j}=0\)then \(F_{ij}\gets F_{ij}\cup Extend(L_{i},V_{j})\) endif endfor \(H_{j}\gets Dominated(F_{ij}\cup H_{j})\) if\(H_{j}\) has changed then \(E\gets E\cup\{v_{j}\}\) endif endfor for all\(L_{i}\in H_{i}\)do if\(L_{i}\) is not extended to any \(v_{j}\in\mathit{Succ}(v_{i})\)then \(Routes\gets Extend(L_{i},n+1)\) endif endfor \(E\gets E-\{v_{i}\}\) endwhile for all\(R_{k}\in\mathit{Routes}\)do {Generate the route graph}  Add \(R_{k}\) to \(V^{T}\)  Calculate \((Ld-time)_{k}\), \((La-time)_{k}\),\((Ed-time)_{k}\), and\((Ea-time)_{k}\).