书目名称 | Location Science | 编辑 | Gilbert Laporte,Stefan Nickel,Francisco Saldanha d | 视频video | http://file.papertrans.cn/588/587795/587795.mp4 | 概述 | Provides an exhaustive coverage of location models.Gives an extended overview on how location theory interacts with many other areas.Best researchers in the field of location convened for this book to | 图书封面 |  | 描述 | .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 locatio | 出版日期 | Book 20151st edition | 关键词 | Coverage; Distance Minimization; Location; Optimization; Spatial Planning | 版次 | 1 | doi | https://doi.org/10.1007/978-3-319-13111-5 | isbn_softcover | 978-3-319-34290-0 | isbn_ebook | 978-3-319-13111-5 | copyright | Springer International Publishing Switzerland 2015 |
1 |
Front Matter |
|
|
Abstract
|
2 |
,Introduction to Location Science, |
Gilbert Laporte,Stefan Nickel,Francisco Saldanha da Gama |
|
Abstract
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.
|
3 |
|
|
|
Abstract
|
4 |
The ,-Median Problem |
Mark S. Daskin,Kayse Lee Maass |
|
Abstract
The .-median problem is central to much of discrete location modeling and theory. While the .-median problem is .-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 .-median problem.
|
5 |
Fixed-Charge Facility Location Problems |
Elena Fernández,Mercedes Landete |
|
Abstract
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.
|
6 |
,-Center Problems |
Hatice Calik,Martine Labbé,Hande Yaman |
|
Abstract
A .-center is a minimax solution that consists in a set of . 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.
|
7 |
Covering Location Problems |
Sergio García,Alfredo Marín |
|
Abstract
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.
|
8 |
Anti-covering Problems |
Emilio Carrizosa,Boglárka G.-Tóth |
|
Abstract
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.
|
9 |
|
|
|
Abstract
|
10 |
Location of Dimensional Facilities in a Continuous Space |
Anita Schöbel |
|
Abstract
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.
|
11 |
Facility Location Under Uncertainty |
Isabel Correia,Francisco Saldanha da Gama |
|
Abstract
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.
|
12 |
Location Problems with Multiple Criteria |
Stefan Nickel,Justo Puerto,Antonio M. Rodríguez-Chía |
|
Abstract
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 .-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.
|
13 |
Ordered Median Location Problems |
Justo Puerto,Antonio M. Rodríguez-Chía |
|
Abstract
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 ..-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.
|
14 |
Multi-Period Facility Location |
Stefan Nickel,Francisco Saldanha da Gama |
|
Abstract
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.
|
15 |
Hub Location Problems |
Ivan Contreras |
|
Abstract
. (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.
|
16 |
The Quadratic Assignment Problem |
Zvi Drezner |
|
Abstract
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.
|
17 |
Competitive Location Models |
H. A. Eiselt,Vladimir Marianov,Tammy Drezner |
|
Abstract
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.
|
18 |
Location-Routing and Location-Arc Routing |
Maria Albareda-Sambola |
|
Abstract
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.
|
19 |
Location and Logistics |
Sibel A. Alumur,Bahar Y. Kara,M. Teresa Melo |
|
Abstract
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.
|
20 |
Stochastic Location Models with Congestion |
Oded Berman,Dmitry Krass |
|
Abstract
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 model
|
|
|