Reliable design of interdependent service facility systems under correlated disruption risks

Facility location;Disruption;Correlation;Station structure;Combinatorial service;Sensor deployment;Districting;Lagrangian relaxation.

Xie, Siyang

关键词: Facility location;    Disruption;    Correlation;    Station structure;    Combinatorial service;    Sensor deployment;    Districting;    Lagrangian relaxation.;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/100922/XIE-DISSERTATION-2018.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Facility location decisions lie at the center of planning many infrastructure systems. In many practice, public agencies (e.g., governments) and private companies (e.g., retailers) need to locate facilities to serve spatially distributed demands. For example, governments locate public facilities, e.g., hospitals, schools, fire stations, to provide public services; retail companies determine the locations of their warehouses and stores to provide business. The design of such facility systems involves considerations of investment of facility construction and transportation cost of serving demands, so as to maximize the system operational efficiency and profit.Recently, devastating infrastructure damages observed in real world show that infrastructure facilities may be subject to disruptions that compromise individual facility functionality as well as overall system performance. This emphasizes the necessity of taking facility disruptions into consideration during planning to balance between system efficiency and reliability. Furthermore, facility systems often exhibit complex interdependence when: (1) facilities are spatially correlated due to physical connections/interrelations, and (2) facilities provide combinatorial service under cooperation, competition and/or restrictions. These further complicate the facility location design. Therefore, facility location models need to be extended to tackle all these challenges and design a reliable interdependent facility system.This dissertation aims at investigating several important and challenging topics in the reliable facility location context, including facility correlations, facility combinations, and facility districting. The main work of this PhD research consist of: (1) establishing a new systematic methodological framework based on supporting stations and quasi-probabilities to describe and decompose facility correlations into succinct mathematical representations, which allows compact mathematical formulations to be developed for planning facility locations under correlated facility disruptions; (2) expanding the modeling framework to allow facilities to provide combinatorial service; e.g., in the context of sensor deployment problems, where sensors work in combinations to provide positioning/surveillance service via trilateration procedure; and (3) incorporating the concepts of spatial districting into the reliable facility location context, with the criteria of spatial contiguity, compactness, and demand balance being ensured.First, in many real-world facility systems, facility disruptions exhibit spatial correlations, which have strong impacts on the system performance, but are difficult to be described with succinct mathematical models. We first investigate facility systems with correlations caused by facilities’ share of network access points (e.g., bridges, railway crossings), which are required to be passed through by customers to visit facilities. We incorporate these network access points and their probabilistic failures into a joint optimization framework. A layer of supporting stations are added to represent the network access points, and are connected to facilities to indicate their real-world relationships. We then develop a compact mixed-integer mathematical model to optimize the facility location and customer assignment decisions. Lagrangian relaxation based algorithms are designed to effectively solve the model. Multiple case studies are constructed to test the model and algorithm, and to demonstrate their performance and applicability.Next, when there exists no real access points, facilities could also be correlated if they are exposed to shared hazards. We develop a virtual station structure framework to decompose these types of facility correlations. First, we define three probabilistic representations of correlated facility disruptions (i.e., with scenario, marginal, and conditional probabilities), derive pairwise transformations between them, and theoretically prove their equivalence. We then provide detailed formulas to transform these probabilistic representations into an equivalent virtual station structure, which enables the decomposition of any correlated facility disruptions into a compact network structure with only independent failures, and helps avoid enumerating an exponential number of disruption scenarios. Based on the augmented system, we propose a compact mixed-integer optimization program, and design several customized solution approaches based on Lagrangian relaxation to efficiently solve the model. We demonstrate our methodology on a series of numerical examples involving different correlation patterns and varying network and parameter settings.We then apply the reliable location modeling framework to sensor deployment problems, where multiple sensors work in combinations to provide combinatorial coverage service to customers via trilateration procedure. Since various sensor combinations may share common sensors, one combination is typically interrelated with some other combinations, which leads to internal correlations among the functionality of sensors and sensor combinations. We address the problem of where to deploy sensors, which sensor combinations are selected to use, and in what sequence and probability to use these combinations in case of disruptions. A compact mixed-integer mathematical model is developed to formulate the problem, by combining and extending the ideas of assigning back-up sensors and correlation decomposition via supporting stations. A customized solution algorithm based on Lagrangian relaxation and branch-and-bound is developed, together with several embedded approximation subroutines for solving subproblems. A series of numerical examples are investigated to illustrate the performance of the proposed methodology and to draw managerial insights.Finally, we develop an innovative reliable network districting framework to incorporate districting concepts into the reliable facility location context. Districting criteria including spatial contiguity, compactness, and demand balance are enforced for location design and extended in considerations of facility disruptions. The problem is modeled into a reliable network districting problem, in the form of a location-assignment based model. We develop customized solution approaches, including heuristics (i.e., constructive heuristic and neighborhood search) and set-cover based algorithms (e.g., district generation, lower bound estimation) to provide near-optimum solution with optimality gap. A series of hypothetical cases and an empirical full-scale application are presented to demonstrate the performance of our methodology for different network and parameter settings.