Research On Vehicle Routing Problem In Time-Varying Networks Environment

In China's 11th Five-Year Plan, we take modern logistics industry as a key development area in future, and put forward that by 2010 the whole societal logistics cost would be reduced 2-3 percentage points. Transportation and logistics distribution are the main factors that affect the total logistics cost, which account for the logistics cost of around 60%. As a key role of logistics optimization, the vehicle's optimal scheduling problem has become the hot research topics. In the past static vehicle routing problem (VRP) study, vehicle routing arrangements are mostly based on certain information, including the certain demand, the certain vehicle location and the certain driving time of vehicles. Especially the operating cost (time) between any two points (customers or depot) of vehicles is considered depending on the distance between points, which is usually regarded as known and constant. While in the actual traffic process, traffic management, traffic flow, traffic accidents, weather changes, and the rushing hours will change the driving speed continually, it leads the operating cost(time) in the road network correspondingly vary. So the theory and methods for static VRP are unable to apply to the dynamic environment, this makes the study of VRP in time-varying network urgent and necessary. In the dissertation, we take the three sub-problems of time-varying VRPs as study objects. They are time dependent traveling salesman problem (TDTSP) based on time period, TDTSP based on point position and time dependent vehicle routing problem (TDVRP). The main contents of this dissertation are listed as follows:In chapter 1, we first introduce the source and purpose of the studying problem, then analyze the background and significance of VRP in time-varying network, and describe the characteristics of the three sub-problems to be discussed. Finally we conclude the technical line and the main research work.In chapter 2, we summarize the study status quo of time-varying VRP, based on the large number of relevant literature, by classifying the studied time-varying VRPs, and summing up the methods for dealing with time-varying characteristics. We also review the algorithm for solving the static VRP and time-varying VRP, and introduce the very large scale neighborhood (VLSN) search technology issues to be used for time-varying VRPs in this dissertation. Finally we conclude the deficiency of the existing literatures and the further necessary research direction. In chapter 3, we take TDTSP based on time period as a research object, describing the characteristics and the nature of the problem, and developing an approach to deal with time-varying characteristics which satisfies first in first out (FIFO) property. Based on it, we establish the mathematical model, and give the traditional dynamic programming heuristic strategy, and then we adopt the dynasearch algorithm based on VLSN search technology for solving the problem. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.In chapter 4, we take TDTSP based on the point position as a research object, describing the characteristics and the nature of the problem, and establishing the mathematical model. Based on it, we also adopt the dynasearch algorithm based on VLSN search technology to solve the problem. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.In chapter 5, we take TDVRP as a research object, describing the characteristics and the nature of the problem, and developing an approach for dealing with time-varying characteristics which satisfies FIFO property. Based on it, we establish the mathematical model, and give the traditional nearest neighborhood heuristic. For the algorithm, we adopt the dynamic programming heuristics and cyclic transfer algorithm based on VLSN search technology to solve the problem. There are all five solving strategies. Through experiments we compare the performance of different algorithms, and analyze the algorithm performance.In chapter 6, we take the distribution operation of one logistics enterprise in Chengdu as a background, by collecting the actual data and establishing the enterprise distribution model. Through the actual collection data and analysis, we give some reasonable assumptions for distribution. Based on it, we get the optimal distribution routes in various situations, which is also the result of algorithms mentioned in this dissertation. The case provides a good actual background for verifying the algorithms' efficiency. From it, we can make the satisfactory decision for the enterprise.In conclusion, we summarize the dissertation content and prospect the future orientation of the problem.