Locating semi-obnoxious facilities with expropriation: minisum criterion

This paper considers the problem of locating semi-obnoxious facilities assuming that demand points within a certain distance from an open facility are expropriated at a given price. The objective is to locate the facilities so as to minimize the total weighted transportation cost and expropriation cost. Models are developed for both single and multiple facilities. For the case of locating a single facility, finite dominating sets are determined for the problems on a plane and on a network. An efficient algorithm is developed for the problem on a network. For the case of locating multiple facilities, a branch-and-bound procedure using Lagrangian relaxation is proposed and its efficiency is tested with computational experiments.     

Locating flow-intercepting facilities: New approaches and results

The problem of locating flow-intercepting facilities on a network with probabilistic customer flows and with facility set-up costs is studied in this paper. Two types of models are investigated, namely the double-counting model and the no-double-counting model (double-counting refers to multiple interceptions of the same customer). For each model, a nonlinear integer programming formulation is first obtained via the theory of Markov chains, and an equivalent linear integer program is then derived. A simple greedy heuristic is proposed for solving both models and a worst-case bound is established, which is shown to be tight under certain conditions.This work is in part supported by the NSERC grants of O. Berman and D. Krass.     

Locating tree-shaped facilities using the ordered median objective

In this paper we consider the location of a tree-shaped facility S on a tree network, using the ordered median function of the weighted distances to represent the total transportation cost objective. This function unifies and generalizes the most common criteria used in location modeling, e.g., median and center. If there are n demand points at the nodes of the tree T=(V,E), this function is characterized by a sequence of reals, =(₁, . . . ,_n), satisfying ₁₂..._n0. For a given subtree S let X(S)={x₁, . . . ,x_n} be the set of weighted distances of the n demand points from S. The value of the ordered median objective at S is obtained as follows: Sort the n elements in X(S) in nonincreasing order, and then compute the scalar product of the sorted list with the sequence . Two models are discussed. In the tactical model, there is an explicit bound L on the length of the subtree, and the goal is to select a subtree of size L, which minimizes the above transportation cost function. In the strategic model the length of the subtree is variable, and the objective is to minimize the sum of the transportation cost and the length of the subtree. We consider both discrete and continuous versions of the tactical and the strategic models. We note that the discrete tactical problem is NP-hard, and we solve the continuous tactical problem in polynomial time using a Linear Programming (LP) approach. We also prove submodularity properties for the strategic problem. These properties allow us to solve the discrete strategic version in strongly polynomial time. Moreover the continuous version is also solved via LP. For the special case of the k-centrum objective we obtain improved algorithmic results using a Dynamic Programming (DP) algorithm and discretization and nestedness results.Acknowledgement We would like to thank Noga Alon for the current version of the proof of Theorem 4.1, which simplifies our original proof significantly. J. Puerto also thanks the Spanish Ministerio de Ciencia y Tecnología through grant number BFM2001-2378 for partially supporting his research.     

Locating two obnoxious facilities using the weighted maximin criterion

Given are a finite set of points P and a compact polygonal set S in R². The problem is to locate two new facilities in S, maximizing the minimum of all weighted distances between the points in P and the two new facilities, and the distance between the pair of new facilities. We present subquadratic algorithms.     

A robust disaster preparedness model for effective and fair disaster response

Humanitarian network design decisions belonging to the preparedness stage of disaster management life-cycle are of critical importance since they set the frame for all further post-disaster operations. Having an adequate number of strategically located storage and distribution centers for critical supplies is the key that enables effectiveness, efficiency and fairness when responding to a disaster situation. The preparedness model proposed in this study selects locations and inventory levels of these facilities such that the right mix of relief items can be supplied at the right time. Our mixed integer linear model aims to find a robust relief network design that satisfies the demand for all given disaster scenarios, and to help achieve a better response during the response stage when the relief items are distributed. The assumptions and the parameters used in the model are justified by authorities of humanitarian organizations. We propose a logic-based Benders decomposition approach to solve this problem to optimality. Although the problem is NP-hard, our numerical studies demonstrate that it is possible to obtain optimal or very good solutions to problem instances with realistic sizes.     

A longitudinal study of evolving networks in response to natural disaster

In this study, we present a longitudinal analysis of the evolution of interorganizational disaster coordination networks (IoDCNs) in response to natural disasters. There are very few systematic empirical studies which try to quantify the optimal functioning of emerging networks dealing with natural disasters. We suggest that social network analysis is a useful method for exploring this complex phenomenon from both theoretical and methodological perspective aiming to develop a quantitative assessment framework which could aid in developing a better understanding of the optimal functioning of these emerging IoDCN during natural disasters. This analysis highlights the importance of utilizing network metrics to investigate disaster response coordination networks. Results of our investigation suggest that in disasters the rate of communication increases and creates the conditions where organizational structures need to move at that same pace to exchange new information. Our analysis also shows that inter-organizational coordination network structures are not fixed and vary in each period during a disaster depending on the needs. This may serve the basis for developing preparedness among agencies with an improved perspective for gaining effectiveness and efficiency in responding to natural disasters.     

A two-stage stochastic programming framework for transportation planning in disaster response

This study proposes a two-stage stochastic programming model to plan the transportation of vital first-aid commodities to disaster-affected areas during emergency response. A multi-commodity, multi-modal network flow formulation is developed to describe the flow of material over an urban transportation network. Since it is difficult to predict the timing and magnitude of any disaster and its impact on the urban system, resource mobilization is treated in a random manner, and the resource requirements are represented as random variables. Furthermore, uncertainty arising from the vulnerability of the transportation system leads to random arc capacities and supply amounts. Randomness is represented by a finite sample of scenarios for capacity, supply and demand triplet. The two stages are defined with respect to information asymmetry, which discloses uncertainty during the progress of the response. The approach is validated by quantifying the expected value of perfect and stochastic information in problem instances generated out of actual data.     

Emergency response in natural disaster management: Allocation and scheduling of rescue units

Natural disasters, such as earthquakes, tsunamis and hurricanes, cause tremendous harm each year. In order to reduce casualties and economic losses during the response phase, rescue units must be allocated and scheduled efficiently. As this problem is one of the key issues in emergency response and has been addressed only rarely in literature, this paper develops a corresponding decision support model that minimizes the sum of completion times of incidents weighted by their severity. The presented problem is a generalization of the parallel-machine scheduling problem with unrelated machines, non-batch sequence-dependent setup times and a weighted sum of completion times – thus, it is NP-hard. Using literature on scheduling and routing, we propose and computationally compare several heuristics, including a Monte Carlo-based heuristic, the joint application of 8 construction heuristics and 5 improvement heuristics, and GRASP metaheuristics. Our results show that problem instances (with up to 40 incidents and 40 rescue units) can be solved in less than a second, with results being at most 10.9% up to 33.9% higher than optimal values. Compared to current best practice solutions, the overall harm can be reduced by up to 81.8%.     

A dynamic logistics coordination model for evacuation and support in disaster response activities

This paper describes an integrated location-distribution model for coordinating logistics support and evacuation operations in disaster response activities. Logistics planning in emergencies involves dispatching commodities (e.g., medical materials and personnel, specialised rescue equipment and rescue teams, food, etc.) to distribution centres in affected areas and evacuation and transfer of wounded people to emergency units. During the initial response time it is also necessary to set up temporary emergency centers and shelters in affected areas to speed up medical care for less heavily wounded survivors. In risk mitigation studies for natural disasters, possible sites where these units can be situated are specified according to risk based urban structural analysis. Logistics coordination in disasters involves the selection of sites that result in maximum coverage of medical need in affected areas. Another important issue that arises in such emergencies is that medical personnel who are on duty in nearby hospitals have to be re-shuffled to serve both temporary and permanent emergency units. Thus, an optimal medical personnel allocation must be determined among these units. The proposed model also considers this issue.     

An exact branch-and-price algorithm for scheduling rescue units during disaster response

In disaster operations management, a challenging task for rescue organizations occurs when they have to assign and schedule their rescue units to emerging incidents under time pressure in order to reduce the overall resulting harm. Of particular importance in practical scenarios is the need to consider collaboration of rescue units. This task has hardly been addressed in the literature. We contribute to both modeling and solving this problem by (1) conceptualizing the situation as a type of scheduling problem, (2) modeling it as a binary linear minimization problem, (3) suggesting a branch-and-price algorithm, which can serve as both an exact and heuristic solution procedure, and (4) conducting computational experiments – including a sensitivity analysis of the effects of exogenous model parameters on execution times and objective value improvements over a heuristic suggested in the literature – for different practical disaster scenarios. The results of our computational experiments show that most problem instances of practically feasible size can be solved to optimality within ten minutes. Furthermore, even when our algorithm is terminated once the first feasible solution has been found, this solution is in almost all cases competitive to the optimal solution and substantially better than the solution obtained by the best known algorithm from the literature. This performance of our branch-and-price algorithm enables rescue organizations to apply our procedure in practice, even when the time for decision making is limited to a few minutes. By addressing a very general type of scheduling problem, our approach applies to various scheduling situations.     

Locating median cycles in networks

In the median cycle problem the aim is to determine a simple cycle through a subset of vertices of a graph involving two types of costs: a routing cost associated with the cycle itself, and the cost of assigning vertices not on the cycle to visited vertices. The objective is to minimize the routing cost, subject to an upper bound on the total assignment cost. This problem arises in the location of a circular-shaped transportation and telecommunication infrastructure. We present a mixed integer linear model, and strengthen it with the introduction of additional classes of non-trivial valid inequalities. Separation procedures are developed and an exact branch-and-cut algorithm is described. Computational results on instances from the classical TSP library and randomly generated ones confirm the efficiency of the proposed algorithm. An application related to the city of Milan (Italy) is also solved within reasonable computation time.     

Location of terror response facilities: A game between state and terrorist

We study a leader follower game with two players: a terrorist and a state where the later one installs facilities that provide support in case of a terrorist attack. While the Terrorist attacks one of the metropolitan areas to maximize his utility, the State, which acts as a leader, installs the facilities such that the metropolitan area attacked is the one that minimizes her disutility (i.e., minimizes ‘loss’). We solve the problem efficiently for one facility and we formulate it as a mathematical programming problem for a general number of facilities. We demonstrate the problem via a case study of the 20 largest metropolitan areas in the United States.     

Locating Benefit Posts in Brazil

In this paper we report on a case study involving the location of benefit distribution facilities (benefit posts) in Brazil. Significant improvements in the distribution of benefits are anticipated as a result of this study.     

Bipartite Locating Array

As a special case of experimental design,locating array is useful for locating interaction faults in component-based systems.In this paper,bipartite locating array is proposed to locate interaction faults between two specific groups.Such arrays are especially suitable for antagonism tests.Based on the definition of bipartite locating array,the lower bound on run sizes are established to measure the optimality for specific parameters.When a single fault is to be located,optimal bipartite locating arrays are proved to be equivalent to certain specific combinatorial configurations.As a result,approaches to constructing optimal bipartite locating arrays are proposed and some infinite classes of optimal bipartite locating arrays are obtained using the corresponding construction met hod.     

Locating concentrators in centralized computer networks

Topological design of centralized computer communication networks is a complex problem that is generally solved in two phases. The first phase of the design process involves dividing network nodes (terminals or clusters of terminals) into groups, and selecting a concentrator location for each group so that all the nodes in a group are assigned to the same concentrator. The next phase determines topology of links that connect network nodes to concentrators and concentrators to each other and to the central computer. The design problem studied in this paper contains some aspects of both phases. In this problem locations of concentrators, assignments of user nodes to concentrators and the topology of the links connecting concentrators to the central computer are jointly determined. The proposed design method is built around the well known sweep heuristic which is used to partition the node space into sectors. Each of these sectors contain a backbone path connecting concentrators to the central computer.     

Locating and paired-dominating sets in graphs

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199–206]. A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. We consider paired-dominating sets which are also locating sets, that is distinct vertices of G are dominated by distinct subsets of the paired-dominating set. We consider three variations of sets which are paired-dominating and locating sets and investigate their properties.     

Locating least-distant lines in the plane

In this paper we deal with locating a line in a plane. Given a set of existing facilities, represented by points in the plane, our objective is to find a straight line l minimizing the sum of weighted distances to the existing facilities, or minimizing the maximum weighted distance to the existing facilities, respectively. We show that for all distance measures derived from norms, one of the lines minimizing the sum objective contains at least two of the existing facilities. For the center objective we always get an optimal line which is at maximum distance from at least three of the existing facilities. If all weights are equal, there is an optimal line which is parallel to one facet of the convex hull of the existing facilities.     

Using the Viable System Model (VSM) to structure information processing complexity in disaster response

Earthquakes, hurricanes, flooding and terrorist attacks continue to threaten our society and, when the worst happens, lives depend on different agencies to manage the response. The literature shows that there is significant potential for operational research (OR) to aid disaster management and that, whilst some of this potential has been delivered, there is more that OR can contribute. In particular, OR can provide detailed support to analysing the complexity of information processing – an essential topic as failure could cause response agencies to act on low quality information or act too slowly – putting responders and victims at risk. However, there is a gap in methods for analysing information processing whilst delivering rapid response. This paper explores how OR can fill this gap through taking a Viable System Model (VSM) approach to analyse information processing. It contributes to the OR literature by showing how VSM can support the analysis of information processing as well as how the OR modelling technique can be further strengthened to facilitate the task.