An efficient heuristic procedure for the uncapacitated warehouse location problem

This paper introduces an efficient heuristic procedure for a special class of mixed integer programming problems called the uncapacitated warehouse (plant) location problem. This procedure is derived from the branching decision rules proposed for the branch and bound algorithm by the author in an earlier paper. It can be viewed as tracing a single path of the branch and bound tree (from the initial node to the terminal node), the path being determined by the particular branching decision rule used. Unlike branch and bound the computational efficiency of this procedure is substantially less than linearly related to the number of potential warehouse locations (integer variables) in the problem. Its computational efficiency is tested on problems found in the literature.     

Routing in packet-switched communication networks with different criticality classes of communicating node pairs

This paper addresses the routing problem with reliability requirements in packet-switched communication networks. In this problem, two classes of communicating node pairs are considered: less critical and highly critical node pairs. We develop a model which identifies a primary route for each less critical node pair and both a primary and a secondary (back up) route for each highly critical node pair. The objective is to minimize the average delay encountered by messages. A solution procedure based on a relaxation of the problem is presented. Computational results over a wide range of problem structures show that the procedure is very effective. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44 : 485–505, 1997     

A node covering algorithm

This paper describes a node covering algorithm, i.e., a procedure for finding a smallest set of nodes covering all edges of an arbitrary graph. The algorithm is based on the concept of a dual node-clique set, which allows us to identify partial covers associated with integer dual feasible solutions to the linear programming equivalent of the node covering problem. An initial partial cover with the above property is first found by a labeling procedure. Another labeling procedure then successively modifies the dual node-clique set, so that more and more edges are covered, i.e., the (primal) infeasibility of the solution is gradually reduced, while integrality and dual feasibility are preserved. When this cannot be continued, the problem is partitioned and the procedure applied to the resulting subproblems. While the steps of the algorithm correspond to sequences of dual simplex pivots, these are carried out implicitly, by labeling. The procedure is illustrated by examples, and some early computational experience is reported. We conclude with a discussion of potential improvements and extensions.     

An operator theory of parametric programming for the transportation problem-II

This paper investigates the effect on the optimum solution of a (capacitated) transportation problem when the data of the problem (the rim conditions-i. e., the warehouse supplies and market demands-, the per unit transportation costs and the upper bounds) are continuously varied as a (linear) function of a single parameter. Operators that effect the transformation of optimum solution associated with such data changes, are shown to be a product of basis preserving operators (described in the earlier paper) that operate on a sequence of adjacent basis structures. Algorithms are provided for both rim and cost operators. The paper concludes with a discussion of the economic and managerial interpretations of the operators.     

An operator theory of parametric programming for the transportation problem-I

This paper investigates the effect on the optimum solution of a (capacitated) transportation problem when the data of the problem (the rim conditions-i. e., the warehouse supplies and market demands-the per unit transportation costs and the upper bounds) are continuously varied as a (linear) function of a single parameter. An operator theory is developed and algorithms provided for applying rim and cost operators that effect the transformation of optimum solution associated with changes in rim conditions and unit costs. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum basis structures are preserved.     

Capacitated warehouse location model with risk pooling

In this article, we introduce the capacitated warehouse location model with risk pooling (CLMRP), which captures the interdependence between capacity issues and the inventory management at the warehouses. The CLMRP models a logistics system in which a single plant ships one type of product to a set of retailers, each with an uncertain demand. Warehouses serve as the direct intermediary between the plant and the retailers for the shipment of the product and also retain safety stock to provide appropriate service levels to the retailers. The CLMRP minimizes the sum of the fixed facility location, transportation, and inventory carrying costs. The model simultaneously determines warehouse locations, shipment sizes from the plant to the warehouses, the working inventory, and safety stock levels at the warehouses and the assignment of retailers to the warehouses. The costs at each warehouse exhibit initially economies of scale and then an exponential increase due to the capacity limitations. We show that this problem can be formulated as a nonlinear integer program in which the objective function is neither concave nor convex. A Lagrangian relaxation solution algorithm is proposed. The Lagrangian subproblem is also a nonlinear integer program. An efficient algorithm is developed for the linear relaxation of this subproblem. The Lagrangian relaxation algorithm provides near‐optimal solutions with reasonable computational requirements for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

OPTIMAL FACILITY LOCATION UNDER RANDOM DEMAND WITH GENERAL COST STRUCTURE

This paper investigates the problem of determining the optimal location of plants, and their respective production and distribution levels, in order to meet demand at a finite number of centers. The possible locations of plants are restricted to a finite set of sites, and the demands are allowed to be random. The cost structure of operating a plant is dependent on its location and is assumed to be a piecewise linear function of the production level, though not necessarily concave or convex. The paper is organized in three parts. In the first part, a branch and bound procedure for the general piecewise linear cost problem is presented, assuming that the demand is known. In the second part, a solution procedure is presented for the case when the demand is random, assuming a linear cost of production. Finally, in the third part, a solution procedure is presented for the general problem utilizing the results of the earlier parts. Certain extensions, such as capacity expansion or reduction at existing plants, and geopolitical configuration constraints can be easily incorporated within this framework.     

An analysis of single item inventory systems with returns

Inventory systems with returns are systems in which there are units returned in a repairable state, as well as demands for units in a serviceable state, where the return and demand processes are independent. We begin by examining the control of a single item at a single location in which the stationary return rate is less than the stationary demand rate. This necessitates an occasional procurement of units from an outside source. We present a cost model of this system, which we assume is managed under a continuous review procurement policy, and develop a solution method for finding the policy parameter values. The key to the analysis is the use of a normally distributed random variable to approximate the steady-state distribution of net inventory. Next, we study a single item, two echelon system in which a warehouse (the upper echelon) supports N(N ? 1) retailers (the lower echelon). In this case, customers return units in a repairable state as well as demand units in a serviceable state at the retailer level only. We assume the constant system return rate is less than the constant system demand rate so that a procurement is required at certain times from an outside supplier. We develop a cost model of this two echelon system assuming that each location follows a continuous review procurement policy. We also present an algorithm for finding the policy parameter values at each location that is based on the method used to solve the single location problem.     

Optimal location of a facility relative to area demands

This paper deals with the Weber single-facility location problem where the demands are not only points but may be areas as well. It provides an iterative procedure for solving the problem with l^p distances when p > 1 (a method of obtaining the exact solution when p = 1 and distances are thus rectangular already exists). The special case where the weight densities in the areas are uniform and the areas are rectangles or circles results in a modified iterative process that is computationally much faster. This method can be extended to the simultaneous location of several facilities.     

Location of facilities with rectangular distances among point and area destinations

This article is concerned with the optimal location of any number (n) of facilities in relation to any number (m) of destinations on the Euclidean plane. The criterion to be satisfied is the minimization of total weighted distances where the distances are rectangular. The destinations may be either single points, lines or rectangular areas. A gradient reduction solution procedure is described which has the property that the direction of descent is determined by the geometrical properties of the problem.     

One-facility location with rectilinear tour distances

This article concerns the location of a facility among n points where the points are serviced by “tours” taken from the facility. Tours include m points at a time and each group of m points may become active (may need a tour) with some known probability. Distances are assumed to be rectilinear. For m ≤ 3, it is proved that the objective function is separable in each dimension and an exact solution method is given that involves finding the median of numbers appropriately generated from the problem data. It is shown that the objective function becomes multimodal when some tours pass through four or more points. A bounded heuristic procedure is suggested for this latter case. This heuristic involves solving an auxiliary three-point tour location problem.     

A two-phase procedure for allotting geostationary orbital locations to communications satellites

We consider the problem of allotting locations in the geostationary orbit to communication satellites, subject to angle of elevation and electromagnetic interference constraints. An optimization framework is used as a means of finding feasible allotment plans. Specifically, we present a two-phase solution procedure for the satellite location problem (SLP). The objective in SLP is to allot geostationary orbital locations to satellites so as to minimize the sum of the absolute differences between the locations prescribed for the satellites and corresponding specified desired locations. We describe two heuristics, an ordering procedure and a k-permutation algorithm, that are used in tandem to find solutions to SLP. Solutions to a worldwide example problem with 183 satellites serving 208 service areas are summarized.     

层次分析法在野战仓库选址中的运用研究

野战仓库在现代高技术局部战争中发挥着极其重要的作用,其库址的合理选择,是野战仓库建设中至关重要的一步。采用层次分析法(AHP),结合野战仓库的职能,从地形良好、位置恰当、地幅适当、交通方便四个方面出发,科学地分析了野战仓库选址过程中的各种影响因素,并得出它们在野战仓库选址中的重要性排序;采用层次分析法大大简化了野战仓库的选址过程,具有一定的适用性。     

从配送中心角度考虑后勤仓库建设

现代物流技术的发展使物资配送的效率越来越高,配送中心建设的方法论也日趋成熟。从后勤仓库与配送中心的相似性出发,从配送中心的角度来考虑后勤仓库的建设,通过外部环境论证、内部力量分析和地址选定三个方面来系统确定后勤仓库建设的诸方面,最终目的是提高物资保障效率。     

Algorithms for solving the conditional covering problem on paths

Consider the conditional covering problem on an undirected graph, where each node represents a site that must be covered by a facility, and facilities may only be established at these nodes. Each facility can cover all sites that lie within some common covering radius, except the site at which it is located. Although this problem is difficult to solve on general graphs, there exist special structures on which the problem is easily solvable. In this paper, we consider the special case in which the graph is a simple path. For the case in which facility location costs do not vary based on the site, we derive characteristics of the problem that lead to a linear‐time shortest path algorithm for solving the problem. When the facility location costs vary according to the site, we provide a more complex, but still polynomial‐time, dynamic programming algorithm to find the optimal solution. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

An iterative algorithm for the multifacility minimax location problem with euclidean distances

An iterative solution method is presented for solving the multifacility location problem with Euclidean distances under the minimax criterion. The iterative procedure is based on the transformation of the multifacility minimax problem into a sequence of squared Euclidean minisum problems which have analytical solutions. Computational experience with the new method is also presented.     

A dual-based optimization procedure for the two-echelon uncapacitated facility location problem

The two-echelon uncapacitated facility location problem (TUFLP) is a generalization of the uncapacitated facility location problem (UFLP) and multiactivity facility location problem (MAFLP). In TUFLP there are two echelons of facilities through which products may flow in route to final customers. The objective is to determine the least-cost number and locations of facilities at each echelon in the system, the flow of product between facilities, and the assignment of customers to supplying facilities. We propose a new dual-based solution procedure for TUFLP that can be used as a heuristic or incorporated into branch-and-bound procedures to obtain optimal solutions to TUFLP. The algorithm is an extension of the dual ascent and adjustment procedures developed by Erlenkotter for UFLP. We report computational experience gained by solving over 420 test problems. The largest problems solved have 25 possible facility locations at each echelon and 35 customer zones, implying 650 integer variables and 21,875 continuous variables.     

Clustered coverage orienteering problem of unmanned surface vehicles for water sampling

This study investigates a clustered coverage orienteering problem (CCOP), which is a generalization of the classical orienteering problem. The problem is widely motivated by the emerging unmanned techniques (eg, unmanned surface vehicles and drones) applied to environmental monitoring. Specifically, the unmanned surface vehicles (USVs) are used to monitor reservoir water quality by collecting samples. In the CCOP, the water sampling sites (ie, the nodes) are grouped into clusters, and a minimum number of nodes must be visited in each cluster. With each node representing a certain coverage area of the water, the objective of the CCOP is to monitor as much as possible the total coverage area in one tour of the USV, considering that overlapping areas provide no additional information. An integer programming model is first formulated through a linearization procedure that captures the overlapping feature. A two-stage exact algorithm is proposed to obtain an optimal solution to the problem. The efficiency and effectiveness of the two-stage exact algorithm are demonstrated through experiments on randomly generated instances. The algorithm can effectively solve instances with up to 60 sampling sites.     

Replacing continuous demand with discrete demand in a competitive location model

Location models commonly represent demand as discrete points rather than as continuously spread over an area. This modeling technique introduces inaccuracies to the objective function and consequently to the optimal location solution. In this article this inaccuracy is investigated by the study of a particular competitive facility location problem. First, the location problem is formulated over a continuous demand area. The optimal location for a new facility that optimizes the objective function is obtained. This optimal location solution is then compared with the optimal location obtained for a discrete set of demand points. Second, a simple approximation approach to the continuous demand formulation is proposed. The location problem can be solved by using the discrete demand algorithm while significantly reducing the inaccuracies. This way the simplicity of the discrete approach is combined with the approximated accuracy of the continuous-demand location solution. Extensive analysis and computations of the test problem are reported. It is recommended that this approximation approach be considered for implementation in other location models. © 1997 John Wiley & Sons, Inc.     

On a rational stopping rule for facilities location algorithms

In the multifacility location problem, a number of new facilities are to be located so as to minimize a sum of weighted distances. Recently, a lower bound on the optimal value was developed, for use in deciding when to stop an iterative solution procedure. We develop a stronger bound that allows some computational savings.