Semi-open Vehicle Routing Problem and Study on Its Tabu Search Algorithm Based on Kernel Route
Shiquan Zhong · Jisuanji fangzhen · 2008
A semi-open vehicle routing problem was proposed. The concept and principium of kernel route were proposed. Based on kernel route,a tabu search algorithm was designed to solve SOVRP. The algorithm was composed of three parts: initial optimization,pick-up and link of kernel routes and final optimization. Based on nature number,the algorithm used three kinds of neighborhoods to extend the search space. The GENI insertion was used to construct the initial solution and the operation of neighborhood. The algorithm used capacity limit to control the number of distribution points in each route. The distance limit was solved by adding penalty function to the object function. The properties of kernel route blocked the building of ill-route. In the second phase of final optimization,kernel routes were disconnected to adjust the optimal route. Many representative results and the analysis were given. The experiment indicates the validity of the algorithm to the SOVRP with the above-mentioned conditions.