Research On An Approximation Algorithm For Large-scale Joint Location-inventory Problems

In an era of globalization characterized by fiercer market competition,enterprises face intense pressure to expand and compete on a global scale.Under this background,the need for large-scale supply chain network design and optimization have taken on new importance,with the objective of minimizing the total costs while providing customers with the highest possible level of service.An ideal supply chain design helps optimize across the entire supply chain simultaneously,so that we can balance inventory and warehousing costs against those of location and transportation and create ongoing efficiency improvements in response to customer demands.In view of this,it is necessary to be able to optimize large-scale logistics distribution system design.In this thesis,we study a joint location-inventory model that incorporates the facility level inventory management in the classical uncapacitated facility location problem.It belongs to logistics distribution network design,which consists of an external supplier,a set of potential location candidates,and a set of retailers.To be demand-driven and seize new opportunities for growth,enterprises must be able to determine the optimal number,location,and size of facilities;develop optimal enterprise-wide sourcing strategies;balance location,inventory,and transportation trade-offs;and ascertain the cost and the service level of doing business across the entire supply chain.The purpose of our research is to establish a supply chain network and to reduce the total cost of the system as far as possible while satisfying the specific service level.However,due to the many complicated inherent trade-offs,integrated supply chain network design optimization is computationally very difficult.In the existing literature,this problem is formulated either as a set-covering model,the linear programming relaxation of which is solved by column generation,or as a nonlinear integer programming model that can be solved by lagrangian relaxation.Under the background of global supply chain management,it remains to be a challenge to develop an efficient and effective algorithm to solve large-scale instances of this NP-hard problem.In response to this,in this thesis we present a greedy 1.861-approximation algorithm for the joint location-inventory problem.We show that the complexity of the greedy approximation algorithm is 0(mn2),where m and n denote the number of potential facility locations and the number of retailers,respectively.Extensive computational results demonstrate that the greedy approximation algorithm can solve large-scale joint location-inventory problems efficiently with errors within 8%on average.It also helps the development of managerial insights on large-scale location-inventory network design optimization.