Facility Location and Relocation Problem: Models and Decomposition Algorithms



Journal Title

Journal ISSN

Volume Title



We consider the facility location and relocation problem (FLRP). Due to demand change in this problem, we may need to close some existing facilities from low demand areas and open new ones in newly emerging areas. Specifically, we discuss three optimization problems in FLRP. The first problem is to locate a certain number of facilities at a point in time, knowing that demand is subject to change and the total number of facilities may increase in the future. We develop a binary integer programming (BIP) model to find a set of initial and future facility locations. Utilizing the block-angular structure of the model, a decomposition algorithm is proposed to solve the problem. The second problem is the robust facility relocation problem. Suppose we already have a set of facilities and the demand distribution over the network has changed, however, we do not know the actual changes of demand. Therefore, different scenarios with known probabilities are used to capture such demand changes. We present two approaches to solve this problem. In the first approach, we develop a BIP model that can determine α-reliable relocations that minimize the maximum regret associated with a set of scenarios whose cumulative probability is at least α. In the second approach, we develop a BIP model that minimizes the expected weighted distance and ensures that relative regret for each scenario is no more than γ. We propose a Lagrangean decomposition algorithm to solve this problem. The third problem, which is the dynamic facility location and relocation problem, is designed to find locations for facilities in the aftermath of disasters such as hurricanes and earthquakes, where the population is in need of essential commodities due to the lack of infrastructure. We develop three MIP models, each having different objectives, and propose a heuristic algorithm to solve this problem. Numerical experiments are made to show the efficiency and complexity of our optimization models.



Facility location, Facility relocation, Uncertainty, Decomposition algorithms, Disaster response