Multiple voting location and single voting location on trees

We examine voting location problems in which the goal is to place, based on an election amongst the users, a given number of facilities in a graph. The user preference is modeled by shortest path distances in the graph. A Condorcet solution is a set of facilities to which there does not exist an alternative set preferred by a majority of the users. Recent works generalize the model to additive indifference and replaced user majority by γ-proportion.     

Relaxed voting and competitive location under monotonous gain functions on trees

We examine competitive location problems where two competitors serve a good to users located in a network. Users decide for one of the competitors based on the distance induced by an underlying tree graph. The competitors place their server sequentially into the network. The goal of each competitor is to maximize his benefit which depends on the total user demand served. Typical competitive location problems include the (1,X₁)-medianoid, the (1,1)-centroid, and the Stackelberg location problem.An additional relaxation parameter introduces a robustness of the model against small changes in distance. We introduce monotonous gain functions as a general framework to describe the above competitive location problems as well as several problems from the area of voting location such as Simpson, Condorcet, security, and plurality.In this paper we provide a linear running time algorithm for determining an absolute solution in a tree where competitors are allowed to place on nodes or on inner points. Furthermore we discuss the application of our approach to the discrete case.     

Outcomes of voting and planning in single facility location problems

For a given set of users located at the vertices of a network N, we consider the location of a single facility. Two different decision making procedures, voting among the users and minimizing total distance travelled by the users, are compared.Provided that a voting solution exists, it is shown that the two solutions sets coincide if N is a so-called cactus. For general networks, the outcomes of the two procedures are compared in terms of the cyclic structure of N and the number of users.     

Min-Max payoffs in a two-player location game

We consider a two-player, sequential location game with arbitrarily distributed consumer demand. Players alternately select locations from a feasible set so as to maximize the consumer mass in their vicinity. Our main result is a complete characterization of feasible market shares, when locations form a finite set in R^d.     

Multiple criteria facility location problems: A survey

This paper provides a review on recent efforts and development in multi-criteria location problems in three categories including bi-objective, multi-objective and multi-attribute problems and their solution methods. Also, it provides an overview on various criteria used. While there are a few chapters or sections in different location books related to this topic, we have not seen any comprehensive review papers or book chapter that can cover it. We believe this paper can be used as a complementary and updated version.     

General network design: A unified view of combined location and network design problems

This paper presents a unified framework for the general network design problem which encompasses several classical problems involving combined location and network design decisions. In some of these problems the service demand relates users and facilities, whereas in other cases the service demand relates pairs of users between them, and facilities are used to consolidate and re-route flows between users. Problems of this type arise in the design of transportation and telecommunication systems and include well-known problems such as location-network design problems, hub location problems, extensive facility location problems, tree-star location problems and cycle-star location problems, among others. Relevant modeling aspects, alternative formulations and possible algorithmic strategies are presented and analyzed.     

Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach

Models developed to analyze facility location decisions have typically optimized one or more objectives, subject to physical, structural, and policy constraints, in a static or deterministic setting. Because of the large capital outlays that are involved, however, facility location decisions are frequently long-term in nature. Consequently, there may be considerable uncertainty regarding the way in which relevant parameters in the location decision will change over time. In this paper, we propose two approaches for analyzing these types of dynamic location problems, focussing on situations where the total number of facilities to be located in uncertain. We term this type of location problem NOFUN (Number Of Facilities Uncertain). We analyze the NOFUN problem using two well-established decision criteria: the minimization of expected opportunity loss (EOL), and the minimization of maximum regret. In general, these criteria assume that there are a finite number of decision options and a finite number of possible states of nature. The minisum EOL criterion assumes that one can assign probabilities for the occurrence of the various states of nature and, therefore, find the initial set of facility locations that minimize the sum of expected losses across all future states. The minimax regret criteria finds the pattern of initial facility locations whose maximum loss is minimized over all possible future states.     

Sequential competitive location on networks

We present a survey of recent developments in the field of sequential competitive location problems, including the closely related class of voting location problems, i.e. problems of locating resources as the result of a collective election. Our focus is on models where possible locations are not a priori restricted to a finite set of points. Furthermore, we restrict our attention to problems defined on networks. Since a line, i.e. an interval of one-dimensional real space, may be interpreted as a special type of network and because models defined on lines might contain ideas worth adopting in more general network models, we include these models as well, yet without describing them in detail for the sake of brevity.     

Some considerations concerning industrial location decisions

The approach most often followed by operations researchers when dealing with the problem of industrial location is based on the notion that very complex location decisions can be reduced into an algorithmic form involving few cost factors. In this they follow closely the orthodox location theory. Recently, there has been a growing dissatisfaction with the classical location theory. Empirical studies carried out during the past two decades tend to analyze a staggering and ever growing number of specific locational factors. The purpose of the study briefly reported on below was limited to an attempt to classify the numerous factors affecting location decisions and to reduce their numbers by grouping and deriving indexes. The validity of the indexes was tested by confronting them with the actual distribution of industries in the U.S.     

On the convergence of the Weiszfeld algorithm for continuous single facility location–allocation problems

A general family of single facility continuous location–allocation problems is introduced, which includes the decreasingly weighted ordered median problem, the single facility Weber problem with supply surplus, and Weber problems with alternative fast transportation network. We show in this paper that the extension of the well known Weiszfeld iterative decrease method for solving the corresponding location problems with fixed allocation yields an always convergent scheme for the location allocation problems. In a generic way, from each starting point, the limit point will be a locally minimal solution, whereas for each possible exceptional situation, a possible solution is indicated. Some computational results are presented, comparing this method with an alternating location–allocation approach. The research of the second author was partially supported by the grant of the Algerian Ministry of High Education 001BIS/PNE/ENSEIGNANTS/BELGIQUE.     

A heuristic for large-sizep-median location problems with application to school location

This paper initially proposes a heuristic algorithm for thep-median problem designed for large weighted graphs. The problem is approached through the construction ofp trees whose shapes are progressively modified according to successive tests over the stability of their roots and vertices. The algorithm seems promising because: (i) on a regular PC it can handle problems of the order of 500 vertices, while the mainframe version goes indefinitely further, (ii) contrary to what normally would be expected, execution times seem to be inversely proportional top, and even for large problems, they may be reasonable, especially ifp is large relative to the number of vertices, and (iii) it produces solutions of good quality and in most of the cases studied, it outperforms the traditional heuristic of Teitz and Bart. A real application of the algorithm embedded in a methodology to evaluate the location of 85 public schools, among 389 possible vertices, in the metropolitan area of Rio de Janeiro is reported. Results confirmed the conjecture of poor location and the procedure was able to identify several micro-regions simply void of schools. The methodology is being well received by the education authorities and its extension to the whole metropolitan area is being considered.     

Dynamic location problems

A class of dynamic location problems is introduced. The relationship between a static problem and its corresponding dynamic one is studied. We concentrate on two types of dynamic problems. The first is the global optimization problem, in which one looks for the all-times optimum. The second is the steady-state problem in which one seeks to determine the steady-state behavior of the system if one exists. General approaches to these problems are discussed.Supported in part by the National Science Foundation under grants MCS-8300984, ECS-8218181 and ECS-8121741.     

A note on two source location problems

We consider Source Location ($\mathsf{SL}$) problems: given a capacitated network $G=(V,E)$, cost $c(v)$ and a demand $d(v)$ for every $v\in V$, choose a min-cost $S\subseteq V$ so that $\lambda (v,S)⩾d(v)$ holds for every $v\in V$, where $\lambda (v,S)$ is the maximum flow value from v to S. In the directed variant, we have demands $d^{\mathit{in}}(v)$ and $d^{\mathit{out}}(v)$ and we require $\lambda (S,v)⩾d^{\mathit{in}}(v)$ and $\lambda (v,S)⩾d^{\mathit{out}}(v)$. Undirected $\mathsf{SL}$ is (weakly) NP-hard on stars with $r(v)=0$ for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected $\mathsf{SL}$ admit a $(\ln D+1)$-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected $\mathsf{SL}$ on trees with running time $O(|V|{\Delta }^3)$, where $\Delta ={\max }_{v\in V}d(v)$. This algorithm is used to derive a linear time algorithm for undirected $\mathsf{SL}$ with $\Delta ⩽3$. We also consider the Single Assignment Source Location ($\mathsf{SASL}$) where every $v\in V$ should be assigned to a single node $s(v)\in S$. While the undirected $\mathsf{SASL}$ is in P, we give a $(\ln |V|+1)$-approximation algorithm for the directed case, and show that this is tight, unless P = NP.     

Robust facility location

Let A be a nonempty finite subset of the plane representing the geographical coordinates of a set of demand points (towns, ), to be served by a facility, whose location within a given region S is sought. Assuming that the unit cost for aA if the facility is located at xS is proportional to dist(x,a) — the distance from x to a — and that demand of point a is given by _a , minimizing the total transportation cost TC(,x) amounts to solving the Weber problem. In practice, it may be the case, however, that the demand vector is not known, and only an estimator circ; can be provided. Moreover the errors in such estimation process may be non-negligible. We propose a new model for this situation: select a threshold value B>0 representing the highest admissible transportation cost. Define the robustness of a location x as the minimum increase in demand needed to become inadmissible, i.e. (x)=min{|–circ;|:TC(,x)>B,0} and find the x maximizing to get the most robust location. Acknowledgment.The authors acknowledge the constructive remarks of the referees. The research of the first author has been supported in part by grant BFM2002-04525-C02-02 of MCYT, Spain. The research of the second author has been supported in part by a grant of the Deutsche Forschungsgemeinschaft.     

A competitive hub location and pricing problem

We formulate and solve a new hub location and pricing problem, describing a situation in which an existing transportation company operates a hub and spoke network, and a new company wants to enter into the same market, using an incomplete hub and spoke network. The entrant maximizes its profit by choosing the best hub locations and network topology and applying optimal pricing, considering that the existing company applies mill pricing. Customers’ behavior is modeled using a logit discrete choice model. We solve instances derived from the CAB dataset using a genetic algorithm and a closed expression for the optimal pricing. Our model confirms that, in competitive settings, seeking the largest market share is dominated by profit maximization. We also describe some conditions under which it is not convenient for the entrant to enter the market.     

Rational ignorance and voting behavior

We model a two-alternative election in which voters may acquire information about which is the best alternative for all voters. Voters differ in their cost of acquiring information. We show that as the number of voters increases, the fraction of voters who acquire information declines to zero. However, if the support of the cost distribution is not bounded away from zero, there is an equilibrium with some information acquisition for arbitrarily large electorates. This equilibrium dominates in terms of welfare any equilibrium without information acquisition – even though generally there is too little information acquisition with respect to an optimal strategy profile.      

On the lexicographic minimax approach to location problems

When locating public facilities, the distribution of travel distances among the service recipients is an important issue. It is usually tackled with the minimax (center) solution concept. The minimax solution concept, despite the most commonly used in the public sector location models, is criticized as it does not comply with the major principles of the efficiency and equity modeling. In this paper we develop a concept of the lexicographic minimax solution (lexicographic center) being a refinement of the standard minimax approach to location problems. We show that the lexicographic minimax approach complies with both the Pareto-optimality (efficiency) principle (crucial in multiple criteria optimization) and the principle of transfers (essential for equity measures) whereas the standard minimax approach may violate both these principles. Computational algorithms are developed for the lexicographic minimax solution of discrete location problems.     

A comparative study of approaches to dynamic location problems

We compare the performance of seven approximate methods for locating new capacity over time to minimize the total discounted costs of meeting growing demands at several locations. Comparisons are based on results for two industrial planning problems from India, and are given for both discrete-time and continuous-time frameworks. We also discuss strategies for combining different methods into possibly more effective hybrid approaches.