A relaxation-guided approach for vehicle routing problems with black box feasibility

Massen, Florence [UCL] Deville, Yves [UCL] Van Hentenryck, Pascal [Brown University, USA]

This paper proposes an abstraction of emerging vehicle routing problems, the Vehicle Routing Problem with Black Box Feasibility. In this problem the routes of a basic VRP need to satisfy an unknown set of constraints. A black box function is provided to test the feasibility of a route. This function is considered of non-linear complexity (in the length of the route). The complexity of the problem under consideration lies in the unknown problem structure and the expensive feasibility check. Practical examples of such problems are combinations of VRP with Loading problems or VRP with Scheduling problems. We propose a column generation-based approach to locally optimize this problem. Columns are heuristically generated by so-called collector ants, executing a construction heuristic and guided by pheromones. The pheromones are not deposited by the ants themselves, but by an oracle. This oracle judges which edges should be preferred by the ants based on the solution of the relaxed problem. Through these steps we improve the lower bound for the problem at hand. The presented work constitutes the pricing step in a heuristic Branch-and-Price framework that is yet to be implemented.