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.     

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.     

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.     

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.     

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.     

基于改进SLP的军事物流基地设施平面布局研究

由于传统SLP方法的不足,在解决设施较多的军事物流基地布局问题上面临较大困难。为解决此问题,提出了改进SLP方法,以军事物流基地设施间综合相互关系为基础,构建平面布局模型,并确定目标函数和主要约束条件。随后对模型的求解进行遗传算法设计,并运用Matlab编程实现模型的求解,从而得出平面布局的最优解。最后以最优解为基础,结合限制条件进行修正,完成军事物流基地设施平面布局设计。     

Optimal location of public facilities

Location of both public and private facilities has become an important consideration in today's society. Progress in solution of location problems has been impeded by difficulty of the fixed charge problem and the lack of an efficient algorithm for large problems. In this paper a method is developed for solving large-scale public location problems. An implicit enumeration scheme with an imbedded transportation algorithm forms the basis of the solution technique.     

Probabilistic formulations of the multifacility weber problem

The problem considered is to locate one or more new facilities relative to a number of existing facilities when both the locations of the existing facilities, the weights between new facilities, and the weights between new and existing facilities are random variables. The new facilities are to be located such that expected distance traveled is minimized. Euclidean distance measure is considered; both unconstrained and chance-constrained formulations are treated.     

基于稀疏表示和非参数判别分析的降维算法

针对人脸识别问题提出一种新的监督降维算法。算法首先基于稀疏表示理论,利用同类样本间的稀疏重构来构建图。此方案不仅可以克服传统图构造方法中参数选择的困难,而且能够更好地刻画类内信息。然后,算法采用非参数类间离差来刻画类间信息,非参数类间离差在处理复杂分布数据时相比于参数类间离差更具判别力。最后,算法通过保持类内稀疏重构关系的同时最大化非参数类间离差来求得最优的投影矩阵。在ORL和Extended Yale B公共人脸数据库的实验表明,该算法能够获得较好的识别结果。     

Polynomial algorithms for center location on spheres

When locating facilities over the earth or in space, a planar location model is no longer valid and we must use a spherical surface. In this article, we consider the one-and two-center problems on a sphere that contains n demand points. The problem is to locate facilities to minimize the maximum distance from any demand point to the closest facility. We present an O(n) algorithm for the one-center problem when a hemisphere contains all demand points and also give an O(n) algorithm for determining whether or not the hemisphere property holds. We present an O(n³ log n) algorithm for the two-center problem for arbitrarily located demand points. Finally, we show that for general p, the p center on a sphere problem is NP-hard. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 341–352, 1997     

新型多目标遗传算法及其在导弹射击效能优化中的应用

多目标规划是一类重要的优化模型,有着广泛的实际应用,但其求解至今仍是运筹学的一个难点.针对一般约束多目标优化问题,在设计了新的适应度函数和选择算子的基础上,提出一种新型多目标遗传算法.将其应用于导弹对集群目标射击效能优化问题,验证了算法的有效性.     

指派问题的降阶优化算法

指派问题是运筹学中特殊线性规划中的一类问题。在现实生活中,指派问题非常普遍,常常可以见到各种各样的指派问题。通过对指派问题的数学模型进行分析,提出了与以往方法不同的求解指派问题的一种新的思路,通过对几个定理的研究,给出了一种新的求解方法——降阶优化算法。对求解指派问题提供了一种新的途径,在运筹学等领域有着较好的应用前景。     

基于H∞滤波的无序量测更新算法

在目标跟踪系统中,传感器量测因通信延迟无序地到达融合中心,产生无序量测融合问题。针对此问题,将H∞滤波作为基础滤波算法,提出了一种可处理单步或多步延迟无序量测的新算法。新算法借鉴有序滤波思想,利用等价量测来代替无序量测发生时刻后的量测序列,然后从该时刻起利用无序量测和等价量测进行有序更新。仿真实验表明,新算法相比于传统算法有更高的滤波精度,尤其在系统模型误差较大时仍有良好的滤波效果。     

瓶颈指派问题的一种多项式时间算法

本文对瓶颈指派问题给出了一种新的算法,该算法不需要利用最大流算法,而类似于解经典指派问题的匈牙利算法。该算法是一个多项式时间算法,其复杂性为Ｏ（ｎ３）     

武警部队开进路线问题的蚂蚁算法研究

部队开进路线问题是类似于TSP的NP问题。本文将蚂蚁算法应用于部队开进路线问题中，在综合考量每条路径的通行条件、隐蔽性、迂回道路数量基础上，通过层次分析法求出每条路径的权值，进而运用蚂蚁算法原理对问题设计算法。算法用Delphi实现，通过对实际部队开进路线问题的测试，得到较好结果。相对于传统的经验选择路径方法，此方法更少依赖选择主体的主观性，从而更具客观性与可重复性。     

A facility reliability problem: Formulation,properties, and algorithm

Having a robustly designed supply chain network is one of the most effective ways to hedge against network disruptions because contingency plans in the event of a disruption are often significantly limited. In this article, we study the facility reliability problem: how to design a reliable supply chain network in the presence of random facility disruptions with the option of hardening selected facilities. We consider a facility location problem incorporating two types of facilities, one that is unreliable and another that is reliable (which is not subject to disruption, but is more expensive). We formulate this as a mixed integer programming model and develop a Lagrangian Relaxation‐based solution algorithm. We derive structural properties of the problem and show that for some values of the disruption probability, the problem reduces to the classical uncapacitated fixed charge location problem. In addition, we show that the proposed solution algorithm is not only capable of solving large‐scale problems, but is also computationally effective. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

采用含22.5°二面角反射器无源定标体组的极化校准方法

在实际应用中,采用传统Whitt点目标无源定标方法往往会出现极化失真矩阵求解错误从而无法正确进行校准的问题。针对这一问题,在剖析常用的Whitt算法失真矩阵求解错误原因的基础上,提出了一种采用含22.5°二面角反射器的定标体组的新定标方法,包括点目标定标体组合、极化散射矩阵测量值预处理方法及特征值配对准则,可有效避免特征值配对错误导致校准结果错误的问题。仿真试验验证了所提方法的有效性和稳健性。     

A branch-bound algorithm for the capacitated facilities location problem

This paper discusses a mixed integer programming method for solving the Facilities Location Problem with capacities on the facilities. The algorithm uses a Decomposition technique to solve the dual of the associated continuous problem in each branch-bound iteration. The method was designed to produce the global optimum solution for problems with up to 100 facilities and 1,000 customers. Computational experience and a complete example are also presented in the appendix.     

初相未知信号联合检测与估计的序贯实现

在未知参数的充分统计量和再生概率密度函数的基础上,引入了联合检测与估计的序贯算法,给出了算法的实现框图,并将该算法应用于高斯噪声中初相位未知信号的联合检测与估计当中.仿真实验表明,新算法较传统算法有一定的性能改善.     

光栅型波前曲率传感器原理与相位恢复研究

对一种新型的基于扭曲衍射光栅的波前曲率传感器原理进行了数值模拟,应用基于Gesrchberg-Saxton(GS)算法的误差减少法对这种波前传感器进行了相位恢复数值模拟。当畸变波前幅度变大时,恢复残差变大;当迭代精度变大时,恢复残差也会变大。