Facility Location

Distance is a numerical description of how far apart objects are at any given moment in time. In physics or everyday discussion, distance may refer to a physical length, a period of time, or it is estimated based on other criteria.

While making location decisions, the distribution of travel distances among the service recipients (clients) is an important issue.

Most classical location studies focus on the minimization of the mean (or total) distance (the median concept) or the minimization of the maximum distance (the center concept) to the service facilities. (Ogryczak 2000) In these studies, the location modeling is divided into four broad categories:

Continuous models. These models are the oldest location models, deal with geometrical representations of reality, and are based on the continuity of location area. The classic model in this area is the Weber problem. Distances in the Weber problem are often taken to be straight-line or Euclidean distances but almost all kind of the distance functions can be used here (Jiang and Xu 2006; Hamacher and Nickel 1998).

In the study of continuous location theory, it is generally assumed that the customers may be treated as points in space. This assumption is valid when the dimensions of the customers are small relative to the distances between the new facility and the customers. However, it is not always the case. Sometimes, we should not ignore the dimensions of the customers. Some researchers have treated the customers as demand regions representing the demand over a region.

Jiang and Xu (2006) discussed that some researchers such as Brimberg andWesolowsky in 1997, 2000 and 2002 and Nickel et al. in 2003 used the distance between the facility and the closest point of a demand region; and in the others, the distance between the facility and a demand region may be calculated as some form of expected or average travel distance.

Discrete models. In these models, there are a discrete set of candidate locations. Discrete N-median, un-capacitated facility location, and coverage models are some well-known models in this area. Like the distances in continuous models, all kind of the distance functions can be used here but sometimes it could be specified exogenously (Hamacher and Nickel 1998; Fouard and Malandain 2005).

Distances and norms are usually defined on the finite space Eⁿ and take real values. In discrete geometry, however, we sometimes need to have discrete distances defined on Zⁿ with their values in Z. Since Zⁿ is not a vector space, the notion of distances and norms had to be extended.

Computational complexity theory (Shortly: Complexity Theory) has been a central area of theoretical computer science since its early development in the mid-1960s. Its subsequent rapid development in the next three decades, has not only established it as a rich, exciting theory, but also has shown strong influence on many other related areas in computer science, mathematics, and operation research (Du and Ko 2000). However, the notions of algorithms and complexity are meaningful only when they are defined in terms of formal computation models (Du and Ko 2000).

Apparently, we need some models to base the foundation of complexity theory on them. In this chapter, we introduce only three basic models: deterministic turing machine (DTM), non-deterministic turing machine (NTM) and Oracle machine models. It should be noted there are also some other models (see Du and Ko 2000).

Using such models, allows us to separate the complexity notion from any physical machine. Hence, we can measure the time complexity of algorithms and hardness of problems independent from a specific machine which runs the algorithm(s). It should be noted that these are just abstract models; means, are defined mathematically (Sipser 1996).

The structure of this chapter is as follows. We first discuss why we actually need complexity theory. Then, we introduce three basic models of computation: DTM and NTM and Oracle model. Then we present a brief introduction about the concept of big O notation which is widely used in the complexity theory. In Sect. 2.5, the decision problems as a special form of problems are described. Following this section, the basic concepts of reduction are presented, which help us to make relationships between different classes of complexity and also provide a rich tool to identify the unknown complexity class of a new problem. Finally, we introduce the most popular classes of complexity: P> , NP, NP-complete and NP-hard. In each class, also, some known problems are presented.

This chapter will focus on the simplest types of location problems, single facility location problem. These problems occur on a regular basis when working, layout problems (e.g., we may need to locate a machine in a shop, or items inside a warehouse). Also, on a larger scale, they can occur in, say, choosing the location of a warehouse to serve customers to whom goods must be delivered.

The models shall be studied as being “quick and dirty.” They are “quick” in the sense that they can be used quickly and easily, and “dirty” in the send that they are approximate. The use of these models should be considered particularly when some location decision must be made quickly and with limited resource available for decision analysis.

When we wish to locate a single new facility in the plane, we often would like to minimize an objective function involving Euclidean or rectilinear distances between the new facility and a collection of existing facilities having known planar locations. The first objective function we consider is that of total travel distance, or total travel cost.

In the previous chapter, we studied the case of a single new facility to be located relative to a number of existing facilities. In this chapter we consider the problem of optimally locating more than one new facilities with respect to locations of a number of existing facilities (demand points), the locations of which are known.

While the problems are natural extension of those of single facility location, there are two important conditions:

1. At least two facilities are to be located

2. Each new facility is linked to at least one other new facility

If the first condition contracted, this problem is considered as a single facility location problem (SFLP) and if the second condition contracted, we can consider the problem as some of independent single facility location problems. Thus the SFLP can be considered as a spatial case of the multifacility location problem (MFLP).

Location-allocation (LA) problem is to locate a set of new facilities such that the transportation cost from facilities to customers is minimized and an optimal number of facilities have to be placed in an area of interest in order to satisfy the customer demand.

This problem occursin many practical settings where facilities provide homogeneous services such as the determination and location of warehouses, distribution centers, communication centers and production facilities.

Since LA problem was proposed by Cooper (1963) and spread to a weighted network by Hakimi (1964), network LA problem and many models were presented by Badri (1999).

For solving these models, numerous algorithms have been designed, involving branch-and-bound algorithms (Kuenne and Soland 1972), simulated annealing (Murray and Church 1996) and Tabu search (Brimberg and Mladenovic 1996; Ohlemüller 1997) and P-Median plus Weber (Hansen et al. 1998). Some hybrid algorithms have been also suggested, such as the one based on simulated annealing and random descent method (Ernst and Krishnamoorthy 1999) and the one utilizing the Lagrange relaxation method and genetic algorithm (Gong et al. 1997). Brimberg et al. (2000) improved present algorithms and proposed variable neighborhood search, which is proved to obtain the best results when the number of facilities to locate is large.

The quadratic assignment problem (QAP) in location Theory is the problem of locating facilities the cost of placing a facility depends on the distances from other facilities and also the interaction with other facilities. QAP was introduced by Koopmans and Beckman in 1957 who were trying to model a facilities location problem.

Church and Revelle (1974) modeled the maximization covering problem. Covering problems are divided into two branches; tree networks and general networks, according to their graph. In addition, these problems are divided into two problems: Total covering and partial covering problems, based on covering all or some demand points.

The median problem is considered as the main problems identified with the location-allocation problems (see Chap. 5). These problems are intended to find the median points among the candidate points, so that the sum of costs can be minimized through this target function. These kinds of problems include the establishment of the public services including schools, hospitals, firefighting, Ambulance, technical audit stations of cars, and etc. The target function in the median problems is of the minisum kind. In fact in these problems we try to quantify the sum of distances (costs).

In the covering problems, the attempt is to determine the location of the minimum number of facilities necessary to cover all demand nodes. In this type of problems, the coverage distance is an exogenous data. But sometimes the number of facilities needed to cover all demand nodes with a predefined coverage distance may be quite large. In order to overcome this, the maximum covering location problem has been discussed. In this model, the objective is to maximize the number of covered demand nodes with a fixed number of facilities. In other words, we relaxed the total coverage requirement (Daskin 1995).

Many facility systems are hierarchical in nature. These facilities are usually hierarchical in terms of the types of services they provide. For example, the health care delivery system consists of local clinics, hospitals and medical centers (Fig. 10.1). In this system a local clinic provides basic health care and diagnostic services. A hospital provides out-patient surgery in addition to those provided by a local clinic; and a medical center provides out-patient surgery and a full range of in-patient services. As another example of a hierarchical system, consider a solid waste disposal system. The solid waste is collected from the source of solid waste and shipped to transfer stations or landfill stations by trucks. Other examples of a hierarchical system are: education system, postal system, banking system and production–distribution system (Narula 1986; Daskin 1995).

One of the novel topics in location problems is the hub location problem. There are plenty of applications for the hub location problem; therefore, this section is dedicated to introducing this problem to readers. The preface is composed of three parts: apprehensions, definitions, and classifications of the hub location problem. In this chapter we discuss services such as, movement of people, commodities and information which occurs between an origin-destination pair of nodes (see A–B in Fig. 11.1 as an origin-destination pair). Each origin-destination pair needs a service different from other pairs. Thus, the commodities carried from i to j are not interchangeable with the commodities carried from j to i.

A location model is said to be about competitive facilities when it explicitly incorporates the fact that other facilities are already (or will be) present in the market and that the new facilities will have to compete with them for its (their) market share. The apparent simplicity of this statement hides several implicit and explicit notions which have to be made more precise before a clear and well-defined model arises. This chapter is organized as follows. In Sect. 12.1, we consider literatures, definitions and classifications of competitive location problem. Section 12.2 presents some models with continuous and discrete space developed for the problem, and also some relevant algorithms to solve these models are given in this section. Finally, Sect. 12.3 represents some real world case studies with a short summary.

Finding the optimal location for industrial facilities has always been of a crucial importance and priority from geographers’ and economists’ view point. Although economics play the main role in presenting location theories by resorting to its theories, geographers, with their focus on locative and spatial changes leading to natural phenomenon, have also had a share in complimenting these location theories and finding optimal points to locate industrial activities location. From this point of view, materials, market and other manufacturing factors have not been concentrated in one point, and their spatial separation necessitates traveling distances which, in turn, brings about costs. That is why optimal industrial location is also a part of geographical studies.

In general, facilities are divided in two groups, the first one are desirable to the nearby inhabitants which try to have them as close as possible such as hospitals, fire stations, shopping stores and educational centers. The second group turns out to be undesirable for the surrounding population, which avoids them and tries to stay away from them such as garbage dump sites, chemical plants, nuclear reactors, military installations, prisons and polluting plants. In this sense, Daskin (1995) discussed that Erkut and Neuman in 1989 distinguished between Noxious (hazardous to health) and Obnoxious (nuisance to lifestyle) facilities, although both can be simply regarded as Undesirable. Moreover, in the last decade, a new nomenclature has been developed to define these oppositions: NIMBY (not in my back yard), NIMNBY (not in my neighbor’s back yard), and NIABY (not in anyone’s back yard).

Facility location is a strategic management decision. This decision is usually made, however, with respect to the current parameters (like weights) which represent population, infrastructure, service requirements and others (Drezner 1995; Francis and Lowe 1992; Mirchandani and Francis 1990). Much of the research published on location theory is drawn from the models such as single/multi facility location, covering, P-median, P-center problems, and their applications and extensions. Solving many of these problems can be extremely difficult. Thus, it is not surprising that so much work has focused on statistic and deterministic problem formulations. While such formulations are reasonable research topics, they do not capture many of the characteristics of real-world location problems.

Decision-making is the process of selecting a possible subset of decisions from all the available alternatives (feasible space). We introduced many decision-making models including one objective function, so far. Almost there are many criteria for judging the optimality of decision. In this situation, we will be faced with the multi-criteria decision-making (MCDM).

The aim of this chapter is to survey the state of the art in location-routing. The location-routing problem (LRP) is a research area within location analysis, with the distinguishing property of paying special attention to underlying issues of vehicle routing. Since the Vehicle-Routing Problem (VRP), which is a complex problem itself, is known as a basic component of LRPs, the main concepts of VRP are introduced in the first section. In the second section, the definition, applications and classifications of LRP are discussed. The next section is dedicated to the LRP models and introduces some basic mathematical models of this field. Solution techniques are presented in the fourth section. Finally, three case studies regarding applications of LRP in real world are briefly reviewed.

A warehouse consists of a number of parallel aisles. The items are stored on both sides of the aisles. Order pickers are assumed to be able to traverse the aisles in both directions and to change direction within the aisles. Their major roles include: buffering the material flow along the supply chain to accommodate variability caused by factors such as product seasonality and/or batching in production and transportation; consolidation of products from various suppliers for combined delivery to customers; and value-added-processing such as kitting, pricing, labeling, and product customization.

Traditionally, logistics analysts have divided decision levels into strategic, tactical and operational (Miranda and Garrido 2006). There are also three important decisions within a supply chain: facilities location decisions; inventory management decisions; and distribution decisions (Shen and Qi 2007). For example, in a distribution network, we could mention location of Distribution centers (DCs) as a strategic decision, distribution decisions as a tactical decision and inventory service level as a tactical or operational decision. Often, for modeling purposes, these levels are considered separately. And this may conduce to make non-optimal decisions, since in reality there is interaction between the different levels (Miranda and Garrido 2006). For example, most well-studied location models do not consider inventory costs, and shipment costs are estimated by direct shipping. Although one may argue that tactical inventory replenishment decisions and shipment schemes are not at the strategic level, and we should not consider them in the strategic planning phase, however, failure to take the related inventory and shipment costs into consideration when deciding the locations of facilities can lead to sub-optimality, since strategic location decisions have a big impact on inventory and shipment costs (Shen and Qi 2007). On the other hand firms would like to consider cost and service levels simultaneously. It is good to have many DCs, since this reduces the cost of transporting product to customers (/retailers) and will provide better service. Also, it is good to have few DCs, since this reduces the cost of holding inventory via pooling effects, and reduces the fixed costs associated with operating DCs via economies of scale (Erlebacher and Meller 2000).

A supply chain (SC) is the network of facilities and activities that performs the function of product development, procurement of material from vendors, the movement of materials between facilities, the manufacturing of products, the distribution of finished goods to customers, and after-market support for sustainment (Mabert and Venkataramanan 1998). The supply chain not only includes the manufacturer and suppliers, but also transporters, warehouses, retailers, and customer tshemselves. Within each organization, the supply chain include, but not limited to, new product development, marketing, operations, distribution, finance, and customer service (Chopra 2003).

According to the importance and advantages of classification, the first section of this chapter is dedicated to some presented classifications of location models, which help in having more disciplined understanding of location models. In the second section, some location softwares will be introduced briefly.

Nowadays, with the increasing development of science in all branches, need for a systematic arrangement or proposing a classification scheme for easy access to scientific researches seems necessary. Location science is a branch of optimization science, which formally introduce by Alfred Weber in 1909. It has been growing so rapidly for years that now without a systematic classification of models, continuing the procedure of researches would be so difficult. Therefore, several efforts in classifying location models have been made that, some of them will be mentioned in this section.

When selecting locations for facilities, such as hospitals, fire stations schools, warehouses and retail outlets, one has to take into account the demand for the service provided by the facility. In many instances, such facilities serve a large number of individuals, and it may not be realistic to model each individual as a separate demand point (DP). To reduce the problem size to a manageable one, an analyst is usually forced to aggregate the demand (population) data by representing a collection of individuals as one DP. While this is a practical solution, it perturbs the original problem and may introduce errors to subsequent analysis (Erkut and Bozkaya 1999).