会议选址问题的优化模型

国内某公司在各省会城市都设有分支机构,公司每年都有频繁的会议和培训工作需要各地分支机构派人参加,如何在大陆地区31个省会城市里选择一个城市作为会议地址,使得举办会议的成本最低且中转次数最少.建立了该会议选址问题的双目标优化模型,收集处理了有关实际数据,利用网络最短路算法和约束法等得到了该会议选址问题的解.在不考虑中转费用的情况下,得出成本最低且中转次数最少的会议地址是西安;在考虑中转费用的情况下,根据中转费用的不同给出了可供实际决策的最优会议选址方案.     

选址问题研究的若干进展

中值问题、覆盖问题、中心问题是选址研究中的三个经典问题，它们的应用非常广泛，也是迄今为止大多数选址理论研究的坚实基础。本文综述了近年来它们的研究进展，包括模型、求解方法以及相关问题，最后，指出这一领域未来研究的一些问题与方向。     

区间图上可带负权的2-中位选址问题（英文）

Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题（p≥2）可分为两类：即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O（n~2）的多项式时间算法.     

平面上的min-max型点-线选址问题

本文研究两类平面选址问题：(1)求一直线到n个给定点的最大加权距离为最小；(2)求一点到n条给定直线的最大加权距离为最小．对这两个非线性优化问题，我们给出最优解的刻划及迭代次数为多项式的算法．     

混凝土搅拌站的选址问题研究

混凝土搅拌站的选址,在施工中占有十分重要的地位.针对混凝土需求随时间不规则变化的情况以及混凝土有效期短等特点,提出了混凝土需求不规则变化的选址模型.该模型把选址与各个时间段的资源配置结合起来确定混凝土搅拌站的位置,在保证需求最大限度得到满足的同时,使选址能够兼顾到尽可能多的需求点,最大化搅拌站的利润.应用该模型和算法成功地解决了一个实际问题,算例验证了模型和算法的有效性.     

顾客为子树结构的树上反中心选址问题

顾客为子树结构的树上反中心选址问题是在树T上寻找一点(位于顶点处或在边的内部),使得该点与子树结构的顾客之间的最小赋权带加数距离尽可能地大.给出了该问题的一个有效算法,其时间复杂度为O(cn+sum from j=1 to m n_j),其中n_j为各子树T_j的顶点个数,c为不同的子树权重个数,n为树的顶点数.     

基于拟物方法的网络服务器选址问题的模型

带约束条件下的网络服务器的选址决策问题在信息服务中具有重要意义．本文从客户段的不确定性分析出发,建立一个基于拟物方法的服务器选址决策的改进模型．与原有模型相比,它能更合理描述信息服务中各种不同类型商品的供应者．并且它克服了原有模型不适用于已有多个供应者存在的情形．为带约束的网络服务决策提供科学依据．     

拆解中心的选址决策研究

针对拆解中心选址决策问题,考虑到检测中心到拆解中心和用户的运输容量,基于成本最小原则,建立了备选拆解中心选址的优化模型,并提出了求解算法,最后通过算例说明了方法的可行性.     

一道合理选址问题的推广

20 0 1年第 8期《中学生数学 (高中版 )》第 19页《合理选址问题的求解两例》(作者 :夏国华 )一文的例 2是一个颇有意义的问题 ,即图 1　例题图如图 1,A地产汽油 ,B地的汽油需从产油地A运入 ,汽车自A地运汽油往B地 ,往返的油耗正好等于其满载汽油的吨数 ,故无法将汽油运至B地 .为解决问题 ,在途中C地设一油库为中间站 ,先由往返于A ,C间的汽车将油运往C地 ,再由往返于C ,B间的汽车将油运至B地 .问当C站设在何处时运油率 (即B地收到的汽油量 /A地运出的汽油量 )最大 ,最大值是多少 ?该文得到的答案是 :C站设在A ,B两地的中点处时 ,运…     

基于人工蜂群算法的配送中心选址问题求解

采用人工蜂群算法对配送中心选址问题进行求解,给出食物源的编码方法,通过整数规范化,使算法能在整数空间内对问题进行求解.应用算法进行了仿真实验,并将结果与其它一些启发式算法进行了比较和分析.计算结果表明人工蜂群算法可以有效求解配送中心选址问题,同时也为算法求解其它一些组合优化问题提供了有益思路.     

COBRA: A New Formulation of the Classic p-Median Location Problem

The p-median problem was first formulated as an integer-linear programming problem by ReVelle and Swain (1970) and further revised by Rosing, ReVelle and Rosing-Vogelaar (1979). These two forms have withstood the test of time, as they have been used by virtually everyone since then. We prove that a property associated with geographical proximity makes it possible to eliminate many of the model variables through a substitution process. This new substitution technique has resulted in the elimination of up to 60% of the variables needed in either of these classic model formulations.     

Robust Optimization for the Connected Facility Location Problem

In this paper we present a robust optimization (RO) model for the Connected Facility Location (ConFL) problem within the framework introduced by Bertsimas and Sim [Bertsimas, D. and M. Sim, Robust discrete optimization and network flows, Mathematical Programming 98 (2003), pp. 49–71], and show how to use a heuristic in conjunction with a lower bounding mechanism to rapidly find high-quality solutions. The use of a heuristic and a lower bound mechanism within this RO approach decreases significantly its computational time and broadens its applicability to other NP-hard problems. Here we present some of our computational results that attest to the efficiency of the approach, particularly on the Robust ConFL problem.     

Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers

This paper studies a facility location problem with stochastic customer demand and immobile servers. Motivated by applications to locating bank automated teller machines (ATMs) or Internet mirror sites, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. Customers are assumed to visit the closest open facility. The objective of this problem is to minimize customers' total traveling cost and waiting cost. In addition, there is a restriction on the number of facilities that may be opened and an upper bound on the allowable expected waiting time at a facility. Three heuristic algorithms are developed, including a greedy-dropping procedure, a tabu search approach and an -optimal branch-and-bound method. These methods are compared computationally on a bank location data set from Amherst, New York.     

A Probabilistic Minimax Location Problem on the Plane

In this paper we consider the weighted minimax (1-center) location problem in the plane when the weights are not given but rather drawn from independent uniform distributions. The problem is formulated and analyzed. For certain parameters of the uniform distributions the objective function is proven to be convex and thus can be easily solved by standard software such as the Solver in Excel. Computational experience is reported.     

鲁棒动态设施选址问题的近似算法

设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务 (带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的 (带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。     

带惩罚的动态设施选址问题的近似算法

本文研究带惩罚的动态设施选址问题,在该问题中假设不同时段内设施的开放费用、用户的需求及连接费用可以不相同,而且允许用户的需求不被满足,但是要有惩罚.对此问题我们给出了第-个近似比为1.8526的原始对偶(组合)算法.     

Solving the p-Median Problem with a Semi-Lagrangian Relaxation

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem. This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish government, MCYT subsidy dpi2002-03330.     

有容量限制的可靠性固定费用选址问题

设施网络可能面临各种失灵风险,而设施选址属于战略决策问题,短期内难以改变,因而在选址设计时需要充分考虑设施的非完全可靠性。本文针对无容量限制的可靠性固定费用选址问题进行扩展,进一步考虑设施的容量约束,基于非线性混合整数规划方法建立了一个有容量限制的可靠性固定费用选址问题优化模型。针对该模型的特点,应用线性化技术进行模型转化,并设计了一种拉格朗日松弛算法予以求解。通过多组算例分析,验证了算法的性能。算例分析结果表明设施失灵风险和设施容量对于选址决策有显著影响,因而在实际的选址决策过程中有必要充分考虑设施的失灵风险及容量约束。     

Location problems

Recent developments for several location problems are surveyed. These include: graph theoretic and combinatorial formulations of the simple plant location problem, the NP-hardness of some p-center problems, worst-case bounds for several polynomial-time heuristics for some p-center problems, and a general solution to a class of one facility network problems with convex cost functions.