# Branch and Price Algorithm

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.

• This question led to an interesting discussion regarding minimax problems: or.stackexchange.com/q/143/2477 Sep 3, 2020 at 0:59

Being a good or bad approach will depend on several factors, for example:

• the size of the instances
• time available to find a solution (this tends to be an important matter in vehicle routing applications)
• computing power
• what level of solution quality qualifies as good enough

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:

1. Take a look at the project's documentation.
2. Take a look at the code in GitHub.
3. Create a fork or download the project as .zip, such that you can make changes locally.
4. Modify the code regarding the subproblem, such that the depot is split as was explained above.
5. Run the experiments, you can follow the example instances from the documentation like here and here.
6. Let us know how it worked. And remember to acknowledge VRPy and its developers in your work (be it a project report, thesis, publication, etc), as well as respecting the terms on the library's license with respect to modifications.
• Thanks for your help.
– Bhr
Sep 3, 2020 at 11:10

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 :

1. Solve the problem without the min_max option

2. Query the largest span

3. Solve again without min_max, but constrain the problem such that each route has a smaller span than the largest one queried in 2.

4. If infeasible, stop, otherwise, go to step 2.

All of this is straightforward with VRPy's ecosystem. Have fun.