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?

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

1 Answer 1


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$.

  • $\begingroup$ is the pricing problem still the shortest path problem (based on time of each arc)? $\endgroup$
    – Bhr
    Commented Aug 14, 2020 at 0:37
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Commented Aug 14, 2020 at 1:34
  • 1
    $\begingroup$ Sorry, I meant $\pi_v c_{i,j}-\alpha_i$ for the weight of arc $(i,j)$ for the elementary shortest path subproblem. $\endgroup$
    – RobPratt
    Commented Aug 23, 2020 at 20:42
  • $\begingroup$ Thanks a lot. I think the right-hand side of the second constraint must be 1 instead of d(i). $\endgroup$
    – Bhr
    Commented Aug 23, 2020 at 22:58
  • 2
    $\begingroup$ @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. $\endgroup$
    – RobPratt
    Commented Sep 4, 2020 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.