带有异常点的平方度量设施选址问题

传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用(设施的开设费用与连接费用之和),也会影响到对其他顾客的服务质量.研究异常点在最终方案中允许不被服务的情况,称之为带有异常点的平方度量设施选址问题.该问题是无容量设施选址问题的推广.问题可描述如下:给定设施集合、顾客集,以及设施开设费用和顾客...     

一类多商品设施选址问题的基于线性松弛解的启发式方法

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中,顾客的需求可能包含不止一种商品.对于大规模问题,成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式,并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解,分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.     

平方度量动态设施选址问题的近似算法

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题. 研究中首先利用原始对偶技巧得到 9-近似算法, 然后利用贪婪增广技巧将近似比改进到2.606, 最后讨论了该问题的相应变形问题.     

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

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

离散设施选址问题研究综述

本文首先回顾了设施选址问题百年发展历史,认为其研究经历了零散研究、系统研究、不确定性研究三个阶段.离散选址问题包括中值问题、覆盖问题、中心问题、多产品问题、动态问题、多目标问题、路径选址问题、网络中心选址问题8个子问题.最后作者讨论了选址问题研究中存在的问题以及今后发展的趋势.     

平方度量的k层设施选址问题的近似算法

本文中,我们研究平方度量的k层设施选址问题,该问题中设施分为k层,每个顾客都要连接到位于不同层上的k个设施,顾客与设施以及设施与设施之间的距离是平方度量的.目标是使得开设费用与连接费用之和最小.基于线性规划舍入技巧,我们给出了9-近似算法.进一步,我们研究了平方度量的k层软容量设施选址问题,并给出了线性规划舍入12.2216-近似算法.     

连续设施选址:模型、方法与应用

给定度量空间和该空间中的若干顾客,设施选址为在该度量空间中确定新设施的位置使得某种目标达到最优。连续设施选址是设施选址中的一类重要问题,其中的设施可在度量空间的某连续区域上进行选址。本文对连续设施选址的模型、算法和应用方面的工作进行了综述。文章首先讨论了连续设施选址中几个重要元素,包括新设施个数、距离度量函数、目标函数;然后介绍了连续选址中的几种经典模型和拓展模型;接着概述了求解连续选址问题的常用优化方法和技术,包括共轭对偶、全局优化、不确定优化、变分不等式方法、维诺图;最后介绍了连续设施选址的重要应用并给出了研究展望。     

设施选址博弈问题的无支付机制设计研究

选址博弈是目前国际相关学术领域的重要前沿课题之一. 在选址博弈问题中, 存在n个相互影响的``理性"居民, 他们的住址等信息是其私有信息;设计者需要设计选址机制, 以居民汇报的住址信息为输入, 输出设施位置. 在进行机制设计的过程中, 如何在没有金钱的刺激下, 保证所有居民``说真话", 设计出防策略性无支付机制是其中的重要研究内容. 设施选址博弈问题的无支付机制设计是组合优化和理论计算机科学的交叉学科课题, 在管理科学、信息科学以及社会经济学等领域有着重要的应用, 具有重要的理论意义和实际的应用价值. 现根据不同设施类型及个数、不同个人偏好、不同度量空间以及不同社会总体目标等条件, 介绍各种类型的设施选址博弈模型, 罗列相关的研究成果, 并总结其中尚待解决的问题.     

大规模多设施Weber问题的改进Cooper算法

 多设施Weber问题（multi-source Weber problem,MWP）是设施选址中的重要模型之一,而Cooper算法是求解MWP最为常用的数值方法.Cooper算法包含选址步和分配步,两步交替进行直至达到局部最优解.本文对Cooper算法的选址步和分配步分别引入改进策略,提出改进Cooper算法：选址步中将Weiszfeld算法和adaptive Barzilai-Borwein （ABB）算法结合,提出收敛速度更快的ABB-Weiszfeld算法求解选址子问题;分配步中提出贪婪簇分割策略来处理退化设施,由此进一步提出具有更好性质的贪婪混合策略.数值实验表明本文提出的改进策略有效地提高了Cooper算法的计算效率,改进算法有着更好的数值表现.     

多阶响应下军事物流配送中心可靠选址模型

为了提高战时物资配送的敏捷性和可靠性,结合军事物资配送的多阶响应过程,以部队用户对配送响应的时间约束为限制条件,以设施固定成本与期望配送成本之和为目标函数,并考虑设施未来失效的可能,建立了混合整数规划形式的军事物流配送中心可靠选址模型.结合模型的特点,采用基于时间约束的启发式算法将模型转化为可行子问题进行求解,使用仿真算例说明模型的优越性和算法的有效性.与不考虑设施失效的选址模型相比,考虑设施失效的选址方案在出现设施失效时,其应急配送成本平均增加量基本不超过设施固定成本的20％,平均最大增加量不超过25％;同一种失效情景下,考虑设施失效的选址方案的应急配送总成本也明显小于不考虑设施失效的选址方案的总成本.     

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

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

软容量约束的动态设施选址问题的近似算法

考虑软容量约束的动态设施选址问题.假设设施的开放费用及连接费用都与时间有关,而且每一个设施均有容量约束.对此问题给出了第一个近似比为6的原始对偶(组合)算法.运行贪婪增加程序后,近似比进一步改进到3.7052.     

带补偿机制的垃圾焚烧厂选址问题研究

研究了带补偿机制的垃圾焚烧厂选址问题,在综合考虑选址成本、补偿标准等因素的前提下,建立了以垃圾焚烧厂对附近居民造成的负面影响极小化和垃圾焚烧厂的总运行费用极小化为目标的垃圾焚烧厂选址问题的双目标规划模型,通过一个具体算例验证了模型的有效性,得到了符合实际的结果.模型可推广应用于其它邻避型设施选址问题.     

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

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

带有惩罚和软容量约束的下界设施选址问题的双标准近似算法研究

研究带惩罚和软容量约束的下界设施选址问题. 扩展Guha等(Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems [C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328)和Karger等(Karger D R,Minkoff M. Building steiner trees with incomplete global knowledge [C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329)的工作到带有惩罚的下界约束设施选址问题,提出了一个新的双标准近似算法,得到了同样的近似比ρ(1+α)/(1-α). 进一步考虑带惩罚和软容量约束的下界设施选址问题,得到了近似比为2ρ(1+α)/(1-α)的双标准近似算法.     

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

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

基于失效情景的应急设施选址问题

非常规突发事件巨大的破坏力以及发生时间、地点和规模的不确定性,使应急系统内设施有可能被破坏而失效,因此选址时必须考虑设施失效情景的发生.给出以最大限度覆盖用户需求为目标,基于失效设施数目具有不确定性情景的设施选址双层随机规划模型;通过计算模型上下界,给出减小规模的等价模型,降低了双层规划求解难度;最后实验验证了模型的合理性,并给出新增选址方案.     

需求导向的容量设施竞争选址问题研究

客户意愿与容量限制是竞争设施选址问题中两个重要的影响因素,在考虑客户意愿与设施容量共同作用条件下,建立了最小化企业总成本以及每个客户费用为目标的竞争设施选址问题优化模型,通过设计需求导向服务分配机制解决设施与客户之间服务关系分配问题,结合模拟退火思想提出了求解模型的算法。最后利用数值例子分析了需求导向服务分配机制以及目标权重、预算限额等参数对于选址决策的影响,其中考虑需求导向因素会适当增加企业的总成本,但可以减少客户所付出的费用从而增强对客户的吸引力;另外企业的预算限额对于企业的设施选址决策有着重要的影响,企业所能获取的市场份额与其选址预算限额呈正相关的关系;而客户所需付出的总费用与企业提供服务的总成本两者之间则呈负相关的关系,因此需要通过服务质量与成本之间的权衡实现最理想的选址决策。     

基于现存设施布局的设施选址:应对恐怖袭击

本文研究了恐怖袭击事件下,政府和极端组织作为参与者的博弈选址问题。在这一博弈过程中,恐怖分子袭击城市以最大化其破坏效用,政府作为斯塔克博弈中的领导者预见恐怖组织的策略选择进行选址决策,以最小化损失程度。针对其中政府选址决策的对象,我们考虑了一种更接近现实的情形—基于现存设施布局的考量。面对这类在恐怖事件发生前就已经存在的反恐设施,本文重点探讨了政府何种情况下需要考虑设施的改建,以及如何进行应急设施的策略选择和选址定位。此外,考虑了固定设施数目与变量设施数目的情景,当设施数目固定时,把博弈问题看作一个设施的数学规划问题,构建基于现存设施的选址决策模型;讨论了设施数目为变量时政府的均衡效用。通过对20个城市的案例仿真,结果表明,对于政府而言,考虑设施改建的策略始终优于不考虑设施改建的策略。在考虑设施改建的选址策略下,当设施数量固定时,已建设施数量与改建设施数量相互制约,并与改建设施、新建设施成本一同影响着政府的均衡效用。政府的策略选择主要取决于改建设施成本的分布,在某些阈值区间范围内策略相同。当设施数量为变量时,政府的均衡效用不是K的单调函数,此时,可以建设少于K个数量的设施达到建立K所得到的效用。     

软容量约束带随机需求的设施选址问题的近似算法

文考虑了软容量约束带随机需求的设施选址问题,根据此问题构造出一个无容量约束带随机需求的设施选址问题,通过求解无容量约束情形给出软容量情形的一个可行解,分析出近似比为6。