Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP.
In the literature, I haven't ever seen that this solution approach used to solve such a problem. As far as I know, this approach is used to solve VRPs minimizing total cost.
Being a good or bad approach will depend on several factors, for example:
See this work by Yu, Nagarajan and Shen on the minimum makespan VRP with compatibility constraints, as it's a similar problem that's been studied before using branch-and-price as an approach to solve a makespan VRP variant. It worked quite well. Note that in their case, they designed an approximation algorithm to accelerate the B&P execution time.
I suggest the following experiment:
First step: Following @RobPratt's answer to your previous question regarding makespan minimization in VRP:
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.
As stated there, the subproblem can be reformulated as elementary shortest path: Split the depot into a source and a sink, and move the node weights to the arcs: $\pi_v c_{i,j}−\alpha_i$ for the weight of arc $(i,j)$ in the elementary shortest path subproblem.
Second: Implement the above method. I recommend trying to use VRPy, as suggested by Kuifje here. That way you won't have to implement all the branch and price operations from scratch. Detailed steps:
VRPy (v0.3.0) now supports this option : all you have to do is set the minimize_global_span option to True when instantiating the VehicleRoutingProblem object:
prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True)
prob.solve()
Of course, your graph $G$ has to be well defined in the first place.
The formulation proposed by @RobPratt is implemented. If you play around with some toy problems, you will see that the formulation is weak compared to the classical one (without the makespan). It is easy to see that the constraint $$ z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j}x_{i,j}^p\right) \lambda^p_v \ge 0 \quad \text{ for $v\in V$} $$ is responsible for this.
You can also try the following alternative approach :
Solve the problem without the min_max option
Query the largest span
Solve again without min_max, but constrain the problem such that each route has a smaller span than the largest one queried in 2.
If infeasible, stop, otherwise, go to step 2.
All of this is straightforward with VRPy's ecosystem. Have fun.
