Let G = (N,A) be a directed graph where N is the set of nodes and A is the
set of arcs. Let I ⊂ N be the set of potential hubs. Each hub i ∈ I is given
a fixed opening cost Fi. Let J ⊂ N be the set of clients. Each
client j ∈ J is given a demand di. An homogeneous fleet of
vehicles of capacity Q is available. They can be located at any open hub to
deliver the clients. Each arc (i,j) ∈ A is given a travel cost cij.
The Location Routing Problem (LRP) consists in selecting the hubs to open
and in computing a set of routes to deliver the clients such that:
The LRP is NP-hard as it generalizes the CVRP. It combines the CVRP with the
Facility Location Problem (FLP).
- each client is visited exactly once
- each vehicle is assigned to an open hub
- each vehicle leaves and enters its hub at most once
- the vehicle load never eaceeds its capacity
- the total cost (hub opening + vehicle fixed cost + travel distance) is
Three classic sets of instances are available:
We propose a new set of instances. Instances range from 16 to 341 nodes.
Graphs are asymmetrical, vehicle fleet is homogeneous and depots are
non-homogeneous. Besides, there is no correlation between distance and
transportation time and between demand and service time. The set has be
split in 3 classes: small, medium and large instances.
- Tuzun set, available here;
- Barreto set, available here;
- Prodhon set, available here.
- small instances (16 to 40 nodes), available here;
- medium instances (42 to 100 nodes), available here;
- large instances (110 to 341 nodes), available here;
- full set of instances, available here;
- the details on the instances are here;
- a list of the best known solutions for this set is here.