Skip to main content
main-content

Über dieses Buch

This comprehensive and clearly structured book presents essential information on modern Location Science. The book is divided into three parts: basic concepts, advanced concepts and applications. Written by the most respected specialists in the field and thoroughly reviewed by the editors, it first lays out the fundamental problems in Location Science and provides the reader with basic background information on location theory. Part II covers advanced models and concepts, broadening and expanding on the content presented in Part I. It provides the reader with important tools to help them understand and solve real-world location problems. Part III is dedicated to linking Location Science with other areas like GIS, telecommunications, healthcare, rapid transit networks, districting problems and disaster events, presenting a wide range of applications. This part enables the reader to understand the role of facility location in such areas, as well as to learn how to handle realistic location problems.

The book is intended for researchers working on theory and applications involving location problems and models. It is also suitable as a textbook for graduate courses on facility location.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction to Location Science

This chapter introduces modern Location Science. It traces the roots of the area and describes the path leading to the full establishment of this research field. It identifies several disciplines having strong links with Location Science and offers examples of areas in which the knowledge accumulated in the field of location has been applied with great success. It describes the purpose and structure of this volume. Finally, it provides suggestions on how to make use of the contents presented in this book, namely for organizing general or specialized location courses targeting different audiences.
Gilbert Laporte, Stefan Nickel, Francisco Saldanha da Gama

Basic Concepts

Frontmatter

Chapter 2. The p-Median Problem

The p-median problem is central to much of discrete location modeling and theory. While the p-median problem is \( \mathcal{N}\mathcal{P} \)-hard on a general graph, it can be solved in polynomial time on a tree. A linear time algorithm for the 1-median problem on a tree is described. We also present a classical formulation of the problem. Basic construction and improvement algorithms are outlined. Results from the literature using various metaheuristics including tabu search, heuristic concentration, genetic algorithms, and simulated annealing are summarized. A Lagrangian relaxation approach is presented and used for computational results on 40 classical test instances as well as a 500-node instance derived from the most populous counties in the contiguous United States. We conclude with a discussion of multi-objective extensions of the p-median problem.
Mark S. Daskin, Kayse Lee Maass

Chapter 3. Fixed-Charge Facility Location Problems

Fixed-Charge Facility Location Problems are among core problems in Location Science. There is a finite set of users with demand of service and a finite set of potential locations for the facilities that will offer service to users. Two types of decisions must be made: Location decisions determine where to establish the facilities whereas allocation decisions dictate how to satisfy the users demand from the established facilities. Potential applications of various types arise in many different contexts. We provide an overview of the main elements that may intervene in the modeling and the solution process of Fixed-Charge Facility Location Problems, namely, modeling hypotheses and their implications, characteristics of formulations and their relation to other formulations, properties of the domains, and appropriate solution techniques.
Elena Fernández, Mercedes Landete

Chapter 4. p-Center Problems

A p-center is a minimax solution that consists in a set of p points that minimizes the maximum distance between a demand point and a closest point belonging to that set. We present different variants of that problem. We review special polynomial cases, determine the complexity of the problems and present mixed integer linear programming formulations, exact algorithms and heuristics. Several extensions are also reviewed.
Hatice Calik, Martine Labbé, Hande Yaman

Chapter 5. Covering Location Problems

When deciding where to locate facilities (e.g., emergency points where an ambulance will wait for a call) that provide a service, it happens quite often that a customer (e.g., a person) can receive this service only if he/she is under a certain distance to the closest facility (e.g., the ambulance can arrive in less than 7 min at this person’s home). The problems that share this property receive the name of covering problems and have many applications (analysis of markets, archaeology, crew scheduling, emergency services, metallurgy, nature reserve selection, etc.). This chapter surveys the Set Covering Problem, the Maximal Covering Location Problem, and related problems and introduces a general model that has as particular cases the main covering location models. The main theoretical results in this topic as well as exact and heuristic algorithms are reviewed. A Lagrangian approach to solve the general model is detailed and, although the emphasis is on discrete models, some information on continuous covering is provided at the end of the chapter.
Sergio García, Alfredo Marín

Chapter 6. Anti-covering Problems

In covering location models, one seeks the location of facilities optimizing the weight of individuals covered, i.e., those at the distance from the facilities below a threshold value. Attractive facilities are wished to be close to the individuals, and thus the covering is to be maximized, while for repulsive facilities the covering is to be minimized. On top of such individual-facility interactions, facility-facility interactions are relevant, since they may repel each other. This chapter is focused on models for locating facilities using covering criteria, taking into account that facilities are repulsive from each other. Contrary to the usual approach, in which individuals are assumed to be concentrated at a finite set of points, we assume the individuals to be continuously distributed in a planar region. The problem is formulated as a global optimization problem, and a branch and bound algorithm is proposed.
Emilio Carrizosa, Boglárka G.-Tóth

Advanced Concepts

Frontmatter

Chapter 7. Location of Dimensional Facilities in a Continuous Space

In many cases, the facilities to be located cannot be represented by isolated points, but may be modeled as dimensional structures. Examples for one-dimensional facilities are straight lines, line segments, or circles while boxes, strips, or balls are two-dimensional facilities. The goal of this chapter is to review the location of lines and circles in the plane and the location of hyperplanes and hyperspheres in higher dimensional spaces. We also discuss the location of some other dimensional facilities. We formulate the resulting location problems, point out some of their important properties and review the basic solution techniques and algorithmic approaches. Our focus lies on presenting a unified understanding of the common characteristics these problems have, and on reviewing the new findings obtained in this field within the last 10 years.
Anita Schöbel

Chapter 8. Facility Location Under Uncertainty

In this chapter, we cover some essential knowledge on facility location under uncertainty. We put a major emphasis on modeling aspects related with discrete facility location problems. Different modeling frameworks are discussed. In particular, we distinguish between robust optimization, stochastic programming and chance-constrained models. We also discuss relevant aspects such as solution techniques, multi-stage stochastic programming models, scenario generation, and extensions of basic problems.
Isabel Correia, Francisco Saldanha da Gama

Chapter 9. Location Problems with Multiple Criteria

This chapter analyzes multicriteria continuous, network, and discrete location problems. In the continuous framework, we provide a complete description of the set of weak Pareto, Pareto, and strict Pareto locations for a general Q-criteria location problem based on the characterization of three criteria problems. In the network case, the set of Pareto locations is characterized for general networks as well as for tree networks using the concavity and convexity properties of the distance function on the edges. In the discrete setting, the entire set of Pareto locations is characterized using rational generating functions of integer points in polytopes. Moreover, we describe algorithms to obtain the solutions sets (the different Pareto locations) using the above characterizations. We also include a detailed complexity analysis. A number of references has been cited throughout the chapter to avoid the inclusion of unnecessary technical details and also to be useful for a deeper analysis.
Stefan Nickel, Justo Puerto, Antonio M. Rodríguez-Chía

Chapter 10. Ordered Median Location Problems

This chapter analyzes the ordered median location problem in three different frameworks: continuous, discrete and networks; where some classical but also new results have been collected. For each solution space we study general properties that lead to resolution algorithms. In the continuous case, we present two solution approaches for the planar case with polyhedral norms (the most intuitive case) and a novel approach applicable for the general case based on a hierarchy of semidefinite programs that can approximate up to any degree of accuracy the solution of any ordered median problem in finite dimension spaces with polyhedral or p -norms. We also cover the problems on networks deriving finite dominating sets for some particular classes of λ parameters and showing the impossibility of finding a FDS with polynomial cardinality for general lambdas in the multifacility case. Finally, we present a covering based formulation for the capacitated discrete ordered median problem with binary assignment which is rather promising in terms of gap and CPU time for solving this family of problems.
Justo Puerto, Antonio M. Rodríguez-Chía

Chapter 11. Multi-Period Facility Location

In this chapter, we cover basic aspects related with facility location problems involving time dependent parameters. The emphasis is put on problems defined over a multi-period finite planning horizon. A brief overview of continuous and network problems is presented. Nevertheless, most of the chapter focus on a discrete setting. Basic modeling aspects and solution techniques are discussed. Additionally, some features of practical relevance are considered. The value of the multi-period solution is introduced as a measure for the relevance of considering a multi-period modeling framework instead of a static one. Current challenges and future trends on the topic are discussed.
Stefan Nickel, Francisco Saldanha da Gama

Chapter 12. Hub Location Problems

Hub Location Problems (HLPs) lie at the heart of network design planning in transportation and telecommunication systems. They are a challenging class of optimization problems that focus on the location of hub facilities and on the design of hub networks. This chapter overviews the key distinguishing features, assumptions and properties commonly considered in HLPs. We highlight the role location and network design decisions play in the formulation and solution of HLPs. We also provide a concise overview of the main developments and most recent trends in hub location research. We cover various topics such as hub network topologies, flow dependent discounted costs, capacitated models, uncertainty, dynamic and multi-modal models, and competition and collaboration. We also include a summary of the most successful integer programming formulations and efficient algorithms that have been recently developed for the solution of HLPs.
Ivan Contreras

Chapter 13. The Quadratic Assignment Problem

The quadratic assignment problem is reviewed in this chapter. Weights between pairs of facilities and distances between the same number of locations are given. The problem is to find the assignment of facilities to locations that minimizes the weighted sum of distances. This problem is considered to be one of the most difficult combinatorial optimization problems. The construction of efficient solution algorithms (exact or heuristic) is challenging and has been extensively investigated by the communities working in Operations Research/Management Science, Industrial Engineering, or Computer Science. Examples of applications are given, the related layout problem is briefly described, exact and heuristic solution algorithms are reviewed, and a list of test problem instances and results are reported.
Zvi Drezner

Chapter 14. Competitive Location Models

This chapter first provides a review of the foundations of competitive location models. It then traces subsequent developments through the decades under special consideration of customer behavior. After developing a general framework for customers’ decision making, the main results are put into this framework. The conclusion outlines a number of areas, in which existing models can be refined and made more realistic.
H. A. Eiselt, Vladimir Marianov, Tammy Drezner

Chapter 15. Location-Routing and Location-Arc Routing

This chapter overviews the most relevant contributions on location-routing problems. Although there exist many different models where location and routing decisions must be made in an integrated way, the chapter focuses on the so-called classical location-routing problems without entering into the details of other related problems that might be included in the location-routing area from a more general point of view. Reflecting the imbalance in the existing literature and available approaches, the case of problems with node routing is treated in detail throughout the chapter, while results concerning arc routing problems are concentrated in a single section.
Maria Albareda-Sambola

Chapter 16. Location and Logistics

Facility location decisions play a critical role in designing logistics networks. This chapter provides some guidelines on how location decisions and logistics functions can be integrated into a single mathematical model to optimize the configuration of a logistics network. This will be illustrated by two generic models, one supporting the design of a forward logistics network and the other addressing the specific requirements of a reverse logistics network. Several special cases and extensions of the two models are discussed and their relation with the scientific literature is described. In addition, some interesting applications are outlined that demonstrate the interaction of location and logistics decisions. Finally, new research directions and emerging trends in logistics network design are provided.
Sibel A. Alumur, Bahar Y. Kara, M. Teresa Melo

Chapter 17. Stochastic Location Models with Congestion

In this chapter we describe facility location models where consumers generate streams of stochastic demands for service, and service times are stochastic. This combination leads to congestion, where some of the arriving demands cannot be served immediately and must either wait in queue or be lost to the system. These models have applications that range from emergency service systems (fire, ambulance, police) to networks of public and private facilities. One key issue is whether customers travel to facilities to obtain service, or mobile servers travel to customer locations (e.g., in case of police cars). For the most part, we focus on models with static (fixed) servers, as the underlying queueing systems are more tractable and thus a richer set of analytical results is available. After describing the main components of the system (customers, facilities, and the objective function), we focus on the customer-facility interaction, developing a classification of models based on the how customer demand is allocated to facilities and whether the demand is elastic or not. We use our description of system components and customer-response classification to organize the rich variety of models considered in the literature into four thematic groups that share common assumptions and structural properties. For each group we review the solution approaches and outline the main difficulties. We conclude with a review of some important open problems.
Oded Berman, Dmitry Krass

Chapter 18. Demand Point Aggregation for Some Basic Location Models

Location problems occurring in urban or regional settings may involve many tens of thousands of “demand points,” usually individual residences. In modeling such problems it is common to aggregate demand points to obtain tractable models. We discuss aggregation approaches to a large class of location models, consider various aggregation error measures, and identify some effective measures. In particular, we focus on an upper bounding methodology for the error associated with aggregation. The chapter includes an example application.
Richard L. Francis, Timothy J. Lowe

Applications

Frontmatter

Chapter 19. Location and GIS

The essence of facility location problems is to determine the position of a set of facilities in a given location space in order to provide some service to a set of actors which are supposed to patronize some of these facilities. This implies that the availability of geographically referenced information represents the fundamental prerequisite to model and solve such problems. Considering that Geographic Information Systems (GIS) offer enormous possibilities for integrating, storing, editing, analyzing, sharing and displaying spatial as well as non-spatial information, it is evident that GIS can play a crucial role for supporting decision making in the field of location science. We aim at illustrating and discussing the various linkages and application opportunities between location science and GIS and highlight the ways these two disciplines have influenced each other. Finally, we wish to indicate possibilities for further connections that may materialize in the future.
Giuseppe Bruno, Ioannis Giannikos

Chapter 20. Location Problems in Telecommunications

Telecommunications is an important area of application in combinatorial optimization. A large class of problems encountered by telecommunications operators are related to location theory. The aim of this chapter is to review recent developments in the application of location models for the design of (wired) telecommunications networks. In particular, we cover the Concentrator Location Problem, the Connected Facility Location Problem, the Regenerator Location Problem and some Ring Location problems.
Bernard Fortz

Chapter 21. Location Problems in Healthcare

In this chapter, we discuss facility location problems arising in the context of healthcare. We concentrate on three main areas: the most classical one is healthcare facility location which is closely related to public facility location. Secondly, we look at ambulance planning which includes ambulance location and relocation problems. In the last part, we give an overview of hospital layout problems. For all three parts, we state some important models and give an overview of relevant literature as well as current research directions. A comprehensive reference list is included at the end of the chapter.
Evrim Didem Güneş, Stefan Nickel

Chapter 22. The Design of Rapid Transit Networks

Metro and other rapid transit systems increase the mobility of urban populations while decreasing congestion and pollution. There are now 191 cities with a metro system in the world, 49 of which were inaugurated in the twenty-first century. The design of a rapid transit system is a hard problem involving several players, multiple objectives, sizeable costs and a high level of uncertainty. Operational research techniques cannot fully solve the problem, but they can generate alternative solutions among which the decision makers can choose, and be employed to solve some specific subproblems. The scientific literature on rapid transit location planning has grown at a fast rate over the past 20 years. In this chapter an account of some of the most important results are provided. First the main objectives and indices used in the assessment of rapid transit systems are described. Then the main models and algorithms used to design such systems are reviewed. The case of a single alignment and of a full network are treated separately. Then follows a section on the location of stations on an already existing network.
Gilbert Laporte, Juan A. Mesa

Chapter 23. Districting Problems

Districting is the problem of grouping small geographic areas, called basic units, into larger geographic clusters, called districts, such that the latter are balanced, contiguous, and compact. Balance describes the desire for districts of equitable size, for example with respect to workload, sales potential, or number of eligible voters. A district is said to be geographically compact if it is somewhat round-shaped and undistorted. Typical examples for basic units are customers, streets, or zip code areas. Districting problems are motivated by quite different applications ranging from political districting over the design of districts for schools, social facilities, waste collection, or winter services, to sales and service territory design. Despite the considerable number of publications on districting problems, there is no consensus on which criteria are eligible and important and, moreover, on how to measure them appropriately. Thus, one aim of this chapter is to give a broad overview of typical criteria and restrictions that can be found in various districting applications as well as ways and means to quantify and model these criteria. In addition, an overview of the different areas of application for districting problems is given and the various solution approaches for districting problems that have been used are reviewed.
Jörg Kalcsics

Chapter 24. Location Problems Under Disaster Events

Facility systems may be vulnerable to a disaster, whether caused by intention, an accident, or by an act of nature. When disrupting events do occur, services may be degraded or even destroyed. This chapter addresses problems of disruption associated with facility based service systems. Three main questions often arise when dealing with a possible disaster: (1) how bad can it get? (2) is there a way in which we can protect our system from such an outcome? and (3) is there a way in which we can incorporate such issues in our future designs and plans? This chapter addresses each of these main questions with respect to several classic location problems. Specifically, it discusses recent location models under disaster events along three main streams of research: facility interdiction, facility protection, and resilient design.
Maria Paola Scaparra, Richard L. Church

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Wieviel digitale Transformation steckt im Informationsmanagement? Zum Zusammenspiel eines etablierten und eines neuen Managementkonzepts

Das Management des Digitalisierungsprozesses ist eine drängende Herausforderung für fast jedes Unternehmen. Ausgehend von drei aufeinander aufbauenden empirischen Untersuchungen lesen Sie hier, welche generellen Themenfelder und konkreten Aufgaben sich dem Management im Rahmen dieses Prozesses stellen. Erfahren Sie hier, warum das Management der digitalen Transformation als separates Konzept zum Informationsmanagement zu betrachten
und so auch organisatorisch separiert zu implementieren ist. Jetzt gratis downloaden!

Bildnachweise