Sfc Method And Simulated Annealing Algorithm For Solving The Positioning - The Vehicle Routing Problem Research

Using the thought and method of system analysis, the paper researches the location-routing problem (LRP), which integrates the location-allocation problem and the vehicle routing problem. Firstly we describe the location-allocation problem (LAP) and the vehicle routing problem (VRP). And the mathematics model of the LAP and the VRP are introduced. Though comparing the LAP, the VRP and the LRP, a mathematics model of the multi-depot location-routing problem (MDLRP) which is closed to the actual constraints is set up. It is difficult to solve in large scale because the LRP is a typical NP-hard problem in combinatorial optimization. Comparing the other concerned algorithm, we find that the simulated annealing algorithm has two characters: the strong ability of overall search range and quickly convergent speed. Then we propose the heuristic algorithm based on spacefilling curves (SFC) and the simulated annealing algorithm. By deeply analyzing the temperature controlling parameters, the temperature dropping method, the stopping criterion of with-in circle and the stopping criterion of the algorithm, we propose a two-phase heuristic approach of the multi-depot location-routing problem based on the simulated annealing algorithm. In first phase it includes initial solution construction and improvement of iterative solution. The spacefilling curves are chosen as the solution method. In solution improvement two types of neighborhood moves are performed, namely, the DC Exchange and the Customer Reassignment. The DC Exchange uses the 2-swap method. The Customer Reassignment applies the insert and 2-swap methods. In second phase the solution improvement includes "between-routes" and "within-route" methods. The insert and 2-swap method are selected for the between-routes improvement. And the 2-opt method is used in within-route improvement. The paper analyses and composes the flowchart of simulated annealing algorithm for the MDLRP in detail. And it achieves the program on computer. Finally the simulated test denotes that the algorithm can solves the MDLRP efficient and quickly. Comparing the other concerned algorithm, the simulated annealing algorithm has practicability and effectiveness. Simultaneously the article provides an effectively heuristics algorithm to solve the vehicle routing problem in large scale.