Comparison of exact and approximate methods of solving the uncapacitated plant location problem

This study was prompted by a recently published article in this journal on facility location by D. R. Sule. We show that the claim made by Sule of a novel and extremely simple algorithm yielding optimum solutions is not true. Otherwise, the algorithm would represent a breakthrough in decision-making for which a number of notoriously hard problems could be efficiently recast as location problems and easily solved.In addition, several variants of common location problems addressed by Sule are reviewed. In the last twenty years, many methods of accurately solving these problems have been proposed. In spite of their increased sophistication and efficiency, none of them claims to be a panacea. Therefore, researchers have concurrently developed a battery of fast but approximate solution techniques. Sule's method was essentially proposed by Kuehn and Hamburger in 1963, and has been adapted many times since.We exhibit several examples (including the one employed by Sule) in which Sule's algorithms lead to nonoptimal solutions. We present computational results on problems of size even greater than those utilized by Sule, and show that a method devised by Erlenkotter is both faster and yields better results.In a cost-benefit analysis of exact and approximate methods, we conclude that planning consists of generating an array of corporate scenarios, submitting them to the “optimizing black box,” and evaluating their respective merits. Therefore, much is to be gained by eliminating the vagaries of the black box—that is, by using an exact method—even if the data collection and the model representation introduce sizable inaccuracies. Ironically, large problems (those that typically require most attention) cannot be solved exactly in acceptable computational times. Pending the imminent design of a new generation of exact algorithms, the best heuristics are those that guarantee a certain degree of accuracy of their solutions.     

Two planar facility location problems with high-speed corridors and continuous demand

The planar minisam (‘median’) and minimax (‘center’) facility location problems are examined under the assumptions that: demand is continuously and uniformly distributed: the L₁ (right-angle) metric is in use; and the planar region is traversed by a high-speed corridor (highway) running parallel to one of the directions of travel. For the minisum problem in a rectangular region, it is shown that, for any combination of problem parameters, there are only two candidate points in the region for the optimum location of the facility. This is also shown to be true for any convex and symmetric planar region. For the minimax problem in a rectangular region, there are only three candidate points for the optimal location. Some extensions and conjectures for the minisum problem involving more than one highway are also discussed.     

A goal programming model for facility location planning

The paper presents a goal programming model for facility location planning. Often the location-decision is coupled with multiple objectives, at times conflicting among themselves. Specifically the model considers the four major objectives: (i) necessary locations, (ii) maximum number of locations, (iii) capacity restrictions and (iv) transportation cost/walking distance minimization, simultaneously and proposes optimal locations in conjunction with the existing facilities in the region. The model developed has been illustrated with an example considering the location of community storage facilities in a specified region.     

Sequential facility location with distance dependent demand

Systems providing identical service to many population centers frequently face the issue of where to locate the next retail outlet, branch, store, etc. In such systems the demand for the facilities' service depends mainly on the distance between facilities and customers. It is assumed that there are already m facilities located on a network to respond to the demand at the nodes. The paper addresses the problems of finding a location on the network for the (m +1 )st facility corresponding to a given total expected demand and of determining which demand points will be served by which facility. Also the range of the total expected demand values that can be realized along each link in the m +1 facility system is determined. Examples and a discussion of the results are provided.     

Strategy-proofness and population-monotonicity for house allocation problems

We study a simple model of assigning indivisible objects to agents, such as dorm rooms to students, or offices to professors, where each agent receives at most one object and monetary compensations are not possible. For these problems population-monotonicity, which requires that agents are affected by population changes in the same way, is a compelling property because tentative assignments are made in many typical situations, which may have to be revised later to take into account the changing population. We completely describe the allocation rules satisfying population-monotonicity, strategy-proofness, and efficiency. The characterized rules assign the objects by an iterative procedure in which at each step no more than two agents “trade” objects from their hierarchically specified “endowments.”     

Including deprivation costs in facility location models for humanitarian relief logistics

Humanitarian assistance is meant to save lives and alleviate human suffering during and in the aftermath of man-made and natural disasters. To prevent and strengthen preparedness for the occurrence of such situations, having available relief supplies in the short-term becomes crucial. The lack of access to life-sustaining items implies a loss in people's welfare, treated as an externality called deprivation costs which must be incorporated into decision-making processes. Since typical humanitarian applications are extensions of commercial logistic models, they usually do not account for externalities, leading to high social costs and likely to unfeasible or suboptimal solutions.This paper develops a facility location model for prepositioning supplies in preparation for disasters; the key feature of this formulation being the fact that it explicitly considers deprivation costs in the objective function. The model attempts to minimize the global social costs, as the sum of both private costs (i.e. costs of transportation, inventory costs and fixed costs of facilities) and deprivation costs, determining the amount per type of product to be prepositioned for serving the areas affected by a disaster during the initial response. The model focuses on those assistance interventions that should be carried out immediately, i.e. within the first 24 h of a humanitarian crisis. We applied the model, using real information, to the Colombian Caribbean region, which was affected by floods in 2010 and 2011. Results demonstrate that deprivation costs represent more than 50% of the total social cost.     

A facility location problem with clients' preference orderings

The Simple Plant Location Problem (SPLP) consists in identifying a pattern of facilities among a set of potential sites so that the sum of the costs for opening the facilities and for supplying a group of geographically dispersed clients therefrom is minimized. It is posited in this framework that the locator rules on the allocation of the clients to the facilities. When the clients are free to decide upon which facility they will attend, their choices do not necessarily match the most economical supply pattern from the point of view of the locator. We suppose here that each client has a preference ordering on the list of potential sites whereby he determines his allocation out of any set of open facilities. This preference ordering depends on characteristics of the client, of the sites, and of the trip between the client's location and the sites. Mathematically, we translate the orderings into a set of constraints to be appended to the SPLP. This new problem, termed SPLPO, has a wide range of applications as shown by a series of examples. We present an algorithm for solving the SPLPO and extensive computational experiments are reported.     

A mechanism for package allocation problems with gross substitutes

We consider a package allocation problem in which a seller owns many indivisible objects and the rest of the agents, buyers, are interested in packages of these objects. Buyers’ valuations satisfy monotonicity and the gross substitutes condition (Kelso and Crawford, 1982). The aim of this paper is to analyze the following mechanism: simultaneously, each buyer requests to the seller a package by announcing how much he would pay for it; once buyers have played, the seller decides the final assignment of packages and the prices, as long as this assignment makes no buyer worse off than with his initial request. The subgame perfect equilibrium outcomes of the mechanism correspond to the Vickrey outcome (Vickrey, 1961) of the market.     

New results for multi-issue allocation problems and their solutions

Review of Economic Design - In this paper we present a different perspective than the more traditional approaches to study solutions for multi-issue allocation problems. This perspective is based...     

A paradigm for location and multidimensional problems in planning

Several theories, concepts, methods, or alternatively, “paradigms” have been suggested for the explanation and prediction of the location behavior of urban households. Increasingly, hwoever, “behavioral” approaches to the explanation of the dimensions of “choice” and/or exploration of alternative hypotheses have been cumbersome in the “mechanistic” paradigms of the social system and its related subsystems.An alternative paradigm of Analytic Hierarchy Process (AHP) is proposed to explore alternative structural specification hypotheses (sequential versus simultaneous) on the grouping and changing relative importance of “instrumental” and “non-instrumental” factors affecting location decision-making. AHP estimates of the “locational shares” of an urban (corridor) zonal population provide a paradigmatic basis for behavioral, vis-a-vis environmental, explanation of location decision-processes in a methodologically efficient, robust and theoretically inclusive framework of hierarchy systems.This paradigm is proposed for locational analysis requiring an effective integration of multilevel, environmental (contextual) and behavioral measures of relative importance, with limited data, and, for multidimensional problems in planning and policy-making, formidably requiring the integration of positive with normative analysis of systems.     

A healthcare facility location problem for a multi-disease,multi-service environment under risk aversion

This paper presents a stochastic optimisation model for locating walk-in clinics for mobile populations in a network. The walk-in clinics ensure a continuum of care for the mobile population across the network by offering a perpetuation of services along the transportation lines, and also establishing referral systems to local healthcare facilities. The continuum of care requirements for different diseases is modelled using coverage definitions that are designed specifically to reflect the adherence protocols for services for different diseases. The risk of not providing the required care under different realisations of health service demand is considered. In this paper, for a multi-disease, multi-service environment, we propose a model to determine the location of roadside walk-in clinics and their assigned services. The objective is to maximise the total expected weighted coverage of the network subject to a Conditional-Value-at-Risk (CVaR) measure. This paper presents developed coverage definitions, the optimisation model and the computational study carried out on a real-life case in Africa.     

Social enterprise factory location and allocation model: Small scale manufacturing for East Africa

The manufacturing location decision for social enterprises that work in the context of sustainable development is rarely based on a quantitative, analytical process. As a result, decisions may be far from profit-maximizing. Location and allocation optimization models have the potential to improve decisions and thus enable such enterprises to scale up their business as well as their impact. We develop and explain a single-period single-factory model, and also a two-echelon location and allocation model, to provide enterprises with information about optimal factory locations, and with future demand allocations and capacity-changing decision information. We apply the models to a company that manufactures and distributes solar cookers in East Africa. Our results illustrate that quantitative location and allocation models can significantly affect social enterprises by improving profitability. The case study shows strong cost-reduction potential of local manufacturing in developing countries due to high transportation costs for small production volumes. We discuss this model-recommended decision by weighing it against associated opportunities and risks. This paper aims to enable and encourage social and sustainability-oriented manufacturing enterprises to apply operations research methods in their strategic factory location decision-making.     

西方城市公共服务设施区位研究进展

通过梳理国外公共服务设施区位理论的发展以及近年来研究的新动向,提出了对我国城市公共服务设施区位研究的展望。     

声发射源定位技术的现状研究

声发射源定位是声发射检测技术的主要目标之一,其准确程度反映了声源的检测位置和实际活动缺陷源位置的符合程度。文章系统阐述了目前声发射定位的各种方法及其优缺点,并展望了声发射源定位技术的发展趋势。     

Integrating expected coverage and local reliability for emergency medical services location problems

Daskin's MEXCLP model [Daskin M. A maximum expected covering location model: formulation, properties, and heuristic solution. Transportation Science 1983;17:48-70] was one of the first efforts to capture the stochastic nature of emergency medical services (EMS) location problems within a mixed-integer formulation. With their subsequent introduction of MALP, ReVelle and Hogan [The maximum availability location problem. Transportation Science 1989;23:192-200] offered two key advances, local vehicle busyness estimates and the α-reliability objective. While these constructs have influenced many subsequent EMS location models, they have been subjected to relatively little empirical analysis. To address this, we introduce the LR-MEXCLP, a hybrid model combining the local busyness estimates of MALP with the maximum coverage objective of MEXCLP. We then solve a series of problems with all three models and employ simulation to estimate aggregate service levels. We find that LR-MEXCLP leads to modest but consistent service gains over both MALP and MEXCLP. These results support the merits of local busyness estimates, but they also suggest that the α-reliability objective may be inappropriate when seeking to maximize aggregate system response capabilities. More generally, our research underscores the utility of (a) linking modeling assumptions and goals with real-world application contexts, and (b) employing simulation or other techniques to validate theoretical results.     

Seat allocation distributions and seat biases of stationary apportionment methods for proportional representation

In a proportional representation system, apportionment methods are used to round the vote proportion of a party to an integer number of seats in parliament. Assuming uniformly distributed vote proportions, we derive the seat allocation distributions for stationary divisor methods. An important characteristic of apportionment methods are seat biases, that is, expected differences between actual seat numbers and ideal shares of seats, when the parties are ordered from largest to smallest. We obtain seat bias formulas for the stationary divisor methods and for the quota method of greatest remainders.Acknowledgement. We thank Friedrich Pukelsheim for many fruitful discussions.Received March 2004     

On Bayesian optimum allocation in some two phase sampling problems

Summary For estimating certain parametric functions, we consider the problem of allocatingN _i, the size of the sample from theith population,i=1,2,...,k, at the second phase of sampling of a two phase sampling procedure, given that we taken _i observations from the population at the first phase. We consider that the observations from theith population follow the exponential distribution with mean _i,i=1,2,...,k, and the functions to be estimated are (i) (d_i/_i) and (ii) (d_ii). When the total cost of sampling at the second phase is c _iN_i and is fixed, allocations using the Bayes approach are obtained so that the estimation is as precise as is possible.     

A comparison of approximately optimal stratification given proportional allocation with other methods of stratification and allocation

Summary In this article, we shall present an approximately optimal method for constructing stratum boundary points when the sample is allocated proportionally. The method is based on an equal partitioning of the cumulative off ^1/3, wheref is the distribution of the stratification variable. We show that in many practical situations this technique compares favourably with approximately optimal stratification and allocation methods previously suggested.

---

Zusammenfassung In diesem Artikel stellen wir eine annähernd optimale Methode zur Festlegung von Stratabegrenzungspunkten dar, die für proportional angeordnete Samples gilt. Die Methode basiert auf einer gleichen Einteilung derf ^1/3-Kummulation, wobeif die Verteilung der Stratifikations-variablen darstellt. Wir zeigen, daß diese Technik in vielen praktischen Fällen gegenüber den bisher vorgeschlagenen Methoden zur optimalen Stratifikation und Zuordnung nicht schlecht abschneidet.

     

Commentary on facility location in the presence of congested regions with the rectilinear distance metric

This paper is a commentary on the work of Butt and Cavalier (Socio-Econ. Plann. Sci. 31(2) (1997) 103), a paper that was published in an earlier issue of this journal. With the aid of an example problem, we demonstrate that the set of gridlines proposed by them to find the rectilinear least cost path between two points in the presence of convex polygonal congested regions is inadequate. We proceed to prove its adequacy for the case of rectangular congested regions in which the edges of the rectangles are parallel to the travel directions. In wake of the difficulties of the general problem, we consider a specific example of a convex quadrilateral congestion region and a pair of external origin and destination points. Finally, we revisit the example shown in Butt and Cavalier's paper and present a mixed integer linear programming formulation that determines the optimal locations of the entry and exit points for this example.     

Preference revelation games and strong cores of allocation problems with indivisibilities

This note considers the equilibrium outcomes of the preference revelation games in the general model of indivisible good allocation introduced by [Sönmez, T., 1999. Strategy-proofness and essentially single-valued cores. Econometrica 67, 677–689]. We adopt the concepts of coalitional equilibria and cores which are both defined in terms of the weak deviation or blocking by a prescribed class of admissible coalitions. We prove that if the solution which induces preference revelation games is individually rational and Pareto optimal and the class of admissible coalitions is “monotonic,” then the set of coalitional equilibrium outcomes coincides with the core. And we point out that the preceding analysis in the context of marriage problems [Gale, D., Shapley, L., 1962. College admissions and the stability of marriage. American Mathematical Monthly 69, 9–15] is hardly extended to the general model.