An exact approach for the capacitated vehicle routing problem with twodimensional loading constraints

The classical Capacitated Vehicle Routing Problem [2] calls for the determination of the optimal set of routes to be performed by a fleet of vehicles, each with a maximum transport capacity, in order to satisfy the demands of a given set of customers. The demands are usually expressed by a positive integer, representing the weight or volume to be delivered. This can lead to a too strong approximation for many practical routing applications, where real demands are composed by items of a given size, and the loading of these items into the vehicles can be difficult. We consider the practical case in which the demand of each customer is defined by a set of rectangular items, each with a given weight and base dimensions. Thus, loading these items into a vehicle requires both checking that the maximum weight capacity is respected, and that the two-dimensional loading is feasible. The problem is composed by a routing part, which was solved through a branch and cut technique, and by a loading part, solved through a dedicated branch and bound derived from the one proposed in [1]. Separation procedures and lower bounds were developed for the new problem, as well as greedy heuristics and local search. The algorithm was coded in C and tested on instances derived from those available in the literature, being able to solve to optimality instances with up to 35 customers and 110 items. References: [1] S. Martello and D. Vigo. Exact Solution of the Two-Dimensional Finite Bin Packing Problem. Management Science 44, 388 - 399 (1998). [2] The Vehicle Routing Problem. P. Toth and D. Vigo editors. SIAM Monographs on Discrete Mathematics and Applications (2002).