A Two-Stage Large and Variable Neighbourhood Search Approach for the Vehicle Routing Problem with Time Windows
Vehicle routing is very important in logistics. This paper presents a two-stage hybrid algorithm for the vehicle routing problem with time windows. The algorithm first minimizes the number of vehicles and then minimizes the travel distance by using large neighbourhood search followed by variable neighbourhood search. For the vehicle number minimization, a new lexicographic evaluation function is proposed to guide the search in a direction that reduces the number of vehicles. The large neighbourhood search is implemented by relocating a number of customers where the optimal relocation points are determined by solving a generalized assignment problem. For the variable neighbourhood search, some diversification strategies are proposed to generate a starting point for the neighbourhood to be explored next. Numerical results on the application of our algorithm to the Solomon’s benchmark problems show that the performance of our algorithm is competitive with those of other algorithms reported in the literature.
Vehicle routing large neighbourhood search variable neighbourhood search transportation logistics
Haoxun CHEN
Institute Charles Delaunay (ICD,FRE CNRS 2848) Industrial systems optimization laboratory,LOSI University of Technology of Troyes 12 rue Marie Curie,BP 2060,Troyes,10010,France
国际会议
北京
英文
2007-05-30（万方平台首次上网日期，不代表论文的发表时间）