Research On Algorithm Of Large-scale VRP Based On Sector-scanning

At present there are many shortages in the research of VRP, with the purpose of overcoming the shortages existing in current research, the paper study on the large-scale VRP.The paper first set up model on some premises and assumptions, then in the condition of considering the model and the characteristics of the large-scale VRP, the paper put forward a two-phase algorithm: a heuristic algorithm based on sector-scanning. There are two steps using this algorithm to solve VRP: in the first step, dividing the whole customers into multi-groups with the grouping algorithm based on sector-scanning; in the second step, a kind of Ant Colony algorithm with the traits of crossover and mutation is adopted to arrange the visiting order of customers in each dispatched route. This heuristic algorithm has some innovations as follow:1)At the phase of dividing customers into multi-groups, it uses the dynamically scanning manner to decide search region. Applying this method to VRP not only attain the objective of reducing the scale of customers but also acquire the same results as using the whole region algorithm.2) At the phase of arrange the visiting order of customers in each dispatched route, the Ant Colony algorithm with the traits of crossover and mutation merge the advanced of Genetic algorithm and Ant Colony algorithm. The crossover operator introduced the Order Insert Crossover operator. With this crossover strategy, the best genes can be inherited to next generation, and this can speed up the algorithms to search the best result.In order to verify the feasibility and validity of the proposed algorithm, a large number of simulation experiments have been carried on. In the simulation of well-known benchmark of TSP, the good results are just 0.81% inferior to the best known solution, in the simulation of well-known benchmark of VRP, the good results are just 2.98% inferior to the best known solution. In the simulation of tobacco delivering VRP with 5933 customers is successfully solved in just 14 minutes with good results. All these simulation results verify the algorithm is feasible and effective.