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
    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
    Aug 11, 2020 at 6:17
  • $\begingroup$ This thread is related to your question or.stackexchange.com/questions/143/… $\endgroup$ 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
    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
    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
    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
    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
    Sep 4, 2020 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.