Column Generation algorithm for vehicle routing problem

Question

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?

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