# 3L-CVRP

home

## 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 L_{i}
of n_{i} items. Each item e is defined as a 3D box (w_{e},l_{e},h_{e})
and a weight p_{e}. Arc (i,j)∈A corresponds to the shortest path
from node i to node j, of lenght c_{ij}. 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:

- each client is visited once
- each vehicle starts and ends its route at the depot
- the total weight of the items delivered to the clients in the route
does not exceed the vehicle capacity

Besides these CVRP constraints, additional 3D constraints have to be
satisfied:

- each item fits the container
- there is no collision between any pair of items
- [rotation] items can be rotated by 90 degrees on the X/Y plane
- [sequence] no items from subsequent clients prevent items from the
current client to be extracted using a translation parallel to the
conteainer's length
- [support] a given percent of each item bottom area must be in direct
contact with the floor or the top of other items
- [fragility] fragile items cannot be located under any other item

The 3L-CVRP is NP-hard as it generalizes the CVRP. It combines the CVRP and
the three-dimensional orthogonal Packing Problem (3PP).

## instances

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.

## references

- Andreas
Bortfeldt: A
hybrid algorithm for the capacitated vehicle routing problem with
three-dimensional loading constraints. Computers
& OR 39(9):
2248-2257 (2012)

- Guenther
Fuellerer, Karl F. Doerner, Richard
F. Hartl, Manuel
Iori: Metaheuristics
for vehicle routing problems with three-dimensional loading
constraints. European
Journal of Operational Research 201(3):
751-759 (2010)

- Michel
Gendreau, Manuel
Iori, Gilbert
Laporte, Silvano
Martello: A
Tabu Search Algorithm for a Routing and Container Loading Problem. Transportation
Science 40(3):
342-350 (2006)