A computational evaluation of a general branch-and-price framework for capacitated network location problems

The purpose of this paper is to illustrate a general framework for network location problems, based on column generation and branch-and-price. In particular we consider capacitated network location problems with single-source constraints. We consider several different network location models, by combining cardinality constraints, fixed costs, concentrator restrictions and regional constraints. Our general branch-and-price-based approach can be seen as a natural counterpart of the branch-and-cut-based commercial ILP solvers, with the advantage of exploiting the tightness of the lower bound provided by the set partitioning reformulation of network location problems. Branch-and-price and branch-and-cut are compared through an extensive set of experimental tests.     

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.     

On solving the discrete location problems when the facilities are prone to failure

The classical discrete location problem is extended here, where the candidate facilities are subject to failure. The unreliable location problem is defined by introducing the probability that a facility may become inactive. The formulation and the solution procedure have been motivated by an application to model and solve a large size problem for locating base stations in a cellular communication network. We formulate the unreliable discrete location problems as 0–1 integer programming models, and implement an enhanced dual-based solution method to determine locations of these facilities to minimize the sum of fixed cost and expected operating (transportation) cost. Computational tests of some well-known problems have shown that the heuristic is efficient and effective for solving these unreliable location problems.     

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.     

Network hub location problems: The state of the art

Hubs are special facilities that serve as switching, transshipment and sorting points in many-to-many distribution systems. The hub location problem is concerned with locating hub facilities and allocating demand nodes to hubs in order to route the traffic between origin–destination pairs. In this paper we classify and survey network hub location models. We also include some recent trends on hub location and provide a synthesis of the literature.     

Filtering Policies in Loss Queuing Network Location Problems

In this paper we deal with two stationary loss queuing network location models. We analyze the influence of filtering policies on the locational aspect of the problems. We assume that requests for service are placed at nodes of a transportation network and they arrive in time as independent homogeneous Poisson processes with different input rates. The considered policies only cover a given proportion of requests even if there are idle service units. This proportion is stationary and fixed in advance and only depends on the node where the request is originated. The objective is to find the location of the facilities together with the filtering policy to be applied that minimize the expected total cost per unit time with respect to a given cost structure. Properties and computational results are presented enabling the resolution of these problems efficiently and showing the good performance of filtering policies in terms of both the overall operating costs, and the demand that is served.     

Integer linear programming models for grid-based light post location problem

Selecting optimal location is a key decision problem in business and engineering. This research focuses to develop mathematical models for a special type of location problems called grid-based location problems. It uses a real-world problem of placing lights in a park to minimize the amount of darkness and excess supply. The non-linear nature of the supply function (arising from the light physics) and heterogeneous demand distribution make this decision problem truly intractable to solve. We develop ILP models that are designed to provide the optimal solution for the light post problem: the total number of light posts, the location of each light post, and their capacities (i.e., brightness). Finally, the ILP models are implemented within a standard modeling language and solved with the CPLEX solver. Results show that the ILP models are quite efficient in solving moderately sized problems with a very small optimality gap.     

The least element property of center location on tree networks with applications to distance and precedence constrained problems

In the classicalp-center location model on a network there is a set of customers, and the primary objective is to selectp service centers that will minimize the maximum distance of a customer to a closest center. Suppose that thep centers receive their supplies from an existing central depot on the network, e.g. a warehouse. Thus, a secondary objective is to locate the centers that optimize the primary objective as close as possible to the central depot. We consider tree networks and twop-center models. We show that the set of optimal solutions to the primary objective has a semilattice structure with respect to some natural ordering. Using this property we prove that there is ap-center solution to the primary objective that simultaneously minimizes every secondary objective function which is monotone nondecreasing in the distances of thep centers from the existing central depot.Restricting the location models to a rooted path network (real line) we prove that the above results hold for the respective classicalp-median problems as well.     

The Ordered Gradual Covering Location Problem on a Network

In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. The Ordered Median Location problem is a generalization of most of the classical locations problems like p-median or p-center problems. The OGCLP model provides a unifying structure for the standard location models and allows us to develop objectives sensitive to both relative and absolute customer-to-facility distances. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities is already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results.     

The minmax regret gradual covering location problem on a network with incomplete information of demand weights

The gradual covering location problem seeks to establish facilities on a network so as to maximize the total demand covered, allowing partial coverage. We focus on the gradual covering location problem when the demand weights associated with nodes of the network are random variables whose probability distributions are unknown. Using only information on the range of these random variables, this study is aimed at finding the “minmax regret” location that minimizes the worst-case coverage loss. We show that under some conditions, the problem is equivalent to known location problems (e.g. the minmax regret median problem). Polynomial time algorithms are developed for the problem on a general network with linear coverage decay functions.     

Proprietor and customer costs in the incomplete hub location-routing network topology

The hub location problem finds the location of hubs and allocates the other nodes to them. It is widely supposed the network created with the hub nodes is complete in the extensive literature. Relaxation of this basic supposition forms the present work. The model minimizes the cost of the proprietor, including the fixed costs of hubs, hub links and spoke links. Costs of hub and spoke links are contemplated as fixed cost or maintenance cost. Moreover, the model considers routing costs of customers who want to travel from origins to destinations. In this study, we offer a model to the multiple allocations of the hub location problems, under the incomplete hub location-routing network design. This model is easily transformed to other hub location problems using one or more constraints. No network format is dictated on the hub network. We suggest a set of valid inequalities for the formulation. Some lower bounds are developed using a Lagrangian relaxation approach and the valid inequalities. Computational analyses evaluate the performances of the lower bounding implementations and valid inequalities. Furthermore, we explore the effects of several factors on the design and solution time of the problem formulation.     

Improved algorithms for several network location problems with equality measures

We consider single facility location problems with equity measures, defined on networks. The models discussed are, the variance, the sum of weighted absolute deviations, the maximum weighted absolute deviation, the sum of absolute weighted differences, the range, and the Lorenz measure. We review the known algorithmic results and present improved algorithms for some of these models.     

需求不确定下应急医疗服务站鲁棒配置模型与算法

大型突发事件发生后需要快速启动应急救灾网络,合理配置应急医疗服务站。本文考虑各应急医疗服务站选址节点需求的不确定性,引入三个不确定水平参数,构建四类不确定需求集合(box, ellipsoid, polyhedron和interval-polyhedron)对应的应急医疗服务站鲁棒配置模型,运用分支-切割算法求解,最后,进行需求扰动比例的灵敏度分析。算例结果表明,四类不确定需求集下的鲁棒配置模型中,ellipsoid不确定需求集合配置模型开放设施较少,总成本最小,鲁棒性较好。决策者还可以根据风险偏好选择不确定水平和需求扰动比例的组合,以使得总成本最小。     

Locating the two-median of a tree network with continuous link demands

Typical formulations of thep-median problem on a network assume discrete nodal demands. However, for many problems, demands are better represented by continuous functions along the links, in addition to nodal demands. For such problems, optimal server locations need not occur at nodes, so that algorithms of the kind developed for the discrete demand case can not be used. In this paper we show how the 2-median of a tree network with continuous link demands can be found using an algorithm based on sequential location and allocation. We show that the algorithm will converge to a local minimum and then present a procedure for finding the global minimum solution.     

On destination optimality in asymmetric distance Fermat-Weber problems

This paper introduces skewed norms, i.e. norms perturbed by a linear function, which are useful for modelling asymmetric distance measures. The Fermat-Weber problem with mixed skewed norms is then considered. Using subdifferential calculus we derive exact conditions for a destination point to be optimal, thereby correcting and completing some recent work on asymmetric distance location problems. Finally the classical dominance theorem is generalized to Fermat-Weber problems with a fixed skewed norm.     

A cooperative location game based on the 1-center location problem

In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We call these games the Minimum Radius Location Games (MRLG).We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the ?_p metric spaces defined over R^d.     

General network design: A unified view of combined location and network design problems

This paper presents a unified framework for the general network design problem which encompasses several classical problems involving combined location and network design decisions. In some of these problems the service demand relates users and facilities, whereas in other cases the service demand relates pairs of users between them, and facilities are used to consolidate and re-route flows between users. Problems of this type arise in the design of transportation and telecommunication systems and include well-known problems such as location-network design problems, hub location problems, extensive facility location problems, tree-star location problems and cycle-star location problems, among others. Relevant modeling aspects, alternative formulations and possible algorithmic strategies are presented and analyzed.     

Locating a 1-Center on a Manhattan Plane with “Arbitrarily” Shaped Barriers

Barriers commonly occur in practical location and layout problems and are regions where neither travel through nor location of the new facility is permitted. Along the lines of (Larson and Sadiq, 1983) we divide the feasible location region into cells. To overcome the additional complications introduced by the center objective, we develop new analysis and classify cells based on number of cell corners. A procedure to determine the optimal location is established for each class of cells. The overall complexity of the approach is shown to be polynomially bounded. Also, an analogy is drawn to the center problem on a network and generalizations of the model are discussed.     

Location–Allocation of Multiple-Server Service Centers with Constrained Queues or Waiting Times

Recently, the authors have formulated new models for the location of congested facilities, so to maximize population covered by service with short queues or waiting time. In this paper, we present an extension of these models, which seeks to cover all population and includes server allocation to the facilities. This new model is intended for the design of service networks, including health and EMS services, banking or distributed ticket-selling services. As opposed to the previous Maximal Covering model, the model presented here is a Set Covering formulation, which locates the least number of facilities and allocates the minimum number of servers (clerks, tellers, machines) to them, so to minimize queuing effects. For a better understanding, a first model is presented, in which the number of servers allocated to each facility is fixed. We then formulate a Location Set Covering model with a variable (optimal) number of servers per service center (or facility). A new heuristic, with good performance on a 55-node network, is developed and tested.     

基于离散与连续选址相结合的平面选址问题研究——以华北石油局大牛地气田污水处理厂选址为例

选址问题的研究中,大多考虑的是理论距离(例如欧式距离等);但在实际问题中,真实的公路运输距离和理论距离有较大差异,并且修建公路的成本较高.在尽量利用当前的公路交通网络同时,又能得到最优选址,在现实中具有重要意义.以华北石油局大牛地气田第一采气厂污水处理厂选址为例,分别采用重心法选址、最大值最小化选址、多目标选址等选址的方法得到污水处理厂的备选点,并结合实际距离模拟出了各个备选点的运输费用,再综合考虑当地政策和交通状况等因素,最终得到了使得运输费用最低的新的污水处理厂的位置坐标P(9.33,11.79),在该位置建立污水处理厂比之前的运输方案每年大约可节约511万元的运输费用.方法最大的优点是减小了在选址过程中理论距离与实际距离的误差,在现实中具有一定的指导意义.