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

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

带投资约束p-中位问题的混合蚁群算法

将投资限制引入经典约束p-中位问题,提出带投资的约束p-中位问题,该问题更适用于交通、物流等领域的设施选址。在深入分析带投资约束p-中位问题的数学模型的基础上,首先提出了适用于该问题求解的局部搜索策略;其次,将局部搜索策略与拉格朗日启发式算法和蚁群算法相结合,设计了求解该问题的拉格朗日混合蚁群算法。实验结果表明,带投资的约束p-中位问题能够根据投资金额规划不同的投资方案;且提出的混合蚁群算法较大程度上提高了蚁群算法和拉格朗日启发式算法的求解精度,具有较好的收敛性。

一种新的求解约束P-中位问题的启发式算法

针对约束P-中位问题的特点,提出了一种新的启发式算法。该算法借鉴了蚁群算法的信息素学习机制,同时针对问题的结构设计了合理的对象分配方式。模拟计算表明,该算法具有更好的全局优化性能和计算效率。

带投资约束且p不确定的推广p-中位问题

p-中位问题是设施选址中的一个经典模型,在交通、物流等领域有着广泛应用.在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题,并且加上总投资约束,使得此推广模型更加实用.针对此推广模型,提出三种启发式算法:简单启发式算法、变邻域搜索算法和改进的遗传算法.数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的.

一种求解厌恶型p-中位问题的混合进化算法

厌恶型p-中位问题是一个NP-困难问题.提出了一种求解厌恶型p-中位问题的混合进化算法.首先,通过贪心随机自适应搜索方法和随机构造方法产生初始种群.然后,利用搜索过程中收集到的全局信息和局部信息构造新解,期间注意提高搜索的多样性,避免早熟.最后,针对厌恶型p-中位问题的特点,构造基于约束交换邻域的局部搜索算法,提高了算法的局部搜索能力.通过求解72个标准测试例子以检验算法的性能,发现该算法在较短时间内得到了高质量解,优于现有算法.

中心问题与中位问题的研究现状

p-中心问题与p-中位问题是两类基本的选址问题,在选址问题的研究中占有十分重要的地位。本文从问题的性质、算法设计思想与计算复杂性等方面总结了现有的研究成果,并指出了进一步研究的方向。

改进的求解约束P-Median问题的分散搜索算法

对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此算法能够得到优化且连续的解。

基于无容量限制的p-枢纽中位问题的随机优化

在枢纽网络设计时,未来的成本和需求等参数具有不确定性.为了使设计的网络能在各种情景下具有最优的期望成本,提出了无容量限制的多分配严格p-枢纽中位随机优化模型.考虑到模型本身的结构特点和复杂程度,采用了PH分解算法结合增广拉格朗日松弛算法,将原问题转化为若干个独立子问题来求解.使用了基于经典算例的随机数据集合对模型和算法进行了测试,算例结果表明尤其在情景数量较大的情况下,算法体现出较高的效率.同时,通过随机解价值分析了使用随机优化模型对于该算例的意义.

基于图论的区域综合能源服务商交易路径优化

随着电力体制改革的不断推进,区域能源服务商数量不断增加,电网结构日益复杂,购、售电交易双方之间的可选路径增多。在此背景下,提出了区域能源服务商交易路径两步选择法。首先基于p-中位模型的区域能源服务商交易路径第1步优化选择,考虑综合建设运行成本、能源站与负荷中心的最短路径距离、用户负荷需求三方因素,构建多目标优化模型,作用于区域综合能源服务商的站址规划;然后,基于OD矩阵和双约束重力模型提出了区域能源服务商交易路径第2步优化选择,以电能传输量最大和区域能源服务商日运营利润最大为目标函数,作用于多个区域能源服务商之间的能源传输路径选择。采用枚举法和Dijkstra算法对所建模型进行求解并通过算例仿真证明该模型能够有效降低网络损耗成本,减少弃风弃光量,提高区域能源服务商的运营利润。

基于网络分割的P-中位问题求解方法

针对传统的PMP（P-median problem）算法在单机环境下无法突破大规模地理网络求解时的空间和时间瓶颈,提出了一种基于网络分割的大规模稀疏网络P-中位问题求解方法.采用多层k-路划分算法对网络进行分割,将大规模PMP问题转换为多个小规模的PMP问题;研究了＂子网络求解-归并-调整中位点数＂操作对PMP解质量的优化效果;应用测试数据评价了网络分割对PMP解质量的影响.结果表明：该算法能够在单机环境下解算大规模PMP问题;分割后PMP解的偏差率在0.16%～2.82%之间;随着中位点数的增加,网络分割对PMP解质量的影响呈减弱的趋势.

遗传算法求解电力设施选址问题

电力系统设施选址优化问题是电力系统规划和设计中的一个基础性问题,可以抽象成约束型的p-中位(p-median)问题,这是一个经典的NP-hard问题。该问题可以描述为从一个点的集合中选择p个有容量限制的中位点,让它们去服务一些有需求的点(客户),要求每一个中位点都不超出容量,并且总花费最小。文中针对这一优化问题,在经典遗传算法的基础上,提出了一种改进的遗传算法,并混合使用局部搜索算法,进行问题的求解。该算法能够利用遗传算法的全局收敛性,并且有效克服遗传算法的局部收敛和早熟问题,从而得到更准确的近似解。最后,使用网上的公开测试数据集以及经地理信息平台(GIS)收集的某供电局的坐标信息进行实验验证。结果表明,提出的算法能够有效解决设施选址问题,并且为企业提供切实可行的方案。

集中供暖中的管路铺设方案设计

在集中供暖的建设过程中,科学合理地设计管路铺方案可以减少成本、节约资源。本文针对不同情况,对所构建的管路模型进行了相应的优化,得出了电厂对用户区供热的最优热网接口位置和最省成本模型,并将此方法推广到用户区内部供热,建立了相应模型。

轴辐式服务网络规划研究综述

轴辐式网络是服务网络中常见的一种形态,在服务企业竞争中发挥着重要的基础作用。本论文首先介绍了轴辐式网络的基本概念和形态以及优缺点,接下来从轴辐式服务网络规划的模型、算法和典型应用等方面介绍了国内外有关的研究成果,并对今后的发展趋势做出分析。