Rearch On The Vehicle Routing Problem With Time Windows Based On Cluster Analysis And Genetic Algorithm

Vehicle Routing Problem (VRP) is one of the key processes of logistics distribution. As competitions among logistics distribution industry are getting more and fiercer and customers'requirements for a time-effective logistics distribution are becoming more and more intense, studies on VRP, especially Vehicle Routing Problem with Time windows (VRPTW), are practically significant on every aspect of logistics distribution industry. Transportation companies can improve their services by providing their customers with fast, punctual, safe and comfortable services, their transportation costs can be cut down by improving vehicles utilization. Besides, fast speed, as a "bottleneck" to the development of e-commerce, is largely solved. Production cycles are shortened and capital turnover is accelerated, therefore,rational allocations of resources can be realized and fortunes from "the third profit source" can as well be made.Under a serious analysis on the researched status of VRP both in China and abroad, VRPTW was particularly analyzed in depth. Considering the impacts from roads congestion on the distribution, mathematical models on VRPTW were built with the introduction of road resistance coefficient. Two-phase heuristic algorithm was applied to solve the models according to the characteristics of large-scale VRP. Firstly, large-scale VRP was simplified into small-scale VRP by using k-means cluster analysis to divide the distribution network in order to reduce computation while improve the computing speed; Secondly, an improved genetic algorithm, whose chromosome coding and cross-ways were changed to a better pattern, was adopted to greatly simplify the solution process and create advantages to quickly and effectively optimize VRPTW. Finally, an automatic optimization on delivery routes was effectively worked out through the implementation of MATLAB programming. Comparisons of computed results with other improved genetic algorithm were carried out under a study case to further indicate that the improved genetic algorithm in this paper have considerable advantages on solving VRPTW, and on the premise of minimization used vehicles, a relatively shortest route can be worked out, thus ensuring the lowest total operating costs.