Geometric complexity of some location problems

Given a set ofn demand points with weightW _i ,i = 1,2,...,n, in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An Ω(n logn) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

Exact approaches for static data segment allocation problem in an information network

In a large distributed database, data are geographically distributed across several separate servers (or data centers). This helps in distributing load in the access network. It also helps to serve data locally where it is required. There are various approaches based on the granularity of data for efficient data distribution in a communication network. The file allocation problem (FAP) locates files to servers, the segment allocation problem (SAP) locates database segments, and the mirror location problem (MLP) locates replicas of the entire database. The placement of such data to multiple servers can be modeled as an optimization problem. The major decisions influencing optimization involves the location of servers, allocation of content and assignment of users. In this paper, we study the segment allocation problem (SAP), which is also known as the partial mirroring problem. This approach is more tractable than the file allocation problem in realistic cases and also eliminates the overhead of (constant) update costs that is incurred in the mirror location problem. Our contribution is two-fold: Firstly, earlier works on SAP assume pre-defined segments. We build a data partitioning method using well-known facility location models. We quantify the performance of the partitioning method. We show that the method partitions the database within a reasonable limit of error. Secondly, we introduce a new model for the segment allocation problem in which the segments are completely connected to each other by high-bandwidth links and contains a cost benefit for inter-segment traffic flows. We formulate this problem as an MILP and build exact solution approaches to solve large scale problems. We demonstrate some structural properties of the problem that make it solvable, using a Benders decomposition algorithm. Computational results validate the superiority of the decomposition approach.     

Optimal location of a single facility with circular demand areas

The single facility minimum location problem in Euclidean space has usually been studied with a certain number of discrete demand points. Some authors have also described the possibility of demand areas. In the present work, a new approach is offered to the optimal location of a single facility, which should serve a number of circular demand areas, each with uniform demand density, along with some discrete demand points. The effect of a circular demand area on the service facility at each stage of the Weiszfeld-like iterative procedure is evaluated for the three possible cases of the incumbent service point being outside, inside, or on the circumference of such a circle. Some limiting cases are considered, such as that of the demand area being very far from the service point to be optimally located. The amended Weiszfeld iterative procedure is described, and some numerical experience of solving such problems is reported.     

Integrated use of fuzzy c-means and convex programming for capacitated multi-facility location problem

In this study a fuzzy c-means clustering algorithm based method is proposed for solving a capacitated multi-facility location problem of known demand points which are served from capacitated supply centres. It involves the integrated use of fuzzy c-means and convex programming. In fuzzy c-means, data points are allowed to belong to several clusters with different degrees of membership. This feature is used here to split demands between supply centers. The cluster number is determined by an incremental method that starts with two and designated when capacity of each cluster is sufficient for its demand. Finally, each group of cluster and each model are solved as a single facility location problem. Then each single facility location problem given by fuzzy c-means is solved by convex programming which optimizes transportation cost is used to fine-tune the facility location. Proposed method is applied to several facility location problems from OR library (Osman & Christofides, 1994) and compared with centre of gravity and particle swarm optimization based algorithms. Numerical results of an asphalt producer’s real-world data in Turkey are reported. Numerical results show that the proposed approach performs better than using original fuzzy c-means, integrated use of fuzzy c-means and center of gravity methods in terms of transportation costs.     

Solving the constrained coverage problem

Coverage problem which is one of the challenging problems in facility location studies, is NP-hard. In this paper, we focus on a constrained version of coverage problem in which a set of demand points and some constrained regions are given and the goal is to find a minimum number of sensors which covers all demand points. A heuristic approach is presented to solve this problem by using the Voronoi diagram and p-center problem's solution. The proposed algorithm is relatively time-saving and is compared with alternative solutions. The results are discussed, and concluding remarks and future work are given.     

Aggregation without Loss of Optimality in Competitive Location Models

In the context of competitive facility location problems demand points often have to be aggregated due to computational intractability. However, usually this spatial aggregation biases the value of the objective function and the optimality of the solution cannot be guaranteed for the original model. We present a preprocessing aggregation method to reduce the number of demand points which prevents this loss of information, and therefore avoids the possible loss of optimality. It is particularly effective in the frequent situation with a large number of demand points and a comparatively low number of potential facility sites, and coverage defined by spatial nearness. It is applicable to any spatial consumer behaviour model of covering type. This aggregation approach is applied in particular to a Competitive Maximal Covering Location Problem and to a recently developed von Stackelberg model. Some empirical results are presented, showing that the approach may be quite effective. This research was partially supported by the projects OZR1067 and SEJ2005-06273ECON.     

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.     

Integrated mathematical optimisation approach for the tower crane hook routing problem to satisfy material demand requests on-site

Optimising decisions around the location and operation of tower cranes can improve the workflow in construction projects. Traditionally, the location and allocation problems involved in tower crane operations in the literature have been solved separately from the assignment of material supply points to demand points and the scheduling of the crane’s activity sequence across supply and demand points on a construction site. To address the gap, this paper proposes a binary integer programming problem, where location of the tower crane, allocation of supply points to material-demanding regions, and routing of hook of the crane based on activity sequencing of the hook across supply and material-demanding regions on site are optimised. The novelty in this work is in the way the crane’s activity scheduling is modelled via mathematical programming, based on routing the hook movement to meet material demand, through minimising tower crane operating costs. A realistic case study is solved to assess the validity of the model. The model is contrasted with results obtained from other solving algorithms commonly adopted in the literature, along with a solution proposed by an experienced practitioner. Results indicate that all instances can be solved when compared to other meta-heuristics that fail to achieve an optimum solution. Compared to the solution proposed by the practitioner, the results of the proposed model achieve a 46% improvement in objective function value. Planners should optimise decisions related to the location of the crane, the crane’s hook movement to meet service requests, and supply points’ locations and assignment to material-demanding regions simultaneously for effective crane operations.     

Large region location problems

The paper describes two algorithms for solving single facility location problems in which the planar assumption is not appropriate. Transformations on the non-Euclidean spherical space are combined with efficient solution techniques in Eⁿ. An example problem illustrates the possible magnitude of error due to a planar assumption for a non-Euclidean space. Due to the nature of the problem (non convexity) a local optimum is obtained. Some computational experience is reported.     

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.     

BEAMR: An exact and approximate model for the p-median problem

The p-median problem is perhaps one of the most well-known location–allocation models in the location science literature. It was originally defined by Hakimi in 1964 and 1965 and involves the location of p facilities on a network in such a manner that the total weighted distance of serving all demand is minimized. This problem has since been the subject of considerable research involving the development of specialized solution approaches as well as the development of many different types of extended model formats. One element of past research that has remained almost constant is the original ReVelle–Swain formulation [ReVelle CS, Swain R. Central facilities location. Geographical Analysis 1970;2:30–42]. With few exceptions as detailed in the paper, virtually no new formulations have been proposed for general use in solving the classic p-median problem. This paper proposes a new model formulation for the p-median problem that contains both exact and approximate features. This new p-median formulation is called Both Exact and Approximate Model Representation (BEAMR). We show that BEAMR can result in a substantially smaller integer-linear formulation for a given application of the p-median problem and can be used to solve for either an exact optimum or a bounded, close to optimal solution. We also present a methodological framework in which the BEAMR model can be used. Computational results for problems found in the OR_library of Beasley [A note on solving large p-median problems. European Journal of Operational Research 1985;21:270–3] indicate that BEAMR not only extends the application frontier for the p-median problem using general-purpose software, but for many problems represents an efficient, competitive solution approach.     

Efficient solution of a class of location–allocation problems with stochastic demand and congestion

We consider a class of location–allocation problems with immobile servers, stochastic demand and congestion that arises in several planning contexts: location of emergency medical clinics; preventive healthcare centers; refuse collection and disposal centers; stores and service centers; bank branches and automated banking machines; internet mirror sites; web service providers (servers); and distribution centers in supply chains. The problem seeks to simultaneously locate service facilities, equip them with appropriate capacities, and allocate user demand to these facilities such that the total cost, which consists of the fixed cost of opening facilities with sufficient capacities, the access cost of users׳ travel to facilities, and the queuing delay cost, is minimized. Under Poisson user demand arrivals and general service time distributions, the problem is set up as a network of independent M/G/1 queues, whose locations, capacities and service zones need to be determined. The resulting mathematical model is a non-linear integer program. Using simple transformation and piecewise linear approximation, the model is linearized and solved to ϵ-optimality using a constraint generation method. Computational results are presented for instances up to 400 users, 25 potential service facilities, and 5 capacity levels with different coefficients of variation of service times and average queueing delay costs per customer. The results indicate that the proposed solution method is efficient in solving a wide range of problem instances.     

Geometric complexity of some location problems

Given a set ofn demand points with weightW _i ,i = 1,2,...,n, in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An (n logn) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.Supported in part by the National Science Foundation under Grants ECS 83-40031 and DCR 84-20814.     

Modeling data envelopment analysis (DEA) efficient location/allocation decisions

Many types of facility location/allocation models have been developed to find optimal spatial patterns with respect to various location criteria that include cost, time, coverage, and access among others. In this paper we develop and test location modeling formulations that utilize data envelopment analysis (DEA) efficiency measures to find optimal and efficient facility location/allocation patterns. We believe that solving for the DEA efficiency measure, simultaneously with other location modeling objectives, provides a promising rich approach to multiobjective location problems.     

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.     

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.     

Aggregation method experimentation for large-scale network location problems

We present demand point aggregation procedures for the p-median and p-center network location models. A coarse aggregation structure is initially obtained by partitioning the demand points according to a grid imposed over the demand region. A “row-column’’ aggregation algorithm is used to determine the spacing of rows and columns of the grid to exploit the problem structure. A second step involves locating aggregate demand points on the subnetworks induced by the cells of the grid partitioning. The aggregate demand point set so obtained then defines an approximating location model; alternatively, it may initialize an iterative network location–allocation procedure to find the aggregate demand points. We have tested our procedures on data sets based on maps from the TIGER/Line database of the United States Census Bureau, and report on our computational experience.     

DisABC: A new artificial bee colony algorithm for binary optimization

Artificial bee colony (ABC) algorithm is one of the recently proposed swarm intelligence based algorithms for continuous optimization. Therefore it is not possible to use the original ABC algorithm directly to optimize binary structured problems. In this paper we introduce a new version of ABC, called DisABC, which is particularly designed for binary optimization. DisABC uses a new differential expression, which employs a measure of dissimilarity between binary vectors in place of the vector subtraction operator typically used in the original ABC algorithm. Such an expression helps to maintain the major characteristics of the original one and is respondent to the structure of binary optimization problems, too. Similar to original ABC algorithm, DisABC's differential expression works in continuous space while its consequence is used in a two-phase heuristic to construct a complete solution in binary space. Effectiveness of DisABC algorithm is tested on solving the uncapacitated facility location problem (UFLP). A set of 15 benchmark test problem instances of UFLP are adopted from OR-Library and solved by the proposed algorithm. Results are compared with two other state of the art binary optimization algorithms, i.e., binDE and PSO algorithms, in terms of three quality indices. Comparisons indicate that DisABC performs very well and can be regarded as a promising method for solving wide class of binary optimization problems.     

Error-bound driven demand point aggregation for the rectilinear distance p-center model

We present an algorithm for aggregating demand points for the rectilinear distance p-center problem. We solve, to optimality, two “projected” problems and then combine the solutions. The maximum objective function error between true and aggregated problems can be well predicted prior to solving the aggregated problem. We also report on our computational experience.