2L-CVRP: A GRASP resolution scheme based on RCPSP

This paper addresses an extension of the well-known Capacitated Vehicle Routing Problem (CVRP) where the customer demands represented by two-dimensional weighted items have to be packed into the vehicles. This problem, denoted 2L-CVRP, is NP-hard and it is particularly difficult to solve in practice. We propose a GRASP algorithm in which the loading constraint is handled by a Resource Constraint Project Scheduling Problem (RCPSP) heuristic specially tuned to address the bin-packing part of the problem. The effectiveness of our approach is demonstrated through computational experiments on both CVRP and non-sequential 2L-CVRP instances. Three new best average costs for class 2–5 are provided for 2L-CVRP instances.