This presentation considers the Clustered Vehicle Routing Problem (CluVRP) which is a variant of the classical Capacitated Vehicle Routing Problem. Customers are partitioned into clusters and it is assumed that each cluster must have been served in total before the next cluster can be served. This decomposes the problem into three subproblems, the assignment of clusters to tours, the routing inside a cluster, and the routing of the clusters in the tour. The second task requires the solution of several Hamiltonion path problems, one for each possibility to start and end the route through the cluster. These Hamiltonion paths are pre-computed for every pair of customers inside each cluster. The chosen start-end-pair of the clusters also affects the routing of clusters. We present a Large Neighborhood Search which makes use of the Balas-Simonetti neighborhood. Computional results are compared to existing exact and heuristic approaches from the literature. In addition a second variant, the CluVRP with soft constraints, is considered. Customers of same clusters must still be part of same routes, but do not need to be served contiguously any more. Adaptions of our approach are discussed.
| Subject : | : | Abstracts |
| Topics | : | Heuristics |
| PDF version | : |  PDF version |
