Social Optimal Location of Facilities with Fixed Servers,Stochastic Demand,and Congestion

We consider two capacity choice scenarios for the optimal location of facilities with fixed servers, stochastic demand, and congestion. Motivating applications include virtual call centers, consisting of geographically dispersed centers, walk‐in health clinics, motor vehicle inspection stations, automobile emissions testing stations, and internal service systems. The choice of locations for such facilities influences both the travel cost and waiting times of users. In contrast to most previous research, we explicitly embed both customer travel/connection and delay costs in the objective function and solve the location–allocation problem and choose facility capacities simultaneously. The choice of capacity for a facility that is viewed as a queueing system with Poisson arrivals and exponential service times could mean choosing a service rate for the servers (Scenario 1) or choosing the number of servers (Scenario 2). We express the optimal service rate in closed form in Scenario 1 and the (asymptotically) optimal number of servers in closed form in Scenario 2. This allows us to eliminate both the number of servers and the service rates from the optimization problems, leading to tractable mixed‐integer nonlinear programs. Our computational results show that both problems can be solved efficiently using a Lagrangian relaxation optimization procedure.     

On multi-criteria chance-constrained capacitated single-source discrete facility location problems

This work aims at investigating multi-criteria modeling frameworks for discrete stochastic facility location problems with single sourcing. We assume that demand is stochastic and also that a service level is imposed. This situation is modeled using a set of probabilistic constraints. We also consider a minimum throughput at the facilities to justify opening them. We investigate two paradigms in terms of multi-criteria optimization: vectorial optimization and goal programming. Additionally, we discuss the joint use of objective functions that are relevant in the context of some humanitarian logistics problems. We apply the general modeling frameworks proposed to the so-called stochastic shelter site location problem. This is a problem emerging in the context of preventive disaster management. We test the models proposed using two real benchmark data sets. The results show that considering uncertainty and multiple objectives in the type of facility location problems investigated leads to solutions that may better support decision making.     

废弃物回收的多层逆向物流网络优化设计问题研究

废弃物逆向物流网络设计问题是一个关系到经济效益和社会效益的问题.本文研究了废弃物逆向物流网络设计问题,包括选择中转站和处理站的地址,确定将产生点的废弃物分配给中转站以及从中转站运送到处理站的最佳策略,确定处理站的容量.考虑了在满足公众的意愿的情况下,建立了一个多目标的纯整数规划模型,最小化总的建设费用和设施对公众产生的负效用.设计了基于启发式的两阶段分解算法求解,从而构建一个废弃物回收的多层逆向物流网络.最后的算例仿真表明了算法的有效性和可行性.     

Temporary Hubs for the Global Vehicle Supply Chain in Humanitarian Operations

We model the global vehicle supply chain of an International Humanitarian Organization (IHO) with a dynamic hub location model across monthly periods. We use actual vehicle data from the International Federation of the Red Cross to feed our model and provide insights into IHO secondary support demand. We find that secondary support demand for items such as vehicles is different from primary beneficiary demand for items such as water and food. When considering disaster response and development program demand simultaneously (disaster cycle management), our results illustrate that keeping a lean centralized hub configuration with an option for temporary hubs in mega disaster locations can reduce overall supply chain costs over a long time horizon. We also show that it is possible to structure a supply chain to take operational advantage of earmarked funding. This research lays the groundwork for using optimization models to analyze disaster cycle management.     

基于双层规划的反恐应急设施选址模型及算法

恐怖袭击常以人流密集地区的平民作为袭击目标，并存在突发性和随机性等特点，极易造成严重的袭击后果。通过反恐应急设施的合理布局可以缩短救援人员和物资的到达时间，从而减轻袭击后果。首先，对反恐应急设施选址问题进行描述，并将其构造为一类离散双层规划模型。其中，上层规划是关于政府选址的0-1规划问题，下层规划则是关于恐怖分子袭击目标选择的0-1规划问题。其次，结合模型和问题的特征设计算法，利用分支定界算法实现上层选址变量的隐枚举，同时通过下层问题的求解来确定上下界并判断是否满足分枝或剪枝的条件。最后，结合南疆地区的交通拓扑网络进行算例分析，结果证明有效的选址方案可以大大降低袭击损失。     

On the Complex Quantification of Risk: Systems‐Based Perspective on Terrorism

This article highlights the complexity of the quantification of the multidimensional risk function, develops five systems‐based premises on quantifying the risk of terrorism to a threatened system, and advocates the quantification of vulnerability and resilience through the states of the system. The five premises are: (i) There exists interdependence between a specific threat to a system by terrorist networks and the states of the targeted system, as represented through the system's vulnerability, resilience, and criticality‐impact. (ii) A specific threat, its probability, its timing, the states of the targeted system, and the probability of consequences can be interdependent. (iii) The two questions in the risk assessment process: “What is the likelihood?” and “What are the consequences?” can be interdependent. (iv) Risk management policy options can reduce both the likelihood of a threat to a targeted system and the associated likelihood of consequences by changing the states (including both vulnerability and resilience) of the system. (v) The quantification of risk to a vulnerable system from a specific threat must be built on a systemic and repeatable modeling process, by recognizing that the states of the system constitute an essential step to construct quantitative metrics of the consequences based on intelligence gathering, expert evidence, and other qualitative information. The fact that the states of all systems are functions of time (among other variables) makes the time frame pivotal in each component of the process of risk assessment, management, and communication. Thus, risk to a system, caused by an initiating event (e.g., a threat) is a multidimensional function of the specific threat, its probability and time frame, the states of the system (representing vulnerability and resilience), and the probabilistic multidimensional consequences.     

On tie breaking in competitive location under binary customer behavior

Ties in customer facility choice may occur when the customer selects the facility with maximum utility to be served. In the location literature ties in maximum utility are broken by assigning a fixed proportion of the customer demand to the facilities with maximum utility which are owned by the entering firm. This tie breaking rule does not take into account the number of tied facilities of both the entering firm and its competitors. In this paper we introduce a more realistic tie breaking rule which assigns a variable proportion of customer demand to the entering firm depending on the number of tied facilities. We present a general framework in which optimal locations for the old and the new tie breaking rules can be obtained through Integer Linear Programming formulations of the corresponding location models. The optimal locations are obtained for the old tie breaking rule for different values of the fixed proportion and a comparison with the results obtained for the new tie breaking rule is drawn with data of Spanish municipalities in a variety of scenarios. Finally, some conclusions are presented.     

Location and reliability problems on a line: Impact of objectives and correlated failures on optimal location patterns

In this paper we study a class of locations models where facilities are not perfectly reliable and failures may be correlated. We analyze problems with Median and Center objectives under complete and incomplete customer information regarding the state of facilities. The goal is to understand how failure probabilities, correlations, availability of information, and problem objective affect the optimal location patterns. In particular, we want to find analytical confirmations for location patterns observed in numerical experiments with network location models. To derive closed-form analytical results the analysis is restricted to a simple (yet classic) setting: a 2-facility problem on a unit segment, with customer demand distributed uniformly over the segment (results can be extended to other demand distributions as well). We derive explicit expressions for facility trajectories as functions of model parameters, obtaining a number of managerial insights. In addition we provide the decomposition of the optimal cost into the closed form components corresponding to the cost of travel, the cost of facility unreliability and the cost of incomplete information. Most of the theoretical insights are confirmed via numerical experiments for models with larger (3–5) number of facilities.     

The facility location problem with Bernoulli demands

This paper presents the facility location problem with Bernoulli demands. In this capacitated discrete location stochastic problem the goal is to define an a priori solution for the locations of the facilities and for the allocation of customers to the operating facilities that minimizes the sum of the fixed costs of the open facilities plus the expected value of the recourse function. The problem is formulated as a two-stage stochastic program and two different recourse actions are considered. For each of them, a closed form is presented for the recourse function and a deterministic equivalent formulation is obtained for the case in which the probability of demand is the same for all customers. Numerical results from computational experiments are presented and analyzed.     

具有遗憾值约束的鲁棒供应链网络设计模型研究

考虑不确定性环境,研究战略层次的供应链网络鲁棒设计问题,目标是设计参数发生摄动时,供应链性能能够保持稳健性。基于鲁棒解的定义,建立从上游供应商选择到下游设施选址-需求分配的供应链网络设计鲁棒优化模型;提出确定遗憾值限定系数上限和下限的方法,允许决策者调节鲁棒水平,选择多种供应链网络结构;通过模型分解与协调,设计了供应链节点配置的禁忌搜索算法。算例的计算结果表明了禁忌搜索算法具有良好的收敛特性,以及在处理大规模问题上的优越性;同时也反映了利用鲁棒优化模型进行供应链网络设计,可以有效规避投资风险。     

产品回收逆向物流网络优化设计模型

为了在传统正向物流网络基础上扩建产品回收逆向物流网络,基于混合整数线性规划方法建立了一种单产品、有能力限制的产品回收逆向物流网络优化设计模型,据此确定物流网络中各种设施的数量和位置,并在由此构成的各条物流路径上合理分配物流量,以使各种设施的投资和运营成本之和最小。给出了提高模型求解效率的Benders分解算法,并通过算例验证了模型和算法的有效性。     

On the location of new facilities for chain expansion under delivered pricing

We study the problem of locating new facilities for one expanding chain which competes for demand in spatially separated markets where all competing chains use delivered pricing. A new network location model is formulated for profit maximization of the expanding chain assuming that equilibrium prices are set in each market. The cannibalization effect caused by the entrance of the new facilities is integrated in the objective function as a cost to be paid by the expanding chain to the cannibalized facilities. It is shown that the profit of the chain is maximized by locating the new facilities in a set of points which are nodes or iso-marginal delivered cost points (points on the network from which the marginal delivered cost equals the minimum marginal delivered cost from the existing facilities owned by the expanding chain). Then the location problem is reduced to a discrete optimization problem which is formulated as a mixed integer linear program. A sensitivity analysis respect to both the number of new facilities and the cannibalization cost is shown by using an illustrative example with data of the region of Murcia (Spain). Some conclusions are presented.     

设施失灵风险下不确定需求应急定位-路径鲁棒优化研究

为抵御突发灾害对路网造成的破坏性和设施失灵风险,降低系统成本,并快速完成应急救援任务,本文考虑到受灾点物资需求量的不确定和风险对救援系统的影响,采用直升机进行物资运送以规避路径风险。建立了最小化应急物流系统总成本和物资到达需求点总救援时间为双目标的应急物流定位-路径鲁棒优化模型,基于相对鲁棒优化方法处理需求不确定,采用偏差鲁棒优化思想描述设施失灵风险损失,采用遗传算法进行求解。通过对三个算例进行数据仿真实验,证明了相对鲁棒优化方法在处理需求不确定和偏差鲁棒优化方法在处理设施失灵风险方面的有效性,进而为解决应急设施点的开设和救援物资的安全及时准确配送,增强应急物流系统的风险应对能力提供了有效的方法。     

灾后不确定需求下应急医疗移动医院鲁棒选址问题研究

我国灾害医学救援主要采用"现场救治"模式，应急医疗移动医院的选址是否合理直接影响救援效率，但各受灾点伤员数量的不确定性增加了决策的困难。本文引入多面体不确定集合刻画伤员数量的不确定性，同时考虑伤员分类及移动医院分型，构建一个以伤员总生存概率最大化为目标的鲁棒选址模型。利用鲁棒优化理论，将模型转化为等价的混合整数规划问题，通过GAMS软件编程并调用CPLEX求解器求解。最后，以四川芦山地震应急医疗救援为例，验证模型和求解方法的可行性和鲁棒性。结果表明，扰动比例和不确定水平对移动医院的选址和伤员的分配方案有显著影响，决策者可根据自己对不确定性风险的偏好程度选择最佳的扰动比例和不确定水平组合，以获得最优的选址分配方案。     

An Optimization‐Based Framework for the Identification of Vulnerabilities in Electric Power Grids Exposed to Natural Hazards

This article proposes a novel mathematical optimization framework for the identification of the vulnerabilities of electric power infrastructure systems (which is a paramount example of critical infrastructure) due to natural hazards. In this framework, the potential impacts of a specific natural hazard on an infrastructure are first evaluated in terms of failure and recovery probabilities of system components. Then, these are fed into a bi‐level attacker–defender interdiction model to determine the critical components whose failures lead to the largest system functionality loss. The proposed framework bridges the gap between the difficulties of accurately predicting the hazard information in classical probability‐based analyses and the over conservatism of the pure attacker–defender interdiction models. Mathematically, the proposed model configures a bi‐level max‐min mixed integer linear programming (MILP) that is challenging to solve. For its solution, the problem is casted into an equivalent one‐level MILP that can be solved by efficient global solvers. The approach is applied to a case study concerning the vulnerability identification of the georeferenced RTS24 test system under simulated wind storms. The numerical results demonstrate the effectiveness of the proposed framework for identifying critical locations under multiple hazard events and, thus, for providing a useful tool to help decisionmakers in making more‐informed prehazard preparation decisions.     

A multi-period ambulance location and allocation problem in the disaster

To achieve quick response in the disaster, this paper addresses the issue of ambulance location and allocation, as well as the location problem of temporary medical centers. Considering budget and capacity limitations, a multi-period mixed integer programming model is proposed and two hybrid heuristic algorithms are designed to solve this complex problem. The proposed model and algorithm are further verified in a real case study, and the numerical experiments demonstrate the effectiveness of our proposed model. Specifically, we obtain several findings based on the computational results: (1) The best locations of ambulance stations should change in each period because the demand rate changes over time. (2) Involving temporary medical centers is necessary to reduce the average waiting time of injured people. (3) It may not be optimal to allocate ambulances from the nearest ambulance stations because of potentially limited station capacity.

     

Multiple facility location on a network with linear reliability order of edges

We study the problem of locating facilities on the nodes of a network to maximize the expected demand serviced. The edges of the input graph are subject to random failure due to a disruptive event. We consider a special type of failure correlation. The edge dependency model assumes that the failure of a more reliable edge implies the failure of all less reliable ones. Under this dependency model called Linear Reliability Order (LRO) we give two polynomial time exact algorithms. When two distinct LRO’s exist, we prove the total unimodularity of a linear programming formulation. In addition, we show that minimizing the sum of facility opening costs and expected cost of unserviced demand under two orderings reduces to a matching problem. We prove NP-hardness of the three orderings case and show that the problem with an arbitrary number of orderings generalizes the deterministic maximum coverage problem. When a demand point can be covered only if a facility exists within a distance limit, we show that the problem is NP-hard even for a single ordering.     

A Bayesian Method to Mine Spatial Data Sets to Evaluate the Vulnerability of Human Beings to Catastrophic Risk

Vulnerability of human beings exposed to a catastrophic disaster is affected by multiple factors that include hazard intensity, environment, and individual characteristics. The traditional approach to vulnerability assessment, based on the aggregate‐area method and unsupervised learning, cannot incorporate spatial information; thus, vulnerability can be only roughly assessed. In this article, we propose Bayesian network (BN) and spatial analysis techniques to mine spatial data sets to evaluate the vulnerability of human beings. In our approach, spatial analysis is leveraged to preprocess the data; for example, kernel density analysis (KDA) and accumulative road cost surface modeling (ARCSM) are employed to quantify the influence of geofeatures on vulnerability and relate such influence to spatial distance. The knowledge‐ and data‐based BN provides a consistent platform to integrate a variety of factors, including those extracted by KDA and ARCSM to model vulnerability uncertainty. We also consider the model's uncertainty and use the Bayesian model average and Occam's Window to average the multiple models obtained by our approach to robust prediction of the risk and vulnerability. We compare our approach with other probabilistic models in the case study of seismic risk and conclude that our approach is a good means to mining spatial data sets for evaluating vulnerability.     

自然异动下关键基础设施网络风险研究

关键基础设施保护是突发事件应急管理的重要对象构成,确定风险和保护排序是其保护机制的基本依据。在自然异动约束下,本文将信息扩散理论的超越概率引入风险分析模型,研究跨区域网络级联失效造成的风险,提出了确定关键基础设施网络构件的风险等级及保护排序的方法。以覆冰灾害下电网为例,研究了电网中不同支路在覆冰灾害下面临风险程度,与基本脆弱点进行对比,验证以异动风险作为保护参考的合理性。     

An approximation algorithm for k-center problem on a convex polygon

This paper studies the constrained version of the k-center location problem. Given a convex polygonal region, every point in the region originates a service demand. Our objective is to place k facilities lying on the region’s boundary, such that every point in that region receives service from its closest facility and the maximum service distance is minimized. This problem is equivalent to covering the polygon by k circles with centers on its boundary which have the smallest possible radius. We present an 1.8841-approximation polynomial time algorithm for this problem.