A primal simplex algorithm to solve a rectilinear distance facility location problem

This paper considers the problem of locating m new facilities in the plane so as to minimize a weighted rectangular distance between the new facilities and n existing facilities. A special purpose primal simplex algorithm is developed to solve this problem. The algorithm will maintain at all times a basis of dimension m by m; however, because of the triangularity of the basis matrix, it will not be necessary to form a basis inverse explicitly.     

An efficient algorithm for the location-allocation problem with rectangular regions

The location-allocation problem for existing facilities uniformly distributed over rectangular regions is treated for the case where the rectilinear norm is used. The new facilities are to be located such that the expected total weighted distance is minimized. Properties of the problem are discussed. A branch and bound algorithm is developed for the exact solution of the problem. Computational results are given for different sized problems.     

The network redesign problem for access telecommunications networks

The network redesign problem attempts to design an optimal network that serves both existing and new demands. In addition to using spare capacity on existing network facilities and deploying new facilities, the model allows for rearrangement of existing demand units. As rearrangements mean reassigning existing demand units, at a cost, to different facilities, they may lead to disconnecting of uneconomical existing facilities, resulting in significant savings. The model is applied to an access network, where the demands from many sources need to be routed to a single destination, using either low‐capacity or high‐capacity facilities. Demand from any location can be routed to the destination either directly or through one other demand location. Low‐capacity facilities can be used between any pair of locations, whereas high‐capacity facilities are used only between demand locations and the destination. We present a new modeling approach to such problems. The model is described as a network flow problem, where each demand location is represented by multiple nodes associated with demands, low‐capacity and high‐capacity facilities, and rearrangements. Each link has a capacity and a cost per unit flow parameters. Some of the links also have a fixed‐charge cost. The resulting network flow model is formulated as a mixed integer program, and solved by a heuristic and a commercially available software. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 487–506, 1999     

Properties of a multifacility location problem involving euclidian distances

This paper considers a problem of locating new facilities in the plane with respect to existing facilities, the locations of which are known. The problem consists of finding locations of new facilities which will minimize a total cost function which consists of a sum of costs directly proportional to the Euclidian distances among the new facilities, and costs directly proportional to the Euclidian distances between new and existing facilities. It is established that the total cost function has a minimum; necessary conditions for a mimumum are obtained; necessary and sufficient conditions are obtained for the function to be strictly convex (it is always convex); when the problem is “well structured,” it is established that for a minimum cost solution the locations of the new facilities will lie in the convex hull of the locations of the existing facilities. Also, a dual to the problem is obtained and interpreted; necessary and sufficient conditions for optimum solutions to the problem, and to its dual, are developed, as well as complementary slackness conditions. Many of the properties to be presented are motivated by, based on, and extend the results of Kuhn's study of the location problem known as the General Fermat Problem.     

A computation procedure for the exact solution of location-allocation problems with rectangular distances

A method is presented to locate and allocate p new facilities in relation to n existing facilities. Each of the n existing facilities has a requirement flow which must be supplied by the new facilities. Rectangular distances are assumed to exist between all facilities. The algorithm proceeds in two stages. In the first stage a set of all possible optimal new facility locations is determined by a set reduction algorithm. The resultant problem is shown to be equivalent to finding the p-median of a weighted connected graph. In the second stage the optimal locations and allocations are obtained by using a technique for solving the p-median problem.     

Solving multifacility location problems involving euclidean distances

This paper considers the problem of locating multiple new facilities in order to minimize a total cost function consisting of the sum of weighted Euclidean distances among the new facilities and between the new and existing facilities, the locations of which are known. A new procedure is derived from a set of results pertaining to necessary conditions for a minimum of the objective function. The results from a number of sample problems which have been executed on a programmed version of this algorithm are used to illustrate the effectiveness of the new technique.     

基于资源平衡的分布式星群网络连接接入策略

针对现有卫星网络接入策略未能充分考虑卫星资源以及合理确定卫星资源权重问题,提出了一种基于资源平衡的星群网络连接接入策略。该策略充分考虑卫星的多种资源建立卫星资源评价模型,利用移动代理技术,采用层次分析法和熵值法计算各卫星资源的主观和客观权重,并通过Kullback散度权重优化方法对主客观权重进行平衡处理,判决过程兼顾了卫星的综合性能水平和用户偏好,提高了接入的准确性和合理性。仿真结果表明,采用该接入策略,有效改善了新呼叫阻塞率和强制中断率。     

New heuristic methods for the capacitated multi‐facility Weber problem

In this paper we consider the capacitated multi‐facility Weber problem with the Euclidean, squared Euclidean, and ?_p‐distances. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the distance between them. We first present a mixed integer linear programming approximation of the problem. We then propose new heuristic solution methods based on this approximation. Computational results on benchmark instances indicate that the new methods are both accurate and efficient. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 2006     

Acceleration of the HAP approach for the multifacility location problem

This article considers the problem of locating multiple new facilities to minimize the cost function consisting of the sum of weighted distances among new facilities and between new and existing facilities. The hyperboloid approximate procedure (HAP) is probably the most widely used approach for solving this problem. In this article, an optimality condition for this problem is derived and a method to accelerate the convergence rate of the HAP for the case of Euclidean distances is presented. From the numerical results presented in this article, it can be concluded that the performance of the new algorithm is superior to the performance of the original HAP.     

Location of regional facilities

In this paper we consider the single-facility and multifacility problems of the minisum type of locating facilities on the plane. Both demand locations and the facilities to be located are assumed to have circular shapes, and demand and service is assumed to have a uniform probability density inside each shape. The expected distance between two facilities is calculated. Euclidean and squared-Euclidean distances are discussed.     

基于梯形直觉模糊数的动态多准则群决策方法

针对决策信息为梯形直觉模糊数的多准则决策问题,引入含参得分函数和相关系数提出了一种动态多准则群决策方法,首先利用参照方案相关系数总偏差最小的非线性规划模型求解客观准则权重,通过参数因子转化犹豫度集结得到各方案综合得分函数,最后根据参数动态变化进行MATLAB仿真分析并排序。该方法适用于准则权重已知和未知的情形,弥补了犹豫度缺失和基于距离测度决策方法的缺陷,并通过航空装备保障合同商的选择决策实例验证了有效性。     

基于遗传算法的应急物流多设施选址模型研究

在现有研究的基础上,建立了应急物流多设施选址模型。在模型建立过程中除了考虑距离这一基本要素,还考虑了流量与安全性等道路特性,并将其转换为道路的综合权值,使模型更具现实意义。采用遗传算法求解,使该问题的求解过程得到简化。最后用实例对模型进行了验证分析,说明该模型的合理性。     

The modern naval fortress: an additional sea denial option for coastal states

As fixed facilities, naval fortresses seem unlikely to be important in a sea denial strategy which is usually about mobility, but new defence technologies and the changing geostrategic environment may revive the concept of the fortress. Extended ranges of anti-ship means allow onshore firepower to engage enemies over distance, even beyond the economic exclusive zones where most maritime territorial disputes occur. In the face of size limits on missile warheads that constrain their destruction of hardened targets, various active and passive defence technologies against missiles can enhance the survivability of onshore fortresses. Furthermore, onshore locations give fortresses the advantage of being unsinkable and able to accommodate greater energy and firepower capacity in contrast to vessels, as well as other mobile platforms. The onshore nature of fortresses also gives a different political meaning to being attacked, for the clear violation of sovereignty, as opposed to vessels and aircraft in a disputed space. However, the fact those fortresses are not invincible means cooperation with other existing capabilities still necessary. The case of Vietnam demonstrates how fortresses could strengthen the inferior defence capability of a coastal state vis-à-vis. a stronger sea power.     

一种有效的距离连接选择度估计方法

距离连接在空间数据库中有着广泛的应用,而距离连接的选择度估计是优化距离查询的基础。通过综合分析和比较了现有的选择度估计技术,提出了一种利用米诃夫斯基和与直方图进行距离连接选择度估计的新方法。实验结果证明该种方法能够有效地进行距离连接选择度估计。     

A note on equity across groups in facility location

An equity model between groups of demand points is proposed. The set of demand points is divided into two or more groups. For example, rich and poor neighborhoods and urban and rural neighborhoods. We wish to provide equal service to the different groups by minimizing the deviation from equality among groups. The distance to the closest facility is a measure of the quality of service. Once the facilities are located, each demand point has a service distance. The objective function, to be minimized, is the sum of squares of differences between all pairs of service distances between demand points in different groups. The problem is analyzed and solution techniques are proposed for the location of a single facility in the plane. Computational experiments for problems with up to 10,000 demand points and rectilinear, Euclidean, or general ?_p distances illustrate the efficiency of the proposed algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A linear programming solution to the generalized rectangular distance weber problem

The Weber Problem generalized to the location of several new points with respect to existing points is formulated as a linear programming problem under the assumption that distances are rectangular. The dual problem is then formulated and subsequently reduced to a problem with substantially fewer variables and constraints than required by an existent alternative linear programming formulation. Flows may exist between new as well as between new and existing points. Linear constraints can be imposed to restrict the location of new points. Pairwise constraints limiting distances between new points and between new and existing points can also be accommodated.     

航天器近距离交会斜滑制导算法

提出了满足测量视场、最小脉冲间隔、最大脉冲受限等约束的燃料最省的航天器近距离交会多脉冲斜滑制导算法.建立了近距离交会(接近和撤离)多脉冲斜滑制导算法的统一数学模型;提出了理想交会轨道距离和速率的指数函数变化关系,使得算法能够实现任意时间的近距离交会,同时满足接近操作减速和撤离过程加速的任务要求;设计了对数函数映射法进行脉冲寻优.最后通过接近段和撤离段的操作仿真算例进行验证,仿真结果表明,相比最优化方法,对数函数映射法以较小的计算量实现了较好的寻优效果;算法能够以较省的燃料消耗实现轨道面内任意方向、任意时间内满足约束的近距离交会.     

Solving quadratic assignment problems with rectangular distances and integer programming

The problem considered involves the assignment of n facilities to n specified locations. Each facility has a given nonnegative flow from each of the other facilities. The objective is to minimize the sum of transportation costs. Assume these n locations are given as points on a two-dimensional plane and transportation costs are proportional to weighted rectangular distances. Then the problem is formulated as a binary mixed integer program. The number of integer variables (all binary) involved equals the number of facilities squared. Without increasing the number of integer variables, the formulation is extended to include “site costs” Computational results of the formulation are presented.     

Client‐contractor bargaining on net present value in project scheduling with limited resources

The client‐contractor bargaining problem addressed here is in the context of a multi‐mode resource constrained project scheduling problem with discounted cash flows, which is formulated as a progress payments model. In this model, the contractor receives payments from the client at predetermined regular time intervals. The last payment is paid at the first predetermined payment point right after project completion. The second payment model considered in this paper is the one with payments at activity completions. The project is represented on an Activity‐on‐Node (AON) project network. Activity durations are assumed to be deterministic. The project duration is bounded from above by a deadline imposed by the client, which constitutes a hard constraint. The bargaining objective is to maximize the bargaining objective function comprised of the objectives of both the client and the contractor. The bargaining objective function is expected to reflect the two‐party nature of the problem environment and seeks a compromise between the client and the contractor. The bargaining power concept is introduced into the problem by the bargaining power weights used in the bargaining objective function. Simulated annealing algorithm and genetic algorithm approaches are proposed as solution procedures. The proposed solution methods are tested with respect to solution quality and solution times. Sensitivity analyses are conducted among different parameters used in the model, namely the profit margin, the discount rate, and the bargaining power weights. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Note: Facility location with closest rectangular distances

This paper considers the problem of locating one or more new facilities on a continuous plane, where the destinations or customers, and even the facilities, may be represented by areas and not points. The objective is to locate the facilities in order to minimize a sum of transportation costs. What is new in this study is that the relevant distances are the distances from the closest point in the facility to the closest point in the demand areas. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 77–84, 2000