You are here

Clustered Vehicle Routing Problem

Defintion

The Clustered Capacitated Vehicle Routing Problem (CCVRP) is a generalization of the VRP where a fleet composed of a unlimited number of identical delivery trucks has to fulfill the service demand of a set of n customers organized in clusters. All the delivery trucks are initially located at a central depot (node 0). Each customer i ∈ {1, ..., n} has a positive demand, di . In addition, we are also given a partition of m clusters, in such a way that, for each customer i ∈ {1, ..., n}, its cluster is denoted by ri ∈ {1, ..., m}. The set of customers belonging to a given cluster r ∈ {1, ..., m} is denoted by Cr . Also, cij denotes the euclidean distance between the nodes i and j, ∀i, j ∈ {0, ..., n}. It is worth to mention that all the distances satisfy the triangle inequality.

Furthermore, the maximum load capacity of the trucks is denoted by k. It is assumed that the total demand of each cluster does not exceed the maximum load capacity of the available trucks, that is, i∈Cr di ≤ k, ∀r ∈ {1, ..., m}. This means that a single delivery truck can fulfill the demand of several clusters whenever its load capacity allows it.

The goal of the CCVRP is to define the set of routes with minimum travel distance used by the fleet of delivery trucks in order to fulfill the demand of the final customers. The feasible solutions for the CCVRP must satisfy the clustering constraints: when a truck visits a customer in cluster, it has to serve all the customers of that cluster before it can enter another cluster or return to the depot.

Example

The figure below describes a solution of the problem

Instances

Several classes of instances are available for testing algorithms.

File format and instances files are available in the file CCVRP_INSTANCES.zip