Noncooperative facility location games

A noncooperative game theoretical approach is considered for the multifacility location problem. It turns out that the facility location game is a potential game in the sense of Monderer and Shapley and some properties of the game are studied.     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

The practice for eight-year operation of the cobalt-60 irradiation facility at Beijing Radiation Application Research Center

The radiation facility was made by Sulzer Company in Switzerland. The designed capacity is 3.7 × 10¹⁶Bq( 1MCi) and 12.21 × 10¹⁵Bq(330kCi)of Cobalt -60 source was loaded at the first phase. Current cobalt -60 source-loading is 2.4 × 10¹⁶Bq(650kCi). The equipment assembling and installation regulating and testing were completed at the end of 1988. The facility was put into commissioning in 1989. It operates 7000–8000 hours per year. The facility has been utilized to carry out many research work and irradiate many kinds of items. Lots of economical benefits have been gained since then. Now it is becoming a radiation processing model base in China. This paper summarized the strong and weak points of the design of the facility through in eight years' practice and analysed the economical benefits.     

Facility location in the presence of forbidden regions,I: Formulation and the case of Euclidean distance with one forbidden circle

A constrained form of the Weber problem is formulated in which no path is permitted to enter a prespecified forbidden region $\text{R}$ of the plane. Using the calculus of variations the shortest path between two points $\text{x}\text{,}\text{y}\text{?}\text{R}$ which does not intersect $\text{R}$ is determined. If $\text{d(}\text{x}\text{,}\text{y}\text{)}$ is unconstrained distance, we denote the shortes distance along a feasible path by $\text{d}\text{(}\text{x}\text{y}\text{)}$. The constrained Weber problem is, then: given points $\text{x}{}_{\mathrm{j}}\text{?}\text{R}$ and positive weights w_j, j = 1,2,…,n, find a point $\text{x}\text{?}\text{R}$ such that

$\text{f(}\text{x}\text{)=}\text{Σ}\text{n}\text{j=1}\text{d(}\text{x}\text{,}\text{x}{}_{\mathrm{j}}\text{)}$

is a minimum.An algorithm is formulated for the solution of this problem when $\text{d(}\text{x}\text{,}\text{y}\text{)}$ is Euclidean distance and $\text{R}$ is a single circular region. Numerical results are presented.     

A computational approach for eliminating error in the solution of the location set covering problem

The location set covering problem continues to be an important and challenging spatial optimization problem. The range of practical planning applications underscores its importance, spanning fire station siting, warning siren positioning, security monitoring and nature reserve design, to name but a few. It is challenging on a number of fronts. First, it can be difficult to solve for medium to large size problem instances, which are often encountered in combination with geographic information systems (GIS) based analysis. Second, the need to cover a region efficiently often brings about complications associated with the abstraction of geographic space. Representation as points can lead to significant gaps in actual coverage, whereas representation as polygons can result in a substantial overestimate of facilities needed. Computational complexity along with spatial abstraction sensitivity combine to make advances in solving this problem much needed. To this end, a solution framework for ensuring complete coverage of a region with a minimum number of facilities is proposed that eliminates potential error. Applications to emergency warning siren and fire station siting are presented to demonstrate the effectiveness of the developed approach. The approach can be applied to convex, non-convex and non-contiguous regions and is unaffected by arbitrary initial spatial representations of space.     

Locating the two-median of a tree network with continuous link demands

Typical formulations of thep-median problem on a network assume discrete nodal demands. However, for many problems, demands are better represented by continuous functions along the links, in addition to nodal demands. For such problems, optimal server locations need not occur at nodes, so that algorithms of the kind developed for the discrete demand case can not be used. In this paper we show how the 2-median of a tree network with continuous link demands can be found using an algorithm based on sequential location and allocation. We show that the algorithm will converge to a local minimum and then present a procedure for finding the global minimum solution.     

基于同步辐射加速器的康普顿背散射γ光源性质及其应用研究

本文介绍了利用康普顿背散射 (BCS)产生γ射线的原理 ,并以SSRF储存环电子运行参数为例 ,给出了利用BCS方法产生MeV量级γ射线束的计算结果 ,预期该光子束具有高强度、高极化度、单色性、方向性好等优点。同时对国际上已运行和拟建的高能和低能γ束线站的装置和性能作了简要介绍 ,并分别探讨了高能和低能准单色极化γ射线在核物理和核天体物理研究中广泛的应用前景。文中对基于正对以及离轴几何条件下 ,采用直线加速器加速的电子同短脉冲强激光发生Compton/Thomson散射的激光同步辐射源作了初步探讨 ,这一方法为我们构建超短脉冲的高亮度、准单色、可调谐的X γ射线源开辟了一条新途径。     

Locating a single facility and a high-speed line

In this paper we study a facility location problem in the plane in which a single point (facility) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time from the clients to the facility, using the _L1$L_1$ or Manhattan metric. The rapid transit line is given by a segment with any length and orientation, and is an alternative transportation line that can be used by the clients to reduce their travel time to the facility. We study the variant of the problem in which clients can enter and exit the highway at any point. We provide an O(n³)$O(n^3)$-time algorithm that solves this variant, where n is the number of clients. We also present a detailed characterization of the solutions, which depends on the speed given along the highway.     

A survey of recent research on location-routing problems

The design of distribution systems raises hard combinatorial optimization problems. For instance, facility location problems must be solved at the strategic decision level to place factories and warehouses, while vehicle routes must be built at the tactical or operational levels to supply customers. In fact, location and routing decisions are interdependent and studies have shown that the overall system cost may be excessive if they are tackled separately. The location-routing problem (LRP) integrates the two kinds of decisions. Given a set of potential depots with opening costs, a fleet of identical vehicles and a set of customers with known demands, the classical LRP consists in opening a subset of depots, assigning customers to them and determining vehicle routes, to minimize a total cost including the cost of open depots, the fixed costs of vehicles used, and the total cost of the routes. Since the last comprehensive survey on the LRP, published by Nagy and Salhi (2007), the number of articles devoted to this problem has grown quickly, calling a review of new research works. This paper analyzes the recent literature (72 articles) on the standard LRP and new extensions such as several distribution echelons, multiple objectives or uncertain data. Results of state-of-the-art metaheuristics are also compared on standard sets of instances for the classical LRP, the two-echelon LRP and the truck and trailer problem.