A Model For Pickup And Delivery Problem With Time Windows And Large Neighborhood Search Algorithm

As a major part of the national economy,logistics industry plays an important role in promoting industrial structure adjustment and enhancing the competitiveness of the national economy.Transportation and distribution takes up the largest proportion among several components of total logistics cost.So the research on the related issues of transportation and distribution has significant value to improve the efficiency of logistics management and reduce the cost of social logistics.Along with the popularity of Internet,new sharing-economy business models such as carpooling platform and freight matching platform begin to rise.But the academic circles paid little attention to the transportation and distribution problem related to these new business model.The traditional vehicle routing problem(VRP)model is not suitable for these more flexible transportation pattern.Therefore,how to develop a highly efficient method to match supply and demand and plan the path for these new participants of logistics industry becomes an urgent problem to be solved.The model of pickup and delivery problem with time window(PDPTW)of this paper is proposed according to the newly emerged carpooling platform and freight matching platform.In order to meet the practical requirements,this paper further extends the traditional PDPTW model.Firstly,the assumption that all vehicles must originate from one location and finally arrive at the same location is relaxed.Secondly,the time windows of the vehicle’s origination and destination are added.Finally,the assumption that all requirements should be met is relaxed.On the other hand,a kind of large neighborhood search algorithm is designed.The algorithm uses parallel insertion method to construct the initial solution,and then improves the quality of the solution by implement a destroy-and-repair process.The annealing algorithm is integrated into the algorithm to prevent falling into local optimization.In the repair step,random allocation is adopted to guarantee the search scope is large enough and a kind of evaluation mechanism is designed to improve the search efficiency.