6

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?

Bhr
  • 455
  • 2
  • 7

1 Answers1

7

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • is the pricing problem still the shortest path problem (based on time of each arc)? – Bhr Aug 14 '20 at 00:37
  • 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 01:34
  • 1
    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
  • Thanks a lot. I think the right-hand side of the second constraint must be 1 instead of d(i). – Bhr Aug 23 '20 at 22:58
  • Yes, corrected just now. The demands appear in the capacity constraint in the subproblem. – RobPratt Aug 24 '20 at 00:18
  • @RobPratt Does this mean you have to run $|K|$ pricing problems at each iteration (one for each $v\in V$) ? – Kuifje Sep 04 '20 at 18:04
  • 2
    @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 04 '20 at 18:55
  • Thanks for your insight – Kuifje Sep 04 '20 at 19:03