Heuristic and exact algorithms for a minmax selective vehicle routing problem
In this work, we investigate a vehicle routing problem where not all clients need to be visited and the goal is to minimize the longest vehicle route. We propose two exact solution approaches for solving the problem: a Branch-and-cut (BC) algorithm and a Local Branching (LB) method that uses BC as its inner solver. Our computational experience indicates that, in practice, the problem is difficult to solve, mainly when the number of vehicles grows. In addition to the exact methods, we present a heuristic that relies on GRASP and on the resolution of a restricted integer program based on a set covering reformulation for the problem. The heuristic was capable of significantly improving the best solutions provided by BC and LB, in one tenth of the times taken by them to achieve their best upper bounds.
heuristics vehicle routing problem branch-and-cut local branching