基于改进NSGA-II算法的多级服务设施备用覆盖选址决策模型

为了应对跨区域突发事件过程中受灾点服务差异化需求的问题,建立了应急储备设施点的多级备用覆盖选址决策模型,即一个需求点由多个应急设施提供不同质量水平的服务,并考虑设施繁忙状态下由其他设施点提供服务的状况,使模型更加符合实际应用。首次通过设计分段的染色体编码方式改进NSGA-II算法提升运算效率以更好地解决多目标选址决策问题,将改进方法下得到的Pareto解分布与NSGA-II算法下的仿真结果进行对比分析,结合设施点的部署策略得到不同的空间布局方案。证明了模型的可行性及改进NSGA-II算法在解决设施点多目标选址决策问题时的有效性。     

Multi-objective competitive location problem with distance-based attractiveness and its best non-dominated solution

The multi-objective competitive location problem (MOCLP) with distance-based attractiveness is introduced. There are m potential competitive facilities and n demand points on the same plane. All potential facilities can provide attractiveness to the demand point which the facility attractiveness is represented as distance-based coverage of a facility, which is “full coverage” within the maximum full coverage radius, “no coverage” outside the maximum partial coverage radius, and “partial coverage” between those two radii. Each demand point covered by one of m potential facilities is determined by the greatest accumulated attractiveness provided the selected facilities and least accumulated distances between each demand point and selected facility, simultaneously. The tradeoff of maximum accumulated attractiveness and minimum accumulated distances is represented as a multi-objective optimization model. A proposed solution procedure to find the best non-dominated solution set for MOCLP is introduced. Several numerical examples and instances comparing with introduced and exhaustive method demonstrates the good performance and efficiency for the proposed solution procedure.     

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.     

A network location-allocation model trading off flow capturing andp-median objectives

The flow capturing and thep-median location—allocation models deal quite differently with demand for service in a network. Thep-median model assumes that demand is expressed at nodes and locates facilities to minimize the total distance between such demand nodes and the nearest facility. The flow-capturing model assumes that demand is expressed on links and locates facilities to maximize the one-time exposure of such traffic to facilities. Demand in a network is often of both types: it is expressed by passing flows and by consumers centred in residential areas, aggregated as nodes. We here present a hybrid model with the dual objective of serving both types of demand. We use this model to examine the tradeoff between serving the two types of demand in a small test network using synthetic demand data. A major result is the counter-intuitive finding that thep-median model is more susceptible to impairment by the flow capturing objective than is the flow capturing model to thep-median objective. The results encourage us to apply the model to a real-world network using actual traffic data.     

Optimal algorithms for the α-neighbor p-center problem

Assigning multiple service facilities to demand points is important when demand points are required to withstand service facility failures. Such failures may result from a multitude of causes, ranging from technical difficulties to natural disasters. The α-neighbor p-center problem deals with locating p service facilities. Each demand point is assigned to its nearest α service facilities, thus it is able to withstand up to α − 1 service facility failures. The objective is to minimize the maximum distance between a demand point and its αth nearest service facility. We present two optimal algorithms for both the continuous and discrete α-neighbor p-center problem. We present experimental results comparing the performance of the two optimal algorithms for α = 2. We also present experimental results showing the performance of the relaxation algorithm for α = 1, 2, 3.     

An algorithm portfolio for the dynamic maximal covering location problem

The location of facilities (antennas, ambulances, police patrols, etc) has been widely studied in the literature. The maximal covering location problem aims at locating the facilities in such positions that maximizes certain notion of coverage. In the dynamic or multi-period version of the problem, it is assumed that the nodes’ demand changes with the time and as a consequence, facilities can be opened or closed among the periods. In this contribution we propose to solve dynamic maximal covering location problem using an algorithm portfolio that includes adaptation, cooperation and learning. The portfolio is composed of an evolutionary strategy and three different simulated annealing methods (that were recently used to solve the problem). Experiments were conducted on 45 test instances (considering up to 2500 nodes and 200 potential facility locations). The results clearly show that the performance of the portfolio is significantly better than its constituent algorithms.     

Locating a minisum annulus: a new partial coverage distance model

The problem is to find the best location in the plane of a minisum annulus with fixed width using a partial coverage distance model. Using the concept of partial coverage distance, those demand points within the area of the annulus are served at no cost, while for ‘uncovered’ demand points there will be additional costs proportional to their distances to the annulus. The objective of the problem is to locate the annulus such that the sum of distances from the uncovered demand points to the annulus (covering area) is minimized. The distance is measured by the Euclidean norm. We discuss the case where the radius of the inner circle of the annulus is variable, and prove that at least two demand points must be on the boundary of any optimal annulus. An algorithm to solve the problem is derived based on this result.     

A Procedure for Locating Emergency-Service Facilities for All Possible Response Distances

The problem of locating emergency-service facilities involves the assignment of a set of demand points to a set of facilities. One way to formulate the problem is to minimize the number of required facilities, given that the maximum distance between the demand points and their nearest facility does not exceed some specified value. We present a procedure for determining the numbers of such facilities for all possible values of the maximum distance. Computational results are presented for a microcomputer implementation.     

Confined location of facilities on a graph

Location problems on a graph are usually classified according to the form that the set of located facilities takes, the specification of the demand location set and the objective function of distances between facilities and demand points. In this paper we suppose that a given number of located facilities is confined to the same number of edges. We consider eight types of optimality criteria: minirnizing(or maximizing) the minimum (or maximum) distance from a demand to its nearest (farthest) facility.     

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

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

On models for continuous facility location with partial coverage

This paper presents a new concept of partial coverage distance, where demand points within a given threshold distance of a new facility are covered in the traditional sense, while non-covered demand points are penalized an amount proportional to their distance to the covered region. Two single facility location models, based on the minisum and minimax criteria, are formulated with the new distance function, and the structure of the models is analysed.     

Location and allocation for distribution systems with transshipments and transportion economies of scale

Locating transshipment facilities and allocating origins and destinations to transshipment facilities are important decisions for many distribution and logistic systems. Models that treat demand as a continuous density over the service region often assume certain facility locations or a certain allocation of demand. It may be assumed that facility locations lie on a rectangular grid or that demand is allocated to the nearest facility or allocated such that each facility serves an equal amount of demand. These assumptions result in suboptimal distribution systems. This paper compares the transportation cost for suboptimal location and allocation schemes to the optimal cost to determine if suboptimal location and allocation schemes can produce nearly optimal transportation costs. Analytical results for distribution to a continuous demand show that nearly optimal costs can be achieved with suboptimal locations. An example of distribution to discrete demand points indicates the difficulties in applying these results to discrete demand problems.     

Deterministic flow-demand location problems

In flow-covering (interception) models the focus is on the demand for service that originates from customers travelling in the network (not for the purpose of obtaining the service). In contrast, in traditional location models a central assumption is that the demand for service comes from customers residing at nodes of the network. In this paper we combine these two types of models. The paper presents four new problems. Two of the four deal with the problem of locating m facilities so as to maximize the total number of potential customers covered by the facilities (where coverage does not necessarily imply the actual consumption of service). In the two other problems the attention is directed to the consumption of service and thus the criteria is to maximize (minimize) the number of actual users (distance travelled). It is shown in the paper that all four problems have similar structure to other known location problems.     

Inventory sharing in integrated network design and inventory optimization with low-demand parts

Service Parts Logistics (SPL) problems induce strong interaction between network design and inventory stocking due to high costs and low demands of parts and response time based service requirements. These pressures motivate the inventory sharing practice among stocking facilities. We incorporate inventory sharing effects within a simplified version of the integrated SPL problem, capturing the sharing fill rates in 2-facility inventory sharing pools. The problem decides which facilities in which pools should be stocked and how the demand should be allocated to stocked facilities, given full inventory sharing between the facilities within each pool so as to minimize the total facility, inventory and transportation costs subject to a time-based service level constraint. Our analysis for the single pool problem leads us to model this otherwise non-linear integer optimization problem as a modified version of the binary knapsack problem. Our numerical results show that a greedy heuristic for a network of 100 facilities is on average within 0.12% of the optimal solution. Furthermore, we observe that a greater degree of sharing occurs when a large amount of customer demands are located in the area overlapping the time windows of both facilities in 2-facility pools.     

Optimizing capacity,pricing and location decisions on a congested network with balking

In this paper, we consider the problem of making simultaneous decisions on the location, service rate (capacity) and the price of providing service for facilities on a network. We assume that the demand for service from each node of the network follows a Poisson process. The demand is assumed to depend on both price and distance. All facilities are assumed to charge the same price and customers wishing to obtain service choose a facility according to a Multinomial Logit function. Upon arrival to a facility, customers may join the system after observing the number of people in the queue. Service time at each facility is assumed to be exponentially distributed. We first present several structural results. Then, we propose an algorithm to obtain the optimal service rate and an approximate optimal price at each facility. We also develop a heuristic algorithm to find the locations of the facilities based on the tabu search method. We demonstrate the efficiency of the algorithms numerically.     

Designing multi-echelon service parts networks with finite repair capacity

We propose an approach to model and solve the joint problem of facility location, inventory allocation and capacity investment in a two echelon, single-item, service parts supply chain with stochastic demand. The objective of the decision problem is to minimize the total expected costs associated with (1) opening repair facilities, (2) assigning each field service location to an opened facility, (3) determining capacity levels of the opened repair facilities, and (4) optimizing inventory allocation among the locations. Due to the size of the problem, computational efficiency is essential. The accuracy of the approximations and effectiveness of the approach are analyzed with two numerical studies. The approach provides optimal results in 90% of scenarios tested and was within 2% of optimal when it did not.We explore the impact of capacity utilization, inventory availability, and lead times on the performance of the approach. We show that including tactical considerations jointly with strategic network design resulted in additional cost savings from 3% to 12%. Our contribution is the development of a practical model and approach to support the decision making process of joint facility location and multi-echelon inventory optimization.     

基于选址效益的联合覆盖模型研究

传统的覆盖模型含有“全有全无”和“单一覆盖”两个假设,即假设需求点在设施的服务半径内才被覆盖,否则不被覆盖;需求点只能被最近的设施覆盖。这两条假设在实际应用中均存在不合理之处。松弛了这两条假设,研究逐渐覆盖和联合覆盖。在保证每个需求点都享受到最低服务水平的情况下,提出了选址效益最大化的联合覆盖模型。由于目标函数中含有分式,通过引入辅助变量的方法,将含有分式目标函数的非线性规划转化成等价的线性规划。最后,通过数值算例分析了最低服务水平限制对最佳选址方案的影响,并得到选址成本、总服务水平和单位成本服务水平随最低服务水平限制的变化,同时对影响模型的重要参数做了敏感性分析。     

Directional approach to gradual cover: the continuous case

Computational Management Science - The objective of the cover location models is covering demand by facilities within a given distance. The gradual (or partial) cover replaces abrupt drop from full...     

Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers

This paper studies a facility location problem with stochastic customer demand and immobile servers. Motivated by applications to locating bank automated teller machines (ATMs) or Internet mirror sites, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. Customers are assumed to visit the closest open facility. The objective of this problem is to minimize customers' total traveling cost and waiting cost. In addition, there is a restriction on the number of facilities that may be opened and an upper bound on the allowable expected waiting time at a facility. Three heuristic algorithms are developed, including a greedy-dropping procedure, a tabu search approach and an -optimal branch-and-bound method. These methods are compared computationally on a bank location data set from Amherst, New York.     

The gradual covering decay location problem on a network

In covering problems it is assumed that there is a critical distance within which the demand point is fully covered, while beyond this distance it is not covered at all. In this paper we define two distances. Within the lower distance a demand point is fully covered and beyond the larger distance it is not covered at all. For a distance between these two values we assume a gradual coverage decreasing from full coverage at the lower distance to no coverage at the larger distance.