An Intelligent Approach To The Generation Of Vehicle Routing Schemes In Distribution

Focusing on the state explosion problem in solving Vehicle Routing Problem,which is derived from the increase of the scale,this paper aims at great reduction of solution state-space.Applying theories of Artificial Intelligence,Knowledge Engineering and Operational Research,it presents an intelligent solution approach,which includes three steps, distribution area division and customer classification,intelligent routing scheme generation, and mathematical model construction and solution.The detailed work studied in the paper is as follows.(1) Method for distribution area division and customer clustering.The principle of distribution area division and customer classification is first presented.And the factors according to what the distribution area is initially divided into smaller areas are analyzed. Then using fuzzy clustering analysis the customers are subdivided.This distribution area division and customer clustering provide a foundation for the intelligent approach to vehicle routing scheme generation.(2) Intelligent generation approach to vehicle routing schemes,mathematical model construction and solution.Based on the distribution area division and customer classification, the formation process of routing schemes and its variety of parameters are summarized and the flowchart of the depth-first search process with control rules is disigned in the paper.Then a set of feasible routing schemes is achieved.After a mathematical model is constructed and solved,the better solutions are selected from the feasible scheme set.Finally,a nearest neighbor principle is developed to interpret solutions to the real problem's vehicle routings.(3) Design and realization of a VRP scheme solution system.A solution system is designed,which includes three modules,distribution area division processor,VRP scheme generator,and VRP scheme solver.Applying Java techniques,SQL Server 2000 Databese, Amzi Prolog,Lindo,the paper realizes the VRP scheme solution system.(4) Application and performance analysis of the VRP solution system.Choosing a pork distribution problem in North Grocery Company in Beijing as application background,the paper does some application research for the approach to routing sheme generation and its solution system to verify the approach's effectiveness of the theoretical result.And it analyzes several scenarios resulted from the combinations of two factors to observe the performance of the routing scheme solution system.The results indicate the new solution approach to VRP realizes that the computation time stays almost unchanged as the sizes of problems increase.The research in this paper provides a new way to solve Vehicle Routing Problem,a kind of complex decision problems,which incorporates quantitative computing process and qualitative reasoning process.Integrating with related existing results in our group,which are GIS-based visualization for information platform in distribution under E-commerce, GIS-based isoline-generating system in urban distribution,real-time and intelligent system for E-Commerce order processing,the vehicle monitoring and scheduling system,the results can provide decision support for distribution center with realtime vehicle navigating,scheduling and monitoring.