New Algorithms for Facility Location Problems on the Real Line

In this paper, we study the facility location problems on the real line. Given a set of n customers on the real line, each customer having a cost for setting up a facility at its position, and an integer k, we seek to find at most k of the customers to set up facilities for serving all n customers such that the total cost for facility set-up and service transportation is minimized. We consider several problem variations including the k-median, the k-coverage, and the linear model. The previously best algorithms for these problems all take O(nk) time. Our new algorithms break the O(nk) time bottleneck and solve these problems in sub-quadratic time. Our algorithms are based on a new problem modeling and interesting algorithmic techniques, which may find other applications as well.     

A bilevel fixed charge location model for facilities under imminent attack

We investigate a bilevel fixed charge facility location problem for a system planner (the defender) who has to provide public service to customers. The defender cannot dictate customer-facility assignments since the customers pick their facility of choice according to its proximity. Thus, each facility must have sufficient capacity installed to accommodate all customers for whom it is the closest one. Facilities can be opened either in the protected or unprotected mode. Protection immunizes against an attacker who is capable of destroying at most r unprotected facilities in the worst-case scenario. Partial protection or interdiction is not possible. The defender selects facility sites from m candidate locations which have different costs. The attacker is assumed to know the unprotected facilities with certainty. He makes his interdiction plan so as to maximize the total post-attack cost incurred by the defender. If a facility has been interdicted, its customers are reallocated to the closest available facilities making capacity expansion necessary. The problem is formulated as a static Stackelberg game between the defender (leader) and the attacker (follower). Two solution methods are proposed. The first is a tabu search heuristic where a hash function calculates and records the hash values of all visited solutions for the purpose of avoiding cycling. The second is a sequential method in which the location and protection decisions are separated. Both methods are tested on 60 randomly generated instances in which m ranges from 10 to 30, and r varies between 1 and 3. The solutions are further validated by means of an exhaustive search algorithm. Test results show that the defender's facility opening plan is sensitive to the protection and distance costs.     

Two level General variable neighborhood search for Attractive traveling salesman problem

Attractive traveling salesman problem (AtTSP) consists of finding maximal profit tour starting and ending at a given depot after visiting some of the facilities. Total length of the tour must not exceed the given maximum distance. Each facility achieves profit from the customers, based on the distance between the facility and customers as well as on the attractiveness of that facility. Total profit of a tour is equal to a sum of profits of all visited facilities. In this paper, we develop a new variant of Variable neighborhood search, called 2-level General variable neighborhood search (2-GVNS) for solving AtTSP. At the second level, we use General variable neighborhood search in the local search lor building neighboring solution and checking its feasibility. Our 2-GVNS heuristic outperforms tabu search heuristic, the only one proposed in the literature so far, in terms of precision and running times. In addition, 2-GVNS finds all optimal known solutions obtained by Branch and cut algorithm and offers several new best known solutions.     

The gravity multiple server location problem

Models for locating facilities and service providers to serve a set of demand points are proposed. The number of facilities is unknown, however, there is a given number of servers to be distributed among the facilities. Each facility acts as an M/M/k queuing system. The objective function is the minimization of the combined travel time and the waiting time at the facility for all customers. The distribution of demand among the facilities is governed by the gravity rule. Two models are proposed: a stationary one and an interactive one. In the stationary model it is assumed that customers do not consider the waiting time at the facility in their facility selection decision. In the interactive model we assume that customers know the expected waiting time at the facility and consider it in their facility selection decision. The interactive model is more complicated because the allocation of the demand among the facilities depends on the demand itself. The models are analyzed and three heuristic solution algorithms are proposed. The algorithms were tested on a set of problems with up to 1000 demand points and 20 servers.     

On solving unreliable planar location problems

In this paper, we generalize conventional P-median location problems by considering the unreliability of facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. We proposed efficient solution methods to determine locations of these facilities in the unreliable location model. Space-filling curve-based algorithms are developed to determine initial locations of these facilities. The unreliable P-median location problem is then decomposed to P 1-median location problems; each problem is solved to the optimum. A bounding procedure is used to monitor the iterative search, and to provide a consistent basis for termination. Extensive computational tests have indicated that the heuristics are efficient and effective for solving unreliable location problems.Scope and purposeThis paper addresses an important class of location problems, where p unreliable facilities are to be located on the plane, so as to minimize the expected travel distance or related transportation cost between the customers and their nearest available facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. Potential application of the unreliable location problem is found in numerous areas. The facilities to be located can be fire station or emergency shelter, where it fails to provide service during some time window, due to the capacity or resource constraints. Alternatively, the facilities can be telecommunication posts or logistic/distribution centers, where the service is unavailable due to breakdown, repair, shutdown of unknown causes. In this paper, we prescribed heuristic procedures to determine the location of new facilities in the unreliable location problems. The numerical study of 2800 randomly generated instances has shown that these solution procedures are both efficient and effective, in terms of computational time and solution quality.     

Optimal control of service for facilities holding inventory

This paper addresses the problem of optimally controlling service rates for an inventory system of service facilities. We consider a finite capacity system with Poisson arrivals and exponentially distributed leadtimes and service times. For given values of maximum inventory and reorder levels, we determine the service rates to be employed at each instant of time so that the long-run expected cost rate is minimized. The problem is modelled as a semi-Markov decision problem. We establish the existence of a stationary optimal policy and we solve it by employing linear programming. Several instances of a numerical example, which provide insight into the behaviour of the system, are presented.Scope and purposeIn this article we discuss the problem of inventory control of service parts at a service facility where there is only a limited waiting space for customers. If a customer enters the service facility and sees all the waiting spaces occupied he/she will leave the facility, which results in both intangible losses (loss of goodwill) and tangible losses (loss in profit). Hence, the service provider aims at obtaining an optimal rate at which service is to be provided by balancing costs due to waiting time and limited waiting spaces against costs due to ordering and overheads due to storing items. We develop an algorithm that controls the service rate as a function of the number of customers waiting for service.     

Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent

The capacitated vertex p-center problem is a location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized construction with adaptive probabilistic sampling and iterated greedy local search with variable neighborhood descent is presented. Empirical evidence over a widely used set of benchmark data sets on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances.     

A heuristic method for large-scale multi-facility location problems

A heuristic method for solving large-scale multi-facility location problems is presented. The method is analogous to Cooper's method (SIAM Rev. 6 (1964) 37), using the authors’ single facility location method (Comput. Optim. Appl. 21 (2002) 213) as a parallel subroutine, and reassigning customers to facilities using the heuristic of nearest center reclassification. Numerical results are reported. Scope and purpose We study the multiple facility location problem (MFLP). The objective in MFLP is to locate facilities to serve optimally a given set of customers. MFLPs have many applications in Operations Research, and a rich literature, see Drezner (Location Sci. 3(4) (1995) 275) for a recent survey.MFLPs involve, in addition to the location decision, also the assignment of customers to facilities. The MFLP is therefore a special clustering problem, the clusters here are the sets of customers assigned to the same facility.We propose a parallel heuristic method for solving MFLPs, using ideas from cluster analysis (nearest mean reclassification (Cluster Analysis, 3rd Edition, Edward Arnold, London, 1993)), and the authors’ Newton bracketing method for convex minimization (Comput. Optim. Appl. 21 (2002) 213) as a subroutine. The method is suitable for large-scale problems, as illustrated by numerical examples.     

A planar single-facility competitive location and design problem under the multi-deterministic choice rule

A new customer choice rule, which may model in some cases the actual patronising behaviour of customers towards the facilities closer to reality than other existing rules, is proposed. According to the new rule, customers split their demand among the firms in the market by patronising only one facility from each firm, the one with the highest utility, and the demand is split among those facilities proportionally to their attraction. The influence of the choice rule in the location of facilities is investigated. In particular, a new continuous competitive single-facility location and design problem using this new rule is proposed. Both exact and heuristic methods are proposed to solve it. A comparison with the classical proportional (or Huff) choice rule when solving the location model reveals that both the location and the quality of the new facility to be located may be quite different depending on the patronising behaviour of customers. Most importantly, the profit that the locating chain may lose if a wrong choice is made can be quite high in some instances.     

GRASP and hybrid GRASP-Tabu heuristics to solve a maximal covering location problem with customer preference ordering

In this study, a maximal covering location problem is investigated. In this problem, we want to maximize the demand of a set of customers covered by a set of p facilities located among a set of potential sites. It is assumed that a set of facilities that belong to other firms exists and that customers freely choose allocation to the facilities within a coverage radius. The problem can be formulated as a bilevel mathematical programming problem, in which the leader locates facilities in order to maximize the demand covered and the follower allocates customers to the most preferred facility among those selected by the leader and facilities from other firms. We propose a greedy randomized adaptive search procedure (GRASP) heuristic and a hybrid GRASP-Tabu heuristic to find near optimal solutions. Results of the heuristic approaches are compared to solutions obtained with a single-level reformulation of the problem. Computational experiments demonstrate that the proposed algorithms can find very good quality solutions with a small computational burden. The most important feature of the proposed heuristics is that, despite their simplicity, optimal or near-optimal solutions can be determined very efficiently.     

The Capacitated p-facility Location Problem on the Real Line

The problem we address involves locating p new facilities to service a set of customers or fixed points on the real line such that a measure of total cost will be minimized. A basic form of this problem was investigated by Love (1976), who observed that the fixed points must be allocated in sequence to the new facilities in an optimal solution, and thus, the problem can be solved by a dynamic programming algorithm. Since then, other forms of the model have been investigated; however, in all cases it is assumed that the new facilities have unlimited capacity so that customer flows are always allocated to the nearest facility. The objective of this paper is to analyze the effect of capacity constraints on the optimal locations of the new facilities. A general fixed-cost function is also included to account for practical considerations such as zoning regulations, and to permit the facilities to be located anywhere on the line instead of only at the fixed vertices. A dynamic programming method is formulated to solve the problem when the variable cost components are increasing convex functions of travel distance. The problem is shown to be NP-hard under more general cost structures.     

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.     

The multi-period incremental service facility location problem

In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproblem that results when fixing the set of facilities to open is totally unimodular. This allows to solve efficiently the Lagrangean problem that relaxes constraints requiring customers to be assigned to open facilities. We propose a solution approach that provides both lower and upper bounds by combining subgradient optimization to solve a Lagrangean dual with an ad hoc heuristic that uses information from the Lagrangean subproblem to generate feasible solutions. Numerical results obtained in the computational experiments show that the obtained solutions are very good. In general, we get very small percent gaps between upper and lower bounds with little computation effort.     

软容量限制设施选址问题的竞争决策算法

软容量设施选址问题是NP-Hard问题之一，具有广泛的应用价值。为了求解软容量设施选址问题，提出一种基于数学性质的竞争决策算法。首先研究该问题的数学性质，运用这些数学性质不仅可以确定某些设施必定开设或关闭，还可以确定部分顾客由哪个设施提供服务，从而缩小问题的规模，加快求解速度。在此基础上设计了求解该问题的竞争决策算法，最后经过一个小规模的算例测试并与精确算法的结果比较，得出了最优解；针对大规模的问题快速地求出了可行解，得到了令人满意的结果。     

Locating a semi-obnoxious facility with expropriation

This paper considers the problem of locating semi-obnoxious facilities assuming that “too close” demand nodes can be expropriated by the developer at a given price. The objective is to maximize the minimum weighted distance from the facility to the non-expropriated demand nodes given a limited budget while taking into account the fact that customers do not want to be too far away from the facility. Two models of this problem on a network are presented. One is to minimize the difference between the maximum and the minimum weighted distances. The other one is to maximize the minimum weighted distance subject to an upper bound constraint on the maximum weighted distance. The dominating sets are determined and efficient algorithms are presented.     

A leader-follower game in competitive facility location

We address the problem of locating new facilities of a firm or franchise that enters a market where a competitor operates existing facilities. The goal of the new entrant firm is to decide the location and attractiveness of its new facilities that maximize its profit. The competitor can react by opening new facilities, closing existing ones, and adjusting the attractiveness levels of its existing facilities, with the aim of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the new facilities of both the firm and the competitor can be located at predetermined candidate sites. We employ the gravity-based rule in modeling the behavior of the customers where the probability that a customer visits a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. We propose heuristics that combine tabu search with exact solution methods.     

The maximum capture problem with heterogeneous customers

A product is sold in a geographical market and it is provided by different companies. Small unmeasurable differences exist between the products sold by different companies and customers have heterogeneous tastes. A newcomer wishes to enter the market locating p new facilities, in order to gain the maximum number of customers. It is assumed that he is not able to specify the exact behavior of every customer, so he models the consumers’ decision making by a random utility function. Under some more technical assumptions, a closed formula for the probability of patronizing a given facility is obtained. By this way, a formulation of the maximum capture problem can be obtained. The computational features of the problem are considered and two branch-and-bound methods are developed. The first method exploits the Lagrangian relaxation of the problem, the second uses the submodularity of the objective function. Data sets are generated according to different competitive scenarios and problems of up to 100 nodes are solved within a few seconds.     

Heuristics for a continuous multi-facility location problem with demand regions

We consider a continuous multi-facility location allocation problem where the demanding entities are regions in the plane instead of points. The problem can be stated as follows: given m (closed, convex) polygonal demand regions in the plane, find the locations of q facilities and allocate each region to exactly one facility so as to minimize a weighted sum of squares of the maximum Euclidean distances between the demand regions and the facilities they are assigned to.We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.     

Efficient approximate solution methods for the multi-commodity capacitated multi-facility Weber problem

The capacitated multi-facility Weber problem is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity. This is a nonconvex optimization problem and difficult to solve. In this work, we focus on a multi-commodity extension and consider the situation where K distinct commodities are shipped subject to capacity constraints between each customer and facility pair. Customer locations, demands and capacities for each commodity, and bundle restrictions are known a priori. The transportation costs, which are proportional to the distance between customers and facilities, depend on the commodity type. We address several location-allocation and discrete approximation heuristics using different strategies. Based on the obtained computational results we can say that the alternate solution of location and allocation problems is a very efficient strategy; but the discrete approximation has excellent accuracy.     

基于混合需求的设施选址问题研究

研究网络中设施的需求一部分来自于网络节点, 一部分来自于过往流量的基于混合需求的设施选址问题。引入引力模型, 以新建设施获得总利润最大为目标建立非线性整数规划模型, 并构造启发式算法, 通过MATLAB进行仿真实验, 将求解结果与GPAH算法及精确算法的结果进行比较。比较结果表明, 提出的算法求解质量高、运行速度快, 可用于大中型网络设施的选址问题。