A Bilevel p-median model for the planning and protection of critical facilities

The bilevel p-median problem for the planning and protection of critical facilities involves a static Stackelberg game between a system planner (defender) and a potential attacker. The system planner determines firstly where to open p critical service facilities, and secondly which of them to protect with a limited protection budget. Following this twofold action, the attacker decides which facilities to interdict simultaneously, where the maximum number of interdictions is fixed. Partial protection or interdiction of a facility is not possible. Both the defender’s and the attacker’s actions have deterministic outcome; i.e., once protected, a facility becomes completely immune to interdiction, and an attack on an unprotected facility destroys it beyond repair. Moreover, the attacker has perfect information about the location and protection status of facilities; hence he would never attack a protected facility. We formulate a bilevel integer program (BIP) for this problem, in which the defender takes on the leader’s role and the attacker acts as the follower. We propose and compare three different methods to solve the BIP. The first method is an optimal exhaustive search algorithm with exponential time complexity. The second one is a two-phase tabu search heuristic developed to overcome the first method’s impracticality on large-sized problem instances. Finally, the third one is a sequential solution method in which the defender’s location and protection decisions are separated. The efficiency of these three methods is extensively tested on 75 randomly generated instances each with two budget levels. The results show that protection budget plays a significant role in maintaining the service accessibility of critical facilities in the worst-case interdiction scenario.     

A Stackelberg game model for resource allocation in cargo container security

This paper presents a game theoretic model that analyzes resource allocation strategies against an adaptive adversary to secure cargo container transportation. The defender allocates security resources that could interdict an unauthorized weapon insertion inside a container. The attacker observes the defender’s security strategy and chooses a site to insert the weapon. The attacker’s goal is to maximize the probability that the weapon reaches its target. The basic model includes a single container route. The results in the basic model suggest that in equilibrium the defender should maintain an equal level of physical security at each site on the cargo container’s route. Furthermore, the equilibrium levels of resources to interdict the weapon overseas increase as a function of the attacker’s capability to detonate the weapon remotely at a domestic seaport. Investment in domestic seaport security is highly sensitive to the attacker’s remote detonation capability as well. The general model that includes multiple container routes suggests that there is a trade-off between the security of foreign seaports and the physical security of sites including container transfer facilities, container yards, warehouses and truck rest areas. The defender has the flexibility to shift resources between non-intrusive inspections at foreign seaports and physical security of other sites on the container route. The equilibrium is also sensitive to the cost effectiveness of security investments.     

An exact solution approach for the interdiction median problem with fortification

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.     

A constant factor approximation algorithm for the fault-tolerant facility location problem

We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. In this generalization, every demand point j must be served by r_j facilities instead of just one. The facilities other than the closest one are “backup” facilities for that demand, and any such facility will be used only if all closer facilities (or the links to them) fail. Hence, for any demand point, we can assign nonincreasing weights to the routing costs to farther facilities. The cost of assignment for demand j is the weighted linear combination of the assignment costs to its r_j closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. We obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. We further improve the approximation ratio to 3.16 using randomization and to 2.41 using greedy local-search type techniques.     

考虑应急设施中断风险与防御的可靠性选址模型研究

为提高应急设施运行的可靠性和抵御中断风险的能力, 研究中断情境下的应急设施选址-分配决策问题。扩展传统无容量限制的固定费用选址模型, 从抵御设施中断的视角和提高服务质量的视角建立选址布局网络的双目标优化模型, 以应急设施的建立成本和抵御设施中断的加固成本最小为目标, 以最大化覆盖服务质量水平为目标, 在加固预算有限及最大最小容量限制约束下, 构建中断情境下应急设施的可靠性选址决策优化模型。针对所构建模型的特性利用非支配排序多目标遗传算法(NSGA-Ⅱ)求解该模型, 得到多目标的Pareto前沿解集。以不同的算例分析和验证模型和算法的可行性。在获得Pareto前沿的同时对不同中断概率进行灵敏度分析, 给出Pareto最优解集的分布及应急设施选址布局网络的拓扑结构。     

An Iterated Local Search for the Budget Constrained Generalized Maximal Covering Location Problem

Capacitated covering models aim at covering the maximum amount of customers’ demand using a set of capacitated facilities. Based on the assumptions made in such models, there is a unique scenario to open a facility in which each facility has a pre-specified capacity and an operating budget. In this paper, we propose a generalization of the maximal covering location problem, in which facilities have different scenarios for being constructed. Essentially, based on the budget invested to construct a given facility, it can provide different service levels to the surrounded customers. Having a limited budget to open the facilities, the goal is locating a subset of facilities with the optimal opening scenario, in order to maximize the total covered demand and subject to the service level constraint. Integer linear programming formulations are proposed and tested using ILOG CPLEX. An iterated local search algorithm is also developed to solve the introduced problem.     

On the ( r | X p )-Medianoid Problem on a Network with Vertex and Edge Demands

This article considers the (r|X _p )-medianoid problem on a network N=(V,E) with vertex and edge demands. There are already p facilities located on the network and customers patronize the closest facility. The aim is to locate r additional facilities on the network where their captured demands will be maximized. Relationships with the (r|X _p )-medianoid problem with vertex demands are established. Complexity and algorithmic results are presented.     

Incorporating congestion in preventive healthcare facility network design

Preventive healthcare aims at reducing the likelihood and severity of potentially life-threatening illnesses by protection and early detection. The level of participation to preventive healthcare programs is a crucial factor in terms of their effectiveness and efficiency. This paper provides a methodology for designing a network of preventive healthcare facilities so as to maximize participation. The number of facilities to be established and the location of each facility are the main determinants of the configuration of a healthcare facility network. We use the total (travel, waiting and service) time required for receiving the preventive service as a proxy for accessibility of a healthcare facility, and assume that each client would seek the services of the facility with minimum expected total time. At each facility, which we model as an M/M/1 queue so as to capture the level of congestion, the expected number of participants from each population zone decreases with the expected total time. In order to ensure service quality, the facilities cannot be operated unless their level of activity exceeds a minimum workload requirement. The arising mathematical formulation is highly nonlinear, and hence we provide a heuristic solution framework for this problem. Four heuristics are compared in terms of accuracy and computational requirements. The most efficient heuristic is utilized in solving a real life problem that involves the breast cancer screening center network in Montreal. In the context of this case, we found out that centralizing the total system capacity at the locations preferred by clients is a more effective strategy than decentralization by the use of a larger number of smaller facilities. We also show that the proposed methodology can be used in making the investment trade-off between expanding the total system capacity and changing the behavior of potential clients toward preventive healthcare programs by advertisement and education.     

A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

Separation in homogeneous systems with independent identical elements

The paper considers strategic defense and attack of a system which can be separated into independent identical homogeneous parallel elements. The defender distributes its resource between separation of the elements and their protection from outside attacks. The attacker distributes its effort evenly among all attacked elements. The vulnerability of each element is determined by a contest success function between the attacker and the defender. The defender can choose a subset of the elements to defend. The attacker does not know which elements are protected and can choose a number of randomly chosen elements to attack. Separation efficiency conditions are formulated dependent on the defender’s and attacker’s budgets, separation costs, contest intensity, and system demand. An algorithm for determining the optimal number of protected elements is suggested for the case when both the defender and the attacker can choose the number of protected and attacked elements freely. The article considers both the cases without and with performance redundancy. Illustrative numerical examples are presented.     

Designing robust coverage networks to hedge against worst-case facility losses

In order to design a coverage-type service network that is robust to the worst instances of long-term facility loss, we develop a facility location–interdiction model that maximizes a combination of initial coverage by p facilities and the minimum coverage level following the loss of the most critical r facilities. The problem is formulated both as a mixed-integer program and as a bilevel mixed-integer program. To solve the bilevel program optimally, a decomposition algorithm is presented, whereby the original bilevel program is decoupled into an upper level master problem and a lower level subproblem. After sequentially solving these problems, supervalid inequalities can be generated and appended to the upper level master in an attempt to force it away from clearly dominated solutions. Computational results show that when solved to optimality, the bilevel decomposition algorithm is up to several orders of magnitude faster than performing branch and bound on the mixed-integer program.     

Local search algorithm for universal facility location problem with linear penalties

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.     

On the complexity of the (r|p)-centroid problem in the plane

In the (r∣p)-centroid problem, two players, called leader and follower, open facilities to service clients. We assume that clients are identified with their location on the Euclidean plane, and facilities can be opened anywhere in the plane. The leader opens p facilities. Later on, the follower opens r facilities. Each client patronizes the closest facility. In case of ties, the leader’s facility is preferred. The goal is to find p facilities for the leader to maximize his market share. We show that this Stackelberg game is \(\varSigma_{2}^{P}\) -hard. Moreover, we strengthen the previous results for the discrete case and networks. We show that the game is \(\varSigma_{2}^{P}\) -hard even for planar graphs for which the weights of the edges are Euclidean distances between vertices.     

Optimizing pricing and location decisions for competitive service facilities charging uniform price

In this paper, we present the problem of optimizing the location and pricing for a set of new service facilities entering a competitive marketplace. We assume that the new facilities must charge the same (uniform) price and the objective is to optimize the overall profit for the new facilities. Demand for service is assumed to be concentrated at discrete demand points (customer markets); customers in each market patronize the facility providing the highest utility. Customer demand function is assumed to be elastic; the demand is affected by the price, facility attractiveness, and the travel cost for the highest-utility facility. We provide both structural and algorithmic results, as well as some managerial insights for this problem. We show that the optimal price can be selected from a certain finite set of values that can be computed in advance; this fact is used to develop an efficient mathematical programming formulation for our model.     

A note on the allocation of queuing facilities using a minisum criterion

This paper suggests a formulation and a solution procedure for resource allocation problems which consider a central planner, m static queuing facilities providing a homogeneous service at their locations, and a known set of demand points or customers. It is assumed that upon a request for service the customer is routed to a facility by a probabilistic assignment. The objective is to determine how to allocate a limited number of servers to the facilities, and to specify demand rates from customers to facilities in order to minimize a weighted sum of response times. This sum measures the total time lost in the system due to two sources: travel time from customer to facility locations and waiting time for service at the facilities. The setting does not allow for cooperation between the facilities.     

p-Median theorems for competitive locations

In competitive location theory, one wishes to optimally choose the locations ofr facilities to compete againstp existing facilities for providing service (or goods) to the customers who are at given discrete points (or nodes). One normally assumes that: (a) the level of demand of each customer is fixed (i.e. this demand is not a function of how far a customer is from a facility), and (b) the customer always uses the closest available facility. In this paper we study competitive locations when one or both of the above assumptions have been relaxed. In particular, we show that for each case and under certain assumptions, there exists a set of optimal locations which consists entirely of nodes.This work was supported by a National Science Foundation Grant ECS-8121741.     

Probabilistic Formulation of the Emergency Service Location Problem

The problem of locating emergency service facilities is studied under the assumption that the locations of incidents (accidents, fires, or customers) are random variables. The probability distribution for rectilinear travel time between a new facility location and the random location of the incident P _i is developed for the case of P _i being uniformly distributed over a rectangular region. The location problem is considered in a discrete space. A deterministic formulation is obtained and recognized to be a set cover problem. Probabilistic variation of the central facility location problem is also presented.An example and some computational experience are provided to emphasize the impact of the probabilistic formulation on the location decision.     

The design of multiactivity multifacility systems

We consider a service/distribution system in which each of N activities is to be carried out at one or several facility locations. Each activity is to be assigned to one out of a specified set of configurations; each configuration is a specific subset of the set of L facilities being considered, along with a specific strategy for their use. We call such a system a multiactivity multifacility system and present a mathematical formulation for its optimal design that includes capacity restrictions at the facilities and the treatment of multiple criteria. The design problem is simply to choose an appropriate configuration for each of the N activities. We discuss various criteria, and we show that the multiactivity multifacility design problem includes many familiar discrete location problems as special cases. We introduce a 0–1 linear optimization model called the Team Generalized Assignment Problem (T-GAP) and show that parametric solution of a T-GAP will yield all efficient solutions of the multiactivity multifacility design problem with multiple criteria. Rather than attempting to find all efficient solutions, however, we advocate an interactive approach and describe an interactive branch-and-bound algorithm that solves the design problem as a finite sequence of T-GAP's.     

Incorporating the threat of terrorist attacks in the design of public service facility networks

In this paper, we consider the design problem of a public service facility network with existing facilities when there is a threat of possible terrorist attacks. The aim of the system planner, who is responsible for the operation of the network, is to open new facilities, relocate existing ones if necessary, and protect some of the facilities to ensure a maximum coverage of the demand that is assumed to be aggregated at customer zones. By doing so, the system planner anticipates that a number of unprotected facilities will be rendered out-of-service by terrorist attacks. It is assumed that the sum of the fixed cost of opening new facilities, the relocation costs, and the protection costs cannot exceed a predetermined budget level. Adopting the approach of gradual (or partial) coverage, we formulate a bilevel programming model where the system planner is the leader and the attacker is the follower. The objective of the former is the maximization of the total service coverage, whereas the latter wants to minimize it. We propose a heuristic solution procedure based on tabu search where the search space consists of the decisions of the system planner, and the corresponding objective value is computed by optimally solving the attacker??s problem using CPLEX. To assess the quality of the solutions produced by the tabu search (TS) heuristic, we also develop an exhaustive enumeration method, which explores all the possible combinations of opening new facilities, relocating existing ones, and protecting them. Since its time complexity is exponential, it can only be used for relatively small instances. Therefore, to be used as a benchmark method, we also implement a hill climbing procedure employed with the same type of moves as the TS heuristic. Besides, we carry out a sensitivity analysis on some of the problem parameters to investigate their effect on the solution characteristics.