Study On Combinatorial Optimization Heuristics Algorithm And Model Building Of Multi-depot Location Routing Problem With Pickups And Deliveries

The optimization and design of the logistics system prividing for related company's logistics optimization solving scheme and consulting is always a main research field for the logistics researcher. MDLRPPD (Multi-depot Location Routing Problem with Pickups and Deliveries)to be studied in this paper is one branch of the logistics system optimization, and also a main research direction of logistics system optimization and a problem that a big logistics distribution company must be faced with and wants to solve. In this paper, the complementary restraint relationship between depot selection, transports, pickups and deliveries is analyzed, and from the point of the lowest total cost, it establishes the mathematical model and develop the combinatorial optimization algorithm of MDLRPPD.This paper establishes the mathematical model of MDLRPPD based on the model of LRP and the verification of correctness of mathematical model established through the application of LINGO software under the condition of small-scale data is conducted. Because of its NP-hard property, the paper puts forwards the taboo-simulated annealing combinatorial optimization algorithm to solve MDLRPPD. At first, this paper gets initial answer of MDLAP randomly under the condition of capacity restriction. Then it uses the taboo search algorithm to optimize MDLAP then gets the results as VRPPD's input. In the process of solving VRPPD, the paper arrages the selected clients in order based on the demands of the clients. When meeting with a client, if service truck can equip the client's goods after unloading the cargo, the client goes into the route. Then it circles like this until all the clients goes into the route. The results are VRPPD's initial answer. Then it uses the simulated annealing algorithm to optimize VRPPD with insert methods, routes interchange, route interchange and 2-opt then gets the results. it makes the results returning to the MDLAP producing the near answers of optimization of the MDLAP as the input of VRPPD adopting insert methods, clients interchang between the plots and plot interchang. It circles between MDLAP and VRPPD under certain terms until gets the result as the optimization solve of MDLRPPD. This paper applies C++ language programming to realize this combinatorial optimization algorithm. To the same small scales data, this paper applies the mentioned combinatorial optimization algorithm and Lingo to it respectively and the cost, facilities and routings are exactly the same. Based on this, the paper applies the method to middle and large scale data. The results shows that it is effective and efficient to use the taboo-simulated annealing combinatorial optimization algorithm to solve MDLRPPD within an acceptable time. When applying the methods to different scale cases, it discovers that alternation time, beginning temperature, droping temperature coefficient, taboo length and neighbour solving is bigger when the scale of the problem is larger, and the competing time of computer sharply increases, but the algorithm's stability and astringency restraining is unchange.