Optimization approaches for vehicle routing problems with Black Box Feasibility

The Vehicle Routing Problem (VRP) is concerned with determining how a set of vehicles can be used to visit a set of customers such as to minimize some cost function. A solution to this problem describes a set of routes each executed by one vehicle. We focus on VRPs with complicated side-problems. In these VRPs each route must respect a set of complex constraints. In order to verify whether a given vehicle route respects these constraints, a complicated side-problem has to be solved. Existing optimization approaches for this type of VRPs make use of very specific knowledge of this side-problem. This entails that these ad-hoc approaches cannot be easily adapted to a VRP with a different side-problem. The goal of this thesis is to propose optimization approaches for VRPs with complicated side-problems that are as generic as possible w.r.t. the side-problem. An abstraction of VRPs with complicated side-problem, the VRP with Black Box Feasibility (VRPBB) is formulated. By definition of the VRPBB, any optimization approach for this problem is completely generic w.r.t. the side-problem. Then, three optimization approaches for the VRPBB are proposed and implemented into a coherent system. They use Column Generation techniques along with Heuristic concepts. An algorithm configuration procedure is used on one of the approaches. This allows to identify high-performing configurations and to analyze the impact of the different components and parameters of this method. Finally all of the proposed approaches are tested on two concrete instantiations of the VRPBB, combining three-dimensional and one-dimensional loading and routing. Their performance and behavior are analyzed and compared. The results show that one of the generic approaches achieves results improving those obtained by ad-hoc methods from the literature, which were designed specifically for the concrete problem at hand.