Heuristics For The Vehicle Routing Problem With Time Windows And Combinatorial Auction

It is widely believed that logistics,an emerging service industry,has broad development prospect and value-added in the world.It has an important effect on enhancing the efficiency of resource allocation of the entire society effectively,and improving the quality,efficiency and power of the country's economic operation.Transportation service is the lifeblood of the national economy,and transportation is the core among all the dynamic functions of logistics system.The vehicle routing problem is the key in the optimization of transportation service.Since 1959,the rich research achievements in this field have been demonstrated in the international renowned journals and practical use of the industry.This paper focuses on a variant of this problem,Vehicle Routing Problem with Time Windows and Combinatorial Auction(VRPTWCA).Firstly,this paper introduces and summarizes the definition,characteristic and the corresponding mathematical model of the Vehicle Routing Problem(VRP),and elaborates the research results of the Vehicle Routing Problem with Time Windows(VRPTW).On the basis of that,the VRPTWCA is drawn by the practical transportation situation of CNPC.Then it analyzes the similarities and differences between this and the classical VRPTW,defines this problem,and presents VRPTWCA's mathematical model and research status.Afterwards,it focuses on the basic principles and applications of algorithms used in this article,including Adaptive Large Neighborhood Search(ALNS),tabu search algorithm(Tabu Search,TS)and Ejection Pool(EP)algorithm.Then it introduces the research emphasis and difficulties of this paper.For the problem,two algorithms are designed,named ALNS-Embedded TS and EP-Based Reactive TS respectively.During the construction phase,algorithm one selects the initial bids through three selection mechanisms and then obtains the initial solution by classical heuristics,and in the improving phase searches the bid space by TS algorithm,uses the modified Ejection Pool to construct routes for unvisited customers and then searches the route space by ALNS,employing best-accept strategy to output a better solution within the specified number of iterations.However,Algorithm two selects the initial bids by three selection mechanisms and then uses the RVN algorithm to obtain the initial solution,searches the bid space by TS algorithm,and search the route space by Reactive TS.This paper analyzes the principles and operation logic of the above two algorithms in detail in Chapter Four and Five.The above two algorithms were implemented using Java JDK 1.8.Their instances running results are analyzed and compared with each other,and with these of the exact algorithms in the literature.It's found that when it comes to running time,compared with the exact algorithm's 4 hours Algorithm one has a prominent advantage,which doesn't exceed 20 minutes;besides,Algorithm one finds the optimal solution of 45 ones of small scale instances.Although it does slightly decrease with the expansion of the instance size,it still discovers some better solutions superior to the upper bound of the exact algorithm for 23 instances among of them;Finally,the quality of Algorithm two is slightly inferior to Algorithm one,but it has significant reference value for some individual instances.In the end,a dialectical summary and future research directions will be provided.