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.     

Sequential location-allocation problems on chains and trees with probabilistic link demands

In this paper, we consider multiperiod minisum location problems on networks in which demands can occur continuously on links according to a uniform probability density function. In addition, demands may change dynamically over time periods and at most one facility can be located per time period. Two types of networks are considered in conjunction with three behavioral strategies. The first type of network discussed is a chain graph. A myopic strategy and long-range strategy for locatingp-facilities are considered, as is a discounted present worth strategy for locating two facilities. Although these problems are generally nonconvex, effective methods are developed to readily identify all local and global minima. This analysis forms the basis for similar problems on tree graphs. In particular, we construct algorithms for the 3-facility myopic problem and the 2-facility long-range and discounted cost problems on a tree graph. Extensions and suggestions for further research on problems involving more general networks are provided.     

Efficient computation of 2-medians in a tree network with positive/negative weights

We consider a variant of the classical two median facility location problem on a tree in which vertices are allowed to have positive or negative weights. This problem was proposed by Burkard et al. in 2000 (R.E. Burkard, E. Çela, H. Dollani, 2-medians in trees with pos/neg-weights, Discrete Appl. Math. 105 (2000) 51-71). who looked at two objectives, finding the total minimum weighted distance (MWD) and the total weighted minimum distance (WMD). Their approach finds an optimal solution in O(n²) time and O(n³) time, respectively, with better performance for special trees such as paths and stars. We propose here an O(nlogn) algorithm for the MWD problem on trees of arbitrary shape. We also briefly discuss the WMD case and argue that it can be solved in time. However, a systematic exposition of the later case cannot be contained in this paper.     

Center location problems on tree graphs with subtree-shaped customers

We consider the p-center problem on tree graphs where the customers are modeled as continua subtrees. We address unweighted and weighted models as well as distances with and without addends. We prove that a relatively simple modification of Handler’s classical linear time algorithms for unweighted 1- and 2-center problems with respect to point customers, linearly solves the unweighted 1- and 2-center problems with addends of the above subtree customer model. We also develop polynomial time algorithms for the p-center problems based on solving covering problems and searching over special domains.     

Reverse selective obnoxious center location problems on tree graphs

In this paper, we investigate a variant of the reverse obnoxious center location problem on a tree graph \(T=(V,E)\) in which a selective subset of the vertex set V is considered as locations of the existing customers. The aim is to augment or reduce the edge lengths within a given budget with respect to modification bounds until a predetermined undesirable facility location becomes as far as possible from the customer points under the new edge lengths. An \({\mathcal {O}}(|E|^2)\) time combinatorial algorithm is developed for the problem with arbitrary modification costs. For the uniform-cost case, one obtains the improved \({\mathcal {O}}(|E|)\) time complexity. Moreover, optimal solution algorithms with \({\mathcal {O}}(|E|^2)\) and \({\mathcal {O}}(|E|)\) time complexities are proposed for the integer version of the problem with arbitrary and uniform cost coefficients, respectively.     

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.     

带次模惩罚和随机需求的设施选址问题

考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构,给出原始对偶3-近似算法. 在算法的第一步,构造了一组对偶可行解;在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.     

Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Let p≥2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p−1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O(n²)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b/a|a∈[1,m],b∈B} such that F(z)≥t. We give an O(n+t_F×(logn+logm))-time algorithm for this problem, where t_F is the time required to evaluate the function value F(z) for any real number z.     

An approximation algorithm for a facility location problem with stochastic demands and inventories

We propose a 2-approximation algorithm for a facility location problem with stochastic demands. At open facilities, inventory is kept such that arriving requests find a zero inventory with (at most) some pre-specified probability. Costs incurred are expected transportation costs, facility operating costs and inventory costs.     

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.     

Revisiting several problems and algorithms in continuous location with \ell _\tau norms

This paper addresses the general continuous single facility location problems in finite dimension spaces under possibly different \(\ell _\tau \) norms, \(\tau \ge 1\) , in the demand points. We analyze the difficulty of this family of problems and revisit convergence properties of some well-known algorithms. The ultimate goal is to provide a common approach to solve the family of continuous \(\ell _\tau \) ordered median location problems Nickel and Puerto (Facility location: a unified approach, 2005) in dimension \(d\) (including of course the \(\ell _\tau \) minisum or Fermat-Weber location problem for any \(\tau \ge 1\) ). We prove that this approach has a polynomial worst case complexity for monotone lambda weights and can be also applied to constrained and even non-convex problems.     

Optimal inventory management for a retail chain with diverse store demands

Item demands at individual retail stores in a chain often differ significantly, due to local economic conditions, cultural and demographic differences and variations in store format. Accounting for these variations appropriately in inventory management can significantly improve retailers’ profits. For example, it is shown that having greater differences across the mean store demands leads to a higher expected profit, for a given inventory and total mean demand. If more than one inventory shipment per season is possible, the analysis becomes dynamic by including updated demand forecasts for each store and re-optimizing store inventory policies in midseason. In this paper, we formulate a dynamic stochastic optimization model that determines the total order size and the optimal inventory allocation across nonidentical stores in each period. A generalized Bayesian inference model is used for demands that are partially correlated across the stores and time periods. We also derive a normal approximation for the excess inventory from the previous period, which allows the dynamic programming formulation to be easily solved. We analyze the tradeoffs between obtaining information and profitability, e.g., stocking more stores in period 1 provides more demand information for period 2, but does not necessarily lead to higher total profit. Numerical analyses compare the expected profits of alternative supply chain strategies, as well as the sensitivity to different distributions of demand across the stores. This leads to novel strategic insights that arise from adopting inventory policies that vary by store type.     

Source location with rigidity and tree packing requirements

We consider the following two problems: (i) given a graph, find a minimum size vertex-set such that the pinning of it makes the graph rigid in the plane. (ii) Given a graph, contract a minimum size vertex-set such that the resulting graph has two edge-disjoint spanning trees. We prove that these problems are polynomially solvable.     

Capacity planning and warehouse location in supply chains with uncertain demands

We discuss the strategic capacity planning and warehouse location problem in supply chains operating under uncertainty. In particular, we consider situations in which demand variability is the only source of uncertainty. We first propose a deterministic model for the problem when all relevant parameters are known with certainty, and discuss related tractability and computational issues. We then present a robust optimization model for the problem when the demand is uncertain, and demonstrate how robust solutions may be determined with an efficient decomposition algorithm using a special Lagrangian relaxation method in which the multipliers are constructed from dual variables of a linear program.     

Single- and multi-objective defensive location problems on a network

This paper considers a new optimal location problem, called defensive location problem (DLP). In the DLPs, a decision maker locates defensive facilities in order to prevent her/his enemies from reaching an important site, called a core; for example, “a government of a country locates self-defense bases in order to prevent her/his aggressors from reaching the capital of the country.” It is assumed that the region where the decision maker locates her/his defensive facilities is represented as a network and the core is a vertex in the network, and that the facility locater and her/his enemy are an upper and a lower level of decision maker, respectively. Then the DLPs are formulated as bilevel 0-1 programming problems to find Stackelberg solutions. In order to solve the DLPs efficiently, a solving algorithm for the DLPs based upon tabu search methods is proposed. The efficiency of the proposed solving methods is shown by applying to examples of the DLPs. Moreover, the DLPs are extended to multi-objective DLPs that the decision maker needs to defend several cores simultaneously. Such DLPs are formulated as multi-objective programming problems. In order to find a satisfying solution of the decision maker for the multi-objective DLP, an interactive fuzzy satisfying method is proposed, and the results of applying the method to examples of the multi-objective DLPs are shown.     

Vector equilibrium problems with elastic demands and capacity constraints

In this paper, a (weak) vector equilibrium principle for vector network problems with capacity constraints and elastic demands is introduced. A sufficient condition for a (weak) vector equilibrium flow to be a solution for a system of (weak) vector quasi-variational inequalities is obtained. By virtue of Gerstewitz’s nonconvex separation functional ξ, a (weak) ξ-equilibrium flow is introduced. Relations between a weak vector equilibrium flow and a (weak) ξ-equilibrium flow is investigated. Relations between weak vector equilibrium flows and two classes of variational inequalities are also studied.     

The location of protection devices on electrical tree networks: a heuristic approach

The problem of determining the number of protection devices and their locations on an electrical tree network with subtrees dependency is investigated. The aim is to reduce the amount of inconvenience caused to customers that are affected by any given fault on the network. A constructive heuristic and an appropriate implementation of tabu search are proposed and compared against a method currently used by the electrical supply companies. Computational tests are performed on randomly generated electrical tree networks varying in size and branch complexity. Both the proposed methods outperformed the one used in practice. In particular our tabu search implementation was found to produce the best results without taking an excessive amount of computational time.     

Large-scale standard pooling problems with constrained pools and fixed demands

We present a new variant of the standard pooling problem in which demands are fixed and there are specific constraints on the intermediate pool. We propose a new formulation composed of proportion-flow variables, and we design an exact branch and bound algorithm by combining existing algorithms. Difficult instances have been generated to demonstrate the efficiency of our method, and our results are compared with those of Couenne, a generic MINLP solver.