Improved approximation for the capacitated inventory access point problem

The Inventory Access Point (IAP) is the single-item lot-sizing problem where a single customer faces demands in a discrete planning horizon, and the goal is to find a replenishment policy that minimizes the total inventory and ordering costs. While the uncapacitated version is polynomial, only a 3-approximation is known for the capacitated case. We improve this factor to 2.619 and, as a byproduct, we also improve the best factor for SIRPFL, which is a variant with multiple depots and customers.     

A continuous approximation approach for the integrated facility-inventory allocation problem

In today’s retail business many companies have a complex distribution network with several national and regional distribution centers. This article studies an integrated facility location and inventory allocation problem for designing a distribution network with multiple distribution centers and retailers. The key decisions are where to locate the regional distribution centers (RDCs), how to assign retail stores to RDCs and what should be the inventory policy at the different locations such that the total network cost is minimized. Due to the complexity of the problem, a continuous approximation (CA) model is used to represent the network. Nonlinear programming techniques are developed to solve the optimization problems. The main contribution of this work lies in developing a new CA modeling technique when the discrete data cannot be modeled by a continuous function and applying this technique to solve an integrated facility location-allocation and inventory-management problem. Our methodology is illustrated with the network from a leading US retailer. Numerical analysis suggests that the total cost is significantly lower in the case of the integrated model as compared with the non-integrated model, where the location-allocation and inventory-management problems are considered separately. This paper also studies the effects of changing parameter values on the optimal solutions and to point out some management implications.     

Contour line construction for a new rectangular facility in an existing layout with rectangular departments

In a recent paper, Savas et al. [S. Savas, R. Batta, R. Nagi, Finite-size facility placement in the presence of barriers to rectilinear travel, Operations Research 50 (6) (2002) 1018–1031] consider the optimal placement of a finite-sized facility in the presence of arbitrarily shaped barriers under rectilinear travel. Their model applies to a layout context, since barriers can be thought to be existing departments and the finite-sized facility can be viewed as the new department to be placed. In a layout situation, the existing and new departments are typically rectangular in shape. This is a special case of the Savas et al. paper. However the resultant optimal placement may be infeasible due to practical constraints like aisle locations, electrical connections, etc. Hence there is a need for the development of contour lines, i.e. lines of equal objective function value. With these contour lines constructed, one can place the new facility in the best manner. This paper deals with the problem of constructing contour lines in this context. This contribution can also be viewed as the finite-size extension of the contour line result of Francis [R.L. Francis, Note on the optimum location of new machines in existing plant layouts, Journal of Industrial Engineering 14 (2) (1963) 57–59].     

The stochastic location model with risk pooling

In this paper, we present a stochastic version of the location model with risk pooling (LMRP) that optimizes location, inventory, and allocation decisions under random parameters described by discrete scenarios. The goal of our model (called the stochastic LMRP, or SLMRP) is to find solutions that minimize the expected total cost (including location, transportation, and inventory costs) of the system across all scenarios. The location model explicitly handles the economies of scale and risk-pooling effects that result from consolidating inventory sites. The SLMRP framework can also be used to solve multi-commodity and multi-period problems.     

A computational approach for eliminating error in the solution of the location set covering problem

The location set covering problem continues to be an important and challenging spatial optimization problem. The range of practical planning applications underscores its importance, spanning fire station siting, warning siren positioning, security monitoring and nature reserve design, to name but a few. It is challenging on a number of fronts. First, it can be difficult to solve for medium to large size problem instances, which are often encountered in combination with geographic information systems (GIS) based analysis. Second, the need to cover a region efficiently often brings about complications associated with the abstraction of geographic space. Representation as points can lead to significant gaps in actual coverage, whereas representation as polygons can result in a substantial overestimate of facilities needed. Computational complexity along with spatial abstraction sensitivity combine to make advances in solving this problem much needed. To this end, a solution framework for ensuring complete coverage of a region with a minimum number of facilities is proposed that eliminates potential error. Applications to emergency warning siren and fire station siting are presented to demonstrate the effectiveness of the developed approach. The approach can be applied to convex, non-convex and non-contiguous regions and is unaffected by arbitrary initial spatial representations of space.     

Locating a minisum circle in the plane

We consider the problem of locating a circle with respect to existing facilities in the plane such that the sum of weighted distances between the circle and the facilities is minimized, i.e., we approximate a set of given points by a circle regarding the sum of weighted distances. If the radius of the circle is a variable we show that there always exists an optimal circle passing through two of the existing facilities. For the case of a fixed radius we provide characterizations of optimal circles in special cases. Solution procedures are suggested.     

Facility location in the presence of forbidden regions,I: Formulation and the case of Euclidean distance with one forbidden circle

A constrained form of the Weber problem is formulated in which no path is permitted to enter a prespecified forbidden region $\text{R}$ of the plane. Using the calculus of variations the shortest path between two points $\text{x}\text{,}\text{y}\text{?}\text{R}$ which does not intersect $\text{R}$ is determined. If $\text{d(}\text{x}\text{,}\text{y}\text{)}$ is unconstrained distance, we denote the shortes distance along a feasible path by $\text{d}\text{(}\text{x}\text{y}\text{)}$. The constrained Weber problem is, then: given points $\text{x}{}_{\mathrm{j}}\text{?}\text{R}$ and positive weights w_j, j = 1,2,…,n, find a point $\text{x}\text{?}\text{R}$ such that

$\text{f(}\text{x}\text{)=}\text{Σ}\text{n}\text{j=1}\text{d(}\text{x}\text{,}\text{x}{}_{\mathrm{j}}\text{)}$

is a minimum.An algorithm is formulated for the solution of this problem when $\text{d(}\text{x}\text{,}\text{y}\text{)}$ is Euclidean distance and $\text{R}$ is a single circular region. Numerical results are presented.     

A cut-and-solve based algorithm for the single-source capacitated facility location problem

In this paper, we present a cut-and-solve (CS) based exact algorithm for the Single Source Capacitated Facility Location Problem (SSCFLP). At each level of CS’s branching tree, it has only two nodes, corresponding to the Sparse Problem (SP) and the Dense Problem (DP), respectively. The SP, whose solution space is relatively small with the values of some variables fixed to zero, is solved to optimality by using a commercial MIP solver and its solution if it exists provides an upper bound to the SSCFLP. Meanwhile, the resolution of the LP of DP provides a lower bound for the SSCFLP. A cutting plane method which combines the lifted cover inequalities and Fenchel cutting planes to separate the 0–1 knapsack polytopes is applied to strengthen the lower bound of SSCFLP and that of DP. These lower bounds are further tightened with a partial integrality strategy. Numerical tests on benchmark instances demonstrate the effectiveness of the proposed cutting plane algorithm and the partial integrality strategy in reducing integrality gap and the effectiveness of the CS approach in searching an optimal solution in a reasonable time. Computational results on large sized instances are also presented.     

A comparison of linear reformulations for multinomial logit choice probabilities in facility location models

In the last decade several papers appeared on facility location problems that incorporate customer demand by the multinomial logit model. Three linear reformulations of the original non-linear model have been proposed so far. In this paper, we discuss these models in terms of solvability. We present empirical findings based on synthetic data.     

Algorithms for central-median paths with bounded length on trees

The location of path-shaped facilities on trees has been receiving a growing attention in the specialized literature in the recent years. Examples of such facilities include railroad lines, highways and public transit lines. Most of the papers deal with the problem of locating a path on a tree by minimizing either the maximum distance from the vertices of the tree to the facility or of minimizing the sum of the distances from all the vertices of the tree to the path. However, neither of the two above criteria alone capture all essential elements of a location problem. The sum of the distances criterion alone may result in solutions which are unacceptable from the point of view of the service level for the clients who are located far away from the facilities. On the other hand, the criterion of the minimization of the maximum distance, if used alone, may lead to very costly service systems. In the literature, there is just one paper that considers the problem of finding an optimal location of a path on a tree using combinations of the two above criteria, and efficient algorithms are provided. In particular, the cases where one criterion is optimized subject to a restriction on the value of the other are considered and linear time algorithms are presented. However, these problems do not consider any bound on the length or cost of the facility. In this paper we consider the two following problems: find a path which minimizes the sum of the distances such that the maximum distance from the vertices of the tree to the path is bounded by a fixed constant and such that the length of the path is not greater than a fixed value; find a path which minimizes the maximum distance with the sum of the distances being not greater than a fixed value and with bounded length. From an application point of view the constraint on the length of the path may refer to a budget constraint for establishing the facility. The restriction on the length of the path complicates the two problems but for both of them we give O(n log² n) divide-and-conquer algorithms.     

A new approximation algorithm for the multilevel facility location problem

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.     

An aggressive reduction scheme for the simple plant location problem

Pisinger et al. introduced the concept of ‘aggressive reduction’ for large-scale combinatorial optimization problems. The idea is to spend much time and effort in reducing the size of the instance, in the hope that the reduced instance will then be small enough to be solved by an exact algorithm.     

应急物资预置问题的可信性优化模型

基于可信性理论,研究了多受灾点、多出救点、多物资的应急设备选址和物资预置问题.考虑到运输费用、出救点的供应量、受灾点的需求量和道路容量的不确定性,用模糊变量来刻画,建立了模糊环境下应急物资预置的可信性优化模型以最小化期望总费用.当模型中的模糊变量相互独立且服从三角分布时,推导了总费用目标及服务质量和弧容量约束的解析表达式,从而将原模型转化为等价的确定模型.鉴于等价模型是一个混合整数规划,可采用Lingo软件编程求解.最后,数值算例演示所提建模思想.实验结果说明了所建模型的有效性.     

A constant factor approximation algorithm for the fault-tolerant facility location problem

We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. In this generalization, every demand point j must be served by r_j facilities instead of just one. The facilities other than the closest one are “backup” facilities for that demand, and any such facility will be used only if all closer facilities (or the links to them) fail. Hence, for any demand point, we can assign nonincreasing weights to the routing costs to farther facilities. The cost of assignment for demand j is the weighted linear combination of the assignment costs to its r_j closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. We obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. We further improve the approximation ratio to 3.16 using randomization and to 2.41 using greedy local-search type techniques.     

From stars to comets: Improved local search for universal facility location

We improve the approximation ratio for the Universal Facility Location Problem to 6.702 by a local search algorithm with an extended pivot operation.     

Disaster preparedness in humanitarian logistics: A collaborative approach for resource management in floods

The logistical deployment of resources to provide relief to disaster victims and the appropriate planning of these activities are critical to reduce the suffering caused. Disaster management attracts many organisations working alongside each other and sharing resources to cope with an emergency. Consequently, successful operations rely heavily on the collaboration of different organisations. Despite this, there is little research considering the appropriate management of resources from multiple organisations, and none optimising the number of actors required to avoid shortages or convergence.This research introduces a disaster preparedness system based on a combination of multi-objective optimisation and geographical information systems to aid multi-organisational decision-making. A cartographic model is used to avoid the selection of floodable facilities, informing a bi-objective optimisation model used to determine the location of emergency facilities, stock prepositioning, resource allocation and relief distribution, along with the number of actors required to perform these activities.The real conditions of the flood of 2013 in Acapulco, Mexico, provided evidence of the inability of any single organisation to cope with the situation independently. Moreover, data collected showed the unavailability of enough resources to manage a disaster of that magnitude at the time. The results highlighted that the number of government organisations deployed to handle the situation was excessive, leading to high cost without achieving the best possible level of satisfaction. The system proposed showed the potential to achieve better performance in terms of cost and level of service than the approach currently employed by the authorities.     

Developments in network location with mobile and congested facilities

We review four facility location problems which are motivated by urban service applications and which can be thought of as extensions of the classic Q-median problem on networks. In problems P1 and P2 it is assumed that travel times on network links change over time in a probabilistic way. In P2 it is further assumed that the facilities (servers) are movable so that they can be relocated in response to new network travel times. Problems P3 and P4 examine the Q-median problem for the case when the service capacity of the facilities is finite and, consequently, some or all of the facilities can be unavailable part of the time. In P3 the facilities have stationary home locations but in P4 they have movable locations and thus can be relocated to compensate for the unavailability of the busy facilities. We summarize our main results to date on these problems.     

Forecast-driven model for prepositioning supplies in preparation for a foreseen hurricane

In this paper, we present a forecast-driven dynamic model for prepositioning relief items in preparation for a foreseen hurricane. Our model uses forecast advisories issued by the National Hurricane Center (NHC), which are issued every 6?h. Every time a new advisory is issued with updated information, our model determines the amount and location of units to be prepositioned and it also re-prepositions already prepositioned units. The model also determines the best time for starting the prepositioning activities. Our approach uses a combination of Decision Theory and stochastic programming. The outcomes of our model are presented in a way that could be easily understood by humanitarian practitioners who are ultimately the ones who would use and apply our model.