COMPARISON OF DIFFERENT CLUSTERING ALGORITHMS VIA GENETIC ALGORITHM FOR VRPTW

Abstract

In this paper, Vehicle Routing Problem with Time Windows (VRPTW) with known customer demands, a central depot and a set of vehicles with limited capacity, is considered. The objectives are both to minimize the total distance and the total waiting time of the vehicles while capacity and time windows constraints are secured. The applied solution techniques consist of three steps: clustering, routing and optimizing. By using K-means, Centroid-based heuristic, DBSCAN and SNN clustering algorithms in the initial population generation phase of genetic algorithm, the customers are divided into feasible clusters. Then feasible routes are constructed for each cluster. Lastly, the feasible route solutions are taken as the initial population and genetic algorithm is utilized for the optimization. A set of well-known benchmark data is used to compare the obtained results. According to the results of the study it is observed that using K-means clustering algorithm in generating the initial population of the genetic algorithm is more effective for the handled problem.