problem description

Let G=(N,A) be a digraph where N = {0, 1, ..., n} is the set of n+1 nodes and A is the set of arcs. Node 0 corresponds to the central depot while nodes 1...n are the clients. Each client i is given a list Li of ni items. Each item e is defined as a 3D box (we,le,he) and a weight pe. Arc (i,j)∈A corresponds to the shortest path from node i to node j, of lenght cij. A homogeneous fleet of vehicles is located at the depot. Let (W,L,H) be the size of each vehicle container and Q its capacity. The three-dimensional Capacitated Vehicle Routing Problem (3L-CVRP) consists in defining a set of routes of minimal total length such that:

Besides these CVRP constraints, additional 3D constraints have to be satisfied:
The 3L-CVRP is NP-hard as it generalizes the CVRP. It combines the CVRP and the three-dimensional orthogonal Packing Problem (3PP).


A classic set of instances has been proposed by (Gendreau et al. 2006). It can be downoladed here.
We propose a new set of 96 instances, based on the french counties. It can be downloaded here.