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

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

竞争环境下截流设施选址问题

研究企业新建设施时,市场上已有设施存在的情况下,使本企业总体利润最大的截流设施选址问题。在一般截留设施选址模型的基础上引入引力模型,消费者到某个设施接受服务的概率与偏离距离及设施的吸引力相关,同时设施的建设费用与设施吸引力正相关,建立非线性整数规划模型并使用贪婪算法进行求解。数值分析表明,该算法求解速度快,模型计算精度较高。     

带覆盖需求约束的设施选址问题

带覆盖需求约束的设施选址问题(FLPWCDL)研究:客户必须在规定的响应半径内被服务,并要求服务站能够覆盖规定的需求数量,如何选择合适的服务站,使总成本(建站成本+路线成本)最小.FLPWCDL广泛应用于应急服务、物流、便利店等服务站的选址.建立了问题的混合整数规划模型,并构造了求解FLPWCDL的Benders分解算法,计算实验显示Benders分解算法具有非常高的求解效率与求解质量.     

重大突发事件应急设施多重覆盖选址模型及算法

为了解决应对重大突发事件过程中应急需求的多点同时需求和多次需求问题,本文研究了应对重大突发事件的应急服务设施布局中的覆盖问题:针对重大突发事件应急响应的特点,引入最大临界距离和最小临界距离的概念,在阶梯型覆盖质量水平的基础上,建立了多重数量和质量覆盖模型。模型的优化目标是满足需求点的多次覆盖需求和多需求点同时需求的要求条件下,覆盖的人口期望最大,并用改进的遗传算法进行求解;最后给出的算例证明了模型和算法的有效性,从而应急设施的多重覆盖选址模型能够为有效应对重大突发事件的应急设施选址决策提供参考依据。     

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

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

基于可信度模糊费用多设施选址模型和算法

设施选址在整个物流网络中是一个十分重要的决策问题，它决定了整个物流系统的模式，结构和形状。设施选址方法尤其是多设施选址方法的研究已经成为一个备受人们关注的研究领域。本文首先介绍了设施选址的重要性，然后在模糊环境中根据不同的决策标准，建立了三种不同类型的模型，并设计了一个遗传算法来解决其中一个模型。最后给出了一个数值例子。     

给定限期条件下应急选址问题的量子竞争决策算法

为求解给定期限条件的应急设施选址问题,本文提出了一种量子竞争决策算法.将量子个体作为博弈者参与到竞争决策中,利用量子位、叠加态等理论提高竞争群体多样性,缩小群体规模,加快优化速度;基于进化博弈论中博弈者学习和策略调整的机制,实现竞争者学习和自演化的目的,增强算法的寻优能力.实验结果表明算法的可行性和有效性.     

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

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

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

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

设施选址问题的近似算法综述

设施选址问题是运筹学和理论计算机科学中的经典问题之一.本文介绍设施选址问题及其变形的近似算法设计与分析思想,并总结设施选址问题的研究中若干未解决的重要问题.     

两阶段选址优化问题研究

本文主要考虑如下实际问题:假设选址决策者需要建设p个设施,但是由于资金等等的影响,实际建设时会被要求先建设q个设施,其次再建设p-q个设施(设p>q),同时要求,在建设p-q个设施的时候,已经建设好的q个设施不被删除。本文建立了一个两阶段优化问题,问题的输出是两个待修建的设施的集合Fq,Fp,|Fp|=p,|Fq|=q,且Fq是Fp的子集,问题的目标是最小化这两个设施集合的费用同对应的最优费用的比值的最大值。本文给出一个近似比为9的近似算法,并对一些特殊的情况进行了讨论。所得结论对实际的选址决策具有理论意义,同时也完善已有相关研究结果。     

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

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

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.     

无容量限制设施选址问题的降阶回溯算法

无容量限制设施选址问题(uncapacitated facility location problem, UFLP)是经典组合优化中NP-Hard问题之一,在诸多领域具有广泛的应用价值。本文首先研究UFLP的数学性质,并进行了数学证明。运用这些数学性质不仅可以确定某些设施必定开设或者关闭,还可以确定某些连接边是否在服务集中,从而缩小问题的规模,加快求解速度;在此基础上设计出一个新的基于上下界的回溯算法来求解UFLP。最后,通过一个示例进一步阐述该算法的原理,结果表明该算法具有明显的可行性和有效性。