Research On Optimization Method For Large-Scale Dynamic Vehicle Routing Problem

With development of Internet, electronic and information technology, Electronic Commerce (EC), Global Positioning System (GPS), Intelligence Transport System (ITS) and Global System of Mobile (GSM) communication are being applied more broadly. Recently, with these tools in the process of logistics, it is convenient for logistics enterprises to get real-time information of delivery such as on-line customers, traffic conditions, fleet conditions, etc. Since the prior delivery scheme may become suboptimal or even infeasible when new information comes, so how to adjust the vehicle delivery route reasonably according to the real-time dynamic informationhas become a key issue for logistics enterprises to enhance their competitiveness. In addition, logistics enterprises get more small-batches of customer need, and with the gradual strengthening of the cooperation between the logistics enterprises, the number of customers are becoming larger and larger. Therefore, the large-scale dynamic vehicle routing problem (DVRP) comes up in this context.To solve this problem, the algorithm needs to continuously conjoin the real-time information, and to fastly get solution of new vehicle routing plan. However, the current algorithms are mostly designed to solve static vehicle routing problem, which leads the solving quality of the current algorithms to be accurate, but the unsatisfactory speed, therefore. the current algorithms are not effective enough for solving the large-scale dynamic vehicle routing problem.According to characteristics of the large-scale dynamic vehicle routing problem, in this dissertation an optimization method is proposed. Firstly, the dynamic vehicle routing problem is converted into a series of classic static vehicle routing problems; Then an Improved Greedy Algorithm (IMGR) is developed, with both fast solving speed and satisfactory solving quality. IMGR can get an initial satisfactory solution when new real-time information comes along; Finally, a Hybrid Large Neighborhood Algorithm (HLNA) is designed to optimize the solution of the IMGR until another real-time information comes up. The specific research work is as follows:(1) Analysis of the large-scaledynamic vehicle routing problem and ideas of solving the problem. Firstly, it is confirmed what the category this problem belonges to. Through the analysis of large-scale dynamic vehicle routing problem, we find out that after such different types of dynamic events as the emergence of new customers, cancellation of orders. disruption of traffic and vehicle’s breaking down, how to design new delivery plan is equivalent to a static Heterogeneous Fleet Open Vehicle Routing Problem (HFOVRP); Secondly, by making the strategy that take position of the vehicles which are executing delivery task as some dummy customers. HFOVRP can be converted into the classical static VRP.Thus solving the large-scale dynamic vehicle routing problem is equivalent to solving a series of classical static vehicle routing problem as well; Finally, based on the classical vehicle routing problem model, we propose a large-scale dynamic vehicle routing problem model and come up with new ideas of solving the problem.(2) The research on IMGR for solving VRP. Firstly, based on the idea of the greedy algorithm, the rules of greedy algorithm for vehicle routing problem are proposed, and the rules are simple but not good in solution quality and speed. Then two strategies are put forwarded to improve greedy algorithm solution quality and speed based on Held Karp model and K-D Tree method respectively. Hence the greedy algorithm combines the two strategies results in the IMGR. Finally, it is found that the complexity of IMGR is only O(nlogn) according to the algorithm complexity theory. By using IMGR to solve the largest24benchmark instances of VRP in the current world, it is shown that the average solution quality-is less than10%deviating from the theoretical optimal solutions.(3) The design for HLNA based on complex network theory. Firstly, the method using the complex network analysis algorithm to solve the space structure is proposed, and the space structures of several common k-opt algorithm are analyzed, it is indicated the solution space structures of the excellent algorithms are similar to the small-world networks. Then, we develop HLNA according to the theoretical basis of the research results, making the algorithm solution space structure is more similar to the small-world networks, thus to have a better performance of the algorithm. In addition, the data structure of HLNA is designed to reduce the memory requirements and to further improve its execution speed. Finally, we solve some benchmark instances of VRP by using the combination of IMGR and HLNA, and it is demonstrated that the overall performance of this solution method is very competitive comparing with the current classical algorithms.The main contribution of this optimization method is to get the latest implementation of the program by re-optimization from a global perspective after each new distribution information appeares and continue to optimize the current implementation of the program by using HLNA, because of IMGR which we proposed is very fast. Comparing with current methods which adjust the local scheme in order to minimize the disruption, this optimization method provides a new idea for solving large-scale dynamic vehicle routing problem.