# Column Generation algorithm for vehicle routing problem

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I want to know how I should write the path-based model?

In path-based models that I have ever seen for VRP, the objective was total cost minimization and all of the variables in the model were binary that corresponds to each route. I think in my problem, I should consider a continuous non-negative variable that represents the latest arrival time of vehicles to depot. I want to know if adding this variable is correct and how will it change the column generation algorithm?

• How many vehicles? Are they identical? Are you required to use them all? – RobPratt Aug 11 '20 at 2:42
• There are finite number of vehicles (max K) which are identical and it is not required to use all of them. – Bhr Aug 11 '20 at 6:17
• This thread is related to your question or.stackexchange.com/questions/143/… – Claudio Contardo Aug 13 '20 at 2:20

Let $$d_i$$ be the demand for customer $$i\in N$$, let $$V=\{1,\dots,K\}$$ be the set of vehicles, and let $$P$$ be the set of columns, where each column corresponds to a feasible subtour starting from the depot, with arc variables $$x_{i,j}$$ and node variables $$y_i$$. Let $$z$$ be the makespan. The master problem over $$z$$ and $$\lambda$$ is as follows, with dual variables in parentheses: \begin{align} &\text{minimize} &z \\ &\text{subject to} &z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j} x_{i,j}^p\right) \lambda^p_v &\ge 0 &&\text{for v\in V} &&(\pi_v \ge 0)\\ &&\sum_{v \in V} \sum_{p\in P} y_i^p \lambda^p_v &\ge 1 &&\text{for i\in N} &&(\text{\alpha_i \ge 0})\\ &&-\sum_{p\in P} \lambda^p_v &\ge -1 &&\text{for v\in V} &&(\text{\beta_v \ge 0})\\ &&\lambda^p_v &\ge 0 &&\text{for v\in V and p\in P} \end{align}
The column generation subproblem over $$x$$ and $$y$$ for each $$v\in V$$ is then to minimize the reduced cost of $$\lambda^p_v$$. That is, minimize $$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ subject to $$(x,y)$$ forming a feasible subtour starting from the depot, with $$\sum_i d_i y_i \le L$$, where $$L$$ is the capacity of each vehicle.
Because the vehicles are identical, you can use a common column pool $$P$$ instead of requiring a different $$P_v$$ for each $$v\in V$$.
• Yes, you can reformulate the subproblem as elementary shortest path by splitting the depot into source and sink and moving the node weights to the arcs: $\pi_v c_{i,j}+\alpha_i$. – RobPratt Aug 14 '20 at 1:34
• Sorry, I meant $\pi_v c_{i,j}-\alpha_i$ for the weight of arc $(i,j)$ for the elementary shortest path subproblem. – RobPratt Aug 23 '20 at 20:42
• @Kuifje The pricing objective function depends on $v$, so you have $K=|V|$ pricing problems. But you don't necessarily have to solve all of them each time. You can return to the master as soon as you find one negative-reduced cost column. – RobPratt Sep 4 '20 at 18:55