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 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 at 6:17
  • $\begingroup$ This thread is related to your question or.stackexchange.com/questions/143/… $\endgroup$ – Claudio Contardo Aug 13 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$.

| improve this answer | |
  • $\begingroup$ is the pricing problem still the shortest path problem (based on time of each arc)? $\endgroup$ – Bhr Aug 14 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 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 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 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 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.