An algorithm for generalized constrained multi-source Weber problem with demand substations

In this paper, we consider a multi-source Weber problem of m new facilities with respect to n demand regions in order to minimize the sum of the transportation costs between these facilities and the demand regions. We find a point on the border of each demand region from which the facilities serve the demand regions at these points. We present an algorithm including a location phase and an allocation phase in each iteration for solving this problem. An algorithm is also proposed for carrying out the location phase. Moreover, global convergence of the new algorithm is proved under mild assumptions, and some numerical results are presented.     

随机容错设施布局问题的近似算法

在确定性的容错设施布局问题中, 给定顾客的集合和地址的集合. 在每个地址上可以开设任意数目的不同设施. 每个顾客j有连接需求r_j. 允许将顾客j连到同一地址的不同设施上. 目标是开设一些设施并将每个顾客j连到r_j个不同的设施上, 使得总开设费用和连接费用最小. 研究两阶段随机容错设施布局问题(SFTFP), 顾客的集合事先不知道, 但是具有有限多个场景并知道其概率分布. 每个场景指定需要服务的顾客的子集. 并且每个设施有两种类型的开设费用. 在第一阶段根据顾客的随机信息确定性地开设一些设施, 在第二阶段根据顾客的真实信息再增加开设一些设施．给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.     

A Lagrangian heuristic algorithm for a public healthcare facility location problem

We consider a healthcare facility location problem in which there are two types of patients, low-income patients and middle- and high-income patients. The former can use only public facilities, while the latter can use both public facilities and private facilities. We focus on the problem of determining locations of public healthcare facilities to be established within a given budget and allocating the patients to the facilities for the objective of maximizing the number of served patients while considering preference of the patients for the public and private facilities. We present an integer programming formulation for the problem and develop a heuristic algorithm based on Lagrangian relaxation and subgradient optimization methods. Results of computational experiments on a number of problem instances show that the algorithm gives good solutions in a reasonable computation time and may be effectively used by the healthcare authorities of the government.     

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.     

An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions

We investigate a logistics facility location problem to determine whether the existing facilities remain open or not, what the expansion size of the open facilities should be and which potential facilities should be selected. The problem is formulated as a mixed integer linear programming model (MILP) with the objective to minimize the sum of the savings from closing the existing facilities, the expansion costs, the fixed setup costs, the facility operating costs and the transportation costs. The structure of the model motivates us to solve the problem using Benders decomposition algorithm. Three groups of valid inequalities are derived to improve the lower bounds obtained by the Benders master problem. By separating the primal Benders subproblem, different types of disaggregated cuts of the primal Benders cut are constructed in each iteration. A high density Pareto cut generation method is proposed to accelerate the convergence by lifting Pareto-optimal cuts. Computational experiments show that the combination of all the valid inequalities can improve the lower bounds significantly. By alternately applying the high density Pareto cut generation method based on the best disaggregated cuts, the improved Benders decomposition algorithm is advantageous in decreasing the total number of iterations and CPU time when compared to the standard Benders algorithm and optimization solver CPLEX, especially for large-scale instances.     

The minimum equitable radius location problem with continuous demand

We analyze the location of p facilities satisfying continuous area demand. Three objectives are considered: (i) the p-center objective (to minimize the maximum distance between all points in the area and their closest facility), (ii) equalizing the load service by the facilities, and (iii) the minimum equitable radius – minimizing the maximum radius from each point to its closest facility subject to the constraint that each facility services the same load. The paper offers three contributions: (i) a new problem – the minimum equitable radius is presented and solved by an efficient algorithm, (ii) an improved and efficient algorithm is developed for the solution of the p-center problem, and (iii) an improved algorithm for the equitable load problem is developed. Extensive computational experiments demonstrated the superiority of the new solution algorithms.     

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 multicriteria approach to the location of public facilities

We argue that practical problems involving the location of public facilities are really multicriteria problems, and ought to be modeled as much. The general criteria are those of cost and service, but there exist several distinct criteria in each of those two categories. For the first category, fixed investment cost, fixed operating cost, variable operating cost, total operating cost, and total discounted cost are all reasonable criteria to consider. In terms of service, both demand served and response time (or distance traveled) are appropriate criteria, either agglomerated or considered on the basis of the individual clients. In this paper we treat such multicriteria questions in the framework of a model for selecting a subset of M sites at which to establish public facilities in order to serve client groups located at N distinct points. We show that for some combinations of specific criteria, parametric solutions of a generalized assignment problem (GAP) will yield all efficient solution. In most other cases the efficient solutions can be found through parametric solution of a GAP with additional constraints of a type which can be incorporated into an existing algorithm for the GAP. Rather than attempting to find all efficient solutions, however, we advocate an interactive approach to the resolution of multicriteria location problems and elaborate on a specific interactive algorithm for multicriteria optimization which for the present model solves a finite sequence of GAP's or GAP-type problems. Finally, some similar aspects of private sector location problems are discussed.     

Solving Graph Coloring Problems with the Douglas-Rachford Algorithm

We present the Douglas-Rachford algorithm as a successful heuristic for solving graph coloring problems. Given a set of colors, these types of problems consist in assigning a color to each node of a graph, in such a way that every pair of adjacent nodes are assigned with different colors. We formulate the graph coloring problem as an appropriate feasibility problem that can be effectively solved by the Douglas-Rachford algorithm, despite the nonconvexity arising from the combinatorial nature of the problem. Different modifications of the graph coloring problem and applications are also presented. The good performance of the method is shown in various computational experiments.     

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.     

A facility location model with safety stock costs: analysis of the cost of single-sourcing requirements

We consider a supply chain setting where multiple uncapacitated facilities serve a set of customers with a single product. The majority of literature on such problems requires assigning all of any given customer??s demand to a single facility. While this single-sourcing strategy is optimal under linear (or concave) cost structures, it will often be suboptimal under the nonlinear costs that arise in the presence of safety stock costs. Our primary goal is to characterize the incremental costs that result from a single-sourcing strategy. We propose a general model that uses a cardinality constraint on the number of supply facilities that may serve a customer. The result is a complex mixed-integer nonlinear programming problem. We provide a generalized Benders decomposition algorithm for the case in which a customer??s demand may be split among an arbitrary number of supply facilities. The Benders subproblem takes the form of an uncapacitated, nonlinear transportation problem, a relevant and interesting problem in its own right. We provide analysis and insight on this subproblem, which allows us to devise a hybrid algorithm based on an outer approximation of this subproblem to accelerate the generalized Benders decomposition algorithm. We also provide computational results for the general model that permit characterizing the costs that arise from a single-sourcing strategy.     

A new memetic algorithm based on cellular learning automata for solving the vertex coloring problem

Vertex coloring problem is a combinatorial optimization problem in graph theory in which a color is assigned to each vertex of graph such that no two adjacent vertices have the same color. In this paper a new hybrid algorithm which is obtained from combination of cellular learning automata (CLA) and memetic algorithm (MA) is proposed for solving the vertex coloring problem. CLA is an effective probabilistic learning model combining cellular automata and learning automaton (LA). Irregular CLA (ICLA) is a generalization of CLA in which the restriction of rectangular grid structure in CLA is removed. The proposed algorithm is based on the irregular open CLA (IOCLA) that is an extension of ICLA in which the evolution of CLA is influenced by both local and global environments. Similar to other IOCLA-based algorithms, in the proposed algorithm, local environment is constituted by neighboring LAs of any cell and the global environment consists of a pool of memes in which each meme corresponds to a certain local search method. Each meme is represented by a set of LAs from which the history of the corresponding local search method can be extracted. To show the superiority of the proposed algorithm over some well-known algorithms, several computer experiments have been conducted. The results show that the proposed algorithm performs better than other methods in terms of running time of algorithm and the required number of colors.     

Near-perfect token distribution

Suppose that n tokens are arbitrarily placed on the n nodes of a graph. At each parallel step one token may be moved from each node to an adjacent node. An algorithm for the near-perfect token distribution problem redistributes the tokens in a finite number of steps, so that, at the end, no more than O(1) tokens reside at each node. (In perfect distribution, at the end, exactly one token resides at each node.) In this paper we present a simple algorithm that works for all extrovert graphs, a new property which we define and study. In terms of connectivity requirements, extrovert graphs are roughly in-between expanders and compressors. Our results lead to an optimal solution for the near-perfect token distribution problem on almost all cubic graphs. The new solution is conceptually simpler than previous algorithms, and applies to graphs of minimum possible degree. © 1994 John Wiley & Sons, Inc.     

Optimal location with equitable loads

The problem considered in this paper is to find p locations for p facilities such that the weights attracted to each facility will be as close as possible to one another. We model this problem as minimizing the maximum among all the total weights attracted to the various facilities. We propose solution procedures for the problem on a network, and for the special cases of the problem on a tree or on a path. The complexity of the problem is analyzed, O(n) algorithms and an O(pn ³) dynamic programming algorithm are proposed for the problem on a path respectively for p=2 and p>2 facilities. Heuristic algorithms (two types of a steepest descent approach and tabu search) are proposed for its solution. Extensive computational results are presented.     

Online facility location with facility movements

In the online facility location problem demand points arrive one at a time and the goal is to decide where and when to open a facility. In this paper we consider a new version of the online facility location problem, where the algorithm is allowed to move the opened facilities in the metric space. We consider the uniform case where each facility has the same constant cost. We present an algorithm which is 2-competitive for the general case and we prove that it is 3/2-competitive if the metric space is the line. We also prove that no algorithm with smaller competitive ratio than \({(\sqrt{13}+1)/4\approx 1.1514}\) exists. We also present an empirical analysis which shows that the algorithm gives very good results in the average case.     

An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.     

Variable neighborhood search with ejection chains for the antibandwidth problem

In this paper, we address the optimization problem arising in some practical applications in which we want to maximize the minimum difference between the labels of adjacent elements. For example, in the context of location models, the elements can represent sensitive facilities or chemicals and their labels locations, and the objective is to locate (label) them in a way that avoids placing some of them too close together (since it can be risky). This optimization problem is referred to as the antibandwidth maximization problem (AMP) and, modeled in terms of graphs, consists of labeling the vertices with different integers or labels such that the minimum difference between the labels of adjacent vertices is maximized. This optimization problem is the dual of the well-known bandwidth problem and it is also known as the separation problem or directly as the dual bandwidth problem. In this paper, we first review the previous methods for the AMP and then propose a heuristic algorithm based on the variable neighborhood search methodology to obtain high quality solutions. One of our neighborhoods implements ejection chains which have been successfully applied in the context of tabu search. Our extensive experimentation with 236 previously reported instances shows that the proposed procedure outperforms existing methods in terms of solution quality.     

带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

A capacitated competitive facility location problem

We consider a mathematical model similar in a sense to competitive location problems. There are two competing parties that sequentially open their facilities aiming to “capture” customers and maximize profit. In our model, we assume that facilities’ capacities are bounded. The model is formulated as a bilevel integer mathematical program, and we study the problem of obtaining its optimal (cooperative) solution. It is shown that the problem can be reformulated as that of maximization of a pseudo-Boolean function with the number of arguments equal to the number of places available for facility opening. We propose an algorithm for calculating an upper bound for values that the function takes on subsets which are specified by partial (0, 1)-vectors.     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.