A Two-Level solution approach to solve the Clustered Capacitated Vehicle Routing Problem

The Clustered Capacitated Vehicle Routing Problem (CCVRP) aims to determine the routes of a fleet of capacitated vehicles to fulfill the service demands of customers organized into clusters. The optimization criterion is to minimize the total travel cost of the routes. The main constraint is that all the customers belonging to the same cluster have to be served by the same vehicle consecutively. In this work, a mathematical formulation for the CCVRP is developed. Since the problem is NP-hard, an approximate Two-Level solution approach is proposed. It is based upon breaking the problem down into two routing problems. The first one aims to determine routes targeted at visiting the clusters. A metaheuristic algorithm is considered to address this sub-problem. Furthermore, the second one is aimed at finding a visiting order of the customers belonging to each cluster. Exact and approximate methods are proposed to tackle this sub-problem. The computational results indicate the high performance of our approach over a wide range of real-size problem instances. In this regard, a cluster generation to define problem instances is presented. (C) 2015 Elsevier Ltd. All rights reserved.