设备定位问题局部搜索算法的实验

讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法,设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解;贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法,但两者求解质量相当;设备价值和服务价值数值范围越大,局部搜索算法越容易求得最优解。     

Efficient algorithms for center problems in cactus networks

Efficient algorithms for solving the center problems in weighted cactus networks are presented. In particular, we have proposed the following algorithms for the weighted cactus networks of size n$n$: an O(nlogn)$O(nlogn)$ time algorithm to solve the 1-center problem, and an O(nlog³n)$O\left(n{log}^{3}n\right)$ time algorithm to solve the weighted continuous 2-center problem. We have also provided improved solutions to the general p$p$-center problems in cactus networks. The developed ideas are then applied to solve the obnoxious 1-center problem in weighted cactus networks.     

Covering problems in facility location: A review

In this study, we review the covering problems in facility location. Here, besides a number of reviews on covering problems, a comprehensive review of models, solutions and applications related to the covering problem is presented after Schilling, Jayaraman, and Barkhi (1993). This survey tries to review all aspects of the covering problems by stressing the works after Schilling, Jayaraman, and Barkhi (1993). We first present the covering problems and then investigate solutions and applications. A summary and future works conclude the paper.     

Competitive facility location: the Voronoi game

We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is then subdivided according to the nearest-neighbor rule, and the player whose points control the larger area wins. We present a winning strategy for the second player, where the arena is a circle or a line segment. We permit variations where players can play more than one point at a time, and show that the first player can ensure that the second player wins by an arbitrarily small margin.     

Solving a class of facility location problems using genetic algorithms

Locating p facilities to serve a number of customers is a problem in many areas of business. The problem is to determine p facility locations such that the weighted average distance traveled from all the demand points to their nearest facility sites is minimized. A variant of the p-median problem is one in which a maximum distance constraint is imposed between the demand point and its nearest facility location, also known as the p-median problem with maximum distance constraint. In this paper, we apply a fairly new methodology known as genetic algorithms to solve a relatively large sized constrained version of the p -median problem. We present our computational experience on the use of genetic algorithms for solving the constrained version of the p-median problem using two different data sets. Our comparative experimental experience shows that this solution procedure performs quite well compared with the results obtained from existing techniques.     

Local search heuristics for the mobile facility location problem

In the mobile facility location problem (MFLP), one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities so that the sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. This paper studies formulations and develops local search heuristics for the MFLP. First, we develop an integer programming (IP) formulation for the MFLP by observing that for a given set of facility destinations the problem may be decomposed into two polynomially solvable subproblems. This IP formulation is quite compact in terms of the number of nonzero coefficients in the constraint matrix and the number of integer variables; and allows for the solution of large-scale MFLP instances. Using the decomposition observation, we propose two local search neighborhoods for the MFLP. We report on extensive computational tests of the new IP formulation and local search heuristics on a large range of instances. These tests demonstrate that the proposed formulation and local search heuristics significantly outperform the existing formulation and a previously developed local search heuristic for the problem.     

Modeling health care facility location for moving population groups

Locating public services for nomadic population groups is a difficult challenge as the locations of the targeted populations seasonally change. In this paper, the population groups are assumed to occupy different locations according to the time of the year, i.e., winter and summer. A binary integer programming model is formulated to determine the optimal number and locations of primary health units for satisfying a seasonally varying demand. This model is successfully applied to the actual locations of 17 seasonally varying nomadic groups in the Middle East. Computational tests are performed on different versions of the model in order analyze the tradeoffs among different performance measures.     

Use of distributed data sources in facility location

Facility location decisions are usually determined by cost and coverage related factors although empirical studies show that such factors as infrastructure, labor conditions and competition also play an important role in practice. The objective of this paper is to develop a multi-objective facility location model accounting for a wide range of factors affecting decision-making. The proposed model selects potential facilities from a set of pre-defined alternative locations according to the number of customers, the number of competitors and real-estate cost criteria. However, that requires large amount of both spatial and non-spatial input data, which could be acquired from distributed data sources over the Internet. Therefore, a computational approach for processing input data and representation of modeling results is elaborated. It is capable of accessing and processing data from heterogeneous spatial and non-spatial data sources. Application of the elaborated data gathering approach and facility location model is demonstrated using an example of fast food restaurants location problem.     

Multi-dimensional dynamic facility location and fast computation at query points

We present O(nlogn) time algorithms for the minimax rectilinear facility location problem in R¹ and R². The algorithms enable, once they terminate, computing the cost of any given query point in O(logn) time. Based on these algorithms, we develop a preprocessing procedure which enables solving the following two problems: Fast computation of the cost of any query point in Rd, and fast solution for the dynamic location problem in R² (namely, in the presence of an additional facility). Finally, we show that the preprocessing always gives a bound on the optimal value, which allows us in many cases to find the optimum fast (for both the traditional and the dynamic location problems in Rd for any d).     

A facility location allocation model for reusing carpet materials

Re-using the huge quantities of carpet waste that are yearly generated has become a must. A facility location–allocation model for the collection, preprocessing and redistribution of carpet waste is presented. This model differs from other mathematical models for supporting the design of the logistic structure of reuse networks among others in a completely free choice of the locations for preprocessing and in explicitly taking into account depreciation costs. Two applications of the model, one in Europe and one in the United States of America, are described.     

An integrated approach to facility location problems

An integrated analysis approach to facility location problems is described. The approach is based on integrating analytical location models and a multicriteria decision model.     

工厂地址集中的k-种产品选址问题的近似算法

k-种产品工厂选址问题是：给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要k-种产品,一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法。     

A leader–follower model for discrete competitive facility location

In this paper we investigate a leader–follower (Stackelberg equilibrium) competitive location model. The competitive model is based on the concept of cover. Each facility attracts consumers within a “sphere of influence” defined by a “radius of influence.” The leader and the follower, each has a budget to be spent on the expansion of their chains either by improving their existing facilities or constructing new ones. We find the best strategy for the leader assuming that the follower, knowing the action taken by the leader, will react by investing his budget to maximize his market share. The objective of the leader is to maximize his market share following the follower׳s reaction.     

Capacitated facility location problem with general setup cost

This paper presents an extension of the capacitated facility location problem (CFLP), in which the general setup cost functions and multiple facilities in one site are considered. The setup costs consist of a fixed term (site setup cost) plus a second term (facility setup costs). The facility setup cost functions are generally non-linear functions of the size of the facility in the same site. Two equivalent mixed integer linear programming (MIP) models are formulated for the problem and solved by general MIP solver. A Lagrangian heuristic algorithm (LHA) is also developed to find approximate solutions for this NP-hard problem. Extensive computational experiments are taken on randomly generated data and also well-known existing data (with some necessary modifications). The detailed results are provided and the heuristic algorithm is shown to be efficient.     

Planar geometric location problems

We present anO(n ² log³ n) algorithm for the two-center problem, in which we are given a setS ofn points in the plane and wish to find two closed disks whose union containsS so that the larger of the two radii is as small as possible. We also give anO(n ² log⁵ n) algorithm for solving the two-line-center problem, where we want to find two strips that coverS whose maximum width is as small as possible. The best previous solutions of both problems requireO(n ³) time.Pankaj Agarwal has been supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), an NSF Science and Technology Center, under Grant STC-88-09648. Micha Sharir has been supported by the Office of Naval Research under Grants N00014-89-J-3042 and N00014-90-J-1284, by the National Science Foundation under Grant CCR-89-01484, by DIMACS, and by grants from the US-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary version of this paper has appeared inProceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 1991, pp. 449–458.     

Solving the uncapacitated facility location problem using tabu search

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.     

An LP rounding algorithm for approximating uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP, for short) in which each client can be either assigned to some opened facility or rejected by paying a penalty. Existing approaches [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642] and [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795] for this variant of facility location problem are all based on primal-dual method. In this paper, we present an efficient linear programming (LP) rounding based approach to show that LP rounding techniques are equally capable of solving this variant of facility location problem. Our algorithm uses a two-phase filtering technique (generalized from Lin and Vitter's [?-approximation with minimum packing constraint violation, in: Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, p. 771]) to identify those to-be-rejected clients and open facilities for the remaining ones. Our approach achieves an approximation ratio of 2+2/e (≈2.736) which is worse than the best approximation ratio of 2 achieved by the much more sophisticated dual fitting technique [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795], but better than the approximation ratio of 3 achieved by the primal-dual method [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642]. Our algorithm is simple, natural, and can be easily integrated into existing LP rounding based algorithms for facility location problem to deal with outliers.     

MIP models for connected facility location: A theoretical and computational study

This article comprises the first theoretical and computational study on mixed integer programming (MIP) models for the connected facility location problem (ConFL). ConFL combines facility location and Steiner trees: given a set of customers, a set of potential facility locations and some inter-connection nodes, ConFL searches for the minimum-cost way of assigning each customer to exactly one open facility, and connecting the open facilities via a Steiner tree. The costs needed for building the Steiner tree, facility opening costs and the assignment costs need to be minimized.     

Determining the timing of project control points using a facility location model and simulation

Projects are usually performed in relatively unstable environments. As such, changes to the baseline schedules of projects are inevitable. Therefore, project progress needs to be monitored and controlled. The control process can be assumed as a continuum in which one side is continuous control and the other side is no-control. Continuous control and no-control strategies are cost-wise prohibited. Hence, project progress should be controlled at some discrete points in time during the project׳s duration. The optimal number and timing of control points are the main issues that should be addressed. In this paper, taking a dynamic view to the project control, for the first time we use an adapted version of the facility location model (FLM) to find the optimal timing of project control points. Initially, the adapted FLM determines the optimum timing of the control points in the project׳s duration. A simulation model is then used to predict the possible disruptions in the time period between the beginning of the project and the first control point (monitoring phase). If no disruptions are observed, the project׳s progress is monitored in the second control point, otherwise possible corrective actions are taken using an activity compression model. Whenever due to disruptions, the baseline schedule is to be updated, the FLM is run again to determine the new timing of the control points for the rest of the project׳s duration. In an iterative manner, this process continues until the timing of the last control point is determined.