# A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet

I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 entitled Subproblem I can't understand how Expression (23) is equivalent to Expression (22)?

The source considers a fleet of size $$U$$ and a directed graph $$G = (V,A)$$ with nodes $$V = \left \{v_0, \ldots, v_n \right \}$$, where $$v_0$$ is the depot and the rest the customers. Every arc $$(i,j)$$ has an associated cost and time $$c_{ij}$$ and $$t_{ij}$$, respectively.

Then, the following notation is introduced to formulate the column generation model:

• $$\Omega$$ is the set of feasible routes
• $$c_k$$ is the cost of route $$r_k \in \Omega$$
• parameter $$a_{ik} = 1$$ if route $$k$$ visits customer $$i$$, 0 else
• parameter $$b_{ijk} = 1$$ if $$k$$ uses arc $$(v_i,v_k)$$, 0 else

With this, the standard column generation formulation for the VRPTW is stated as \begin{align} &\text{minimize} & \sum_{r_k \in \Omega} c_k \theta_k \\ &\text{s.t.} &\sum_{r_k \in \Omega} a_{ik} \theta_{k} &\ge 1, && v_i\in V \setminus \left \{ v_0 \right \}\\ &&\sum_{r_k \in \Omega} \theta_{k} &\le U \\ &&\theta_{k} &\in \mathbb{N}, && r_k \in \Omega \end{align}

Let $$\lambda_0, \lambda_i$$, be the dual variable associated to the fleet size constraint and for constraints related to visiting client $$i$$, respective, and $$\lambda^*$$ be an optimal solution to the dual of the restricted master program. The mentioned expressions (22) and (23) are the following:

Reduced cost subproblem: $$(22) \; c_k - \sum_{v_i \in V \setminus \left \{v_0 \right \} } a_{ik} \lambda^*_i - \lambda^*_0 < 0.$$ Equivalent problem: $$(23) \;\sum_{(v_i,v_j) \in A} b_{ijk}(c_{ij} - \lambda^*_i) < 0.$$

I 'm so appreciated if someone can help me.

• Could you write the expressions and some context regarding the variables and parameters? (for the ones among us who don't have access to the publication) Aug 12, 2020 at 16:21
• in this part, it is said that the subproblem reduces to an elementary shortest path problem with resource constraints (ESPPRC).
– Bhr
Aug 12, 2020 at 21:54

1. The cost of a route is the addition of the arcs that compose it: $$c_k = \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij}$$
2. Relate $$a_{ik}$$ ($$r_k$$ visits customer $$i$$) with $$b_{ijk}$$ (route $$k$$ uses arc $$(i,j)$$): $$a_{ik} = \sum_{v_j \in V: (v_i, v_j) \in A} b_{ijk}$$
And the conditions (22) and (23) are equivalent because: \begin{align*} c_k - \sum_{v_i \in V \setminus \left \{v_0 \right \} } a_{ik} \lambda^*_i - \lambda^*_0 &\stackrel{1.}{=} \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{v_i \in V \setminus \left \{v_0 \right \} } a_{ik} \lambda^*_i - \lambda^*_0 \\ &\stackrel{2.}{=} \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{v_i \in V \setminus \left \{v_0 \right \} } \sum_{v_j \in V: (v_i, v_j) \in A} b_{ijk} \lambda^*_i - \lambda^*_0 \\ &= \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{(v_i, v_j) \in A: v_i \in V \setminus \left \{v_0 \right \}} b_{ijk} \lambda^*_i - \lambda^*_0 \\ &= \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{(v_i, v_j) \in A: v_i \in V \setminus \left \{v_0 \right \}} b_{ijk} \lambda^*_i - \sum_{v_j \in V - v_0} b_{0jk} \lambda^*_0 \\ &= \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{(v_i, v_j) \in A} b_{ijk} \lambda^*_i \\ &= \sum_{(v_i, v_j) \in A} b_{ijk}( c_{ij} - \lambda^*_i) \end{align*} where we used the fact that $$\sum_{0jk} = 1$$ for every feasible route $$r_k$$.