Joint ground and air emergency medical services coverage models: A greedy heuristic solution approach

Aeromedical and ground ambulance services often team up in responding to trauma crashes, especially when the emergency helicopter is unable to land at the crash scene. We propose location-coverage models and a greedy heuristic for their solution to simultaneously locate ground and air ambulances, and landing zones (transfer points). We provide a coverage definition based on both response time and total service time, and consider three coverage options; only ground emergency medical services (EMS) coverage, only air EMS coverage, or joint coverage of ground and air EMS in which the patient is transferred from an ambulance into an emergency helicopter at a transfer point. To analyze this complex coverage situation we develop two sets of models, which are variations of the Location Set Covering Problem (LSCP) and the Maximal Covering Location Problem (MCLP). These models address uncertainty in spatial distribution of motor vehicle crash locations by providing coverage to a given set of both crash nodes and paths. The models also consider unavailability of ground ambulances by drawing upon concepts from backup coverage models. We illustrate our results on a case study that uses crash data from the state of New Mexico. The case study shows that crash node and path coverage percentage values decrease when ground ambulances are utilized only within their own jurisdiction.     

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.     

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.     

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.     

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.     

An Improved IP Formulation for the Uncapacitated Facility Location Problem: Capitalizing on Objective Function Structure

In this paper we examine the Uncapacitated Facility Location Problem (UFLP) with a special structure of the objective function coefficients. For each customer the set of potential locations can be partitioned into subsets such that the objective function coefficients in each are identical. This structure exists in many applications, including the Maximum Cover Location Problem. For the problems possessing this structure, we develop a new integer programming formulation that has all the desirable properties of the standard formulation, but with substantially smaller dimensionality, leading to significant improvement in computational times. While our formulation applies to any instance of the UFLP, the reduction in dimensionality depends on the degree to which this special structure is present. This work was supported by grants from NSERC.     

An overview on available models and techniques for the multicriteria reliability problem with emphasis on a potential use in a DSS for this problem type

The paper reviews available models and techniques covering three classes of the multi-criteria reliability problem. These classes include allocation of reliabilities in presence of multiple goals, reliability optimization with several kinds of failures and allocation of resources to optimize multiattribute systems. Optimization techniques are also suggested. The models and techniques are also evaluated with respect to their potential use in a DSS for reliability optimization.     

Two-phase method and Lagrangian relaxation to solve the Bi-Objective Set Covering Problem

This paper deals with the Bi-Objective Set Covering Problem, which is a generalization of the well-known Set Covering Problem. The proposed approach is a two-phase heuristic method which has the particularity to be a constructive method using the primal-dual Lagrangian relaxation to solve single objective Set Covering problems. The results show that this algorithm finds several potentially supported and unsupported solutions. A comparison with an exact method (up to a medium size), shows that many Pareto-optimal solutions are retrieved and that the other solutions are well spread and close to the optimal ones. Moreover, the method developed compares favorably with the Pareto Memetic Algorithm proposed by Jaszkiewicz.     

The Single Period Coverage Facility Location Problem: Lagrangean heuristic and column generation approaches

In this paper we introduce the Single Period Coverage Facility Location Problem. It is a multi-period discrete location problem in which each customer is serviced in exactly one period of the planning horizon. The locational decisions are made independently for each period, so that the facilities that are open need not be the same in different time periods. It is also assumed that at each period there is a minimum number of customers that can be assigned to the facilities that are open. The decisions to be made include not only the facilities to open at each time period and the time period in which each customer will be served, but also the allocation of customers to open facilities in their service period.     

Resource allocation in state-dependent emergency evacuation networks

Most of the previous studies on the Emergency Evacuation Problem (EEP) assume that the length and widths of the circulation spaces are fixed. This assumption is only true if one is evaluating facilities that are already built. However, when designing the network for the first time, the size of the circulation space is not known to the designer, in fact it is one of several design parameters. After the routes have been established, it seems that the next logical question is to find out whether or not the system circulation spaces are capable of accommodating the traffic for both normal circulation and in an emergency. The problem of designing emergency evacuation networks is very complex and it is only recently that queueing networks are now being used to model this problem. Recent advances include state-dependent queueing network models that incorporate the mean value analysis algorithm to capture the non-linearities in the problem. We extend these models by incorporating the mean value analysis algorithm within Powell's derivative free unconstrained optimization algorithm. The effect of varying circulation widths on throughput will be discussed and a methodology for solving the resource allocation problem is proposed and demonstrated on several examples. The computational experience of the new methodology illustrates its usefulness in network design problems.     

A Branch-and-Price algorithm for the Single Source Capacitated Plant Location Problem

This paper considers the Single Source Capacitated Plant Location Problem (SSCPLP). We propose an exact algorithm in which a column generation procedure for finding upper and lower bounds is incorporated within a Branch-and-Price framework. The bounding procedure exploits the structure of the problem by means of an iterative approach. At each iteration, a two-level optimization problem is considered. The two levels correspond with the two decisions to be taken: first, the selection of a subset of plants to be opened and then, the allocation of clients within the subset of open plants. The second level subproblem is solved using column generation. The algorithm has been tested with different sets of test problems and the obtained results are satisfactory.     

重大突发事件应急设施多重覆盖选址模型及算法

为了解决应对重大突发事件过程中应急需求的多点同时需求和多次需求问题,本文研究了应对重大突发事件的应急服务设施布局中的覆盖问题:针对重大突发事件应急响应的特点,引入最大临界距离和最小临界距离的概念,在阶梯型覆盖质量水平的基础上,建立了多重数量和质量覆盖模型。模型的优化目标是满足需求点的多次覆盖需求和多需求点同时需求的要求条件下,覆盖的人口期望最大,并用改进的遗传算法进行求解;最后给出的算例证明了模型和算法的有效性,从而应急设施的多重覆盖选址模型能够为有效应对重大突发事件的应急设施选址决策提供参考依据。     

A simple and effective algorithm for the MaxMin diversity problem

The challenge of maximizing the diversity of a collection of points arises in a variety of settings, including the setting of search methods for hard optimization problems. One version of this problem, called the Maximum Diversity Problem (MDP), produces a quadratic binary optimization problem subject to a cardinality constraint, and has been the subject of numerous studies. This study is focused on the Maximum Minimum Diversity Problem (MMDP) but we also introduce a new formulation using MDP as a secondary objective. We propose a fast local search based on separate add and drop operations and on simple tabu mechanisms. Compared to previous local search approaches, the complexity of searching for the best move at each iteration is reduced from quadratic to linear; only certain streamlining calculations might (rarely) require quadratic time per iteration. Furthermore, the strong tabu rules of the drop strategy ensure a powerful diversification capacity. Despite its simplicity, the approach proves superior to most of the more advanced methods from the literature, yielding optimally-proved solutions for many problems in a matter of seconds and even attaining a new lower bound.     

A Lagrangean Heuristic for a Modular Capacitated Location Problem

This paper considers the Modular Capacitated Location Problem (MCLP) which consists of finding the location and capacity of the facilities, to serve a set of customers at a minimum total cost. Each customer has an associated demand and the capacity of each potential location must be chosen from a finite and discrete set of available capacities. Practical applications of this problem can be found in the location of warehouses, schools, health care services or other types of public services. For the MCLP different mixed integer linear programming models are proposed. The authors develop upper and lower bounds on the problem's optimal value and present computational results with randomly generated tests problems.     

A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem

Summary We introduce a generalization of the well-know Uncapacitated Facility Location Problem, in which clients can be served not only by single facilities but also by sets of facilitities. The problem, calledGaneralized Uncapacitated Facility Lacition Problem (GUFLP), was inspired by the Index Selection Problem in physical database design. We for mulate GUFLP as a Set Packing Problem, showing that our model contains all the clique inequalities (in polynomial number). Moreover, we describe and exact separation procedure for odd-hole inequalities, based on the particular structure of the problem. These results are used within a branch-and-cut algorithm for the exact solution of GUFLP. Computational results on two different classes of test problems are given.     

A dynamic programming operator for tour location problems applied to the covering tour problem

This paper presents an evaluation operator for single-trip vehicle routing problems where it is not necessary to visit all the nodes. Such problems are known as Tour Location Problems. The operator, called Selector, is a dynamic programming algorithm that converts a given sequence of nodes into a feasible tour. The operator returns a subsequence of this giant tour which is optimal in terms of length. The procedure is implemented in an adaptive large neighborhood search to solve a specific tour location problem: the Covering Tour Problem. This problem consists in finding a lowest-cost Hamiltonian cycle over a subset of nodes such that nodes outside the tour are within a given distance from a visited node. The metaheuristic proposed is competitive as shown by the quality of results evaluated using the output of a state-of-the-art exact algorithm.     

The return plant location problem: Modelling and resolution

The formulation and analysis of a new plant location problem is presented. The problem studied, herein referred to as the Return Plant Location Problem (RPLP), is that of cost minimization in a system of suppliers and customers in which there exists a return product from each customer. Lagrangian decomposition based heuristic and exact solution methods are given. The methods are applied to test problems with different structures and compared with the classical subgradient optimization approach.     

Linear programs for constraint satisfaction problems

A novel representation is described that models some important NP-hard problems, such as the propositional satisfiability problem (SAT), the Traveling Salesperson Problem (TSP), the Quadratic Assignment Problem (QAP), and the Minimal Set Covering Problem (MSCP) by means of only two types of constraints: ‘choice constraints’ and ‘exclusion constraints’. In its main section the paper presents an approach for solving an m-CNF-SAT problem (Conjunctive Normal Form Satisfaction: n variables, p clauses, clause length m) by integer programming. The approach is unconventional, because 2n distinct 0–1 variables are used for each clause of the m-CNF-SAT problem. The constraint matrix A forces that for every clause exactly one 0–1 variable is set equal to 1 (choice constraint), and no two 0–1 variables, representing a literal and its complement, are both set equal to 1 (exclusion constraints). The particular m-CNF-SAT instance is coded in a cost vector, which serves for maximization of the number of satisfied clauses. The paper presents a modification of the Simplex for solving the obtained integer program. A main theorem of the paper is that this algorithm always finds a 0–1 integer solution. A solution of the integer program corresponds to a solution of the m-CNF-SAT and vice versa. The results of significant experimental tests are reported, and the procedure is compared to other approaches. The same modelling technique is then used for the Traveling Salesperson Problem, for the Minimal Set Covering, and for the Quadratic Assignment Problem: it is shown that a uniform approach is thus useful.