变邻域量子烟花算法求解CVRP 被引量：17

1

作者 蔡延光 陈厚仁 戚远航 《计算机工程与应用》 CSCD 北大核心 2019年第9期230-236,共7页

针对带容量约束的车辆路径问题,提出一种融合量子进化算法和变邻域优化策略的变邻域量子烟花算法。该算法采用等分随机键与最大位置法结合的实数编码方式,通过量子旋转门和非门变异提高算法全局搜索能力,同时运用结合2-Opt的变邻域优化... 针对带容量约束的车辆路径问题,提出一种融合量子进化算法和变邻域优化策略的变邻域量子烟花算法。该算法采用等分随机键与最大位置法结合的实数编码方式,通过量子旋转门和非门变异提高算法全局搜索能力,同时运用结合2-Opt的变邻域优化策略加强局部搜索能力。选取17个基准算例进行参数实验和对比实验,实验结果表明,相对于对比算法,所提出的算法具有较好的寻优能力和收敛速度。 展开更多

关键词 烟花算法 量子进化算法 变邻域搜索 容量约束车辆路径问题(cvrp) 最大位置法

在线阅读 下载PDF 职称材料

一种新的免疫克隆算法在CVRP问题中的应用 被引量：1

2

作者 石刚 井元伟 马佳 《东北大学学报（自然科学版）》 EI CAS CSCD 北大核心 2009年第10期1373-1376,共4页

基于克隆选择学说,通过引入克隆算子提出一种新的免疫克隆算法,并将其用于求解CVRP问题.该算法采用了克隆增殖、高频变异和克隆选择算子的操作,增加了种群中优秀个体获得克隆增殖实现亲和度成熟的机会,提高抗体群分布的多样性,在深度搜... 基于克隆选择学说,通过引入克隆算子提出一种新的免疫克隆算法,并将其用于求解CVRP问题.该算法采用了克隆增殖、高频变异和克隆选择算子的操作,增加了种群中优秀个体获得克隆增殖实现亲和度成熟的机会,提高抗体群分布的多样性,在深度搜索和广度寻优之间取得了平衡.仿真结果表明,该算法具有良好的全局收敛性和较快的收敛速度,能有效解决CVRP问题. 展开更多

关键词 人工免疫系统 免疫克隆算法 克隆选择 疫苗 cvrp

在线阅读 下载PDF 职称材料

基于改进蚁群算法的CVRP问题研究 被引量：3

3

作者 程亮 干宏程 刘勇 《重庆工商大学学报（自然科学版）》 2021年第5期81-86,共6页

车辆路径优化问题归属于NP-hard问题;针对基本蚁群算法求解效率低下,可行解质量不高,容易陷入局部最优解的情况,在充分考虑具有一般性的车辆路径优化问题的数学模型与解决方案后,提出了一种带有轮盘赌运算与2-opt优化运算相结合的改进... 车辆路径优化问题归属于NP-hard问题;针对基本蚁群算法求解效率低下,可行解质量不高,容易陷入局部最优解的情况,在充分考虑具有一般性的车辆路径优化问题的数学模型与解决方案后,提出了一种带有轮盘赌运算与2-opt优化运算相结合的改进蚁群算法,算法在运算过程中对选取路径的概率进行二次计算,扩大了全局的搜索范围;同时对得到的路径进行内部优化,增强了局部搜索能力,提高了解的质量;通过MATLAB软件进行仿真实验的结果表明:相较于基本的ACO算法以及遗传算法得到的结果,改进的蚁群算法在性能上和求解的质量具有很大的优势,可以更好地解决带有容量约束的车辆路径优化问题,为相应的企业更好地节省物流成本。 展开更多

关键词 物流配送 蚁群算法 2-opt cvrp问题

在线阅读 下载PDF 职称材料

CVRP问题的一种启发式算法 被引量：3

4

作者 柏明国 李书金 韩梅 《山东科技大学学报（自然科学版）》 CAS 2003年第4期52-54,共3页

推广了DenieIe Vigo提出的解决ACVRP的方法,给出一种解决CVRP的启发式算法,并且举例 说明了这种算法的有效性与优越性。

关键词 cvrp问题 启发式算法 车辆路径问题 容量固定 穿插过程 细化过程 组合优化

在线阅读 下载PDF 职称材料

蚂蚁优化算法在解决CVRP中的应用 被引量：2

5

作者 刘瑛 《重庆工商大学学报（自然科学版）》 2013年第4期45-49,共5页

针对基本蚁群算法收敛性差,易于停滞的缺陷,通过引入信息素窗口限制信息素的最大最小值,只对迭代最好解进行信息素更新,判断汇聚情况进行信息素重新初始化,在每次迭代中加入局部搜索优化,在选择概率中加入与问题相关的参数等措施对蚁群... 针对基本蚁群算法收敛性差,易于停滞的缺陷,通过引入信息素窗口限制信息素的最大最小值,只对迭代最好解进行信息素更新,判断汇聚情况进行信息素重新初始化,在每次迭代中加入局部搜索优化,在选择概率中加入与问题相关的参数等措施对蚁群进行优化,提高蚁群算法的收敛性,避免了算法的停滞现象。 展开更多

关键词 cvrp 优化蚁群算法 车辆路径规划

在线阅读 下载PDF 职称材料

基于改进蚁群算法的CVRP问题 被引量：7

6

作者 张海军 徐廷学 +1 位作者 逯程 韩玉 《火力与指挥控制》 CSCD 北大核心 2019年第1期67-71,共5页

为了能够更好地求解CVRP问题,对蚁群算法进行了一定程度的改进。改进后的算法更加科学地初始化蚂蚁的位置,使蚂蚁有更大可能性地寻找到最优路径。在搜索的过程中与禁忌搜索算法结合,添加新的参数负信息素来记忆已经访问过的客户。同时,... 为了能够更好地求解CVRP问题,对蚁群算法进行了一定程度的改进。改进后的算法更加科学地初始化蚂蚁的位置,使蚂蚁有更大可能性地寻找到最优路径。在搜索的过程中与禁忌搜索算法结合,添加新的参数负信息素来记忆已经访问过的客户。同时,使用局部信息素更新和全局信息素更新相结合的信息素更新方式,并且全局信息素更新添加了动态更新的新模式。使用2-opt搜索对结果进行进一步的探索,扩大搜索的范围,增加了得到最优解的概率。 展开更多

关键词 cvrp 蚁群算法 禁忌搜索 2-opt

在线阅读 下载PDF 职称材料

求解CVRP的改进蚁群系统算法 被引量：3

7

作者 陈亮 周晶晶 《军事交通学院学报》 2014年第5期92-94,95,共4页

针对基本蚁群算法在求解CVRP时收敛速度慢、求解质量不高的缺点,提出了一种改进的蚁群系统算法求解CVRP,该算法引入基于DT策略的候选列表,以提高构建路径的质量,在每次迭代中加入GIIM算子,增强局部搜索能力。实验结果表明,改进的蚁群系... 针对基本蚁群算法在求解CVRP时收敛速度慢、求解质量不高的缺点,提出了一种改进的蚁群系统算法求解CVRP,该算法引入基于DT策略的候选列表,以提高构建路径的质量,在每次迭代中加入GIIM算子,增强局部搜索能力。实验结果表明,改进的蚁群系统算法在收敛能力和收敛速度方面都较基本蚁群算法更有优势。 展开更多

关键词 车辆路径规划问题 cvrp 蚁群算法

在线阅读 下载PDF 职称材料

基于多态变异的单亲遗传算法解CVRP问题

8

作者 陈肖莉 谭代伦 《洛阳师范学院学报》 2024年第8期13-17,26,共6页

针对遗传算法求解带容量约束的车辆路径规划问题(CVRP)时存在收敛速度慢、易早熟等问题,提出一种基于多态变异的单亲遗传算法(PM-PGA).将多种算子分组构成局部搜索、整体搜索和随机移动三种策略,使种群发生多态变异,增强种群多样性,提... 针对遗传算法求解带容量约束的车辆路径规划问题(CVRP)时存在收敛速度慢、易早熟等问题,提出一种基于多态变异的单亲遗传算法(PM-PGA).将多种算子分组构成局部搜索、整体搜索和随机移动三种策略,使种群发生多态变异,增强种群多样性,提高寻优能力;采用个体浓度控制和Metropolis准则相结合的混合跳跃策略,避免陷入局部最优;为提高解的质量,设计了基于迭代次数和车辆超载量的自适应罚函数.选取CVRP问题算例进行仿真实验,结果表明PM-PGA算法在收敛速度和求解精度方面得到明显改善和增强. 展开更多

关键词 cvrp问题 单亲遗传算法 多态变异 个体浓度 METROPOLIS准则

在线阅读 下载PDF 职称材料

面向不同目标偏好的CVRP多目标模型及其求解方法

9

作者 王超 金淳 韩庆平 《计算机应用研究》 CSCD 北大核心 2016年第8期2270-2274,共5页

为了更有效地求解车辆路径问题、全方位地评估物流运输成本,提出了面向不同目标偏好的车载能力约束车辆路径问题的多目标优化模型(MOCVRPFDTP),其包括三种不同的偏好结构:装载与CVRP联合优化、绝对最小车辆数偏好及路径优化偏好。为了... 为了更有效地求解车辆路径问题、全方位地评估物流运输成本,提出了面向不同目标偏好的车载能力约束车辆路径问题的多目标优化模型(MOCVRPFDTP),其包括三种不同的偏好结构:装载与CVRP联合优化、绝对最小车辆数偏好及路径优化偏好。为了求解该模型,设计了算法架构及具体算法。在实验中,该模型及其求解方法对CVRP国际标准算例VRPLIB的测试结果显示了令人满意的性能,并且它更适用于实际CVRP问题的求解。 展开更多

关键词 车载能力约束车辆路径问题 多目标优化 启发式算法 联合优化偏好

在线阅读 下载PDF 职称材料

一种求解CVRP的动态图转换模型 被引量：2

10

作者 王扬 陈智斌 《计算机工程与科学》 CSCD 北大核心 2023年第5期859-868,共10页

带容量的车辆路径问题是组合最优化问题中的经典问题,多年以来一直被反复研究。最近,Transformer已经成为解决车辆路径问题的主流深度学习架构。然而,由于一个实例在模型不同构造步骤中会发生改变,相应的节点特征也需要更新,传统位置编... 带容量的车辆路径问题是组合最优化问题中的经典问题,多年以来一直被反复研究。最近,Transformer已经成为解决车辆路径问题的主流深度学习架构。然而,由于一个实例在模型不同构造步骤中会发生改变,相应的节点特征也需要更新,传统位置编码方法不适用于提取动态优化问题的位置信息。因此,现有方法在提高学习效率方面效果较差。以最小化路径长度为目标,提出一种动态图转换模型(DGTM)和动态位置编码(DPE)方法,并使用一种双重损失REINFORCE算法训练DGTM模型。此外,强化学习、图神经网络和Transformer架构相结合,提高了模型的训练效率,增强了神经网络对带约束路径问题信息的表征能力。实验结果表明,DGTM模型在此问题上的优化效果超越了目前基于深度强化学习的方法和部分传统算法,整体性能优于专业求解器的,且具有较好的泛化性能,为求解图上组合最优化问题提供了一种有效方法。 展开更多

关键词 带容量的车辆路径问题 动态图转换模型 动态位置编码 深度强化学习 图神经网络 组合最优化问题

在线阅读 下载PDF 职称材料

针对CVRP的2-OPT算法的时间复杂度均值分析 被引量：2

11

作者 祝崇隽 刘民 +1 位作者 吴澄 吴晓冰 《清华大学学报（自然科学版）》 EI CAS CSCD 北大核心 2002年第9期1218-1221,共4页

分析了需求不可分割带能力约束的车辆路径问题(CVRP)的 2 - OPT算法计算时间的平均复杂度。利用需求分布独立于客户的空间分布的特点 ,将车辆路径问题 (VRP)转化为多旅行商 (MTSP)问题 ,并通过分析 MTSP进行 2 -OPT操作的可行性条件 ,... 分析了需求不可分割带能力约束的车辆路径问题(CVRP)的 2 - OPT算法计算时间的平均复杂度。利用需求分布独立于客户的空间分布的特点 ,将车辆路径问题 (VRP)转化为多旅行商 (MTSP)问题 ,并通过分析 MTSP进行 2 -OPT操作的可行性条件 ,建立起该算法运行所需的迭代次数的分布函数 ,进而求得平均运算时间复杂度的上界。该文为有效评价针对 VRP的 2 - OPT算法 ,提供了理论依据 ,并为VRP领域的启发式算法的复杂度分析 ,提供了一种新思路。 展开更多

关键词 cvrp 2-OPT算法 时间复杂度 均值分析 迭代次数 分布函数 车辆路径问题 能力约束 组合优化

原文传递

核中心驱动混合蛙跳算法及其应用 被引量：6

12

作者 刘立群 顾任远 《计算机科学与探索》 CSCD 北大核心 2022年第5期1169-1181,共13页

针对混合蛙跳算法(SFLA)青蛙个体当前位置提供的惯性以及跳跃步长引起的进化速度慢,易陷入局部收敛的缺陷,将青蛙个体跳跃进化行为定义为量子力学行为,提出一种核中心驱动混合蛙跳算法(NCSFLA)。在全局寻优中,以原子核为中心的同心圆作... 针对混合蛙跳算法(SFLA)青蛙个体当前位置提供的惯性以及跳跃步长引起的进化速度慢,易陷入局部收敛的缺陷,将青蛙个体跳跃进化行为定义为量子力学行为,提出一种核中心驱动混合蛙跳算法(NCSFLA)。在全局寻优中,以原子核为中心的同心圆作为电子轨道构成青蛙族群;在局部寻优中,分别以跃迁步长为半径向局部最优个体跳跃,以驱动步长为半径向全局最优个体跳跃,随机产生不重复的青蛙个体分量等三种不同的局部搜索策略对族群内最差个体进行更新。以电子轨道中心即局部最优个体为跃迁的惯性指导,使得族群内的收敛更加有利于寻找局部最优解,提升搜索能力;如果陷入局部最优,则以原子核中心即全局最优个体为驱动的惯性指导,使得青蛙个体尽可能聚集在原子核中心周围,从而加快收敛速度。将该算法应用于解决容量限制车辆路径问题(CVRP),提出一种核中心驱动混合蛙跳算法的容量限制车辆路径优化算法(NCSFLA-CVRP)。实验结果显示,在单峰值、多峰值函数以及复合函数等20个测试函数上,改进后的核中心驱动混合蛙跳算法相比其他五种算法具有收敛速度快、精度高的特点。Solomon算例标准测试数据测试结果表明该方法可有效提高容量限制车辆路径的优化性能。 展开更多

关键词 混合蛙跳算法(SFLA) 核中心 轨道中心 驱动策略 容量限制车辆路径问题(cvrp)

在线阅读 下载PDF 职称材料

基于最近邻居选择、信息素动态更新和局部启发搜索的蚁群算法 被引量：1

13

作者 王则林 罗永平 陆建德 《南通大学学报（自然科学版）》 CAS 2006年第4期71-76,共6页

文章使用最近邻居选择、信息素动态更新和局部启发搜索法对MMAS算法进行优化,得出NDLACO算法.此算法运用于解CVRP问题时,取得了较好的效果.在关于参数值的问题上取得了一定的成效,也有效地解决了蚁群算法的收敛过快和早熟、停滞问题.

关键词 蚁群算法 NDLACO cvrp

在线阅读 下载PDF 职称材料

基于容量约束的城市共同配送路线优化 被引量：2

14

作者 马秀丽 《物流技术》 2017年第6期137-140,共4页

在城市共同配送中,对配送路线进行优化十分重要。介绍了CVRP模型以及城市共同配送的路线优化方法,着重分析了节约里程法的原理和计算步骤,最后通过实例,描述了不同优化方法的应用,并选出了最优的方法。

关键词 cvrp模型 城市共同配送 路线优化

在线阅读 下载PDF 职称材料

蚁群优化算法NDLACO

15

作者 任善全 吕强 +1 位作者 钱培德 杨季文 《计算机应用与软件》 CSCD 北大核心 2007年第3期159-162,共4页

ACO算法在解NP-hard问题上虽然取得了广泛应用,但在解同一类型的不同问题时,需要更改α,β,ρ等参数的值才能取得相应问题的最优解或更接近最优解的解。通过使用最近邻居选择、信息素动态更新和局部启发搜索法对MMAS算法进行优化,得出ND... ACO算法在解NP-hard问题上虽然取得了广泛应用,但在解同一类型的不同问题时,需要更改α,β,ρ等参数的值才能取得相应问题的最优解或更接近最优解的解。通过使用最近邻居选择、信息素动态更新和局部启发搜索法对MMAS算法进行优化,得出NDLACO算法。此算法运用于解CVRP问题时,取得了较好的效果。在关于参数值的问题上取得了一定的成效,也有效地解决了蚁群算法的收敛过快和早熟、停滞问题。 展开更多

关键词 蚁群算法 NDLACO cvrp

在线阅读 下载PDF 职称材料

一种基于图神经网络的改进邻域搜索算法 被引量：4

16

作者 伍康 夏维 王子源 《计算机应用研究》 CSCD 北大核心 2024年第5期1402-1408,共7页

近年来图神经网络与深度强化学习的发展为组合优化问题的求解提供了新的方法。当前此类方法大多未考虑到算法参数学习问题,为解决该问题,基于图注意力网络设计了一种智能优化模型。该模型对大量问题数据进行学习,自动构建邻域搜索算子... 近年来图神经网络与深度强化学习的发展为组合优化问题的求解提供了新的方法。当前此类方法大多未考虑到算法参数学习问题,为解决该问题,基于图注意力网络设计了一种智能优化模型。该模型对大量问题数据进行学习,自动构建邻域搜索算子与序列破坏终止符,并使用强化学习训练模型参数。在标准算例集上测试模型并进行三组不同实验。实验结果表明,该模型学习出的邻域搜索算子具备较强的寻优能力和收敛性,同时显著降低了训练占用显存。该模型能够在较短时间内求解包含数百节点的CVRP问题,并具有一定的扩展潜力。 展开更多

关键词 组合优化 cvrp 邻域搜索 图注意力网络 深度强化学习

在线阅读 下载PDF 职称材料

带容量约束车辆路由问题的改进蚁群算法 被引量：15

17

作者 王沛栋 唐功友 李扬 《控制与决策》 EI CSCD 北大核心 2012年第11期1633-1638,1643,共7页

提出一种带容量约束车辆路由问题(CVRPs)的改进蚁群算法.该算法使用一种新的蚂蚁位置初始化方式,增加了蚂蚁走出最优路径的可能性.在搜索过程中,以客户之间路径的节省量作为启发式信息.信息素更新采用一种动态更新的方法,能够根据当前... 提出一种带容量约束车辆路由问题(CVRPs)的改进蚁群算法.该算法使用一种新的蚂蚁位置初始化方式,增加了蚂蚁走出最优路径的可能性.在搜索过程中,以客户之间路径的节省量作为启发式信息.信息素更新采用一种动态更新的方法,能够根据当前车辆所构建路径的情况对信息素进行更新,避免算法陷入停滞状态.局部搜索除使用2-opt方法外,针对不同车辆访问的客户,还增加了交换搜索和插入搜索以扩大搜索范围.仿真实验验证了所提出算法的有效性. 展开更多

关键词 车辆路由 路径规划 蚁群算法 带容量约束车辆路由问题

原文传递

改进蚁群算法求解带容量限制的车辆路径问题 被引量：3

18

作者 徐泽峰 蔡延光 《自动化与信息工程》 2016年第4期19-23,共5页

对蚁群算法进行改进以增加其在处理带容量限制的车辆路径问题时的性能。改进后的算法建立每一个点的临近点序列以增加生成解的质量并减少计算时间。设定一个信息素最小值,避免算法由于部分边上信息素值过低而被忽略。在计算选择概率时... 对蚁群算法进行改进以增加其在处理带容量限制的车辆路径问题时的性能。改进后的算法建立每一个点的临近点序列以增加生成解的质量并减少计算时间。设定一个信息素最小值,避免算法由于部分边上信息素值过低而被忽略。在计算选择概率时将所有边全部减小一个相同的值,以增加边长在决定选择时的作用。增加一只记忆蚂蚁来增强算法的收敛能力,令蚂蚁在前进过程中有可能回到出发点,通过这种方法让算法具有检索所有解的可能。在算法的最后加入对解的调整操作,进一步靠近全局最优解。用该算法计算通用的VRP算例,验证了算法的有效性。 展开更多

关键词 cvrp 蚁群算法 临近点序列

在线阅读 下载PDF 职称材料

带容量约束的多车调度暂态混沌神经网络算法 被引量：4

19

作者 孙华丽 谢剑英 薛耀锋 《上海交通大学学报》 EI CAS CSCD 北大核心 2006年第7期1148-1151,共4页

带容量约束的多车调度问题是典型的NP-hard问题,利用模糊C均值聚类算法的相似性分类原理及混沌神经网络的全局搜索能力和高搜索效率,提出了一种快速且易于实现的新的混合启发式算法.该算法分为用模糊C均值聚类算法将所有客户按车容量要... 带容量约束的多车调度问题是典型的NP-hard问题,利用模糊C均值聚类算法的相似性分类原理及混沌神经网络的全局搜索能力和高搜索效率,提出了一种快速且易于实现的新的混合启发式算法.该算法分为用模糊C均值聚类算法将所有客户按车容量要求装车和用暂态混沌神经网络方法对每条路线排序两个阶段.实例计算以及与其他算法比较表明,该算法是一种求解多车调度问题的可行且高效的方法. 展开更多

关键词 车辆调度 模糊C均值聚类 暂态混沌神经网络 混合优化算法

在线阅读 下载PDF 职称材料

一体化炼钢炉次计划模型与算法 被引量：2

20

作者 董红宇 黄敏 +1 位作者 王兴伟 郑秉霖 《系统仿真学报》 CAS CSCD 北大核心 2009年第15期4801-4805,共5页

根据一体化钢铁生产模式需求,考虑客户需求柔性化的特点,首先描述炉次计划及其一体化工艺约束,然后建立了多目标一体化炉次计划优化模型,针对模型设计了两阶段启发式算法,第一阶段提出了基于规则的分组策略,第二阶段提出了概率匹配法。... 根据一体化钢铁生产模式需求,考虑客户需求柔性化的特点,首先描述炉次计划及其一体化工艺约束,然后建立了多目标一体化炉次计划优化模型,针对模型设计了两阶段启发式算法,第一阶段提出了基于规则的分组策略,第二阶段提出了概率匹配法。最后,对比分析两阶段启发式算法与人工编制方法处理某钢厂实际生产数据结果表明,所提出的模型和算法具有良好的有效性。 展开更多

关键词 炉次计划 两阶段启发式算法 概率匹配法 柔性 能力车辆路径问题

原文传递