Arrangements, Based On Dynamic Programming And Genetic Simulated Annealing Algorithm Positioning Line

Location routing problem is an important problem in logistic system. Because of its NP-hard property, it is difficult to get the optimal solution when the point is more. This paper gives the model of the Single Depot Location Routing Problem(SDLRP) and the Mutil-Depot Location Routing Problem(MDLRP) respectively,and tested by lingo program.Based on the complexity of solving the model, two heuristic algorithm is proposed accordingly. A algorithm based on Spacefilling Curves(SFC) and dynamic programming for SDLRP is proposed. First designs a initial solution by SFC,and locates the position of the depot at the same time. Then based on the good initial solution the optimal allocation of vehicle is determined by dynamic programming, further improved by 2-opt procedure. Also a two-phase heuristic approach for solving MDLRP is proposed. First, the candidate facilities and their customers are determined on basis of Simulated Annealing algorithm by using heuristic technique. Second, Genetic- Simulated Annealing algorithm (GA-SA) is used to search the optimal routes. This two-phase heuristic approach integrates facility location and routing problem, which architecture makes it possible to search the solution space easily and effectively without overpass computation. It avoids effectively the defects of premature convergence in traditional genetic algorithm, and enhances the algorithm's global convergence. Also it improves the algorithm's convergence rate to some extent by using the accelerating fitness function. Finally the rapidity and validity of the two algorithms is proved by examples.