Study Of Model And Heuristic Algorithms For Location Routing Problems

Along with the development of substance needing variety and irregularly all over the world, logistics as"the third profit source"has played a more important role in the economic activity than any time. At present, many developed countries have formed comparatively mature logistics management concepts,advanced logistics techniques and effective logistics operating systems. Entering the 21th century, the Chinese government has made a rapid development in logistics, in order to enhance its international competition ability. Now all the business managers hope to run every link in the logistics system well to satisfy the client's need with the lowest price and best service. So the decision-making of logistics is very important.In the traditional decision-making of logistics model, location allocation problems (LAP) and vehicle routing problem (VRP) are the most concerned problems. But the LAP only considers the locations of facilities (such as factory, Inventory place, sale centers etc.) and the relationship between facilities and goods distributions, ignoring the vehicle's route, which may has a significant effect on the cost. Although the VRP considers the characteristic of vehicle's circuit visit in every client, which may improve the transport efficiency, but it doesn't analyze the locations of facilities, which can makes the cost to drop in logistics systems. Therefore, by the means of systems analysis, this thesis studies the facilities location distribution and the vehicle routing combination optimize problem—location routing problem(LRP)in logistics systems.As the LRP and its extending model belong to NP-hard problem, it is difficult to get the model's optimal solving when nodes amount is so much. Consequently, it is meaningful to systematically get optimal solving of LRP models. Contribution of the research is the innovation in big scale mathematical calculation of NP-hard problem and it is also the academic foundation of developed city logistics distribution systems on account of electronic commerce. The research has extraordinary significance to developed self-action logistics distribution software in large amount of electronic commerce dealings. This thesis bases on the restricted relationship in location choosing, transporting and inventory in logistics systems, in order to promote whole efficiency of logistics systems, from the theory research points of view, to systemically analyze the LRP models optimize problem in complex logistics environment. This thesis studies in a deep going the LRP by bounding the problem, establishing the model, testing the model, getting solving by heuristic algorithm, combination optimize algorithm achieving and analyzing data, in the end, gets the conclusions as:(1)This thesis investigates the LRP math model, and describes the math model of location-distribution problem, vehicle routing problem, location routing problem, inventory location routing problem, and scales the LRP math problem by LINGO software with small scale data, which is the basic model base for the future study of LRP.(2)According to the characteristics of LRP math model, this thesis uses Tabu search algorithm(TS) and Simulated annealing algorithm(SA) to get the optimize value of LRP math model, and programs corresponding algorithm software ,then uses the simulated data to substantiate the validity of the algorithm to LRP model. Meanwhile, it finds out the proper parameters corresponding to LRP model. Compared with relative literature, the thought of this thesis has a more excellent means to LRP model solving.(3)This thesis develops the genetic -simulated annealing algorithm and genetic- tabu search algorithm to get the optimize value on the LRP math model. By programming the account software and testing with some data, the heuristic combined algorithm gets the optimize value of LRP come true. It has an important science role in improved and developed of combined optimize theory research.(4)This thesis analyzes the effect of inventory control strategy on the facilities location and route optimize problems, and establishes more complex Combined Location Routing and Inventory Problems(CLRIP) model, and designs a two-stage heuristic algorithm to get the optimize value. By testing with small scale data, it proves that Combined Location Routing and Inventory Problems model can more effectively reduce the logistics cost than the Location-route problem model ,or the inventory control problem model. Besides the heuristic algorithm provided a basic thoughts for analyze solving process of the LRP model in depth.(5)This thesis provides 8 to 200 nodes testing data source in different scales based on the LRP model, supplies an approach of every algorithm scientific contrasted for the future LRP researchers and does some initiative work for establishing LRP model testing data source.