A cutting plane algorithm for the Capacitated Connected Facility Location Problem

We consider a network design problem that arises in the cost-optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design problem and the single-source capacitated facility location problem. We refer to it as the Capacitated Connected Facility Location Problem. We develop a basic integer programming model based on single-commodity flows. Based on valid inequalities for the capacitated network design problem and the single-source capacitated facility location problem we derive several (new) classes of valid inequalities for the Capacitated Connected Facility Location Problem including cut set inequalities, cover inequalities and combinations thereof. We use them in a branch-and-cut framework and show their applicability and efficacy on a set of real-world instances.     

Heuristic Procedures for Solving the Discrete Ordered Median Problem

We present two heuristic methods for solving the Discrete Ordered Median Problem (DOMP), for which no such approaches have been developed so far. The DOMP generalizes classical discrete facility location problems, such as the p-median and p-center. The first procedure proposed in this paper is based on a genetic algorithm developed by Moreno Vega (1996) for p-median and p-center problems. Additionally, a second heuristic approach based on the Variable Neighborhood Search metaheuristic (VNS) proposed by Hansen and Mladenović (1997) for the p-median problem is described. An extensive numerical study is presented to show the efficiency of both heuristics and compare them.     

An analysis of p-median location problem: Effects of backup service level and demand assignment policy

Any solution to facility location problems will consider determining the best suitable locations with respect to certain criteria. Among different types of location problems, involving emergency service system (ESSs) are one of the most widely studied in the literature, and solutions to these problems will mostly aim to minimize the mean response time to demands. In practice, however, a demand may not be served from its nearest facility if that facility is engaged in serving other demands. This makes it a requirement to assign backup services so as to improve response time and service quality. The level of backup service is a key, strategic-level planning factor, and must be taken into consideration carefully. Moreover, in emergency service operations conducted in congested demand regions, demand assignment policy is another important factor that affects the system performance. Models failing to adopt sufficient levels of backup service and realistic demand assignment policies may significantly deteriorate the system performance.Considering the classic p-median problem (pMP) location model, this paper investigates the effects of backup service level, demand assignment policy, demand density, and number of facilities and their locations on the solution performance in terms of multiple metrics. For this purpose, we adopt a combined optimization and simulation approach. We will first modify the classic pMP to account for distances to backup services. Next, we employ a discrete event simulation to evaluate the performance of location schemes obtained from the deterministic mathematical model. Our results provide insights for decision-makers while planning ESS operations.     

Probabilistic Formulation of the Emergency Service Location Problem

The problem of locating emergency service facilities is studied under the assumption that the locations of incidents (accidents, fires, or customers) are random variables. The probability distribution for rectilinear travel time between a new facility location and the random location of the incident P _i is developed for the case of P _i being uniformly distributed over a rectangular region. The location problem is considered in a discrete space. A deterministic formulation is obtained and recognized to be a set cover problem. Probabilistic variation of the central facility location problem is also presented.An example and some computational experience are provided to emphasize the impact of the probabilistic formulation on the location decision.     

The design of multiactivity multifacility systems

We consider a service/distribution system in which each of N activities is to be carried out at one or several facility locations. Each activity is to be assigned to one out of a specified set of configurations; each configuration is a specific subset of the set of L facilities being considered, along with a specific strategy for their use. We call such a system a multiactivity multifacility system and present a mathematical formulation for its optimal design that includes capacity restrictions at the facilities and the treatment of multiple criteria. The design problem is simply to choose an appropriate configuration for each of the N activities. We discuss various criteria, and we show that the multiactivity multifacility design problem includes many familiar discrete location problems as special cases. We introduce a 0–1 linear optimization model called the Team Generalized Assignment Problem (T-GAP) and show that parametric solution of a T-GAP will yield all efficient solutions of the multiactivity multifacility design problem with multiple criteria. Rather than attempting to find all efficient solutions, however, we advocate an interactive approach and describe an interactive branch-and-bound algorithm that solves the design problem as a finite sequence of T-GAP's.     

On the uniqueness of optimal solutions in continuous location theory

This paper deals with the uniqueness of an optimal solution in general continuous single facility minisum and minimax location problems. We define the concept of an S-norm and obtain general conditions which guarantee the existence of a unique optimal location. Some consequences for the uniqueness of optimal locations in multi-facility location problems are discussed.     

p-Median theorems for competitive locations

In competitive location theory, one wishes to optimally choose the locations ofr facilities to compete againstp existing facilities for providing service (or goods) to the customers who are at given discrete points (or nodes). One normally assumes that: (a) the level of demand of each customer is fixed (i.e. this demand is not a function of how far a customer is from a facility), and (b) the customer always uses the closest available facility. In this paper we study competitive locations when one or both of the above assumptions have been relaxed. In particular, we show that for each case and under certain assumptions, there exists a set of optimal locations which consists entirely of nodes.This work was supported by a National Science Foundation Grant ECS-8121741.     

Extreme points of discrete location polyhedra

The problem of characterizing extreme points of a family of polyhedra is considered. This family embraces a variety of linear relaxations of feasible regions of discrete location problems. After characterizing the extreme points by means of a homogeneous system of linear equations, we obtain, as particular cases, four problems which have already been treated from a polyhedral point of view in the literature. Finally, we show that our characterization improves the one known for the Simple Plant Location Problem and corrects the one established for the Two-Level Uncapacitated Facility Location Problem. The first and third authors were supported by Fundación Séneca, project PB/11/FS/97     

The transfer point location problem

In this paper, we introduce the transfer point location problem. Demand for emergency service is generated at a set of demand points who need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The general model involves the location of p helicopter pads and one facility. In this paper, we solve the special case where the location of the facility is known and the best location of one transfer point that serves a set of demand points is sought. Both minisum and minimax versions of the models are investigated. In follow up papers we investigate the general model using the results obtained in this paper.     

The location of public facilities intermediate to the journey to work

Location—allocation models typically locate facilities with respect to points to be served, for example to the homes of potential patrons. Certain types of facility, however, are employed by persons who travel to the facility from their homes and continue their journey to another location. Child care facilities are an example of this pattern of patronage, with parents dropping children off at a centre en route to work. The paper presents a discrete-space location—allocation model minimizing the diversion of patrons' journeys to work. The problem reduces to the structure and combinatorial dimensions of the simple P-median problem. The model is applied to the transit worktrip patterns of single parents in Edmonton, Canada. The facilities generated by the model tend to central locations in the city where workplaces are concentrated and transit connections are efficient. The model provides a compromise between ones minimizing home-facility travel times and facility-workplace travel times.     

A specialized branch & bound & cut for Single-Allocation Ordered Median Hub Location problems

The Single-Allocation Ordered Median Hub Location problem is a recent hub model introduced by Puerto et al. (2011) [32] that provides a unifying analysis of the class of hub location models. Indeed, considering ordered objective functions in hub location models is a powerful tool in modeling classic and alternative location paradigms, that can be applied with success to a large variety of problems providing new distribution patterns induced by the different users’ roles within the supply chain network. In this paper, we present a new formulation for the Single-Allocation Ordered Median Hub Location problem and a branch-and-bound-and-cut (B&B&Cut) based algorithm to solve optimally this model. A simple illustrative example is discussed to demonstrate the technique, and then a battery of test problems with data taken from the AP library are solved. The paper concludes that the proposed B&B&Cut approach performs well for small to medium sized problems.     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

Analysis of centroid aggregation for the Euclidean distance p-median problem

Demand data aggregation results in loss of information and thereby induces errors in the locational decision being made, both in the facility location configurations (optimality error) and in the computed value of the objective function (cost error). The aggregation effect is quite problem-specific, depending on the aggregation scheme used and on the demand pattern. In this paper, we perform a theoretical analysis for the centroid aggregation effect on the Euclidean distance p-median location problem. We study the worst case and average case errors, and in the multi-facility location model Source C error is closely examined. The results of the paper are illustrated via numerical examples and some empirical findings of previous work are interpreted using our analytical results.     

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 flexible model and efficient solution strategies for discrete location problems

Flexible discrete location problems are a generalization of most classical discrete locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer, which depends on the position of that cost relative to the costs of fulfilling the demand of other customers.In this paper a covering type of model for the discrete ordered median problem is presented. For the solution of this model two sets of valid inequalities, which reduces the number of binary variables tremendously, and several variable fixing strategies are identified. Based on these concepts a specialized branch & cut procedure is proposed and extensive computational results are reported.     

Robust supply chain network design with service level against disruptions and demand uncertainties: A real-life case

We have developed a stochastic mathematical formulation for designing a network of multi-product supply chains comprising several capacitated production facilities, distribution centres and retailers in markets under uncertainty. This model considers demand-side and supply-side uncertainties simultaneously, which makes it more realistic in comparison to models in the existing literature. In this model, we consider a discrete set as potential locations of distribution centres and retailing outlets and investigate the impact of strategic facility location decisions on the operational inventory and shipment decisions of the supply chain. We use a path-based formulation that helps us to consider supply-side uncertainties that are possible disruptions in manufacturers, distribution centres and their connecting links. The resultant model, which incorporates the cut-set concept in reliability theory and also the robust optimisation concept, is a mixed integer nonlinear problem. To solve the model to attain global optimality, we have created a transformation based on the piecewise linearisation method. Finally, we illustrate the model outputs and discuss the results through several numerical examples, including a real-life case study from the agri-food industry.     

A Continuous Location-Allocation Problem with Zone-Dependent Fixed Cost

A zone-dependent fixed cost is introduced within the framework of minisum location of facilities in the continuous space. An efficient algorithm for determining the optimal solution for the single facility location problem is put forward, and its properties are validated. A hypothetical example is given to illustrate the algorithm. Some heuristic procedures are proposed for the multi-facility case with encouraging results.     

Relaxed voting and competitive location under monotonous gain functions on trees

We examine competitive location problems where two competitors serve a good to users located in a network. Users decide for one of the competitors based on the distance induced by an underlying tree graph. The competitors place their server sequentially into the network. The goal of each competitor is to maximize his benefit which depends on the total user demand served. Typical competitive location problems include the (1,X₁)-medianoid, the (1,1)-centroid, and the Stackelberg location problem.An additional relaxation parameter introduces a robustness of the model against small changes in distance. We introduce monotonous gain functions as a general framework to describe the above competitive location problems as well as several problems from the area of voting location such as Simpson, Condorcet, security, and plurality.In this paper we provide a linear running time algorithm for determining an absolute solution in a tree where competitors are allowed to place on nodes or on inner points. Furthermore we discuss the application of our approach to the discrete case.     

Facility location for market capture when users rank facilities by shorter travel and waiting times

A firm wants to locate several multi-server facilities in a region where there is already a competitor operating. We propose a model for locating these facilities in such a way as to maximize market capture by the entering firm, when customers choose the facilities they patronize, by the travel time to the facility and the waiting time at the facility. Each customer can obtain the service or goods from several (rather than only one) facilities, according to a probabilistic distribution. We show that in these conditions, there is demand equilibrium, and we design an ad hoc heuristic to solve the problem, since finding the solution to the model involves finding the demand equilibrium given by a nonlinear equation. We show that by using our heuristic, the locations are better than those obtained by utilizing several other methods, including MAXCAP, p-median and location on the nodes with the largest demand.     

Emergency ambulance deployment in Barbados: a multi-objective approach

A multi-objective version of the Maximum Availability Location Problem is presented in this paper. The assumption of server independence is relaxed by adopting the approach of the Queuing Probabilistic Location Set Covering Problem for calculating the probability that all servers in a given region are busy. The first objective seeks to maximize the population receiving coverage within a given distance standard and with a given level of reliability. The second objective chooses those locations which minimize the cost of covering the population. This model is used to obtain sets of good locations using data obtained from the Barbados Emergency Ambulance Service. The solutions obtained from the optimization model are then subject to a detailed analysis by simulation. The results reveal the potentially good performance of the system, when locations derived from the optimization model are used.