You are here

Metaheuristics for Clustered Vehicle Routing Problems

Part of the seminar cycle "Computational logistics", M. Sevaux has presented some research work in collaboration with A. Rossi, K. Sörensen and T. Barthélémy on "Metaheuristics for Clustered Vehicle Routing Problems".

The clustered Vehicle Routing Problem is defined as follows. An unlimited number of identical vehicles is available in the depot, and have to deliver goods to n customers. The capacity of the vehicles is denoted by K and the demand of customer ci is denoted by Di for all i in {1, . . . , n}. A partition of customers into m clusters is also provided, and all the customers that belong to the same cluster have to be visited by the same vehicle (or equivalently in the same trip). The problem objective is to visit all the customers exactly once while minimising the total travelled distance.
Such a situation arises in the field of delivery companies, where clusters are defined by zip codes or geographical locations: in that case, all the goods to be delivered to customers in the same cluster are loaded in a single truck. Of course, more than one cluster can be visited in a trip, but once a customer is visited, the vehicle cannot come back to the depot or visit a customer out of the current cluster unless all the customers in that cluster have been visited. Thus, a trip can also be viewed as a sequence of clusters to visit. That clustering constraint implies that the vehicle capacity has to be larger than the sum of the customer demands in any cluster for the problem to be feasible.

The presentation can be downloaded here.

Page tag: