The planar hub location problem: a probabilistic clustering approach

Given the demand between each origin-destination pair on a network, the planar hub location problem is to locate the multiple hubs anywhere on the plane and to assign the traffic to them so as to minimize the total travelling cost. The trips between any two points can be nonstop (no hubs used) or started by visiting any of the hubs. The travel cost between hubs is discounted with a factor. It is assumed that each point can be served by multiple hubs. We propose a probabilistic clustering method for the planar hub-location problem which is analogous to the method of Iyigun and Ben-Israel (in Operations Research Letters 38, 207–214, 2010; Computational Optmization and Applications, 2013) for the solution of the multi-facility location problem. The proposed method is an iterative probabilistic approach assuming that all trips can be taken with probabilities that depend on the travel costs based on the hub locations. Each hub location is the convex combination of all data points and other hubs. The probabilities are updated at each iteration together with the hub locations. Computations stop when the hub locations stop moving. Fermat-Weber problem and multi-facility location problem are the special cases of the proposed approach.     

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.     

An algorithm for solving the multi-period online fulfillment assignment problem

This paper develops an optimal solution procedure for the multi-period online fulfillment assignment problem to determine how many and which of a retailer/e-tailer’s capacitated regional warehouse locations should be set up to handle online sales over a finite planning horizon. To reduce the number of candidate solutions in each period, dominance rules from the facility location literature are extended to handle the nonlinear holding and backorder cost implications of our problem. Computational results indicate that multi-period considerations can play a major role in determining the optimal set of online fulfillment locations. In 92% of our test problems, the multi-period solution incorporated fewer openings and closings than myopic single period solutions. To illustrate the use of the model under changing demands, the multi-period solution yielded different supply chain configurations than the myopic single period solution in over 37% of the periods.     

The Pattern of Multiple Rings from Morphogenesis in Development

Under certain conditions the problem of morphogenesis in development and the problem of morphology in block copolymers may be reduced to one geometric problem. In two dimensions two new types of solutions are found. The first type of solution is a disconnected set of many components, each of which is close to a ring. The sizes and locations of the rings are precisely determined from the parameters and the domain shape of the problem. The solution of the second type has a coexistence pattern. Each component of the solution is either close to a ring or to a round disc. The first-type solutions are stable for certain parameter values but unstable for other values; the second-type solutions are always unstable. In both cases one establishes the equal area condition: the components in a solution all have asymptotically the same area.     

A finite differences method for a two-dimensional nonlinear hyperbolic equation in a class of discontinuous functions

A numerical scheme is proposed for a scalar two-dimensional nonlinear first-order wave equation with both continuous and piecewise continuous initial conditions. It is typical of such problems to assume formal solutions with discontinuities at unknown locations, which justifies the search for a scheme that does not rely on the regularity of the solution. To this end, an auxiliary problem which is equivalent to, but has more advantages then, the original system is formulated and shown that regularity of the solution of the auxiliary problem is higher than that of the original system. An efficient numerical algorithm based on the auxiliary problem is derived. Furthermore, some results of numerical experiments of physical interest are presented.     

One-dimensional machine location problems in a multi-product flowline with equidistant locations

An assignment of machines to locations along a straight track is required to optimize material flow in many manufacturing systems. The assignment of M unique machines to M locations along a linear material handling track with the objective of minimizing the total machine-to-machine material transportation cost is formulated as a quadratic assignment problem (QAP). The distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Since an optimal solution to a problem with large M is computationally intractable (the QAP is NP-hard), a number of the amoebic properties are exploited to devise heuristics and a lower bound on the optimal solution. Computational results which demonstrate the performance of the heuristics and the lower bound are presented.     

Complements and substitutes among locations in the two-stage transshipment problem

This paper considers complementarity and substitutability among locations for a two-stage transshipment problem with locations being factories, warehouses, and demand centers. A direct generalization of properties known for the transportation problem would be that any two locations of different types are complements and any two locations of the same type are substitutes. Examples show that these properties need not hold for pairs of locations that include at least one warehouse. An algorithm of Nagelhout and Thompson (European J. Operational Res. 6 (1981) 149–161) for locating warehouses is based on the incorrect supposition that any two warehouses are substitutes, and an example shows that their algorithm need not generate an optimal solution as claimed. For pairs of locations that do not include a warehouse, complementarity and substitutability properties hold just as in the transportation problem.     

Backtracking and its Amoebic Properties in One-dimensional Machine Location Problems

This paper studies the assignment of M unique machines to M equally spaced locations along a linear material handling track with the objective of minimizing the cost of (jobs) backtracking (i.e. moving upstream). Because of the arrangement of machines and restrictions imposed by the sequence of operations for each job, some jobs may have to backtrack to complete required processing on different machines. This problem is formulated as a quadratic assignment problem. An optimal solution to a problem with large M is computationally intractable. The backtracking distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Ten amoebic properties have been identified and exploited to devise a heuristic and a lower bound on the optimal solution. Results which describe the performance of the heuristic and the lower bound are presented.     

Depot location: A technique for the avoidance of local optima

This paper is concerned with facility location as exemplified by the depot-siting problem. In particular it considers the problem of achieving only locally-optimal locations and describes a readily-available technique which greatly increases the chance of attaining the global solution. The technique is exemplified on two data sets using a depot cost function which is linear in throughput and also one displaying economies of scale.     

A geometrical solution for quadratic bicriteria location models

This paper deals with a single-facility, unweighted, quadratic bicriteria location problem defined in the continuous space. First we describe an analytical method for constructing the set of Pareto-optimal locations for this problem based on the farthest-point Voronoi diagram. Then we present an analytical method for finding the solution to the scalarized location problems based on the Pareto-optimal locations. The analytical results enable planners to carry out some sensitivity analyses. Since both methods are based entirely on geometrical analysis, they can be understood intuitively.     

Boundary Identification for a Blast Furnace

In this paper,the authors discuss an inverse boundary problem for the axi- symmetric steady-state heat equation,which arises in monitoring the boundary corrosion for the blast-furnace.Measure temperature at some locations are used to identify the shape of the corrosion boundary. The numerical inversion is complicated and consuming since the wear-line varies during the process and the boundary in the heat problem is not fixed.The authors suggest a method that the unknown boundary can be represented by a given curve plus a small perturbation,then the equation can be solved with fixed boundary,and a lot of computing time will be saved. A method is given to solve the inverse problem by minimizing the sum of the squared residual at the measuring locations,in which the direct problems are solved by axi- symmetric fundamental solution method. The numerical results are in good agreement with test model data as well as industrial data,even in severe corrosion case.     

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.     

基于多候选储位的存取路径优化问题研究

针对单储位储存方式可能导致仓库存取通道拥挤和作业效率低的情形,提出了一种基于多候选储位的存取路径优化方法。首先分配了货物的存取储位,然后建立了多候选储位的车辆路径问题(MLVRP)模型,并基于储位优先解码原则设计了遗传算法,最后通过算例证明该方法的有效性和算法的高效性。多候选储位的方法可以为取货任务至少节约18.4%(两个候选储位)和21.8%(三个候选储位)的路程,算法迭代10000次只需要434s。     

A Benders decomposition approach for a distribution network design problem with consolidation and capacity considerations

We develop a model for a strategic freight-forwarding network design problem in which the design decisions involve the locations and capacities of consolidation and deconsolidation centers, and capacities on linehaul linkages as well as the shipment routes from origins to destinations through centers. We devise a solution approach based on Benders decomposition and conduct a computational study that illustrates the efficiency and the effectiveness of the approach.     

Approximate algorithms for the competitive facility location problem

We consider the competitive facility location problem in which two competing sides (the Leader and the Follower) open in succession their facilities, and each consumer chooses one of the open facilities basing on its own preferences. The problem amounts to choosing the Leader’s facility locations so that to obtain maximal profit taking into account the subsequent facility location by the Follower who also aims to obtain maximal profit. We state the problem as a two-level integer programming problem. A method is proposed for calculating an upper bound for the maximal profit of the Leader. The corresponding algorithm amounts to constructing the classical maximum facility location problem and finding an optimal solution to it. Simultaneously with calculating an upper bound we construct an initial approximate solution to the competitive facility location problem. We propose some local search algorithms for improving the initial approximate solutions. We include the results of some simulations with the proposed algorithms, which enable us to estimate the precision of the resulting approximate solutions and give a comparative estimate for the quality of the algorithms under consideration for constructing the approximate solutions to the problem.     

ATM network design for corporate networks

Asynchronous transfer mode (ATM) networks play an important role in support of distributed applications and modern corporate systems. The applications that use these architectures transfer high volumes of data in high-speed bursts and have stringent delay requirements. To address these needs, network managers seek cost efficient network solutions that provide network capacity sufficient to support high-speed applications.In this paper we present a new formulation and solution procedure for designing ATM networks to support corporate applications. Given the locations of the application servers and multiple clients we would like to design a minimum cost ATM network by which the clients can access the servers. Most of the previous work done in this area separates the problem into a routing problem (virtual circuit routing) and an assignment (virtual path assignment) problem. Thus, the solutions tend to be sub-optimal in the combined problem. This research optimizes virtual path (VP) assignment and virtual circuit (VC) routing simultaneously. We formulate the combined problem explicitly and develop an effective solution method. The solution method provides the designer with virtual paths and virtual circuits over which the actual communication takes place. Computational results are provided.     

Exact and approximate solutions to the multisource weber problem

The problem considered is the choice of locations form sources so as to minimize the sum of weighted distances betweenn fixed sinks and the source closest to each sink. The weights represent the amounts to be shipped between the sinks and their respective sources; the allowable source locations are free of restriction. An algorithm for the approximate solution of the problem, and computational experience with it, are discussed first. A branch-and-bound algorithm for exact solution of the problem is then developed, and computational experience with it is described.For a more detailed discussion of the analyses contained in the present paper, the computational results, and for detailed program listings, the reader is referred to [8]. Tapes for the two programs discussed in the present paper are available at cost of reproduction from Program Analysis Division, Institute for Defense Analyses, Arlington, Virginia.     

Multi-location transshipment problem with capacitated transportation

We consider coordination among stocking locations through replenishment strategies that take explicitly into consideration transshipments, transfer of a product among locations at the same echelon level. We incorporate transportation capacity such that transshipment quantities between stocking locations are bounded due to transportation media or the location’s transshipment policy. We model different cases of transshipment capacity as a capacitated network flow problem embedded in a stochastic optimization problem. Under the assumption of instantaneous transshipments, we develop a solution procedure based on infinitesimal perturbation analysis to solve the stochastic optimization problem, where the objective is to find the policy that minimizes the expected total cost of inventory, shortage, and transshipments. Such a numerical approach provides the flexibility to solve complex problems. Investigating two problem settings, we show the impact of transshipment capacity between stocking locations on system behavior. We observe that transportation capacity constraints not only increase total cost, they also modify the inventory distribution throughout the network.     

A primal-dual algorithm for the fermat-weber problem involving mixed gauges

We give a new algorithm for solving the Fermat-Weber location problem involving mixed gauges. This algorithm, which is derived from the partial inverse method developed by J.E. Spingarn, simultaneously generates two sequences globally converging to a primal and a dual solution respectively. In addition, the updating formulae are very simple; a stopping rule can be defined though the method is not dual feasible and the entire set of optimal locations can be obtained from the dual solution by making use of optimality conditions. When polyhedral gauges are used, we show that the algorithm terminates in a finite number of steps, provided that the set of optimal locations has nonepty interior and a counterexample to finite termination is given in a case where this property is violated. Finally, numerical results are reported and we discuss possible extensions of these results.