Location Science

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.