Rajesh Dhake

Dr. (Mrs.) NR Rajhans

Nagesh Bhole

Abstract

This paper proposes a simple hybrid approach that combines Sweep, K-Means, Minimal Spanning Tree and 2-opt algorithm to solve multi-objective capacitated vehicle routing problem. The objective is to minimize the total distance travelled (directly proportional to the transportation costs) and minimize the number of vehicles.The solution is found using cluster first and route second approach. Clusters are initially formed usinga combination of sweep heuristic and K-means clustering. Optimal routes within each cluster are formedusing minimal spanning tree (MST) and 2 opt algorithm.The proposed approach is tested on Christofides benchmark CVRPinstances ranging from 50 to 200 customers.

Keywords-