Starita, S. and Scaparra, M. (2020). Assessing road network vulnerability: a User Equilibrium interdiction model. Journal of the Operational Research Society [Online]. Available at: https://doi.org/10.1080/01605682.2020.1740621.
Road networks are vulnerable to natural and man-made disruptions. The loss of one or many critical links of the network often leads to increased traffic congestion. Therefore, quantitative models are necessary to identify these critical assets so that actions can be taken by decision makers to mitigate the impact of disruptions. This paper proposes an optimisation model to identify the set of arcs that, when lost, results in the worst congestion under user equilibrium traffic. The model is formulated as a bi-level non-linear problem. The challenging formulation is solved via a customised version of Greedy Randomised Adaptive Search Procedure (GRASP) meta-heuristic. Computational experiments are run on a dataset of artificial grids and managerial insights are provided based on popular Sioux and Berlin network case-studies.
Preston, G., Horne, P., Scaparra, M. and O’Hanley, J. (2020). Masterplanning at the Port of Dover: The Use of Discrete-Event Simulation in Managing Road Traffic. Sustainability [Online] 12:1067. Available at: http://dx.doi.org/10.3390/su12031067.
The Port of Dover is Europe’s busiest ferry port, handling £119 billion or 17% of the UK’s annual trade in goods. The Port is constrained geographically to a small area and faces multiple challenges, both short- and long-term, with managing the flow of five million vehicles per year to/from mainland Europe. This article describes some of the work that the Port is doing to minimize the impact of port road traffic on the local community and environment using discrete-event simulation modeling. Modeling is particularly valuable in identifying where future bottlenecks are likely to form within the Port due to projected growth in freight traffic and comparing the effectiveness of different interventions to cope with growth. One of our key findings is that space which can be used flexibly is far more valuable than dedicated space. This is supported by the much greater reduction in traffic congestion that is expected to be achieved given a 10% increase in freight traffic by reallocating space at the front of the system to temporarily hold vehicles waiting to pass through border control and check-in compared to extending the amount of space for ferry embarkation at the rear of the system. The importance of flexible space has implications for port design that can be applied more broadly. Modeling is also useful in identifying critical thresholds for vehicle processing times that would cause the system to become overwhelmed. Increasing the check-in time by just three to five minutes, for example, would completely exceed the Port’s capacity and produce indefinite queueing. This finding has important implications for Brexit planning. From a wider context, the research presented here nicely illustrates how simulation can be used to instill more evidence-based thinking into port masterplanning and support “green port” and other corporate sustainability initiatives.
Jones, W., Kotiadis, K., Scaparra, M. and O’Hanley, J. (2020). Using Simulation to Improve the Customer Experience at Eurostar. Impact [Online] 2020:7-11. Available at: https://doi.org/10.1080/2058802X.2019.1703346.
Esposito Amideo, A., Scaparra, M. and Kotiadis, K. (2019). Optimising shelter location and evacuation routing operations: The critical issues. European Journal of Operational Research [Online] 279:279-295. Available at: https://dx.doi.org/10.1016/j.ejor.2018.12.009.
Shelter opening and evacuation of vulnerable populations are operations crucial to disaster response, which is one of the four phases of Disaster Operations Management (DOM). Optimisation has tried to capture some of the different issues related to shelter location and evacuation routing: several models have been developed over the years. However, they are still far from being fully comprehensive. The aim of this paper is to identify the current challenges in devising realistic and applicable optimisation models in the shelter location and evacuation routing context, with the ultimate goal of outlining a roadmap for future research in this topical area. A critical analysis of the most recent combined models is provided, including insights from the authors of the existing papers. The analysis highlights numerous gaps and research opportunities, such as the need for future optimisation models to involve stakeholders, include evacuee as well as system behaviour, be application-oriented rather than theoretical or model-driven, and interdisciplinary.
Esposito Amideo, A., Starita, S. and Scaparra, M. (2019). Assessing Protection Strategies for Urban Rail Transit Systems: A Case-Study on the Central London Underground. Sustainability [Online] 11. Available at: https://www.mdpi.com/2071-1050/11/22/6322/htm.
Urban rail transit systems are highly prone to disruptions of various nature (e.g., accidental,
environmental, man-made). Railway networks are deemed as critical infrastructures given that a
service interruption can prompt adverse consequences on entire communities and lead to potential
far-reaching effects. Hence, the identification of optimal strategies to mitigate the negative impact of
disruptive events is paramount to increase railway systems’ resilience. In this paper, we investigate
several protection strategies deriving from the application of either single asset vulnerability metrics
or systemic optimization models. The contribution of this paper is threefold. Firstly, a single asset
metric combining connectivity, path length and flow is defined, namely the Weighted Node Importance
Evaluation Index (WI). Secondly, a novel bi-level multi-criteria optimisation model, called the Railway
Fortification Problem (RFP), is introduced. RFP identifies protection strategies based on stations
connectivity, path length, or travel demand, considered as either individual or combined objectives.
Finally, two different protection strategy approaches are applied to a Central London Underground
case study: a sequential approach based on single-asset metrics and an integrated approach based on
RFP. Results indicate that the integrated approach outperforms the sequential approach and identifies
more robust protection plans with respect to different vulnerability criteria.
Scaparra, M., Ngo, C., Dang, T. and Tran, T. (2019). Community perceptions of social, economic and environmental impacts of flooding in central districts of Hanoi, Vietnam. Journal of the British Academy [Online] 7:137-154. Available at: http://dx.doi.org/10.5871/jba/007s2.137.
The impacts of flooding on road infrastructure in Hanoi are highly disruptive, despite recent progress by the Vietnamese authorities in improving the city’s drainage systems. The GCRF–OSIRIS Project aims to optimise investment strategies to minimise the impacts of flood disasters, making disaster risk reduction more effective, by introducing operational research methods. In support of this objective, the project carried out an impact assessment in four of the city’s central districts. The assessment considered locally perceived social, economic and environmental impacts on residents, local entrepreneurs, and on visiting street vendors and transport service providers. Impacts of flooding were found to be highly gender-differentiated. When roads are flooded, women—both resident and visiting—face greater conflicts between the need to maintain their incomes and the responsibilities of caring for vulnerable family members, resulting in increased stress and increasing risks to their health. The assessment suggests that such disproportionate impacts on women could be mitigated through public education and pre-emptive planning measures.
Preston, C., Horne, P., O’Hanley, J. and Scaparra, M. (2018). Traffic Modelling at the Port of Dover. Impact [Online] 2018:7-11. Available at: https://doi.org/10.1080/2058802X.2018.1452422.
The port of Dover has undergone many reincarnations over the centuries: from a fortified port complete with lighthouse in the first century AD, to a military Cinque Port in the middle ages, to the ferry and hovercraft terminal of the late twentieth century. Dover’s principal role now is as a Roll-on, Roll-off (Ro-Ro) Ferry Terminal, in which 2 ferry companies (P&O and DFDS) between them make up to 60 round trips a day to the French Ports of Calais and Dunkerque. They carry over 2.6 million lorries, 2 million cars, and 12 million people a year. The economic value in goods handled through the Port is up to 17% of the UK’s overall trade in goods. Based on 2016 projections, freight traffic is expected to increase by up to 40% in the next 30 years. However, the Dover Eastern Docks Ferry Terminal is small, around half a square kilometre, and expansion is challenging since it is hemmed in by the sea, the White Cliffs of Dover, and Dover town.
Starita, S. and Scaparra, M. (2018). Passenger railway network protection: A model with variable post-disruption demand service. Journal of the Operational Research Society [Online] 69:603-618. Available at: http://dx.doi.org/10.1057/s41274-017-0255-y.
Protecting transportation infrastructures is critical to avoid loss of life and to guard against economic upheaval. This paper addresses the problem of identifying optimal protection plans for passenger rail transportation networks, given a limited budget. We propose a bi-level protection model which extends and refines the model previously introduced by Scaparra et al, (Railway infrastructure security, Springer, New York, 2015). In our extension, we still measure the impact of rail disruptions in terms of the amount of unserved passenger demand. However, our model captures the post-disruption user behaviour in a more accurate way by assuming that passenger demand for rail services after disruptions varies with the extent of the travel delays. To solve this complex bi-level model, we develop a simulated annealing algorithm. The efficiency of the heuristic is tested on a set of randomly generated instances and compared with the one of a more standard exact decomposition algorithm. To illustrate how the modelling approach might be used in practice to inform protection planning decisions, we present a case study based on the London Underground. The case study also highlights the importance of capturing flow demand adjustments in response to increased travel time in a mathematical model.
Starita, S., Scaparra, M. and O’Hanley, J. (2017). A dynamic model for road protection against flooding. Journal of the Operational Research Society [Online] 68:74-88. Available at: http://dx.doi.org/10.1057/s41274-016-0019-0.
This paper focuses on the problem of identifying optimal protection strategies to reduce the impact of flooding on a road network. We propose a dynamic mixed-integer programming model that extends the classic concept of road network protection by shifting away from single-arc fortifications to a more general and realistic approach involving protection plans that cover multiple components. We also consider multiple disruption scenarios of varying magnitude. To efficiently solve large problem instances, we introduce a customised GRASP heuristic. Finally, we provide some analysis and insights from a case study of the Hertfordshire road network in the East of England. Results show that optimal protection strategies mainly involve safeguarding against flooding events that are small and likely to occur, whereas implementing higher protection standards are not considered cost-effective.
Tran, T., Scaparra, M. and O’Hanley, J. (2017). A Hypergraph Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem. European Journal of Operational Research [Online] 263:173-187. Available at: http://dx.doi.org/10.1016/j.ejor.2017.04.032.
In this paper, we introduce a large-scale neighborhood search procedure for solving the single-source capacitated facility location problem (SSCFLP). The neighborhood structures are induced by innovative split multi-customer multi-exchanges, where clusters of customers assigned to one facility can be moved simultaneously to multiple destination facilities and vice versa. To represent these exchanges, we use two types of improvement hypergraphs. The improvement hypergraphs are built dynamically and the moving customers associated with each hyperedge are selected by solving heuristically a suitably defined mixed-integer program. We develop a hypergraph search framework, including forward and backward procedures, to identify improving solutions efficiently. Our proposed algorithm can obtain improving moves more quickly and even find better solutions than a traditional multi-exchange heuristic (Ahuja et al., 2004). In addition, when compared with the Kernel Search algorithm (Guastaroba and Speranza, 2014), which at present is the most effective for solving SSCFLP, our algorithm is not only competitive but can find better solutions or even the best known solution to some very large scale benchmark instances from the literature.
Tran, T., O’Hanley, J. and Scaparra, M. (2016). Reliable hub network design: Formulation and solution techniques. Transportation Science [Online] 51:358-375. Available at: http://dx.doi.org/10.1287/trsc.2016.0679.
In this paper, we investigate the issue of unreliability in hub location planning. A mixed integer nonlinear programming model is formulated for optimally locating p uncapacitated hubs, each of which can fail with a site-specific probability. The objective is to determine the location of hubs and the assignment of demand nodes to hubs in order to minimize expected demand weighted travel cost plus a penalty if all hubs fail. A linear version of the model is developed employing a specialized flow network called a probability lattice to evaluate compound probability terms. A Tabu search algorithm is proposed to find optimal to near optimal solutions for large problem instances. A parallel computing strategy is integrated into the Tabu search process to improve performance. Experimental results carried out on several benchmark instances show the efficiency of our linearized model and heuristic algorithm. Compared to a standard hub median model that disregards the potential for hub failures, our model produces solutions that serve larger numbers of customers and at lower cost per customer.
Starita, S. and Scaparra, M. (2016). Optimizing dynamic investment decisions for railway systems protection. European Journal of Operational Research [Online] 248:543-557. Available at: http://www.dx.doi.org/10.1016/j.ejor.2015.07.025.
Past and recent events have shown that railway infrastructure systems are particularly vulnerable to natural catastrophes, unintentional accidents and terrorist attacks. Protection investments are instrumental in reducing economic losses and preserving public safety. A systematic approach to plan security investments is paramount to guarantee that limited protection resources are utilized in the most efficient manner. In this article, we present an optimization model to identify the railway assets which should be protected to minimize the impact of worst case disruptions on passenger flows. We consider a dynamic investment problem where protection resources become available over a planning horizon. The problem is formulated as a bilevel mixed-integer model and solved using two different decomposition approaches. Random instances of different sizes are generated to compare the solution algorithms. The model is then tested on the Kent railway network to demonstrate how the results can be used to support efficient protection decisions.
Gama, M., Santos, B. and Scaparra, M. (2015). A multi-period shelter location-allocation model with evacuation orders for flood disasters. EURO Journal on Computational Optimization [Online] 4:299-323. Available at: https://doi.org/10.1007/s13675-015-0058-3.
Floods are a significant threat for several countries, endangering the safety and the well-being of populations. Civil protection authorities are in charge of flood emergency evacuation, providing means to help the evacuation and ensuring that people have comfortable and safe places to stay. This work presents a multi-period location-allocation approach that identifies where and when to open a predefined number of shelters, when to send evacuation orders, and how to assign evacuees to shelters over time. The objective is to minimize the overall network distances that evacuees have to travel to reach the shelters. The multi-period optimization model takes into account that the travel times vary over time depending on the road conditions. People’s reaction to the flood evolution is also considered to be dynamic. We also assume that shelters become available in different time periods and have a limited capacity. We present a mathematical formulation for this model which can be solved using an off-the-shelf commercial optimization solver, but only for small instances. For real size problems, given the dynamic characteristics of the problem, obtaining an optimal solution can take several hours of computing time. Thus, a simulated annealing heuristic is proposed. The efficiency of the heuristic is demonstrated with a comparison between the heuristic and the solver solutions for a set of random problems. The applicability of the multi-period model and of the heuristic is illustrated using a case study which highlights the importance and the benefits of adopting a dynamic approach for optimizing emergency response operations.
Irawan, C., Salhi, S. and Scaparra, M. (2014). An adaptive multiphase approach for large unconditional and conditional p-median problems. European Journal of Operational Research [Online] 237:590-605. Available at: http://dx.doi.org/10.1016/j.ejor.2014.01.050.
A multiphase approach that incorporates demand points aggregation, Variable Neighbourhood Search (VNS) and an exact method is proposed for the solution of large-scale unconditional and conditional p-median problems. The method consists of four phases. In the first phase several aggregated problems are solved with a "Local Search with Shaking" procedure to generate promising facility sites which are then used to solve a reduced problem in Phase 2 using VNS or an exact method. The new solution is then fed into an iterative learning process which tackles the aggregated problem (Phase 3). Phase 4 is a post optimisation phase applied to the original (disaggregated) problem. For the p-median problem, the method is tested on three types of datasets which consist of up to 89,600 demand points. The first two datasets are the BIRCH and the TSP datasets whereas the third is our newly geometrically constructed dataset that has guaranteed optimal solutions. The computational experiments show that the proposed approach produces very competitive results. The proposed approach is also adapted to cater for the conditional p-median problem with interesting results.
Scaparra, M., Church, R. and Medrano, F. (2014). Corridor location: the multi-gateway shortest path model. Journal of Geographical Systems [Online] 16:287-309. Available at: http://dx.doi.org/10.1007%2Fs10109-014-0197-8.
The problem of corridor location can be found in a number of fields including power transmission, highways, and pipelines. It involves the placement of a corridor or rights-of-way that traverses a landscape starting at an origin and ending at a destination. Since most systems are subject to environmental review, it is important to generate competitive, but different alternatives. This paper addresses the problem of generating efficient, spatially different alternatives to the corridor location problem. We discuss the weaknesses in current models and propose a new approach which is designed to overcome many of these problems. We present an application of this model to a real landscape and compare the results to past work. Overall, the new model called the multi-gateway shortest path problem can generate a wide variety of efficient alignments, which eclipse what could be generated by past work.
Liberatore, F., Vitoriano, B., Ortuno, M., Tirado, G. and Scaparra, M. (2014). A hierarchical compromise model for the joint optimization of recovery operations and distribution of emergency goods in humanitarian logistics. Computers and Operations Research [Online] 42:3-13. Available at: http://dx.doi.org/10.1016/j.cor.2012.03.019.
The distribution of emergency goods to a population affected by a disaster is one of the most fundamental operations in Humanitarian Logistics. In the case of a particularly disruptive event, parts of the distribution infrastructure (e.g., bridges, roads) can be damaged. This damage would make it impossible and/or unsafe for the vehicles to reach all the centers of demand (e.g., towns and villages). In this paper, we propose and solve the problem of planning for recovery of damaged elements of the distribution network, so that the consequent distribution planning would benefit the most. We apply the model, called RecHADS, to a case study based on the 2010 Haiti earthquake. We also show empirically the importance of coordinating recovery and distribution operations optimization.
O’Hanley, J., Scaparra, M. and García-Quiles, S. (2013). Probability chains: A general linearization technique for modeling reliability in facility location and related problems. European Journal of Operational Research [Online] 230:63-75. Available at: http://dx.doi.org/10.1016/j.ejor.2013.03.021.
In this paper, we propose an efficient technique for linearizing facility location problems with site-dependent failure probabilities, focusing on the unreliable p-median problem. Our approach is based on the use of a specialized flow network, which we refer to as a probability chain, to evaluate compound probability terms. The resulting linear model is compact in size. The method can be employed in a straightforward way to linearize similarly structured problems, such as the maximum expected covering problem. We further discuss how probability chains can be extended to problems with co-location and other, more general problem classes. Additional lower bounds as well as valid inequalities for use within a branch and cut algorithm are introduced to significantly speed up overall solution time. Computational results are presented for several test problems showing the efficiency of our linear model in comparison to existing
Losada, C., Scaparra, M., Church, R. and Daskin, M. (2012). The stochastic interdiction median problem with disruption intensity levels. Annals of Operations Research [Online] 201:345-365. Available at: http://dx.doi.org/10.1007/s10479-012-1170-x.
In this paper we introduce a stochastic interdiction problem for median systems in which the operational state of the system's disrupted elements in the aftermath of the disruption is uncertain as it is based on the intensity of the disruption. We assume that a disruption disables a facility with a given probability and this probability depends on the intensity of the disruption. The objective of this problem is to identify which disruption scenario entails a maximum overall traveling distance in serving all customers. We show that the initial two stage stochastic formulation can be reformulated into a deterministic counterpart whose
size is polynomial in the number of facilities and intensity levels. Then, our ensuing efforts to solve the problem e±ciently focus on studying alternative deterministic formulations that allow the solution of realistic size instances of the model. We observe that the most efficient of the deterministic formulations provide great scalability with respect to variations in the input parameters and size of the instances solved. Finally, we analyze the robustness of the optimal solutions due to misestimations in the probability functions that relate disruption intensity levels with the probabilities of facility survivability.
Scaparra, M. and Church, R. (2012). Protecting supply systems to mitigate potential disaster: a model to fortify capacitated facilities. International Regional Science Review [Online] 35:188-210. Available at: http://dx.doi.org/10.1177/0160017611435357.
Planning to mitigate the impacts of a disaster can be an important activity for both private companies and public agencies. In this article, the authors consider a supply system that provides needed goods or services to a region that may be the subject of some type of disaster, such as an attack by a terrorist or the result of a natural event or accident. The supply system is represented by a set of existing capacitated facilities. The authors assume that the loss of one or more facilities to a disaster will tighten available supply and increase the distances over which the service or good must be delivered, thereby increasing operation costs and reducing service. Such a disaster may even reduce the capacity of the supply/storage to the extent that the goods must be rationed as remaining supply may be outstripped by demand. The authors consider the case where resources may be available to mitigate some of the impacts of a possible disaster by the advanced protection of one or more facilities. The authors show how this problem can be formulated as a “tri-level” optimization model and propose a solution approach based on a tree search strategy. The authors demonstrate the policy implications of this model using a hypothetical planning problem. Through this example, the authors show how the results of our model can be used to inform planners and policy makers in disaster mitigation planning.
Losada, C., Scaparra, M. and O’Hanley, J. (2012). Optimizing system resilience: A facility protection model with recovery time. European Journal of Operational Research [Online] 217:519-530. Available at: http://dx.doi.org/10.1016/j.ejor.2011.09.044.
Optimizing system resilience is concerned with the development of strategies to restore a system to normal operations as quickly and efficiently as possible following potential disruption. To this end, we present in this article a bilevel mixed integer linear program for protecting an uncapacitated median type facility network against worst-case losses, taking into account the role of facility recovery time on system performance and the possibility of multiple disruptions over time. The model differs from previous types of facility protection models in that protection is not necessarily assumed to prevent facility failure altogether, but more precisely to speed up recovery time following a potential disruption. Three different decomposition approaches are devised to optimally solve medium to large problem instances. Computational results provide a cross comparison of the efficiency of each algorithm. Additionally, we present an analysis to estimate cost-efficient levels of investments in protection resources.
Mingers, J., Watson, K. and Scaparra, M. (2012). Estimating Business And Management Journal Quality From The 2008 Research Assessment Exercise In The UK. Information Processing and Management [Online] 48:1078-1093. Available at: http://dx.doi.org/10.1016/j.ipm.2012.01.008.
The 2008 Research Assessment Exercise in the UK involved the peer review of over 12,500 research outputs in Business and Management, of which 92% were journal articles. Each output was graded on a 4-point scale from "world leading" to "national" with a fifth point being unclassified. These grades were accumulated for each department to provide an overall quality profile in terms of the proportions of its outputs in each category. The assessments of individual papers were not made public but the papers submitted by each department were. This data provides a major opportunity for addressing issues of concern about the evaluation of research and the effects of journal rankings, as well as the possibility of reconstructing the judgements made by the Panel about journal quality. Given the submission details and the resulting grade profile for each department, we have used linear programming to produce the best estimate of the grades awarded to papers from each journal that had more than three entries. This provides both a grade profile for each journal and a single quality estimate. The results are shown to have good validity in comparison with other journal rankings. Apart from providing a ranking of 700 journals based on the RAE results, the paper is also able to shed light on issues such as the accuracy and coverage of the ABS ranking: the degree of selectivity of submissions; the dispersion of grades for a journal; and differences between different subject areas.
Liberatore, F., Scaparra, M. and Daskin, M. (2012). Hedging against disruptions with ripple effects in location analysis. Omega [Online] 40:21-30. Available at: http://dx.doi.org/10.1016/j.omega.2011.03.003.
Supply systems are subject to disruptions whose impact may not remain confined, but might actually propagate across the network. We consider the problem of optimally protecting a capacitated median system with a limited amount of protective resources subject to disruptions. Specifically, the type of disruption studied is characterized by correlation effects between the facilities, and may result in partial or complete disruption of the facilities involved. The model optimizes protection plans in the face of large area disruptions; i.e., disruptions that affect regions rather than single elements of the system. Examples may be earthquakes, storms, floods, fires, hurricanes, droughts, the spread of diseases, the spread of chemical agents, and cascading failures. The model is also a general framework for the family of fortification problems in the context of locationanalysis, as it includes uncapacitated facilities and single-target disruptions as special cases. We provide a tri-level formulation of the problem, and we propose an exact solution algorithm which makes use of a tree-search procedure to identify which facilities to protect. The procedure is enhanced by a dual-based pruning rule. The underlying disruption problem is reformulated as a single-level mixed-integer program. The algorithm has been tested on a dataset based on the 2009 L’Aquila earthquake. We verify empirically the efficiency of the pruning rule, and we provide an evaluation of the importance of considering propagation effects in the disruptions.
Cappanera, P. and Scaparra, M. (2011). Optimal allocation of protective resources in shortest path networks. Transportation Science [Online] 45:64-80. Available at: http://dx.doi.org/10.1287/trsc.1100.0340.
This article introduces a game theoretic approach for allocating protection resources among the components of a network so as to maximize its robustness to external disruptions. Specifically, we consider shortest-path networks where disruptions may result in traffic flow delays through the affected components or in the complete loss of some elements. A multi-level program is proposed to identify the set of components to harden so as to minimize the length of the shortest path between a supply node and a demand node
after a worst-case disruption of some unprotected components. An implicit enumeration algorithm is then developed to solve the multi-level problem to optimality. The approach is streamlined by solving the lower level interdiction problem heuristically at each node of an enumeration tree and by using some variable fixing rules to reduce the dimension of the lower level problems. A thorough computational investigation demonstrates that the proposed solution method is able to identify optimal protection strategies for networks of significant size. The paper is concluded with a study of the sensitivity of the solution
approach to variations of the problem parameters, such as the level of disruption and protective resources, and the distribution of the arc lengths and delays.
Liberatore, F., Scaparra, M. and Daskin, M. (2011). Analysis of facility protection strategies against an uncertain number of attacks: The Stochastic R-Interdiction Median Problem with Fortification. Computers and Operations Research [Online] 38:357-366. Available at: https://doi.org/10.1016/j.cor.2010.06.002.
We present the Stochastic R-Interdiction Median Problem with Fortification (S-RIMF). This model optimally allocates defensive resources among facilities to minimize the worst-case impact of an intentional disruption. Since the extent of terrorist attacks and malicious actions is uncertain, the problem deals with a random number of possible losses. A max-covering type formulation for the S-RIMF is developed. Since the problem size grows very rapidly with the problem inputs, we propose pre-processing techniques based on the computation of valid lower and upper bounds to expedite the solution of instances of realistic size. We also present heuristic approaches based on heuristic concentration-type rules. The heuristics are able to find an optimal solution for almost all the problem instances considered. Extensive computational testing shows that both the optimal algorithm and the heuristics are very successful at solving the problem. Finally, a discussion of the importance of recognizing the stochastic nature of the number of possible attacks is provided.
Liberatore, F. and Scaparra, M. (2011). Optimizing protection strategies for supply chains: Comparing classic decision making criteria in an uncertain environment. Annals of the Association of American Geographers 101:1-17.
Losada, C., Scaparra, M. and Church, R. (2010). On a bi-level formulation to protect uncapacitated p-median systems with facility recovery time and frequent disruptions. Electronic Notes in Discrete Mathematics [Online] 36:591-598. Available at: http://dx.doi.org/doi:10.1016/j.endm.2010.05.075.
We consider an uncapacitated p-median system that is subject to external manmade or natural disruptions and formulate the problem of protecting against the worst-case losses when taking into account facility recovery issues. The model is a mixed integer bi-level problem with integer variables controlled by both the upper and lower level. To solve it, we apply two exact decomposition methods: a decomposition algorithm based on a special type of valid inequalities and Benders decomposition coupled with variable reduction and some heuristic rules to speed up the resolution of the master problems. Although we compare the performance of the two decomposition approaches, for brevity, we only show here the Benders decomposition.
Scaparra, M. and Church, R. (2008). An exact solution approach for the interdiction median problem with fortification. European Journal of Operational Research [Online] 189:76-92. Available at: http://dx.doi.org/10.1016/j.ejor.2007.05.027.
Systematic approaches to security investment decisions are crucial for improved homeland security. We present an optimization modeling approach for allocating protection resources among a system of facilities so that the disruptive effects of possible intentional attacks to the system are minimized. This paper is based upon the p-median service protocol for an operating set of p facilities. The primary objective is to identify the subset of q facilities which, when fortified, provides the best protection against the worst-case loss of r non-fortified facilities. This problem, known as the r-interdiction median problem with fortification (IMF), was first formulated as a mixed-integer program by Church and Scaparra [R.L. Church, M.P. Scaparra, Protecting critical assets: The r-interdiction median problem with fortification, Geographical Analysis 39 (2007) 129-146]. In this paper, we reformulate the IMF as a maximal covering problem with precedence constraints, which is amenable to a new solution approach. This new approach produces good approximations to the best fortification strategies. Furthermore, it provides upper and lower bounds that can be used to reduce the size of the original model. The reduced model can readily be solved to optimality by general-purpose MIP solvers. Computational results on two geographical data sets with different structural characteristics show the effectiveness of the proposed methodology for solving IMF instances of considerable size.
Scaparra, M. and Church, R. (2008). A bilevel mixed-integer program for critical infrastructure protection planning. Computers and Operations Research [Online] 35:1905-1923. Available at: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6VC5-4M69JVY-1&_user=125871&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000010239&_version=1&_urlVersion=0&_userid=125871&md5=7db18bde82875a10a5876ee535486a0b.
Vulnerability to sudden service disruptions due to deliberate sabotage and terrorist attacks is one of the major threats of today. In this paper, we present a bilevel formulation of the r-interdiction median problem with fortification (RIMF). RIMF identifies the most cost-effective way of allocating protective resources among the facilities of an existing but vulnerable system so that the impact of the most disruptive attack to r unprotected facilities is minimized. The model is based upon the classical p-median location model and assumes that the efficiency of the system is measured in terms of accessibility or service provision costs. In the bilevel formulation, the top level problem involves the decisions about which facilities to fortify in order to minimize the worst-case efficiency reduction due to the loss of unprotected facilities. Worst-case scenario losses are modeled in the lower-level interdiction problem. We solve the bilevel problem through an implicit enumeration (1E) algorithm, which relies on the efficient solution of the lower-level interdiction problem. Extensive computational results are reported, including comparisons with earlier results obtained by a single-level approach to the problem.
Oliva, G., Esposito Amideo, A., Starita, S., Setola, R. and Scaparra, M. (2019). Aggregating Centrality Rankings: A Novel Approach to Detect Critical Infrastructure Vulnerabilities. In: Critical Information Infrastructures Security. CRITIS 2019. Lectures Notes in Computer Science. Cham, Switzerland: Springer, pp. 57-68. Available at: https://dx.doi.org/10.1007/978-3-030-37670-3_5.
Assessing critical infrastructure vulnerabilities is paramount to arrange efficient plans for their protection. Critical infrastructures are network-based systems hence, they are composed of nodes and edges. The literature shows that node criticality, which is the focus of this paper, can be addressed from different metric-based perspectives (e.g., degree, maximal flow, shortest path). However, each metric provides a specific insight while neglecting others. This paper attempts to overcome this pitfall through a methodology based on ranking aggregation. Specifically, we consider several numerical topological descriptors of the nodes’ importance (e.g., degree, betweenness, closeness, etc.) and we convert such descriptors into ratio matrices; then, we extend the Analytic Hierarchy Process problem to the case of multiple ratio matrices and we resort to a Logarithmic Least Squares formulation to identify an aggregated metric that represents a good tradeoff among the different topological descriptors. The procedure is validated considering the Central London Tube network as a case study.
Starita, S., Esposito Amideo, A. and Scaparra, M. (2018). Assessing Urban Rail Transit Systems Vulnerability: Metrics vs. Interdiction Models. In: D’Agostino, G. ed. Critical Information Infrastructures Security. Springer. Available at: https://doi.org/10.1007/978-3-319-99843-5_13.
Urban rail transit systems are highly vulnerable to a variety of disruptions, including accidental failures, natural disasters and terrorist attacks. Due to the crucial role that railway infrastructures play in economic development, productivity and social well-being of communities, evaluating their vulnerability and identifying their most critical components is of paramount importance. Two main approaches can be deployed to assess transport infrastructure vulnerabilities: vulnerability metrics and interdiction models. In this paper, we compare these two approaches and apply them to the Central London Tube to identify the most critical stations with respect to accessibility, efficiency and flow measures.
Esposito Amideo, A. and Scaparra, M. (2017). A Synthesis of Optimization Approaches for Tackling Critical Information Infrastructure Survivability. In: Havarneanu, G., Setola, R., Nassopoulos, H. and Wolthusen, S. eds. Critical Information Infrastructures Security. Springer, pp. 75-87. Available at: https://doi.org/10.1007/978-3-319-71368-7_7.
Over the years, Critical Infrastructures (CI) have revealed themselves to be extremely disaster-prone, be the disasters nature-based or man-made. This paper focuses on a specific category of CI: Critical Information Infrastructures (CII), which are commonly deemed to include communication and information net-works. The majority of all the other CI (e.g. electricity, fuel and water supply, transport systems, etc.) are crucially dependent on CII. Therefore, problems associated with CII that disrupt the services they are able to provide (whether to a single end-user or to another CI) are of increasing interest. This paper discusses some recent developments in optimization models regarding CII’s ability to with-stand disruptive events within three main spheres: network survivability assessment, network resource allocation strategy and survivable design.
Faramondi, L., Oliva, G., Setola, R., Pascucci, F., Esposito Amideo, A. and Scaparra, M. (2017). Performance Analysis of Single and Multi-objective Approaches for the Critical Node Detection Problem. In: Sforza, A. and Sterle, C. eds. Optimization and Decision Science: Methodologies and Applications. Springer, pp. 315-324. Available at: https://doi.org/10.1007/978-3-319-67308-0_32.
Critical infrastructures are network-based systems which are prone to various types of threats (e.g., terroristic or cyber-attacks). Therefore, it is paramount to devise modelling frameworks to assess their ability to withstand external disruptions and to develop protection strategies aimed at improving their robustness and security. In this paper, we compare six modelling approaches for identifying the most critical nodes in infrastructure networks. Three are well-established approaches in the literature, while three are recently proposed frameworks. All the approaches take the perspective of an attacker whose ultimate goal is to inflict maximum damage to a network with minimal effort. Specifically, they assume that a saboteur must decide which nodes to disable so as to disrupt network connectivity as much as possible. The formulations differ in terms of the attacker objectives and connectivity metrics (e.g., trade-off between inflicted damage and attack cost, pair-wise connectivity, size and number of disconnected partitions). We apply the six formulations to the IEEE24 and IEEE118 Power Systems and conduct a comparative analysis of the solutions obtained with different parameters settings. Finally, we use frequency analysis to determine the most critical nodes with respect to different attack strategies.
Esposito Amideo, A. and Scaparra, M. (2017). A Scenario Planning Approach for Shelter Location and Evacuation Routing. In: Sforza, A. and Sterle, C. eds. Optimization and Decision Science: Methodologies and Applications. Springer, pp. 567-576. Available at: https://doi.org/10.1007/978-3-319-67308-0_32.
Emergency planning operations are one of the key aspects of Disaster Operations Management (DOM) . This work presents a scenario-based location-allocation-routing model to optimise evacuation planning decisions, including where to establish shelter sites and which routes to arrange to reach them, across different network disruption scenarios. The model considers both supported-evacuation and self-evacuation. The objective is to minimise the duration of the supported-evacuation while guaranteeing that the routes of self-evacuees do not exceed a given travelling time threshold. Both shelter location and routing decisions are optimised so as to identify solutions which perform well across different disruption scenarios. A mathematical formulation of this model is provided, which can be solved through a general-purpose solver optimisation package for modest size instances. Some computational results are reported.
Scaparra, M. and Church, R. (2015). Location Problems under Disaster Events. In: Saldanha-da-Gama, F., Nickel, S. and Laporte, G. eds. Location Science. Springer, pp. 623-642.
Facility systems may be vulnerable to a disaster, whether caused by intention, an accident, or by an act of nature. When disrupting events do occur, services may be degraded or even destroyed. This chapter addresses problems of disruption associated with facility based service systems. Three main questions often arise when dealing with a possible disaster: 1) how bad can it get? 2) is there a way in which we can protect our system from such an outcome? and 3) is there a way in which we can incorporate such issues in our future designs and plans? This chapter addresses each of these main questions with respect to several classic location problems. Specifically, it discusses recent location models under disaster events along three main streams of research: facility interdiction, facility protection, and resilient design.
Scaparra, M., Starita, S. and Sterle, C. (2015). Optimizing investment decisions for railway systems protection. In: Setola, R., Sforza, A., Vittorini, V. and Pragliola, C. eds. Railway Infrastructure Security. Springer, pp. 215-233.
As demonstrated by recent events, railway systems are often the target of terrorist bombings and attacks. To preserve public safety and essential economic functions, railroad networks should be made as secure and resilient as possible. However, railway protection investments may involve significant and often unaffordable capital expenditure. Given the limited resources available for protection efforts, it is essential that a strategic approach to the planning of security investments is adopted. This chapter presents a mathematical model for identifying the optimal allocation of protective resources among the components of a railway network. The aim is to minimize the impact on passenger flow of worst-case disruptions which might affect both railway stations and tracks. The proposed model is tested on an Italian railroad network to demonstrate how the model results can be used to inform policy making and protection investment decisions.