A Barzilai-Borwein-based heuristic algorithm for locating multiple facilities with regional demand

We are interested in locations of multiple facilities in the plane with the aim of minimizing the sum of weighted distance between these facilities and regional customers, where the distance between a facility and a regional customer is evaluated by the farthest distance from this facility to the demand region. By applying the well-known location-allocation heuristic, the main task for solving such a problem turns out to solve a number of constrained Weber problems (CWPs). This paper focuses on the computational contribution in this topic by developing a variant of the classical Barzilai-Borwein (BB) gradient method to solve the reduced CWPs. Consequently, a hybrid Cooper type method is developed to solve the problem under consideration. Preliminary numerical results are reported to verify the evident effectiveness of the new method.     

Distress among disaster-affected populations: delay in relief provision

Central to humanitarian logistics is the minimization of distress among impacted populations in the aftermath of a disaster. In this paper, we characterize two levels of distress, termed criticality and destitution, with respect to the delay provision of relief items. Delay in provision of a relief item will lead to destitution for a tolerable number of days, beyond which it will lead to criticality. We develop a mixed-integer goal program that quantifies these two metrics with respect to the number of days without provision of each of a set of relief items. The model determines the allocation of resources and the distribution of available relief items in a manner that minimizes criticality and destitution in affected population segments. The use of the model is demonstrated for the aftermath of a catastrophic earthquake in Istanbul, expected to occur by 2030.     

A multicriteria facility location model for municipal solid waste management in North Greece

Up to 2002, Hellenic Solid Waste Management (SWM) policy specified that each of the country’s 54 prefectural governments plan its own SWM system. After 2002, this authority was shifted to the country’s 13 regions entirely. In this paper, we compare and contrast regional and prefectural SWM planning in Central Macedonia. To design the prefectural plan, we assume that each prefecture must be self-sufficient, and we locate waste facilities in each prefecture. In contrast, in the regional plan, we assume cooperation between prefectures and locate waste facilities to serve the entire region. We present a new multicriteria mixed-integer linear programming model to solve the location–allocation problem for municipal SWM at the regional level. We apply the lexicographic minimax approach to obtain a “fair” nondominated solution, a solution with all normalized objectives as equal to one another as possible. A solution to the model consists of locations and technologies for transfer stations, material recovery facilities, incinerators and sanitary landfills, as well as the waste flow between these locations.     

A robust disaster preparedness model for effective and fair disaster response

Humanitarian network design decisions belonging to the preparedness stage of disaster management life-cycle are of critical importance since they set the frame for all further post-disaster operations. Having an adequate number of strategically located storage and distribution centers for critical supplies is the key that enables effectiveness, efficiency and fairness when responding to a disaster situation. The preparedness model proposed in this study selects locations and inventory levels of these facilities such that the right mix of relief items can be supplied at the right time. Our mixed integer linear model aims to find a robust relief network design that satisfies the demand for all given disaster scenarios, and to help achieve a better response during the response stage when the relief items are distributed. The assumptions and the parameters used in the model are justified by authorities of humanitarian organizations. We propose a logic-based Benders decomposition approach to solve this problem to optimality. Although the problem is NP-hard, our numerical studies demonstrate that it is possible to obtain optimal or very good solutions to problem instances with realistic sizes.     

A robust model for a leader–follower competitive facility location problem in a discrete space

This paper aims at determining the optimal locations for the leader’s new facilities under the condition that the number of the follower’s new facilities is unknown for the leader. The leader and the follower have some facilities in advance. The first competitor, the leader, opens p new facilities in order to increase her own market share. On the other hand, she knows that her competitor, the follower, will react to her action and locate his new facilities as well. The number of the follower’s new facilities is unknown for the leader but it is assumed that the leader knows the probability of opening different numbers of the follower’s new facilities. The leader aims at maximizing her own market share after the follower’s new facilities entry. The follower’s objective is also to maximize his own market share. Since the number of the follower’s new facilities is unknown for leader, “Robust Optimization” is used for maximizing the leader’s market share and making the obtained results “robust” in various scenarios in terms of different numbers of the follower’s new facilities. The optimal locations for new facilities of both the leader and the follower are chosen among pre-determined potential locations. It is assumed that the demand is inelastic. The customers probabilistically meet their demands from all different facilities and the demand level which is met by each facility is computed by Huff rule. The computational experiments have been applied to evaluate the efficiency of the proposed model.     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.     

A discrete competitive facility location model with variable attractiveness

We consider the discrete version of the competitive facility location problem in which new facilities have to be located by a new market entrant firm to compete against already existing facilities that may belong to one or more competitors. The demand is assumed to be aggregated at certain points in the plane and the new facilities can be located at predetermined candidate sites. We employ Huff's gravity-based rule in modelling the behaviour of the customers where the probability that customers at a demand point patronize a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. The objective of the firm is to determine the locations of the new facilities and their attractiveness levels so as to maximize the profit, which is calculated as the revenue from the customers less the fixed cost of opening the facilities and variable cost of setting their attractiveness levels. We formulate a mixed-integer nonlinear programming model for this problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and another branch-and-bound method with nonlinear programming relaxation. Computational results obtained on a set of randomly generated instances show that the last method outperforms the others in terms of accuracy and efficiency and can provide an optimal solution in a reasonable amount of time.     

Generation of simulation input scenarios using bootstrap methods

Simulation modellers frequently face a choice between fidelity and variety in their input scenarios. Using an historical trace provides only one realistic scenario. Using the input modelling facilities in commercial simulation software may provide any number of unrealistic scenarios. We ease this dilemma by developing a way to use the moving blocks bootstrap to convert a single trace into an unlimited number of realistic input scenarios. We do this by setting the bootstrap block size to make the bootstrap samples mimic independent realizations in terms of the distribution of distance between pairs of inputs. We measure distance using a new statistic computed from zero crossings. We estimate the best block size by scaling up an estimate computed by analysing subseries of the trace.     

Stop location design in public transportation networks: covering and accessibility objectives

We consider the location of new stops along the edges of an existing public transportation network. Examples of StopLoc include the location of bus stops along some given bus routes or of railway stations along the tracks in a railway system. In order to evaluate the decision assume that potential customers in given demand facilities are known. Two objectives are proposed. In the first one, we minimize the number of stations such that any of the demand facilities can reach a closest station within a given distance of r. In the second objective, we fix the number of new stations and minimize the sum of the distances between demand facilities and stations. The resulting two problems CovStopLoc and AccessStopLoc are solved by a reduction to a classical set covering and a restricted location problem, respectively. We implement the general ideas in two different environments, the plane, where demand facilities are represented by coordinates, and in networks, where they are nodes of a graph.     

Variable neighbourhood search heuristics for the probabilistic multi-source Weber problem

The Multi-source Weber Problem (MWP) is concerned with locating m facilities in the Euclidean plane, and allocating these facilities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation for the probabilistic MWP called the PMWP. For its solution, we propose two heuristics based on variable neighbourhood search (VNS). Computational results obtained on a number of test instances show that the VNS heuristics improve the performance of a probabilistic alternate location-allocation heuristic referred to as PALA. In its original form, the applicability of the new heuristics depends on the existence of a closed-form expression for the expected distances between facilities and customers. Unfortunately, such an expression exists only for a few distance function and probability distribution combinations. We therefore use two approximation methods for the expected distances, which make the VNS heuristics applicable for any distance function and bivariate distribution of customer locations.     

Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique

In this paper, we propose two exact algorithms for the GQAP (generalized quadratic assignment problem). In this problem, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized. This problem generalizes the well-known quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branch-and-bound scheme with a new Lagrangean relaxation procedure over a known RLT (Reformulation-Linearization Technique) formulation. We also apply transformational lower bounding techniques to improve the performance of the new procedure. We report detailed experimental results where 19 out of 21 instances with up to 35 facilities are solved in up to a few days of running time. Six of these instances were open.     

A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems where Distances are Rectangular

The problem of locating new facilities with respect to existing facilities is stated as a linear programming problem where inter-facility distances are assumed to be rectangular. The criterion of location is the minimization of the maximum weighted rectangular distance in the system. Linear constraints which (a) limit the new facility locations and (b) enforce upper bounds on the distances between new and existing facilities and between new facilities can be included. The dual programming problem is formulated in order to provide for an efficient solution procedure. It is shown that the duLal variables provide information abouLt the complete range of new facility locations which satisfy the minimax criterion.     

A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage

In this study, we present a bi-objective facility location model that considers both partial coverage and service to uncovered demands. Due to limited number of facilities to be opened, some of the demand nodes may not be within full or partial coverage distance of a facility. However, a demand node that is not within the coverage distance of a facility should get service from the nearest facility within the shortest possible time. In this model, it is assumed that demand nodes within the predefined distance of opened facilities are fully covered, and after that distance the coverage level decreases linearly. The objectives are defined as the maximization of full and partial coverage, and the minimization of the maximum distance between uncovered demand nodes and their nearest facilities. We develop a new multi-objective genetic algorithm (MOGA) called modified SPEA-II (mSPEA-II). In this method, the fitness function of SPEA-II is modified and the crowding distance of NSGA-II is used. The performance of mSPEA-II is tested on randomly generated problems of different sizes. The results are compared with the solutions of the most well-known MOGAs, NSGA-II and SPEA-II. Computational experiments show that mSPEA-II outperforms both NSGA-II and SPEA-II.     

An arc cover–path-cover formulation and strategic analysis of alternative-fuel station locations

In this study, we present a new formulation of the generalized flow-refueling location model that takes vehicle range and trips between origin–destination pairs into account. The new formulation, based on covering the arcs that comprise each path, is more computationally efficient than previous formulations or heuristics. Next, we use the new formulation to provide managerial insights for some key concerns of the industry, such as: whether infrastructure deployment should focus on locating clusters of facilities serving independent regions or connecting these regions by network of facilities; what is the impact of uncertainty in the origin–destination demand forecast; whether station locations will remain optimal as higher-range vehicles are introduced; and whether infrastructure developers should be willing to pay more for stations at higher-cost intersections. Experiments with real and random data sets are encouraging for the industry, as optimal locations tend to be robust under various conditions.     

Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach

Models developed to analyze facility location decisions have typically optimized one or more objectives, subject to physical, structural, and policy constraints, in a static or deterministic setting. Because of the large capital outlays that are involved, however, facility location decisions are frequently long-term in nature. Consequently, there may be considerable uncertainty regarding the way in which relevant parameters in the location decision will change over time. In this paper, we propose two approaches for analyzing these types of dynamic location problems, focussing on situations where the total number of facilities to be located in uncertain. We term this type of location problem NOFUN (Number Of Facilities Uncertain). We analyze the NOFUN problem using two well-established decision criteria: the minimization of expected opportunity loss (EOL), and the minimization of maximum regret. In general, these criteria assume that there are a finite number of decision options and a finite number of possible states of nature. The minisum EOL criterion assumes that one can assign probabilities for the occurrence of the various states of nature and, therefore, find the initial set of facility locations that minimize the sum of expected losses across all future states. The minimax regret criteria finds the pattern of initial facility locations whose maximum loss is minimized over all possible future states.     

连续设施选址:模型、方法与应用

给定度量空间和该空间中的若干顾客,设施选址为在该度量空间中确定新设施的位置使得某种目标达到最优。连续设施选址是设施选址中的一类重要问题,其中的设施可在度量空间的某连续区域上进行选址。本文对连续设施选址的模型、算法和应用方面的工作进行了综述。文章首先讨论了连续设施选址中几个重要元素,包括新设施个数、距离度量函数、目标函数;然后介绍了连续选址中的几种经典模型和拓展模型;接着概述了求解连续选址问题的常用优化方法和技术,包括共轭对偶、全局优化、不确定优化、变分不等式方法、维诺图;最后介绍了连续设施选址的重要应用并给出了研究展望。     

The hierarchical traveling salesman problem

The distribution of relief aid is a complex problem where the operations have to be managed efficiently due to limited resources. We present a routing problem for relief operations whose primary goal is to satisfy demand for relief supplies at many locations taking into account the urgency of each demand. We have a single vehicle of unlimited capacity. Each node (location) has a demand and a priority. The priority indicates the urgency of the demand. Typically, nodes with the highest priorities need to be visited before lower priority nodes. We describe a new and interesting model for humanitarian relief routing that we call the hierarchical traveling salesman problem (HTSP). We compare the HTSP and the classical TSP in terms of worst-case behavior. We obtain a simple, but elegant result that exhibits the fundamental tradeoff between efficiency (distance) and priority and we provide several related observations and theorems.     

Bicriteria efficiency/equity hierarchical location models for public service application

As is often the case in healthcare provision, public services may offer facilities at a hierarchy of levels in different locations, ranging from basic to specialised levels of care. In addition to efficiency objectives, with public services there is the concern of equity of provision when locating new facilities. We present, as a tool-kit for decision makers, a range of discrete hierarchical location models with bicriteria efficiency/equity objectives. These models are for use in location of facilities within hierarchical systems where a fair but efficient hierarchical service is sought. The hierarchical models have as efficiency criteria both p-median and maximal-covering types. These components are combined in a novel manner with appropriate equity objectives to give decision makers a range of choices of scenarios. We illustrate use of the models in a healthcare setting.     

Simulation of capacity expansion and sequencing alternatives for a sheet metal producer

We present a simulation case study carried out for a make-to-order aluminium sheet producer located in Istanbul, Turkey. We are concerned with a subsystem of the factory consisting of continuous casting, cold rolling, and annealing processes. Two simulation models are developed: (1) a combined model for studying the casting process only; (2) a discrete event model for comparing capacity expansion alternatives and order sequencing rules in the subsystem. Operational characteristics of the real system and past data are extensively analysed for modelling and validation purposes. Capacity expansion and sequencing alternatives are evaluated in an experimental design setting with the objectives of satisfying the demand, balancing the process loads, and keeping the work-in-process inventory under control.     

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.