Reliable facility location design and traffic sensor deployment under probabilistic disruptions

Many private enterprises and public agencies have faced the problem of locating facilities over spatial dimensions to provide certain service functions. In the supply chain context, we often need to locate a variety of private or public facilities (e.g., manufacturing, assembly plants, schools and hospitals) to serve distributed customers. In the traffic engineering context, various types of surveillance sensors (e.g., induction loops, video cameras and radio frequency transponders) are deployed in transportation networks to estimate real-time traffic states, which are valuable information for both private sectors (e.g., tracking fleets for trucking companies, providing real-time traveler information) and public agencies (e.g., congestion mitigation, accident management). In every case, the operational efficiency and system benefit depend on the choices of facility locations. A good location design can maximize the system benefit while saving as much infrastructure investment as possible. Due to natural disasters or human hazards (e.g., power outages, operational accidents, labor actions or terrorist attacks), facility disruptions are frequently observed in many contexts in the real world. These disruptions often adversely impair the benefit from these facilities. Proper redundancy in the location design is helpful to enhance system reliability and mitigate losses from such disruptions. However, reliable facility location problems are difficult mainly due to the large number of possible failure scenarios. In this Ph.D. research, we will overcome this challenge by developing a range of innovative modeling methods, and then generalize the methodologies to address supply chain design and traffic surveillance sensor location problems. Traditional discrete location models (where customers and candidate facility locations are represented by discrete points) are NP-hard; i.e., they are suitable for small-scale problem instances, but suffer from excessive computational burden when problem size becomes large. To improve computational tractability, continuum approximation models (where customers and facilities are approximated by continuous spatial densities) are developed to approximate problems in a continuous metric space and provide good approximate solutions to large-scale instances. We propose a continuum approximation (CA) model for the reliable uncapacitated fixed charge facility location problem to determine optimal facility locations that minimize the one-time investment for facility constructions and the long-run expected transportation costs for serving spatially distributed customers under correlated facility failures. Complex facility failure mechanisms such as spatial correlation or cascading failure effect are addressed. We identified a few interesting properties of the CA model and developed effective solution algorithms. We have tested this model over different types of numerical examples, and useful managerial insights on how failure correlation impacts the location design are drawn. There are many connections between supply chain facility location problems and sensor location design problems in the traffic surveillance context. For example, in traffic surveillance, we can view traffic surveillance sensors as facilities and traffic OD flow paths as customers being served (or inspected) by these facilities. For a traffic surveillance sensor system, benefits are generated by estimating the real-time traffic states with collected samples at installed sensors, and hence costs come from estimation errors, i.e., the differences between the estimated and the actual traffic states. Based on these connections, this research uses methodologies for supply chain facility location problems to determine surveillance sensor location design in a traffic network. We propose a discrete reliable sensor location model that takes into account the surveillance benefit from not only individual sensor data but also synthesized information from multiple sensors under probabilistic sensor failures. Like many other location design problems, the deterministic version of the sensor location model is already complex; considering an exponential number of possible failure scenarios will further increase the difficulty. Hence we propose efficient customized solution algorithms based on greedy heuristic and Lagrangian relaxation. We compare their performance with that of well-known commercial software (e.g., CPLEX). Numerical examples including a full-scale railroad wayside sensor location design are presented to show that the innovative model significantly improves the state of practice, and the proposed algorithms solve the problem efficiently even when commercial software fails to provide reasonable solutions. We further encapsulated the solution algorithm into a piece of stand-alone software for railroad wayside sensor location design, which has been adopted by the industry. This sensor location model is further extended to generalize surveillance effectiveness measures and accommodate site-dependent failure probabilities. In the extended sensor location design framework, traffic surveillance effectiveness is defined as the reduction of ``generalized estimation errors" on all highway segments between neighboring sensor pairs, such that most existing measures can be expressed as special cases. The problem is first formulated into a compact mixed-integer program, and we develop a variety of solution algorithms (including a custom-designed Lagrangian relaxation algorithm) and analyze their properties. We also propose alternative formulations including a continuum approximation model for single corridor problems and reliable fixed-charge sensor location models. Numerical case studies are conducted to test the performances of the proposed algorithms and draw managerial insights on how different parameter settings (e.g., failure probability and spatial heterogeneity) affect the optimal sensor deployment and the overall surveillance effectiveness