## 4 Column Generation for \(Mtvp\)-\(Vw\)-\(Tw\)
### Generating All Non-Dominated Paths  
All non-dominated routes must first be generated to solve the sub-problems. The label correcting algorithm [33] is used to create all these routes. To keep track of previously visited nodes, elementary paths must be generated. A path \(p\) from an origin node \(o\in N\) to a node \(j\in N\) is labelled with \(R_{p}=(C_{p},t_{p}^{1},t_{p}^{2},s_{pe},V_{p}^{1},\ldots,V_{p}^{n})\). Time consumption, \(t_{p}^{1}\) is the time used in the path till customer \(v_{j}\) which sets to 0 at the depot, and after extending a path by visiting a new customer, it is updated as \(t_{p}^{1}=t_{p}^{1}+t_{ij}+s_{j}\), where \(v_{i}\) and \(v_{j}\) are two adjacent customers on the route and \(s_{j}\) represents the service time for the customer \(v_{j}\). Load consumption, \(t_{p}^{2}\) is the capacity used for the path and sets to 0 at the beginning when the vehicle is at the depot, then when a customer is added to the path, it is updated by \(t_{p}^{2}=t_{p}^{2}+d_{j}\) where \(d_{j}\) is the quantity that must be delivered to the customer \(v_{j}\). A time interval \([a_{i},b_{i}]\) representing the time window is associated with each customer \(v_{i}\) and a load interval \([0,Q]\), where \(Q\) is the vehicle's capacity. \(C_{p}\) is the length of the path and is made negative by replacing the distance \(t_{ij}\) of each arc with \(t_{ij}-a\), such that \(a>max_{(i,j)\in A}t_{ij}\). We make the distances negative so that vehicles leave the depot. Otherwise, it would be optimal to stay at the depot; \(s_{pe}\) is the number of unreachable nodes and \(V_{p}^{1}=1\) if node \(i\) is unreachable, 0 otherwise. The following dominance relation is used to determine non-dominated routes:  
**Dominance Relation:** If two paths, \(p\), and \(p^{\prime}\), extend from origin \(o\) to node \(j\) with labels \(R_{p}\) and \(R_{p^{\prime}}\), respectively, then path \(p\) dominates \(p^{\prime}\) if and only if \(C_{p}\leq C_{p^{\prime}},s_{pv}\leq s_{p^{\prime}v}\), \(t^{k}_{p}\leq t^{k}_{p^{\prime}},\forall k=1,\ldots,l,V^{i}_{p}\leq V^{i}_{p^{ \prime}},\forall i=1,\ldots,n\)[38].  
In other words, a path \(p\) dominates a path \(p^{\prime}\) if (a) it is no longer, (b) it does not use more resources for each resource taken into account, and (c) every node that is unreachable for path \(p\) is also unreachable for path \(p^{\prime}\)[38].  
Using this relation will keep only the labels for non-dominated elementary paths.  
To implement the label correcting algorithm for our problem, we need to create a label \((C_{p},t^{1}_{p^{\prime}},t^{2}_{p^{\prime}},s_{pv},V^{1}_{p},\ldots,V^{n}_{p})\) which represents a path \(p\) from the depot to the customer \(j\). All feasible non-dominated routes are generated using these labels.  
During the path extension, we need to see if the current time consumption (\(t^{1}_{p}\)) plus the distance \(d_{ij}\) is less than \(a_{i}\), then \(t^{1}_{p}\) is replaced by \(a_{i}\), and the extension of the path continues. Each time we extend one node or the node is unreachable, \(s_{pv}\) increases by one. We also eliminate the partial routes when we are extending the paths. So, at the end of the algorithm, we will have all non-dominated routes.