Abstract: To solve vehicle routing problem with indeterminate number of vehicles,large-scale outlets and multi-level transportation network,we established the road property mode based on rich network and GIS,mixed N-order nearest-neighbor adaptive clustering algorithm and genetic algorithm.Firstly,to solve the problem of small-scale outlets(less than 20 outlets) in traditional vehicle routing problem and the defect that abstracting the outlets into graph’s vertices during model establishing,we established network dataset based on actual road data,utilized GIS to exactly calculate the distance between outlets and built OD matrix of distance.Secondly,to reduce the complexity of designing large-scale outlets optimization algorithm,this paper used N-order nearest-neighbor adaptive clustering algorithm to determine the number of clusters,then divided the distribution outlets by clusters.Subsequently,to determine the kind and number of distribution vehicles and restriction of time window,we used genetic algorithm to optimize the distribution path.Finally,two examples verified the effectiveness of the proposed method.

Key words: Rich network model,Clustering algorithm,Genetic algorithm,OD matrix,Vehicle routing