Facility Location Problems Considering Facility Disruptions: Models And Algorithms

The facility location problem is a fundamental problem in designing supply network,logistic network,or service network.Properly locating facilities is of great importance for providing products,information or services to customers efficiently and economically.However,in real life,facilities may fail to work from time to time due to various natural or manmade events,which is called as facility disruption.The harm of facility disruption is huge,it interrupts supply or service,increases the cost,causes delay of orders,leads to the losses of customers,to name a lot.In some circumstances,facility disruptions can even compromise the performance of the whole supply network and result in devastating consequences.Facility location decisions are strategic: once a facility network is constructed,it is costly and time consuming to reconfigure and rebuild.To make things worse,recourses are always limited and restoration processes can be very lengthy after a disruption happens.Therefore,decision makers should take the facility disruptions into account when designing a facility network,and should improve its reliability through different kinds of measures.Furthermore,facility location problem is NP-hard.Although as the development of integer programming theory,some commercial optimization software can solve large scale instances for the traditional location problems,they are inefficient when dealing with the new models which considers facility disruptions.When solving these new models,their efficiency deteriorates dramatically and even fails to solve large scale instances.Therefore,it is necessary to develop sophisticated solution algorithms for the new models.To this end,the paper has done the following works:First,it studies a facility location and fortification problem,in which both facility fortifying measures and assignments backup options are used to increase the reliability of a facility network with unreliable facilities.It points out that the existed mathematical model for this problem is only suitable for the uniform case when all facilities have the same failure probability.Then,a new integer programming model is proposed,which can deal with the general case when different facilities have different failure probabilities,thus it can be seen as a generalization of the original model.Based on the new model,structural properties of the problem are analyzed.Finally,computational experiments on some benchmark datasets demonstrate that the optimal solutions of the new model are remarkably better than that of the original model.Since the state-of-the-art mathematical optimization solver CPLEX fails to solve the large scale instance of the facility location and fortification problem,a solution approach combining Lagrangian Relaxation and local search is proposed.The solution algorithm decomposes the original problem into several independent subproblems which can be easily solved,and which is demonstrated to be both effective and efficient based on computational experiments on benchmark datasets.Second,because the capitals and resources for fortifying facilities are always limited,and which are influenced by decision makers' attitude towards to the facility disruption risks.A budget constrained reliable facility location problem with facility fortification is studied,in which the total investment on facility fortification should not exceed the fortification budget.An integer programming model is formulated for this problem,and based on which a fortification model for an existing network is also proposed.To solve the model efficiently,three solution approaches combining Lagrangian relaxation and local search strategies are proposed,which are shown much more efficient than CPLEX for large-sized problems,and they can also produce high-quality solutions for the problems which CPLEX fails to solve.Finally,considering the facts that the capacity of a facility is always limited and single sourcing is popular in real life,a reliable capacitated facility location problem with single source constraints is proposed,and both a mixed integer programming(MIP)model and a stochastic programming model are proposed.The properties of the MIP model are analysed,and based on which a Lagrangian relaxation algorithm is developed.Computational experiments on more than 100 benchmark instances demonstrate that the developed algorithm can produce high quality solutions for all the instances of different sizes.A realistic case study for a 100-city network in Hunan province,China,is presented,based on which the properties of the three models are discussed,sensitivity analysis of critical parameters are conducted and some managerial insights are revealed,which can help the managers make better decisions when designing a resilient facility network.