Covering models and optimization techniques for emergency response facility location and planning: a review

With emergencies being, unfortunately, part of our lives, it is crucial to efficiently plan and allocate emergency response facilities that deliver effective and timely relief to people most in need. Emergency Medical Services (EMS) allocation problems deal with locating EMS facilities among potential sites to provide efficient and effective services over a wide area with spatially distributed demands. It is often problematic due to the intrinsic complexity of these problems. This paper reviews covering models and optimization techniques for emergency response facility location and planning in the literature from the past few decades, while emphasizing recent developments. We introduce several typical covering models and their extensions ordered from simple to complex, including Location Set Covering Problem (LSCP), Maximal Covering Location Problem (MCLP), Double Standard Model (DSM), Maximum Expected Covering Location Problem (MEXCLP), and Maximum Availability Location Problem (MALP) models. In addition, recent developments on hypercube queuing models, dynamic allocation models, gradual covering models, and cooperative covering models are also presented in this paper. The corresponding optimization techniques to solve these models, including heuristic algorithms, simulation, and exact methods, are summarized.     

Improving emergency service in rural areas: a bi-objective covering location model for EMS systems

Emergency medical service (EMS) systems are public services that often provide the first line of response to urgent health care needs within a community. Unfortunately, it has been widely documented that large disparities in access to care exist between rural and urban communities. While rural EMS is provided through a variety of resources (e.g. air ambulances, volunteer corps, etc.), in this paper we focus on ground ambulatory care. In particular our goal is to balance the level of first-response ambulatory service provided to patients in urban and rural areas by locating ambulances at appropriate stations. In traditional covering location models the objective is to maximize demand that can be covered; consequently, these models favor locating ambulances in more densely populated areas, resulting in longer response times for patients in more rural areas. To address the issue of fairness in semi-rural/semi-urban communities, we propose three bi-objective covering location models that directly consider fairness via a secondary objective. Results are discussed and compared which provide a menu of alternatives to policy makers.     

Location coverage models with demand originating from nodes and paths: Application to cellular network design

Location covering problems, though well studied in the literature, typically consider only nodal (i.e. point) demand coverage. In contrast, we assume that demand occurs from both nodes and paths. We develop two separate models – one that handles the situation explicitly and one which handles it implicitly. The explicit model is formulated as a Quadratic Maximal Covering Location Problem – a greedy heuristic supported by simulated annealing (SA) that locates facilities in a paired fashion at each stage is developed for its solution. The implicit model focuses on systems with network structure – a heuristic algorithm based on geometrical concepts is developed. A set of computational experiments analyzes the performance of the algorithms, for both models. We show, through a case study for locating cellular base stations in Erie County, New York State, USA, how the model can be used for capturing demand from both stationary cell phone users as well as cell phone users who are in moving vehicles.     

Location–Allocation of Multiple-Server Service Centers with Constrained Queues or Waiting Times

Recently, the authors have formulated new models for the location of congested facilities, so to maximize population covered by service with short queues or waiting time. In this paper, we present an extension of these models, which seeks to cover all population and includes server allocation to the facilities. This new model is intended for the design of service networks, including health and EMS services, banking or distributed ticket-selling services. As opposed to the previous Maximal Covering model, the model presented here is a Set Covering formulation, which locates the least number of facilities and allocates the minimum number of servers (clerks, tellers, machines) to them, so to minimize queuing effects. For a better understanding, a first model is presented, in which the number of servers allocated to each facility is fixed. We then formulate a Location Set Covering model with a variable (optimal) number of servers per service center (or facility). A new heuristic, with good performance on a 55-node network, is developed and tested.     

A Non-linear Multi-criteria Programming Approach for Determining County Emergency Medical Service Ambulance Allocations

In this paper an integer, non-linear mathematical programming model is developed to allocate emergency medical service (EMS) ambulances to sectors within a county in order to meet a government-mandated response-time criterion. However, in addition to the response-time criterion, the model also reflects criteria for budget and work-load, and, since ambulance response is best described within the context of a queueing system, several of the model system constraints are based on queueing formulations adapted to a mathematical programming format. The model is developed and demonstrated within the context of an example of a county encompassing rural, urban and mixed sectors which exhibit different demand and geographic characteristics. The example model is solved using an integer, non-linear goal-programming technique. The solution results provide ambulance allocations to sectors within the county, the probability of an ambulance exceeding a prespecified response time, and the utilization factor for ambulances per sector.     

城市医疗急救绩效分析研究

为了准确评估城市医疗急救(120急救)系统的救援绩效,面向救护车救援调度过程,通过将救护车状态定义为空闲或繁忙建立救护车队的救援状态空间,基于条件概率的乘法规则以及生灭过程平衡方程,构造求解各救护车工作强度(救护车处在繁忙状态的时间占比)的近似线性方程组及其迭代求解算法,由此提出了救护车工作强度近似模型。基于救护车工作强度,给出了救护车跨区救援比例、响应时间等救援绩效计算方法。为了验证上述模型,评价了苏州市区120急救系统的绩效指标,据此改善了救护车救援系统配置方案。研究表明,救护车工作强度近似模型克服了以往救护车数量较多时(大于20辆)难以求解的困难;根据救援距离设置救护车指派优先级能够实现救护车共享、平衡各救护车工作强度以及跨区救援比例;在不增加救护车总数的情况下,基于救援绩效能够改善救护车分布以及急救辖区划分从而有效缩短医疗急救响应时间。     

考虑繁忙率的多时段救护车优化布局研究

救护车布局对院前急救服务中需求的响应具有决定性作用。本文重点研究了考虑繁忙率的多时段救护车优化布局问题,在传统双覆盖模型基础上引入救护车繁忙率因素,提出改进后的双覆盖模型。首先计算考虑繁忙率的期望覆盖需求量,进而结合实际,将一天以早晚高峰划分为5个时段,探究不同时段下繁忙率差异带来的不同布局方案。以上海市松江区2014年数据为例,应用改进后的模型进行了系统深入的实证研究,并绘制繁忙率对需求覆盖率的影响曲线。结果表明,本文提出的布局方案比实际方案得到的期望覆盖需求量提高了3.19%,比传统双覆盖模型得到的期望覆盖需求量提高了0.54%,证明了改进后模型的有效性;需求覆盖率曲线随繁忙率增加而下降,与实际意义相符。该方法能够直观简洁地得出救护车布局方案,利于院前急救服务水平的提升,为社会安全提供有力保障。     

Emergency ambulance deployment in Barbados: a multi-objective approach

A multi-objective version of the Maximum Availability Location Problem is presented in this paper. The assumption of server independence is relaxed by adopting the approach of the Queuing Probabilistic Location Set Covering Problem for calculating the probability that all servers in a given region are busy. The first objective seeks to maximize the population receiving coverage within a given distance standard and with a given level of reliability. The second objective chooses those locations which minimize the cost of covering the population. This model is used to obtain sets of good locations using data obtained from the Barbados Emergency Ambulance Service. The solutions obtained from the optimization model are then subject to a detailed analysis by simulation. The results reveal the potentially good performance of the system, when locations derived from the optimization model are used.     

The Ordered Gradual Covering Location Problem on a Network

In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. The Ordered Median Location problem is a generalization of most of the classical locations problems like p-median or p-center problems. The OGCLP model provides a unifying structure for the standard location models and allows us to develop objectives sensitive to both relative and absolute customer-to-facility distances. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities is already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results.     

Alternate risk measures for emergency medical service system design

The stochastic nature of emergency service requests and the unavailability of emergency vehicles when requested to serve demands are critical issues in constructing valid models representing real life emergency medical service (EMS) systems. We consider an EMS system design problem with stochastic demand and locate the emergency response facilities and vehicles in order to ensure target levels of coverage, which are quantified using risk measures on random unmet demand. The target service levels for each demand site and also for the entire service area are specified. In order to increase the possibility of representing a wider range of risk preferences we develop two types of stochastic optimization models involving alternate risk measures. The first type of the model includes integrated chance constraints (ICCs ), whereas the second type incorporates ICCs  and a stochastic dominance constraint. We develop solution methods for the proposed single-stage stochastic optimization problems and present extensive numerical results demonstrating their computational effectiveness.     

A multi-period double coverage approach for locating the emergency medical service stations in Istanbul

We consider the multi-period location planning problem of emergency medical service (EMS) stations. Our objective is to maximize the total population serviced by two distinct stations within two different response time limits over a multi-period planning horizon. Our aim is to provide a backup station in case no ambulance is available in the closer station and to develop a strategic plan that spans multiple periods. In order to solve this problem, we propose a Tabu Search approach. We demonstrate the effectiveness of the proposed approach on randomly generated data. We also implement our approach to the case of Istanbul to determine the locations of EMS stations in the metropolitan area.     

Scheduling ambulance crews for maximum coverage

This paper addresses the problem of scheduling ambulance crews in order to maximize the coverage throughout a planning horizon. The problem includes the subproblem of locating ambulances to maximize expected coverage with probabilistic response times, for which a tabu search algorithm is developed. The proposed tabu search algorithm is empirically shown to outperform previous approaches for this subproblem. Two integer programming models that use the output of the tabu search algorithm are constructed for the main problem. Computational experiments with real data are conducted. A comparison of the results of the models is presented.     

An optimization approach for ambulance location and the districting of the response segments on highways

In this paper we present a method to optimize the configuration and operation of emergency medical systems on highways. Different from the approaches studied in the previous papers, the present method can support two combined configuration decisions: the location of ambulance bases along the highway and the districting of the response segments. For example, this method can be used to make decisions regarding the optimal location and coverage areas of ambulances in order to minimize mean user response time or remedy an imbalance in ambulance workloads within the system. The approach is based on embedding a well-known spatially distributed queueing model (hypercube model) into a hybrid genetic algorithm to optimize the decisions involved. To illustrate the application of the proposed method, we utilize two case studies on Brazilian highways and validate the findings via a discrete event simulation model.     

Supporting decision making to improve the performance of an Italian Emergency Medical Service

An Emergency Medical Service (EMS) plays a fundamental role in providing good quality health care services to citizens, as it provides the first answer in distressing situations. Early response, one of the key factors in a successful treatment of an injury, is strongly influenced by the performance of ambulances, which are sent to rescue the patient. Here we report the research carried on by the authors on the ambulance location and management in the Milano area (Italy), as a part of a wider research project in collaboration with the EMS of Milano and funded by Regione Lombardia. The question posed by the EMS managers was clear and, at the same time, tricky: could decision making tools be applied, based on the currently available data, to provide suggestions for decision makers? To answer such a question, three different studies have been carried on: first the evaluation of the current EMS system performance through statistical analysis; then the study of operational policies which can improve the system performance through a simulation model; and finally the definition of an alternative set of posts through an optimization model. This paper describes the methodologies underlying such studies and reports on how their main findings were crucial to help the EMS in changing its organization model.     

A Markovian queueing model for ambulance offload delays

Ambulance offload delays are a growing concern for health care providers in many countries. Offload delays occur when ambulance paramedics arriving at a hospital Emergency Department (ED) cannot transfer patient care to staff in the ED immediately. This is typically caused by overcrowding in the ED. Using queueing theory, we model the interface between a regional Emergency Medical Services (EMS) provider and multiple EDs that serve both ambulance and walk-in patients. We introduce Markov chain models for the system and solve for the steady state probability distributions of queue lengths and waiting times using matrix-analytic methods. We develop several algorithms for computing performance measures for the system, particularly the offload delays for ambulance patients. Using these algorithms, we analyze several three-hospital systems and assess the impact of system resources on offload delays. In addition, simulation is used to validate model assumptions.     

A new model for maximal coverage exploiting GIS capabilities

The representation of demand is a key issue which can significantly affect results in several demand covering models. In this paper we concentrate on the well known Maximal Coverage Location Problem and demonstrate that alternative representations of the demand space may lead to largely fluctuating as well as misleading results which seriously overestimate the real coverage achieved by a specified number of servers. We introduce a new model based on the notion of complementary partial coverage and exploit the capabilities of Geographic Information Systems in order to better represent demand. Results of an empirical study indicate that the proposed model is less susceptible to fluctuations for alternative representations of the demand space and that it provides coverage of a larger proportion of demand than traditional models.     

The transfer point location problem

In this paper, we introduce the transfer point location problem. Demand for emergency service is generated at a set of demand points who need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The general model involves the location of p helicopter pads and one facility. In this paper, we solve the special case where the location of the facility is known and the best location of one transfer point that serves a set of demand points is sought. Both minisum and minimax versions of the models are investigated. In follow up papers we investigate the general model using the results obtained in this paper.     

Decision support tools for ambulance dispatch and relocation

In this paper, the development of decision support tools for dynamic ambulance relocation and automatic ambulance dispatching is described. The ambulance dispatch problem is to choose which ambulance to send to a patient. The dynamic ambulance relocation problem occurs in the operational control of ambulances. The objective is to find new locations for some of the ambulances, to increase the preparedness in the area of responsibility. Preparedness is a way of evaluating the ability to serve potential patients with ambulances now and in the future. Computational tests using a simulation model show that the tools are beneficial in reducing the waiting periods for the patients.     

Branch-and-Cut-and-Price for Capacitated Connected Facility Location

We consider a generalization of the Connected Facility Location Problem (ConFL), suitable to model real world network extension scenarios such as fiber-to-the-curb. In addition to choosing a set of facilities and connecting them by a Steiner tree as in ConFL, we aim to maximize the resulting profit by potentially supplying only a subset of all customers. Furthermore, capacity constraints on potential facilities need to be considered. We present two mixed integer programming based approaches which are solved using branch-and-cut and branch-and-cut-and-price, respectively. By studying the corresponding polyhedra we analyze both approaches theoretically and show their advantages over previously presented models. Furthermore, using a computational study we are able to additionally show significant advantages of our models over previously presented ones from a practical point of view.     

Alternative metrics to measure EMS system performance

In the development of strategy for the response to emergent incidents, emergency medical services (EMS) organizations must properly manage their resources while also adhering to response time mandates established by contractual agreements. Performance of an EMS system is typically measured by focusing on the response time of its first responders. However, given that some incidents require the response of multiple emergency vehicles, investigating only the initial response to incidents is inadequate. In this research, we propose two new metrics, in addition to the first response metric, to evaluate the performance of EMS operations: total response time and last responder response time. We develop three mixed integer programming formulations, each one focused on minimizing one of the three metrics, to model the assignment of emergency vehicles to incidents. We also propose a fourth model that combines the metrics via a weighted objective function. This model allows for the simultaneous consideration of the response metrics when evaluating the effectiveness of an emergency response dispatch policy. Experimental results, from comparisons of the models against a greedy dispatch policy, suggest the consideration of multiple response metrics leads to a more robust and effective dispatch policy. Finally, analysis using the models has potential to shape improved strategic and operational policies of EMS organizations. Journal of the Operational Research Society advance online publication, 29 June 2016; doi:10.1057/jors.2016.39