Exact Method for Routing Vehicles with Two-Dimensional Packaging and Conflicts

In this paper, we present the Problem of Capacitated Vehicle Routing with Two-Dimensional Loading Constraints and Conflicts, which consists in finding routes for a fleet of vehicles that must meet the demands of a set of customers without exceeding the capacity of the vehicles. In addition, it is necessary to find a two-dimensional packing for the items, respecting the unloading order and the conflicts between them. We present a Branch-and-Cut algorithm that uses an Integer Linear Programming model and propose improvements involving breaking symmetry and preprocessing. We use a Constraint Programming model to determine whether a set of items can be allocated to a vehicle and thus find violated cuts. Tests were performed on instances adapted from the literature and we found that the implemented improvements had a modest impact on the execution time, but enabled the model to double the number of optimal solutions achieved.