Search

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement– odd , even , or unconstrained –of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparseT-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem. [ABSTRACT FROM AUTHOR]

Given an n-vertex m-edge graph G of clique-width at most k, and a corresponding k-expression, we present algorithms for computing some well-known centrality indices (eccentricity and closeness) that run in O (2 O (k) (n + m) 1 + ϵ) time for any ϵ > 0 . Doing so, we can solve various distance problems within the same amount of time, including: the diameter, the center, the Wiener index and the median set. Our run-times match conditional lower bounds of Coudert et al. (SODA'18) under the Strong Exponential-Time Hypothesis. On our way, we get a distance-labeling scheme for n-vertex m-edge graphs of clique-width at most k, using O (k log 2 n) bits per vertex and constructible in O ~ (k (n + m)) time from a given k-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on k in their scheme. As a corollary, we get an O ~ (k n 2) -time algorithm for computing All-Pairs Shortest-Paths on n-vertex graphs of clique-width at most k, being given a k-expression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with non-negative vertex-weights, under two different types of distances studied in the literature. For that, we introduce a new type of orthogonal range query as a side contribution of this work, that might be of independent interest. [ABSTRACT FROM AUTHOR]

Pursuing the overarching goal of saving both lives and healthcare costs, we introduce an approach to increase the expected participation in a preventive healthcare program, e.g., breast cancer screening. In contrast to sick people who need urgent medical attention, the clients in preventive healthcare decide whether to go to a specific facility (if this maximizes their utility) or not to take part in the program. We consider clients' utility functions to include decision variables denoting the waiting time for an appointment and the quality of care. Both variables are defined as functions of a facility's utilization. We employ a segmentation approach to formulate a mixed-integer linear program. Applying GAMS/CPLEX, we optimally solved instances with up to 400 demand nodes and 15 candidate locations based on both artificial data as well as in the context of a case study based on empirical data within one hour. We found that using a Benders decomposition of our problem decreases computational effort by more than 50%. We observe a nonlinear relationship between participation and the number of established facilities. The sensitivity analysis of the utility weights provides evidence on the optimal participation given a specific application (data set, empirical findings). [ABSTRACT FROM AUTHOR]

This paper considers the problem of router node placement (WMN-RNP) in wireless mesh networks (WMN). A wireless mesh network consists of three kinds of nodes: mesh clients, mesh routers and gateways interconnected via radio links. The problem considered in this paper is the following: given a set of mesh clients deployed in a rectangular area, determine the best placement of mesh routers so that both client coverage and network connectivity are maximized. This issue is known to be NP-hard since it can be modeled as a facility location problem. To solve this issue, we propose to use a metaheuristic technique inspired from the interactions between molecules in chemical reactions to reach a low stable energy state, namely Chemical Reaction Optimization algorithm (CRO). A simulation tool has been developed to compare the performance of our CRO algorithm to the existing Genetic Algorithm (GA) and Simulated Annealing (SA). Simulation results show that our proposed algorithm can improve client coverage by 4.5% to 18% (3% to 17% respectively) and network connectivity by 5% to 61% (4.5% to 41% respectively) when compared to GA algorithm (SA algorithm respectively). [ABSTRACT FROM AUTHOR]

The delineation of the transportation network is a strategic issue for all over the place. The problem of locating new facilities among several existing facilities and minimizing the total transportation cost are the main topics of the location network system. This paper addresses the transportation-p-facility location problem (T-p-FLP) which makes a connection between the facility location problem and the transportation problem, where p corresponds to the number of facilities. The T-p-FLP is a generalization of the classical transportation problem in which we have to seek where and how we impose the p-number of facilities such that the total transportation cost from existing facility sites to the potential facility sites will be minimized. The exact approach, based on the iterative procedure, and a heuristic approach as applied to the T-p-FLP are discussed and corresponding results are compared. An experimental example is incorporated to explore the efficiency and effectiveness of our proposed study in reality. Finally, a summary is given together with suggestions for future studies. [ABSTRACT FROM AUTHOR]

Determining the best location to serve companies' profitability and sustainability is becoming more crucial every day, since the rivalry between companies is getting more intense. The transformation of economies from manufacturing orientation towards service based activities has resulted in a growing contribution of the service based economy in gross domestic product and workforce of developing countries. These recent changes in the economy are indicators that service facility related location science has received greater interest. Service location problems has been studied since the 1900s and interest on these types of problems has started to grow especially after the aforementioned economic transformation in the 2000s. A large number of problems have been investigated for different service facilities. However, there is a need for a survey that systematically classifies these papers in order to comprehend them thoroughly due to their prominence and complexity. This paper examines 90 papers that have been published on service facility location problems since 2000. The paper presents a classification based on 19 main characteristics including key features and descriptive dimensions of location problems in order to develop a taxonomy from an operations research perspective to assist the location scientists and practitioners who work on service facility location problems. Furthermore, service facility location problems are categorized according to their application fields and investigated in detail relating to each characteristic. We also draw interesting comparisons of characteristics between facility location problems in different application fields and highlight directions for future research. [ABSTRACT FROM AUTHOR]

We aim to design an effective supply chain network for a blood distribution system to satisfy the needs of hospitals in a certain region. In the analyzed current system, each hospital keeps a certain level of inventory, received at certain time periods by the shipments from a main blood bank. We propose an alternative system, in which some of the hospitals are selected as local blood banks (LBB) and all other hospitals will be assigned to an LBB. More frequent shipments will be made from LBBs to these hospitals, leading to lower inventory levels to be kept at each hospital. The inventories kept separately at the hospitals in the current system will be pooled at the selected LBBs in the proposed system. We develop a mixed integer nonlinear programming (MINLP) model to determine the optimal selection of LBBs, assignment of hospitals to LBBs, optimal inventory levels at each LBB and routing decisions among the facilities in order to minimize total system costs. We also propose a piecewise linear approximation method and a simulated annealing heuristic approach to find the solution of this problem. The proposed model and the solution techniques are applied on a real life case study for the blood distribution network in Istanbul. It is observed that significant improvements can be obtained by the proposed system when compared to the current design. Performances of the solution methods are also compared and a sensitivity analysis related to system parameters is presented via detailed numerical experiments. [ABSTRACT FROM AUTHOR]

Determining optimum places for the facilities and optimum transportation from existing sites to the facilities belongs to the main problems in supply chain management. The solid transportation-p-facility location problem (ST-p-FLP) is an integration between the facility location problem and the solid transportation problem (STP). This paper delineates the ST-p-FLP, a generalization of the classical STP in which location of p-potential facility sites are sought so that the total transportation cost by means of conveyances from existing facility sites to potential facility sites will be minimized. This is one of the most important problems in the transportation systems and the location research areas. Two heuristic approaches are developed to solve such type of problem: a locate-allocate heuristic and an approximate heuristic. Thereafter, the performance of the proposed model and the heuristics are evaluated by an application example, and the obtained results are compared. Moreover, a sensitivity analysis is introduced to investigate the resiliency of the proposed model. Finally, conclusions and an outlook to future research works are provided. [ABSTRACT FROM AUTHOR]

In traditional facility location recommendations, the objective is to select the best locations which maximize the coverage or convenience of users. However, since users' behavioral habits are often influenced by time, the temporal impacts should not be neglected in recommendation. In this paper, we study the problem of time-aware facility location recommendation problem, taking the time factor into account. To solve this problem, we develop a framework, TAILOR, which incorporates the temporal influence, user-coverage, and user-convenience. Based on TAILOR, we derive a greedy algorithm with (1- 1 e )-approximation and an online algorithm with ( 1 4 )-competitive ratio. Extensive experimental evaluation and two case studies demonstrate the efficiency and effectiveness of the proposed approaches. [ABSTRACT FROM AUTHOR]

This paper presents a first continuous, linear, conic formulation for the discrete ordered median problem (DOMP). Starting from a binary, quadratic formulation in the original space of location and allocation variables that are common in location analysis (L.A.), we prove that there exists a transformation of that formulation, using the same space of variables, that allows us to cast DOMP as a continuous, linear programming problem in the space of completely positive matrices. This is the first positive result that states equivalence between the family of continuous, convex problems and some hard combinatorial problems in L.A. The result is of theoretical interest because it allows us to share the tools from continuous optimization to shed new light into the difficult combinatorial structure of the class of ordered median problems that combines elements of the p-median, quadratic assignment and permutation polytopes. [ABSTRACT FROM AUTHOR]

In the leader-follower, (r|p)-centroid or Stackelberg location problem, two players sequentially enter the market and compete to provide goods or services. This paper considers this competitive facility location problem in a discrete space. To solve it, the linear programming formulations for the leader and the follower are integrated into an algorithm which, in an iterative process, finds a solution by solving a sequence of these linear problems. We propose a matheuristic procedure that provides solutions for the leader via a kernel search algorithm. Taking into account binary and S-shaped customer choice rules, we present the computational results obtained and compare the exact algorithm with two versions of the kernel search procedure. [ABSTRACT FROM AUTHOR]

We study a facility location problem where a single facility serves multiple customers each represented by a (possibly non-convex) region in the plane. The aim of the problem is to locate a single facility in the plane so that the maximum of the closest Euclidean distances between the facility and the customer regions is minimized. Assuming that each customer region is mixed-integer second order cone representable, we firstly give a mixed-integer second order cone programming formulation of the problem. Secondly, we consider a solution method based on the Minkowski sums of sets. Both of these solution methods are extended to the constrained case in which the facility is to be located on a (possibly non-convex) subset of the plane. Finally, these two methods are compared in terms of solution quality and time with extensive computational experiments. [ABSTRACT FROM AUTHOR]

The median problem on a graph is an important field of facility location problem in which the aim is to find the best place among vertices and interior points of edges such that the summation of weighted distances are minimized. This point is called absolute median point. Beforehand, it was shown that the absolute median of a graph is always at a vertex of it. This theorem is called vertex optimality theorem. In this paper, a graph with fuzzy weights is considered. Then, the fuzzy vertex optimality theorem is proved for this problem. That is, it is proved that an absolute median of this fuzzy graph is always at a vertex of it. Thereafter, this theorem is proved for the general form problem where the weights of vertices and the lengths of the arcs are all fuzzy numbers. It is worthwhile to note that this is the first time that this theorem is proved for fuzzy location problems. Also, by proving this fuzzy theorem and applying it on existing algorithms for obtaining median point, the computational complexity is reduced. Finally, by solving some numerical examples, the concept of these proved theorems and their proofs are illustrated. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of mesh router placement in a wireless mesh network (WMN). The latter is an emerging networking technology consisting of three kinds of nodes: mesh clients, mesh routers and gateways. Mesh routers form a backbone to forward data between client nodes and the external network. Therefore, the optimization of mesh routers positions strongly influences the performance of the WMN. Since this issue has already been proved as being computationally NP-hard to solve, the use of non-exact methods (such as heuristics and metaheuristics) is indispensable. In this sense, our current work consists to apply and adapt the electromagnetism-like mechanism (EM) metaheuristic to solve the router node placement issue. The idea is to consider a population of solutions encoded as particles subject to attractions and repulsions as in electromagnetic systems. Finally, we have evaluated our proposed approach by simulating different scenarios under various settings. The obtained results indicate that the proposed EM algorithm outperforms the existing particle swarm intelligence algorithm and genetic algorithm in defining near optimal positions for mesh routers with regard to coverage and connectivity. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new variant of the p-median facility location problem in which it is assumed that the exact location of the potential facilities is unknown. Instead, each of the facilities must be located in a region around their initially assigned location (the neighborhood). In this problem, two main decisions have to be made simultaneously: the determination of the potential facilities that must be open to serve the customers' demand and the location of the open facilities in their neighborhoods, at global minimum cost. We present several mixed integer non-linear programming formulations for a wide family of objective functions which are common in Location Analysis: ordered median functions. We also develop two math-heuristic approaches for solving the problem. We report the results of extensive computational experiments. [ABSTRACT FROM AUTHOR]

In this paper we deal with the planar location problem with forbidden regions. We consider the median objective with block norms and show that this problem is APX-hard, even when considering the Manhattan metric as distance function and polyhedral forbidden areas. As direct consequence, the problem cannot be approximated in polynomial time within a factor of 1.0019, unless P = N P . In addition, we give a dominating set that contains at least one optimal solution. Based on this result an approximation algorithm is derived. For special instances it is possible to improve the algorithm. These instances include problems with bounded forbidden areas and a special structure as interrelation between the new facilities. For uniform weights, this algorithm becomes an FPTAS. [ABSTRACT FROM AUTHOR]

Facility location allocation is key to success of urban design, mainly in designing transport systems, finding locations for warehouse, fire stations and so on. The problem of determining locations of k facilities so that provides service to n customers, also known as p-median problems, is one of the well-known NP-hard problems. Several heuristics have been proposed to solve location allocation problems, each of which has several limitations such as accuracy, time and flexibility, besides their advantages. In this paper, we propose to solve the p-median problems using crowdsourcing and gamification techniques. We present a crowdsourced game, called SolveIt, which employs wisdom and intelligence of the crowd to solve location allocation problems. We have presented a data model for representing p-median problems, designed and implemented the game and tested it using gold standards generated using a genetic algorithm tool. We have also compared the results obtained from SolveIt with the results of a well-known approach called Cooper. The evaluations show the accuracy and superiority of the results obtained from SolveIt players. We have also discussed the limitations and possible applications of the proposed approach. [ABSTRACT FROM AUTHOR]

We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to an open facility. Furthermore, capacities of the edges can be purchased in discrete units from K different cable types with costs that satisfy economies of scale. We extend the linear programming framework of Talwar (IPCO 2002) for the single-source buy-at-bulk problem to these variants and prove integrality gap upper bounds for both facility location and connected facility location buy-at-bulk problems. For the unconnected variant we prove an integrality gap bound of O(K), and for the connected version, we get the first LP-based bound of O(1). [ABSTRACT FROM AUTHOR]

We consider the stochastic queue core problem on a tree network. Our aim is to find an optimal path on a tree network subject to the average travel time of particles moving along the tree for service given by a server traversing along the optimal path. We assume that particles originating at a node on a tree network request their demands for service randomly and the server is modeled first by an M/M/1 and then by an M/G/1 queue using the FIFO discipline. We consider that all paths along which the particles travel are modeled with an M/G/c/c state-dependent queue with the particles being independent of each other having demands according to the Poisson distribution. Two algorithms are developed for computing the optimal path on a tree network along with the M/M/1 and the M/G/1 queues. The computational complexity of the algorithms and illustrative numerical results obtained by implementations of the algorithms in MATLAB software environment are given. [ABSTRACT FROM AUTHOR]

In the Preventive Healthcare Network Design Problem (PHNDP), one seeks to locate facilities in a way that the uptake of services is maximised given certain constraints such as congestion considerations. We introduce the incremental and cooperative version of the problem, IC-PHNDP for short, in which facilities are added incrementally to the network (one at a time), contributing to the service levels. We first develop a general non-linear model of this problem and then present a method to make it linear. As the problem is of a combinatorial nature, an efficient Variable Neighbourhood Search (VNS) algorithm is proposed to solve it. In order to gain insight into the problem, the computational studies were performed with randomly generated instances of different settings. Results clearly show that VNS performs well in solving IC-PHNDP with errors not more than 1.54%. [ABSTRACT FROM AUTHOR]

In this paper, the multi-product facility location problem in a two-stage supply chain is investigated. In this problem, the locations of depots (distribution centres) need to be determined along with their corresponding capacities. Moreover, the product flows from the plants to depots and onto customers must also be optimised. Here, plants have a production limit whereas potential depots have several possible capacity levels to choose from, which are defined as multilevel capacities. Plants must serve customer demands via depots. Two integer linear programming (ILP) models are introduced to solve the problem in order to minimise the fixed costs of opening depots and transportation costs. In the first model, the depot capacity is based on the maximum number of each product that can be stored whereas in the second one, the capacity is determined by the size (volume) of the depot. For large problems, the models are very difficult to solve using an exact method. Therefore, a matheuristic approach based on an aggregation approach and an exact method (ILP) is proposed in order to solve such problems. The methods are assessed using randomly generated data sets and existing data sets taken from the literature. The solutions obtained from the computational study confirm the effectiveness of the proposed matheuristic approach which outperforms the exact method. In addition, a case study arising from the wind energy sector in the UK is presented. [ABSTRACT FROM AUTHOR]

We consider the issue of choosing a subset of locations to construct new housing developments maximizing the satisfaction of potential buyers, which has not been previously studied in the literature. The allocation of demands to the selected locations is modeled by a choice model, based on the distance to the location, real-estate prices and incomes. We study two robust counterparts of the optimal location problem, where uncertainty lies on demand volumes for the first one, and on customer preferences for the second one. In both cases, the parameters subject to uncertainty appear both in the objective function and constraints. The second robust model combines a scenario-based approach with nominal, price-centric and distance-centric scenarios on customers preferences, and an uncertainty budget approach that limits the number of customers that can deviate from the nominal scenario. We show that the subproblem of finding the worst-case deviation of parameters subject to uncertainty is tractable and leads to linear formulations of the robust problem. Computational experiments conducted on instances of the Paris region show that the average loss of value of the robust solution is reasonably low when compared to the optimal solution of deviated instances. We also derive insights for the new housing development issue. [ABSTRACT FROM AUTHOR]

k-median and facility location problems are classical NP-hard combinatorial optimization problems. Although there are many experimental studies on them, their theoretical results are relatively few. This paper mainly contributes to investigating the approximation performance of two evolutionary algorithms for the k-median and facility location problems from a theoretical perspective. For k-median problem, we show that the evolutionary algorithms with standard bit mutation (SBM) operator can obtain approximation ratios 5 and 3+2/p in expected polynomial time while the evolutionary algorithm with somatic contiguous hypermutation (CHM) operator cannot obtain them. For facility location problem, we show that the evolutionary algorithms with SBM operator can obtain approximation ratio 3 in expected polynomial time while the evolutionary algorithm with CHM operator cannot obtain it. Further, we prove that on a facility location instance the evolutionary algorithm with CHM operator greatly outperforms the evolutionary algorithm with SBM operator. [ABSTRACT FROM AUTHOR]

This paper considers a family of bi-objective discrete facility location problems with a cost objective and a bottleneck objective. A special case is, for instance, a bi-objective version of the (vertex) p-centdian problem. We show that bi-objective facility location problems of this type can be solved efficiently by means of an ε-constraint method that solves at most (n-1)·m minisum problems, where n is the number of customer points and m the number of potential facility sites. Additionally, we compare the approach to a lexicographic ε-constrained method that only returns efficient solutions and to a two-phase method relying on the perpendicular search method. We report extensive computational results obtained from several classes of facility location problems. The proposed algorithm compares very favorably to both the lexicographic ε-constrained method and to the two phase method. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a variant of the reverse obnoxious center location problem on a tree graph T=(V,E) in which a selective subset of the vertex set V is considered as locations of the existing customers. The aim is to augment or reduce the edge lengths within a given budget with respect to modification bounds until a predetermined undesirable facility location becomes as far as possible from the customer points under the new edge lengths. An O(|E|2) time combinatorial algorithm is developed for the problem with arbitrary modification costs. For the uniform-cost case, one obtains the improved O(|E|) time complexity. Moreover, optimal solution algorithms with O(|E|2) and O(|E|) time complexities are proposed for the integer version of the problem with arbitrary and uniform cost coefficients, respectively. [ABSTRACT FROM AUTHOR]

Knapsack median is a generalization of the classic k-median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known algorithms in several ways, including adding randomization and applying sparsification as a preprocessing step. The latter improvement produces the first LP for this problem with bounded integrality gap. The new algorithm obtains an approximation factor of 17.46. We also give a 3.05 approximation with small budget violation. [ABSTRACT FROM AUTHOR]

In this paper, a new bi-objective hub facility location problem is studied where the demands of customers are stochastic and follow a normal distribution function. The first objective is to minimize total amount of value at risk which has a new probabilistic criterion and optimizes amount of lost demand. In addition, the second objective minimizes total costs of the network. Furthermore, some constraints are nonlinear in this model and it is aimed to linearize them by efficient approximate procedures. This paper tries to apply three efficient solution procedures to solve the bi-objective model. Thus, three algorithms are $$\varepsilon $$ -constraint, non-dominated sorting genetic algorithm-II (NSGA-II), and multi-objective particle swarm optimizers (MOPSO) which are creativity ways used in this paper to approximate the Pareto-optimal solutions. Taguchi experimental design is used to find the right parameter settings for metaheuristic algorithms. A comparative study of three proposed algorithms demonstrates the most effectiveness algorithm with respect to five existing performance measures for numerous test problems. Finally, the comparison within each two algorithms is completed by applying multiple statistical tests and diagrams. The obtained solutions by MOPSO are better than NSGA-II at 95 % confidence level. [ABSTRACT FROM AUTHOR]

In this work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based $$(3+\epsilon )$$ -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a $$ (4+ 1/ (e-1) +\epsilon )$$ -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately. [ABSTRACT FROM AUTHOR]

The application of facility location problems in choosing the best location of relief distribution centers plays a salient role in emergency operations of large-scale disasters. On the premise that the service recipients are uniformly distributed along the network edges, this study investigates a combined mobile and immobile pre-earthquake facility location problem. A predefined number of locations are to be selected among a set of potential locations. Each facility is used in the relief distribution operation. It is incontrovertible that due to earthquakes, some network edges collapse and corresponding areas may lose their accessibility. Thus in this study, it is assumed that people on intact and accessible edges travel to the location of the distribution centers to receive the relief. For those who are located on collapsed or inaccessible network edges, the medium-scale unmanned aerial vehicle (UAV) helicopters are utilized in the relief distribution operation. This study aims to develop a mathematical model which minimizes the aggregate traveling time for both people and UAVs over a set of feasible scenarios. Since the network problems are NP-hard, some metaheuristic algorithms are developed to solve the proposed model. In order to demonstrate the applicability of developed model, a case study based on feasible earthquake scenarios in Tehran is presented. [ABSTRACT FROM AUTHOR]

In this paper a two-stage optimization model is studied to find the optimal location of new facilities and the optimal partition of the consumers (location-allocation problem). The social planner minimizes the social costs, i.e. the fixed costs plus the waiting time costs, taking into account that the citizens are partitioned in the region according to minimizing the capacity costs plus the distribution costs in the service regions. By using optimal transport tools, existence results of solutions to the location-allocation problem are presented together with some examples. [ABSTRACT FROM AUTHOR]

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function $$f_i(z)$$ . In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a ( $$7.88+\epsilon $$ )-approximation local search algorithm for this problem. [ABSTRACT FROM AUTHOR]

Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack et al. (Discrete Comput Geom 4(1): 611-626, 1989) showed an $$O(n\log n)$$ -time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem. [ABSTRACT FROM AUTHOR]

This work considers the problem of locating $$p$$ facilities on the nodes of a path such that the range of the weights assigned to facilities will be as small as possible. We present a polynomial progressive search algorithm to solve the problem. [ABSTRACT FROM AUTHOR]

Agglomeration of facilities that compete with each other is common in practice, which suggests the existence of forces driving facilities to locate in clusters. Shopping centers and food courts are everyday examples. Although these agglomeration forces have been adequately analyzed and explained in the economic literature, operational research location models have not taken them into consideration as of today. This is particularly troublesome, as locations prescribed by these models are rather dispersed, which is in blatant disagreement with the examples that can be observed in real life. We present a selective review of the economic literature dealing with agglomeration forces acting in a linear market, classifying these forces into weak and strong. This paper demonstrates the sensitivity of competitive location models with respect to some assumptions that cause agglomeration or dispersion. [ABSTRACT FROM AUTHOR]

We consider the facility location problem for an expanding chain which competes with other chains offering the same goods or service in a geographical area. Customers are supposed to select the facility with maximum utility to be served and facilities in the expanding chain may have different owners. We first use the weighted method to develop an integer linear programming model to obtain Pareto optimal locations related to the inner competition between the owners of the old facilities and the owners of the new facilities. This model is applied to maximizing the profit of the expanding chain taking into account the loss in market share of its old facilities caused by the entering of new facilities (cannibalization effect). A study with data of Spanish municipalities shows that the cannibalization effect can be significantly reduced by sacrificing a small portion of profit. [ABSTRACT FROM AUTHOR]

In this paper we extend the Rectilinear 1- center problem as follows: given a set $$S$$ of $$n$$ demand points in the plane, simultaneously locate a facility point $$f$$ and a rapid transit line (i.e. highway) $$h$$ that together minimize the expression $$\max _{p\in S}T_{h}(p,f)$$ , where $$T_{h}(p,f)$$ denotes the travel time between $$p$$ and $$f$$ . A point of $$S$$ uses $$h$$ to reach $$f$$ if $$h$$ saves time: every point $$p\in S$$ moves outside $$h$$ at unit speed under the $$L_1$$ metric, and moves along $$h$$ at a given speed $$v>1$$ . We consider two types of highways: (1) a turnpike in which the demand points can enter/exit the highway only at the endpoints; and (2) a freeway problem in which the demand points can enter/exit the highway at any point. We solve the location problem for the turnpike case in $$O(n^2)$$ or $$O(n\log n)$$ time, depending on whether or not the highway's length is fixed. In the freeway case, independently of whether the highway's length is fixed or not, the location problem can be solved in $$O(n\log n)$$ time. [ABSTRACT FROM AUTHOR]

In this paper we propose a stochastic model for the location of emergency facilities. The model is formulated and analyzed. The location of one facility in the plane is optimally solved. Optimal algorithms are proposed for the location of multiple facilities on a network. Computational experiments illustrate the effectiveness of these solution procedures. [ABSTRACT FROM AUTHOR]

We investigate sequential location of two facilities. One strategy is to locate the first facility at its single facility optimum. A second strategy is to randomly locate the first facility. The second facility is then located at its optimal location given the first facility's location. We investigate which of these two strategies is better. Three objectives are tested: minisum, minimax, and competitive. We considered three environments: uniform demand in a square, discrete demand in the plane, and demand at nodes of a network. For the competitive objective we obtained what might be considered the expected result of locating the first facility optimally is better. For the minisum and minimax objectives, we found a surprising result: it is better to locate the first facility at random. We investigate the reasons behind these results which support the principle of add-heuristics and the greedy randomized adaptive search procedure where the search does not necessarily select the best solution in a greedy sequential approach. [ABSTRACT FROM AUTHOR]

The usage of the Internet has grown substantially in recent times. This has resulted in high volumes of data traffic. There is a concomitant rise in bandwidth demands that could result in excessive download delays (or latency). Thus, a single-server system is no more a prudent choice for data storage. Replication of content and placing them on multiple servers is a method that is used to reduce latency. However, this solution comes at a huge cost. Moreover, replicating objects randomly does not necessarily improve system performance. It is possible to arrive at a solution to the problem of placing content so as to achieve better cost performance. Other performance measures include latency, load balancing and data availability. We refer to the problem of locating content as data location problem in information networks, or DLPIN. The choice of server locations, query routing strategy and user assignment are some of the important problems that require attention along with the location of the data/content. Resource constraints and the nature of traffic (static/dynamic) are two important parameters in the problem environment, and therefore are key distinguishing features in the models. The main contribution of this paper is a novel classification and study of DLPIN on the basis of problem features. The research in this area started with files, the smallest units of allocation. Gradually, files and programs, database segments and entire databases (or mirrors) have been studied. We design examples from these use cases to elaborate a variety of problems in a comprehensive review. Facility location models from physical logistics are extensively used to model these problems. Our paper presents a literature survey of such mathematical models for data location problems. We present a gap analysis that provides pointers to possible future research in this area. This paper also serves to document the success in the use of mathematical programming approaches for data location in information networks. [ABSTRACT FROM AUTHOR]

There has been a number of facility location problems dealing with the introduction of the equity issue in the travel distances distribution. In this paper we analyze a new aspect of equity concerning the distribution of the arrival times of customers. Given a depot and a set of demand points generating flow which also represent potential locations, we consider a discrete two-stage location problem whose aim is to locate a given number of facilities and to allocate the demand points to a facility. We assume as objective the maximization of the minimum difference between two consecutive arrival times of flows to the depot through the patronized facility. This particular equity measure is introduced in order to reduce risks of congestion in the dynamic of flow arrivals at the common destination. The problem is described through two Integer Programming formulations. Computational results for solution methods based on both formulations are then shown and analyzed. [ABSTRACT FROM AUTHOR]

We investigate the quality of Condorcet solutions when compared to a central decision maker solution in the context of a facility location model in the plane. We perform an extensive set of experiments and conclude that if each population member votes according to his/her own self interest, then the Weber objective at the Condorcet solution point is very close to the optimal Weber objective value. Reducing the set of voters has little impact on the quality of the Condorcet solution. Being short of a good candidate has some impact but the final decision is still a good one. The distance metric seems to be of little relevance as well. As long as candidates are diverse, the Condorcet solution results in a good decision when compared to the decision by a benevolent dictator. [ABSTRACT FROM AUTHOR]

We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007; Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 Oct 2005, Pittsburgh, PA, USA, 2005; Nagarajan and Williamson in Discret Optim 10(4):361-370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an $$O\left( \log (mK)\log n\right) $$ -competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361-370, 2013) gave an $$O\left( K\log n\right) $$ -competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of $$O\left( l_{\text {max}} \log l_{\text {max}} \right) $$ (with the maximal lease length $$l_{\text {max}} $$ ). For many natural problem instances, the bound improves to $$O\left( K^2\right) $$ . [ABSTRACT FROM AUTHOR]

In this note we study the general facility location problem with connectivity. We present an O( np )-time algorithm for the general facility location problem with connectivity on trees. Furthermore, we present an O( np)-time algorithm for the general facility location problem with connectivity on equivalent binary trees. [ABSTRACT FROM AUTHOR]

A version of the facility location problem (the well-known p-median minimization problem) and its generalization-the problem of minimizing a supermodular set function-is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the p-median minimization problem in terms of the production and transportation cost matrix is obtained. [ABSTRACT FROM AUTHOR]

Additive manufacturing (AM), or popular scientific 3D printing, disseminates in more and more production processes. This changes not only production processes themselves, e.g. by replacing subtractive production technologies, but AM will in all likelihood also impact the configuration of supply networks. Due to a more efficient use of raw materials, transportation relations may change and production sites may be relocated. How this change will look like is part of an ongoing discussion in industry and academia. However, quantitative studies on this question are scarce. In order to quantify the potential impact of AM on a two-stage supply network, we use a facility location model. The impact of AM on the production process is integrated into the model by varying resource efficiency ratios. We create a test data set of 700 instances. Features of this data set are, among others, different geographical clusters of source nodes, production nodes, and customer nodes. By means of a computational study, the impact of AM on the supply network structure is measured by four indicators. In the context of our experimental set-up, AM reduces the overall transportation costs of a supply network compared to subtractive production. However, the share of the transportation costs on the second stage of a supply network in the total costs increases significantly. Therefore, supply networks in which production sites and customer sites are closely spaced improve their cost-effectiveness stronger than other regional configurations of supply networks. [ABSTRACT FROM AUTHOR]

Metric uncapacitated facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. Capacitated facility location ( Cfl) is a generalization for which there are local-search-based constant-factor approximations, while there is no known compact relaxation with constant integrality gap. This paper produces, through a host of impossibility results, the first comprehensive investigation of the effectiveness of mathematical programming for metric capacitated facility location, with emphasis on lift-and-project methods. We show that the relaxations obtained from the natural LP at $$\varOmega (n)$$ levels of the semidefinite Lovász-Schrijver hierarchy for mixed programs, and at $$\varOmega (n)$$ levels of the Sherali-Adams hierarchy, have an integrality gap of $$\varOmega (n)$$ , where $$n$$ is the number of facilities, partially answering an open question of An et al. (Centrality of trees for capacitated k-center, ), Li and Svensson (Proceedings of 45th ACM Symposium on Theory of Computing, STOC '13. ACM, pp 901-910, ). For the families of instances we consider, both hierarchies yield at the $$n$$ th level an exact formulation for Cfl. Thus our bounds are asymptotically tight. Building on our methodology for the Sherali-Adams result, we prove that the standard Cfl relaxation enriched with the submodular inequalities of Aardal et al. (Math Oper Res 20:562-582, ), a generalization of the flow-cover valid inequalities, has also an $$\varOmega (n)$$ gap and thus not bounded by any constant. This disproves a long-standing conjecture of Levi et al (Math Program 131(1-2):365-379, ). We finally introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation and captures general configuration-style LPs. We characterize the behavior of proper relaxations for Cfl through a sharp threshold phenomenon. [ABSTRACT FROM AUTHOR]

The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a 'solver' applied to the initial MIP formulation, provided that 'small' optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This 'simplified' approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s). [ABSTRACT FROM AUTHOR]

This research introduces the multi-product capacitated facility location problem with general production and building costs (MP-CFLPGC). The MP-CFLPGC extends previous problems found in the literature by including multiple products and general production and building cost functions that allow the modeling of different behaviors like economies of scale and congestion. The MP-CFLPGC is formulated as a mixed integer linear program (MILP). To evaluate the performance of the proposed formulation we analyze the results of a commercial optimizer on a set of 288 randomly generated test instances that resemble the Colombian cement industry supply chain. After one hour the optimizer achieved an optimality gap of 1.0 % or less in 55 % out of the 288 test instances. On average the optimality gap was 3.57 %. Additionally, we propose a randomized mathematical-programming-based heuristic for the test instances where the MILP formulation presents significantly high optimality gaps. [ABSTRACT FROM AUTHOR]

We study a capacitated multi-facility location-allocation problem in which the customers have stochastic demands based on Bernoulli distribution function. We consider the capacitated sub-sources of facilities to satisfy demands of customers. In the discrete stochastic problem, the goal is to find optimal locations of facilities among candidate locations and optimal allocations of existing customers to operating facilities so that the total sum of fixed costs of operating facilities, allocation cost of the customers, expected values of servicing and outsourcing costs is minimized. The model is formulated as a mixed-integer nonlinear programming problem. Since finding an optimal solution may require an excessive amount of time depending on nonlinear constraints, we transform the nonlinear constraints of the problem to linear ones to arrive at a simple formulation of the model. Numerical results show that the LINGO 9.0 software is capable of solving small size problems. For medium and large-size problems, we propose two meta-heuristic algorithms, namely a genetic algorithm and a discrete version of colonial competitive algorithm. Computational results show that the proposed algorithms efficiently obtain effective solutions. [ABSTRACT FROM AUTHOR]

In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. This problem is motivated by its applications in many practical problems including supply chain problems of indivisible goods (Verter in Foundations of location analysis, chapter 2. International series in operations research and management science. Springer, Berlin, 2011) and the assignment problem in the content distribution networks (Bateni and Hajiaghayi in Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp 805-814, 2009). While there are several approximation algorithms for the soft capacitated version of this problem (in which one can open multiple copies of each facility) or the splittable version (in which the demand of each client can be divided to be served by multiple open facilities), there are very few results for the UCFLP. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria $$(\alpha ,\beta )$$ -approximations where the algorithm returns a solution whose cost is within factor $$\alpha $$ of the optimum and violates the capacity constraints within factor $$\beta $$ . Shmoys et al. (Proceedings of the twenty-ninth annual ACM symposium on theory of computing, pp 265-274, 1997) were the first to consider this problem and gave a (9, 4)-approximation. Later results imply ( O(1), 2)-approximations, however, no constant factor approximation is known with capacity violation of less than 2. We present a framework for designing bicriteria approximation algorithms for this problem and show two new approximation algorithms with factors (9, 3 / 2) and (29.315, 4 / 3). These are the first algorithms with constant approximation in which the violation of capacities is below 2. The heart of our algorithm is a reduction from the UCFLP to a restricted version of the problem. One feature of this reduction is that any $$(O(1),1+{\epsilon })$$ -approximation for the restricted version implies an $$(O(1),1+{\epsilon })$$ -approximation for the UCFLP and we believe our techniques might be useful towards finding such approximations or perhaps $$(f({\epsilon }),1+{\epsilon })$$ -approximation for the UCFLP for some function f. In addition, we present a quasi-polynomial time $$(1+\epsilon ,1+\epsilon )$$ -approximation for the (uniform) UCFLP in Euclidean metrics, for any constant $${\epsilon }>0$$ . [ABSTRACT FROM AUTHOR]