Capacitated Vehicle Routing Problem
Vehicle routing problems deal with the optimal use of
a fleet of vehicles to transport (pick up or deliver) goods
between a central depot and a set of clients. Several
interesting examples arise in scheduling school buses,
mail collection from the mail-boxes, delivery of laundry,
garbage collection, ... Because of this enormous number
of practical applications (every one with specific objective and
constraints) several particular versions have been studied in the
literature.
We have worked on the following well-known version:
let us consider a road network with a set
N={1,...,n} of clients and a depot 0 as points. The depot has a set
M={1,...,m} of identical vehicles. Let cij
be the travel cost
of going directly from a point i to a point j in the network
(i.e., the cost of link ij),
qi the (positive) demand of a client i,
and Q the capacity of a vehicle.
A feasible route is defined as a subset of links representing
a simple cycle containing the depot 0 and a subset of clients
with total demand not bigger than Q.
Then, the Capacitated Vehicle Routing Problem (CVRP) is the problem
of finding a collection of at most m feasible routes
such that every client is
in exactly one feasible route and the total cost
of the considered links is minimized.
We made this work in Bologna, April 30, 1995.
My contributions with P. Toth and M. Fischetti are:
Experiments with a multi-commodity formulation for the
Symmetric Capacitated Vehicle Routing Problem
3rd Meeting of the EURO Working Group
on Transportation Barcelona (1995) 169-173.