A Clustering-based Algorithm For Vehicle Routing Problem

The thesis deals with the Vehicle Routing Problem (VRP) in the logistics. The Vehicle Routing Problem is a problem to design the optimal delivery or collection routes, starting and ending at the depot, with minimum total cost under certain constraints. VRP has been attracting lots of logistics researchers for long.Until recently, some valuable conclusions and algorithms have been remarkably explored. Proper methods for small-scale problems have been well developed. However as the great expansion of the problems' scales in practical requirements, the existing algorithms fall short of the practical need. Aiming at the difficulties in solving them, a three-phase algorithm is put forward: firstly clustering customers: a DBSCAN based clustering algorithm is developed so as to merge customers into a few groups; secondly deploying vehicles: Clark-Wright saving algorithm is used to assign customer groups to delivery vehicles; finally arranging customers visiting sequence: effective TSP algorithms, such as Ant Colony Algorithm ,Nearest Neighbor Algorithm, can be chosen to arrange customers visiting sequence for every vehicle.In order to verify the feasibility and validity of the proposed algorithm, a large number of simulation experiments have been carried on. They can be divided into two parts: experiments on the well-known benchmarks and the tobacco delivering vehicles routing problem of Shanxi province Yangquan Tobacco. The first part of simulations ends up with good results which are just 3%-7% inferior to the best known solutions. Besides, the Yangquan VRP problem with 4642 customers is successfully solved by the clustering-based algorithm in just 27 minutes with good results.At last, the thesis discusses some challenging topics which deserve further investigation in future and forecasts the prospects of the research and application in the domain.