竞争环境下截流问题的选址-价格模型

研究了竞争环境下考虑产品定价的截流设施选址问题。连锁企业在市场上新建设施时,市场上已有属于竞争对手的设施存在,在连锁企业新建设施位置确定之后,两个企业关于产品定价进行双寡头完全信息非合作博弈。定义了效用函数,引入Huff模型,以企业利润最大为目标,建立双层规划模型,证明了模型纳什均衡价格的存在性,并构造启发式算法对模型进行求解。算例分析表明,该算法求解结果较为理想,可用于大中型网络的规划选址问题。     

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

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

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

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

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

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

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

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

拥塞情形下的电动汽车充电设施选址优化

由于充电汽车充电时间较长,充电设施具有明显的拥塞情形.在假设充电设施容量限制的基础上,研究了在车流量和充电时间随机的情形下,如何对充电设施布局使得充电车满足充电服务的平均数量最大化.在基本截流选址模型的基础上,建立了0-1非线性整数规划,通过选址决策使得截得的平均车流量最大化,并结合贪婪算法和dogleg路径信赖域方法来求解该问题,通过算例表明了算法的有效性.     

多类型需求流的截流选址问题研究和算法实现

本文研究了网络上固定的O-D对上存在不同类型的需求流的选址问题。在基本截流模型的基础上提出了多类型需求流多目标截流选址问题的模型,将模型转化为多目标模糊规划问题,运用混合遗传算法求解模型,最后给出了算例,并与分支定界法相比,证明了混合遗传算法可以有效的求解此模型。     

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

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

考虑顾客便利半径和质量阈值的竞争设施选址问题

在竞争设施选址问题中,顾客选择行为是决定设施占领市场份额的重要因素,其描述了需求在设施之间的分配方式。为了贴近顾客真实的光顾行为,本文提出了一种考虑顾客便利半径和质量阈值的顾客选择规则,并研究了在该规则下市场中新进入公司的竞争设施选址问题。提出了一种基于排名的遗传算法(RGA)求解该问题,并将该算法与经典遗传算法(GA)和基于排名的离散优化算法(RDOA)进行了比较,结果说明了算法的有效性以及模型中质量阈值的重要性。     

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

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

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.     

两阶段选址优化问题研究

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

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

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

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

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

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