求解无容量设施选址问题的改进禁忌搜索算法

无容量限制设施选址问题(Uncapacitated Facility Location Problem,UFLP)属于经典组合优化NP-Hard问题,为了快速有效地求解UFLP,文章采用禁忌搜索算法来求解无容量设施选址问题。首先,描述了局部搜索中用来求解该问题的三种操作算子,进一步增强其全局搜索性能。其次,禁忌搜索算法在寻优过程中对初始解具有一定的依赖性,运用随机化与贪心算法相结合的方法来生成初始解,通过引入动态禁忌列表的方法,避免搜索到重复表中的解,并对改进后禁忌搜索算法的有效性进行了评估。最后,通过求解经典算例进行测试和其他算法进行比较的方式,验证了该算法用来求解UFLP的可行性和有效性。

考虑容量和成本的最大最小分散度选址问题的降阶回溯算法

最大最小分散度问题可简单描述为:在给定的集合中选择包含固定元素个数的子集,使得该子集中的元素在给定距离度量下的最小距离最大;该问题在生产生活中有广泛的应用.近些年来,该问题的一种考虑容量下限和成本上限的变体开始引起学者们的关注,并已被证明为NP-Complete问题.基于考虑容量和成本的最大最小分散度选址问题进行研究,首先提出该问题的数学性质并证明,利用这些性质可以减小问题规模或缩减搜索空间,以加快问题的求解速度,然后设计了上下界子算法及降阶子算法;基于这些子算法提出一种可大幅缩减搜索空间并能得到最优解的降阶回溯算法.通过分析和求解一个示例来阐述该算法的原理和执行过程,并通过随机算例测试、算法对比分析和案例分析进一步验证了该算法的可行性和有效性.结果表明该算法可有效通过大幅缩减搜索空间加快问题的求解速度.

基于OpenMP求解无容量设施选址问题的并行PSO算法

讨论无容量设施选址(UFL)问题,提出了一个基于OpenMP技术的并行多粒子群优化(PSO)算法.将整个种群分为若干子种群,同时利用局部信息来更新粒子速度,使得并行算法异步进行.算法运行一定代数后,每个子种群都会与其相邻种群交换最优粒子.通过将并行多粒子群算法对OR-library中的标准测试问题进行测试,并将计算结果与串行多粒子群算法的计算结果进行比较.相比之下,并行多粒子群算法执行时间短,特别对于大规模的计算问题,所得结果有更好的鲁棒性.

求解无容量设施选址问题的拉格朗日狼群算法及其应用

无容量设施选址问题(UFL)是应用于诸多领域的经典组合优化难题。首先,结合UFL问题的具体特征,重新定义了狼群算法中狼群协作捕食的智能行为,提出了求解该问题的狼群优化算法;其次,将狼群算法与拉格朗日松弛相结合,设计了一种求解UFL问题的拉格朗日狼群算法;最后,将本文提出的狼群智能优化算法及拉格朗日狼群算法用于UFL基准问题库中部分算例的求解,并将其求解结果与混合蚁群算法、半拉格朗日松弛方法以及优化软件CPLEX的求解结果进行比较。结果表明:拉格朗日狼群算法较狼群优化算法、混合蚁群算法及半拉格朗日松弛方法具有更好的求解效果,而且在一定程度上缓解了CPLEX求解时间长、消耗内存大的缺点,拥有良好的求解性能。

求解无容量设施选址问题的混合蚁群算法

无容量设施选址(UFL)问题是经典的优化问题,属于NP难题,易于描述却难于求解.首先,介绍了UFL问题的数学模型,并对UFL问题的特点进行深入分析,得到其最优解所具有的基本特征;其次,针对UFL问题的最优解所具有的基本特征,设计了两种局部搜索策略,并将其与基本蚁群算法相结合,提出了一种用于求解UFL问题的混合蚁群搜索算法;最后,为了测试该算法的性能,分别利用混合蚁群算法和基本蚁群算法求解UFL问题基准问题库中的16个测试算例.计算结果表明,混合蚁群算法有效改进了基本蚁群算法求解UFL问题时易陷入局部最优、收敛速度慢等不足,该算法对求解UFL问题具有明显的可行性和有效性.

多阶段粒子群优化算法求解容量约束p-中位问题

容量约束p-中位问题(Capacitated P-Median Problem,CPMP)已被证明是一类计算机难以求解的具有NP-hard特性的组合优化问题.本文提出一种多阶段粒子群优化算法(Multi-Phase Particle Swarm Optimization,MPPSO)及在算法设计中应用模式有关理论和方法.所提MPPSO在标准PSO基础上,考虑CPMP结构特征信息,采用一种以字符编码为基础的结构体编码结构,重新定义粒子速度与位置更新方式.它将CPMP优化求解分为种群粒子初始化阶段及两个优化阶段.在优化求解第一阶段,分析了惯性因子对所求问题编码结构粒子搜索的局限性,设计一种保留粒子最优特征中位点信息的变异算子.以粒子全局搜索算子操作为重点,期望从整个搜索空间搜索到好的模式结构分布特性的粒子.在优化求解第二阶段,对高适应性粒子执行一种改进的迭代局部搜索操作,达成对粒子精度的进一步提升.迭代局部搜索分为基本局部搜索和深层次局部搜索.基本局部搜索侧重对粒子需求点和中位点提炼用于发现候选粒子相邻的局部最优解.在深层次局部搜索中,采用对粒子执行扰动算子操作,使得算子操作在更大邻域范围内搜索粒子新的模式结构,从而发现蕴含高适应性模式结构的潜在更好解.文中提出模式范数及模式结构距离等概念,并将它们用于扰动算子设计.实验测试表明:MPPSO对4大类CPMP用例问题进行求解得到的实验数据,与4种文献对比算法提供的数据相比有一定优势,且能发现3个大数据集用例新的最好解.

基于伪布尔模型和启发式算法求解无容量设施选址问题

采用伪布尔模型和启发式算法来求解无容量设施选址问题。首先给出了问题的伪布尔(pseudo-Boolean)表示,然后基于Khumawala规则对问题进行预处理,最后提出两种启发式分支准则来求解问题。实验结果表明所提算法简单有效。

自适应混合蚁群算法求解带容量约束车辆路径问题

针对带容量约束车辆路径问题(capacitated vehicle routing problem,CVRP),提出了一种自适应混合蚁群算法.由蚁群算法生成子回路,为增强跳出局部最优能力,在蚁群算法的状态转移规则和信息素更新规则中引入了自适应机制.基于子回路组合,由遗传算法构造近似解,根据问题编码特性设计了适应度函数和遗传算子,提高了构造效率,并采用Clark和Wright节约算法将近似解修复成可行解.采用扫描法和2-opt局部优化方法提高可行解的质量.标准算例的实验结果表明,该算法在求解CVRP问题上具有良好的寻优精度和寻优效率.灵敏度分析结果表明蚂蚁数量对算法性能具有显著影响.

带容量约束的车辆路径问题算法综述

CVRP的研究带动了确定性算法和启发式算法的发展。简要回顾了这些新算法的发展,总结对比现有方法,提出可能的研究方向。

变容量限制多阶段存储问题及其求解算法

本文给出了求变容量限制多阶段存储问题的最优存储方案的一个数值算法 ,证明了它的理论依据 ,并举例说明了算法的应用。该算法具有概念清楚、步骤明确、收敛性好、易于编程实现等优点 。

有容量集合覆盖选址问题的降阶回溯算法

有容量集合覆盖选址问题是组合优化中的一个经典的NP-Hard问题,在许多工程领域和科学领域中的应用十分广泛.本文将集合覆盖问题的模型应用到有容量设施选址问题中,首先研究了该问题的数学性质并给予相应的证明,利用这些数学性质能够对问题进行降阶,降低问题求解难度;然后设计了上界子算法、下界子算法和分配子算法,基于这些子算法提出了一种能够快速缩小问题规模同时能得到精确解的降阶回溯算法;最后文章通过分析和求解一个示例来进一步阐述本文算法的原理和执行过程.

求解无容量设施选址问题的拉格朗日蝙蝠算法

无容量设施选址问题(Uncapacitated Facility Location Problem,UFLP)是一类经典的组合优化问题,被证明是一种NP-hard问题,易于描述却难于求解.首先根据UFLP的数学模型及其具体特征,重新设计了蝙蝠算法的操作算子,给出了求解UFLP的蝙蝠算法.其次构建出三种可行化方法,并将其与求解UFLP的蝙蝠算法和拉格朗日松弛算法相结合,设计了求解该问题的拉格朗日蝙蝠算法.最后通过仿真实例和与其他算法进行比较的方式,验证了该混合算法用来求解UFLP的可行性,是解决离散型问题的一种有效方式.

多起始点进化算法在容量约束弧路径问题上的应用

容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.

固定容量设备选址问题的求解算法研究

由于大多数选址问题都已证明是NP-难问题,研究问题的近似算法成为其关键技术。本文就是基于大规模邻域搜索(VLSN)技术的迭代局域搜索(ILS)算法来解决资源固定容量设备选址问题(CFLP)。为了说明VLSN技术的有效性,本文又实现了多点下降算法,并且结合大规模算法和多点下降算法求得了质量更好的解。

面向5G演进的4G容量问题探讨

一、前言5G网络相比当前的4G网络具有更高的传输速率,更快的响应速度和更大连接能力的特点,在国家战略层面,5G是实现"中国制造2025"与"网络强国战略"的必要组成部分。预测到2030年,5G可以带动总产出达到6.3万亿元,就业人数达到800万个,未来5G将赋能各行各业应用,给人们生活带来便利,移动通信网络向5G演进的进程也随之加快。

求解无容量设施选址问题的混合蝙蝠算法

无容量设施选址(Un-capacitated Facility Location,UFL)问题是可以运用于不同领域的经典优化难题。蝙蝠算法(Bat Algorithm,BA)是一种新的群智能优化算法,目前还未被应用到无容量设施选址问题的求解中。针对蝙蝠算法易陷入局部最优、收敛精度低、后期收敛速度慢的缺点,并结合无容量设施选址问题的具体特征,将三种局部搜索策略、和声搜索机制与基本蝙蝠算法相结合,使用一种新的随机游走法则公式改善蝙蝠的搜索能力,设计了求解无容量设施选址问题的混合蝙蝠算法。通过实例测试将混合蝙蝠算法与其他算法进行比较,验证了该算法求解无容量设施选址问题的有效性与可行性。

基于分支割平面的一类无容量限制设施选址问题求解算法

无容量限制设施选址问题是经典的组合优化问题,具有广泛的应用价值,然而该问题已被证明是NP难问题,并且传统的分支定界方法求解速度较慢.研究以最大化总收益费用与总投建费用之差为目标的无容量限制设施选址问题,将其转化为节点包装问题,并根据模型的图形特点提出了新的合法不等式族一轴不等式族,经过严格的数学证明后得出轴不等式要强于原有的奇洞不等式.同时,设计出切割不等式快速搜索算法嵌入到分支割平面方法中.最后,通过实验验证了轴不等式族的强有效性,以及分支割平面方法比分支定界方法求解速度快、节点数量少的优点.

同时配送和回收需求的带容量约束弧路径问题

提出了一种同时配送和回收需求的带容量约束的弧路径问题(CARPSPD),建立了该问题的基于直观描述的数学模型,设计了求解该问题的构造启发式算法与变邻域搜索算法。前者利用基于路径扫描的构造方法产生弱可行解,再转换成强可行解;后者采用5种邻域结构混合进行局部搜索,并采用了一种分层的局部搜索策略,扩大了算法的搜索空间。两种算法在23个基准数据集上的求解结果表明,变邻域搜索算法在稳定性与解的质量等方面都优于构造启发式算法,能更有效地求解CARPSPD。

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

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

有容量约束车辆路径问题的蒙特卡洛模拟算法

带容量约束的车辆路径问题是一个NP-hard问题。针对此问题将蒙特卡洛模拟方法与流行的节省算法结合。提出Flag-MCS-CWS算法,该方法通过对CWS算法得到的节省序列进行蒙特卡洛模拟,适用于不同节点数、不同车辆载重量的车辆路径问题。在标准数据集测试,相比当前最优解有平均0.75%的改进,为车辆路径问题提供了更加有效的解决方案。