A hierarchical location model for public facility planning

In this article, we present a discrete hierarchical location model for public facility planning. The main features of the model are: an accessibility maximization objective; several levels of demand and of facilities; a nested hierarchy of facilities (i.e. a facility of a given level can serve demand of equal and lower levels); maximum and minimum capacity constraints; and user-to-facility assignment constraints. The latter include single-assignment and closest-assignment constraints, as well as a new type of constraints called path-assignment constraints. Their purpose is to enforce some desirable properties for the spatial pattern of assignments. If they are not included, model solutions are difficult to interpret and to explain in a public facility planning context, therefore being less likely to be accepted by the users. The usefulness of the model is illustrated through a real-world application to school network planning.     

Linear upper-bound unavailability set covering models for locating ambulances: Application to Tehran rural roads

This paper presents a linear reliability-based model as an extension of the well-known linear location set covering problem (LSCP) for emergency service vehicles such as ambulances. Linear programming models have a practical advantage over other nonlinear or queuing-based models. They can be simply coded by practitioners and can be solved routinely using existing commercial software to achieve exact solutions especially for large problem instances.     

A general model for the undesirable single facility location problem

In this paper, a finite set in which an optimal solution for a general Euclidean problem of locating an undesirable facility in a polygonal region, is determined and can be found in polynomial time. The general problem we propose leads us, among others, to several well-known problems such as the maxisum, maximin, anticentdian or r-anticentrum problem.     

A note on a symmetrical set covering problem: The lottery problem

In a lottery, n numbers are drawn from a set of m numbers. On a lottery ticket we fill out n numbers. Consider the following problem: what is the minimum number of tickets so that there is at least one ticket with at least p matching numbers? We provide a set-covering formulation for this problem and characterize its LP solution. The existence of many symmetrical alternative solutions, makes this a very difficult problem to solve, as our computational results indicate.     

A facility location and installation of resources model for level of repair analysis

The Level of Repair Analysis – LORA – is an analytic methodology aimed at determining: (i) the optimal location of facilities that compose a maintenance structure; (ii) the quantity of required resources in each facility; and (iii) the best repair policies, i.e., rules that determine if a given component should be discarded or repaired, and where those actions should take place. This work presents a mixed-integer programming model for LORA that is more comprehensive than others in the literature, being suitable to many practical situations. The model was applied to 15 substantial real world problems, and considering distinct maintenance policies to some of them, resulted in 22 different solutions, all of which could be achieved by a commercial Mixed-Integer Programming (MIP) solver in reasonable times.     

A multicriteria facility location model for municipal solid waste management in North Greece

Up to 2002, Hellenic Solid Waste Management (SWM) policy specified that each of the country’s 54 prefectural governments plan its own SWM system. After 2002, this authority was shifted to the country’s 13 regions entirely. In this paper, we compare and contrast regional and prefectural SWM planning in Central Macedonia. To design the prefectural plan, we assume that each prefecture must be self-sufficient, and we locate waste facilities in each prefecture. In contrast, in the regional plan, we assume cooperation between prefectures and locate waste facilities to serve the entire region. We present a new multicriteria mixed-integer linear programming model to solve the location–allocation problem for municipal SWM at the regional level. We apply the lexicographic minimax approach to obtain a “fair” nondominated solution, a solution with all normalized objectives as equal to one another as possible. A solution to the model consists of locations and technologies for transfer stations, material recovery facilities, incinerators and sanitary landfills, as well as the waste flow between these locations.     

The minmax regret gradual covering location problem on a network with incomplete information of demand weights

The gradual covering location problem seeks to establish facilities on a network so as to maximize the total demand covered, allowing partial coverage. We focus on the gradual covering location problem when the demand weights associated with nodes of the network are random variables whose probability distributions are unknown. Using only information on the range of these random variables, this study is aimed at finding the “minmax regret” location that minimizes the worst-case coverage loss. We show that under some conditions, the problem is equivalent to known location problems (e.g. the minmax regret median problem). Polynomial time algorithms are developed for the problem on a general network with linear coverage decay functions.     

On a new class of nonlinear set covering problems arising in wireless network design

This is a summary of the author’s PhD thesis, supervised by Edoardo Amaldi and defended on 28 April 2006 at Politecnico di Milano, Dipartimento di Matematica. The thesis is written in English and is available from the author upon request. The thesis investigates a class of nonlinear set covering variants arising from the problem of designing single-frequency Wireless Local Area Networks (WLANs) with maximum efficiency. In the first part of the thesis a basic hyperbolic formulation of the problem is considered. After a complexity and approximability study, the problem is tackled by linearization techniques, and by Lagrangean and Dantzig–Wolfe decompositions. The second part of the thesis focuses on variants accounting for various relevant features of the WLAN application. A Branch-and-Price algorithm is presented, and extensions to the multiple-frequency WLAN design problem are considered.      

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.     

A network model for airline cabin crew scheduling

Airline crew scheduling problems have been traditionally formulated as set covering problems or set partitioning problems. When flight networks are extended, these problems become more complicated and thus more difficult to solve. From the current practices of a Taiwan airline, whose work rules are relatively simple compared to many airlines in other countries, we find that pure network models, in addition to traditional set covering (partitioning) problems, can be used to formulate their crew scheduling problems. In this paper, we introduce a pure network model that can both efficiently and effectively solve crew scheduling problems for a Taiwan airline using real constraints. To evaluate the model, we perform computational tests concerning the international line operations of a Taiwan airline.     

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.     

A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints

This paper deals with the problem of locating at minimum total costs both plants and warehouses in a two-level distribution system where commodities are delivered from plants to customers either directly or indirectly via warehouses. Some side-constraints are imposed on the problem, which represent the adjunct relationship of some warehouses to a certain plant. Proposed is an efficient branch and bound solution procedure, employing a set of new devices for lower bounds and simplifications which are obtained by exploiting the submodularity of the objective function and the special structure of the side-constraints. Computational experiments with fifteen test problems are provided.     

General models in min-max continous location: Theory and solution techniques

In this paper, a class of min-max continuous location problems is discussed. After giving a complete characterization of th stationary points, we propose a simple central and deep-cut ellipsoid algorithm to solve these problems for the quasiconvex case. Moreover, an elementary convergence proof of this algorithm and some computational results are presented.The work of the second author was supported by JNICT (Portugal), under Contract BD/631/90-RM, during his stay at Erasmus University in Rotterdam.The authors would like to thank the anonymous referees for simplifying the proofs in the first part of Section 2 and for their constructive remarks improving the presentation.     

A hybrid fuzzy integral decision-making model for locating manufacturing centers in China: A case study

This study presents a hybrid fuzzy integral decision-making model that integrates factor analysis, interpretive structural modeling, Markov chain, fuzzy integral and the simple additive weighted method for selecting locations of high-tech manufacturing centers in China. The analytical results of this case study demonstrate the feasibility of the proposed model for solving fuzzy multiple attribute decision-making problems, especially when criteria are interdependent. Further, the empirical study brings out some properties that are crucial for high-tech manufacturing centers to invest in China.     

Covering models and optimization techniques for emergency response facility location and planning: a review

With emergencies being, unfortunately, part of our lives, it is crucial to efficiently plan and allocate emergency response facilities that deliver effective and timely relief to people most in need. Emergency Medical Services (EMS) allocation problems deal with locating EMS facilities among potential sites to provide efficient and effective services over a wide area with spatially distributed demands. It is often problematic due to the intrinsic complexity of these problems. This paper reviews covering models and optimization techniques for emergency response facility location and planning in the literature from the past few decades, while emphasizing recent developments. We introduce several typical covering models and their extensions ordered from simple to complex, including Location Set Covering Problem (LSCP), Maximal Covering Location Problem (MCLP), Double Standard Model (DSM), Maximum Expected Covering Location Problem (MEXCLP), and Maximum Availability Location Problem (MALP) models. In addition, recent developments on hypercube queuing models, dynamic allocation models, gradual covering models, and cooperative covering models are also presented in this paper. The corresponding optimization techniques to solve these models, including heuristic algorithms, simulation, and exact methods, are summarized.     

A multi-objective integrated facility location-hardening model: Analyzing the pre- and post-disruption tradeoff

Two methods of reducing the risk of disruptions to distribution systems are (1) strategically locating facilities to mitigate against disruptions and (2) hardening facilities. These two activities have been treated separately in most of the academic literature. This article integrates facility location and facility hardening decisions by studying the minimax facility location and hardening problem (MFLHP), which seeks to minimize the maximum distance from a demand point to its closest located facility after facility disruptions. The formulation assumes that the decision maker is risk averse and thus interested in mitigating against the facility disruption scenario with the largest consequence, an objective that is appropriate for modeling facility interdiction. By taking advantage of the MFLHP’s structure, a natural three-stage formulation is reformulated as a single-stage mixed-integer program (MIP). Rather than solving the MIP directly, the MFLHP can be decomposed into sub-problems and solved using a binary search algorithm. This binary search algorithm is the basis for a multi-objective algorithm, which computes the Pareto-efficient set for the pre- and post-disruption maximum distance. The multi-objective algorithm is illustrated in a numerical example, and experimental results are presented that analyze the tradeoff between objectives.     

Improving emergency service in rural areas: a bi-objective covering location model for EMS systems

Emergency medical service (EMS) systems are public services that often provide the first line of response to urgent health care needs within a community. Unfortunately, it has been widely documented that large disparities in access to care exist between rural and urban communities. While rural EMS is provided through a variety of resources (e.g. air ambulances, volunteer corps, etc.), in this paper we focus on ground ambulatory care. In particular our goal is to balance the level of first-response ambulatory service provided to patients in urban and rural areas by locating ambulances at appropriate stations. In traditional covering location models the objective is to maximize demand that can be covered; consequently, these models favor locating ambulances in more densely populated areas, resulting in longer response times for patients in more rural areas. To address the issue of fairness in semi-rural/semi-urban communities, we propose three bi-objective covering location models that directly consider fairness via a secondary objective. Results are discussed and compared which provide a menu of alternatives to policy makers.     

A bi-level programming model and solution algorithm for the location of logistics distribution centers

In this paper, by considering benefits of customers and logistics planning departments, a bi-level programming model is presented to seek the optimal location for logistics distribution centers. The upper-level model is to determine the optimal location by minimizing the planners’ cost, and the lower gives an equilibrium demand distribution by minimizing the customers’ cost. Based on the special form of constraints, a simple heuristic algorithm is proposed. Finally, a numerical example is used to illustrate the application of the method, which shows that the algorithm is feasible and advantageous.     

Capacity management in public service facility networks: a model,computational tests and a case study

In this work, we present a mathematical model to support location decisions oriented to rationalize facility systems in non-competitive contexts. In order to test the model, computational results are shown and an application to a real-world case study, concerning the Higher Education system in an Italian region, is discussed.     

Dynamic dairy facility location and supply chain planning under traffic congestion and demand uncertainty: A case study of Tehran

In this paper, dynamic dairy facility location and supply chain planning are studied through minimizing the costs of facility location, traffic congestion and transportation of raw/processed milk and dairy products under demand uncertainty. The proposed model dynamically incorporates possible changes in transportation network, facility investment costs, monetary value of time and changes in production process. In addition, the time variation and the demand uncertainty for dairy products in each period of the planning horizon is taken into account to determine the optimal facility location and the optimal production volumes. Computational results are presented for the model on a number of test problems. Also, an empirical case study is conducted in order to investigate the dynamic effects of traffic congestion and demand uncertainty on facility location design and total system costs.