Clustering Based Two-Stage Search for Capacitated Vehicle Routing Problem

Capacitated Vehicle Routing Problem (CVRP) is a variant of Vehicle Routing Problem constrained with demand and capacity is investigated. Due to its extensive uses in the field of logistics and transportation, CVRP becomes one of the major research topics. Researcher all over the world has investigated several solving approaches for CVRP. In this project, a two-phase approach is proposed for solving the CVRP. This approach consists two parts with initial solution generation and route optimization phase. For the first phase, two clustering algorithms Fuzzy-C-Means and K-Means with Nearest Neighbor have used. Two different combination Fuzzy-C-Means with Nearest Neighbor approach and K-Means with Nearest Neighbor approach have independently used for generating initial solution. In the second phase, two well know meta-heuristics; Generic Algorithm and Simulated Annealing Algorithm have applied independently with the two different initial solution approaches. This leads to four different experimental setup with Fuzzy-C-Means and Nearest Neighbor with SA, Fuzzy-C-Means and Nearest Neighbor with GA, K-Means and Nearest Neighbor with SA and K-Means and Nearest Neighbor with GA. Each of the four setup has investigated on 45 benchmark datasets. It has been found that K-Means and Nearest Neighbor with SA has better performance among the four setups. In addition, comparing the results of K-Means and Nearest Neighbor with SA with the previous six research, it provides also satisfactory outcomes.

• Supervision