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

1

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

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

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

原文传递

基于混合人工蜂群算法的容量约束车辆路径优化

2

作者 李阳 谷雯雯 《供应链管理》 2025年第4期97-112,共16页

针对容量约束车辆路径问题,文章构建了以路径成本最低为目标的混合整数规划模型,结合模型及CVRP问题特征设计了混合启发式算法进行求解。混合启发式算法集合人工蜂群算法及变邻域搜索算法,在人工蜂群局部搜索环节嵌入多变邻域算子展开迭... 针对容量约束车辆路径问题,文章构建了以路径成本最低为目标的混合整数规划模型,结合模型及CVRP问题特征设计了混合启发式算法进行求解。混合启发式算法集合人工蜂群算法及变邻域搜索算法,在人工蜂群局部搜索环节嵌入多变邻域算子展开迭代,算子中包含对路径节点、字符串及子路径的针对性变换操作,保证蜂群种群多样性,设计侦察蜂变邻域算子扰动策略强化算法跳出局部最优的能力。文献算例集及其算法求解的对比分析表明,混合变邻域人工蜂群算法参数及局部搜索策略设置合理有效,全局搜索能力强,能求得74个算例中47个最优解,求解精度高,最优解平均最小偏差为0.34%,尤其在求解稳定性方面表现良好,平均算例集平均值偏差为0.57%,整体性能优于所对比文献算法。 展开更多

关键词 组合优化 车辆路径问题 人工蜂群算法 变邻域搜索算子 容量约束 路径优化

在线阅读 下载PDF 职称材料

一种带时间窗和容量约束的车辆路线问题及其TabuSearch算法 被引量：11

3

作者 魏明 高成修 胡润洲 《运筹与管理》 CSCD 2002年第3期49-54,共6页

本文提出一种带时间窗和容量约束的车辆路线问题 (CVRPTW ) ,并利用TabuSearch快速启式算法 ,针对Solomon提出的几个标准问题 ,快捷地得到了优良的数值结果。

关键词 时间窗 容量约束 车辆路线问题 Tabu Search算法 VRPTW 巨集启发式算法

在线阅读 下载PDF 职称材料

求解带容量约束车辆路径问题的多模态差分进化算法 被引量：5

4

作者 林剑 叶璟轩 +1 位作者 刘雯雯 邵晓雯 《计算机应用》 CSCD 北大核心 2023年第7期2248-2254,共7页

针对带容量约束车辆路径问题(CVRP)中交通拥堵、资源供给、客户需求等不确定性因素的影响容易导致单一最优解不可行或非最优的问题,提出一种多模态差分进化(MDE)算法,以同时求解得到目标值相近的多个备选车辆路径方案。首先结合CVRP的特... 针对带容量约束车辆路径问题(CVRP)中交通拥堵、资源供给、客户需求等不确定性因素的影响容易导致单一最优解不可行或非最优的问题,提出一种多模态差分进化(MDE)算法,以同时求解得到目标值相近的多个备选车辆路径方案。首先结合CVRP的特点,构建高效的解个体编解码策略,并基于修复机制提升解个体的质量;然后在差分进化(DE)算法框架下,基于多模态优化视角引入动态半径小生境生成方法,并采用杰卡德系数来度量解个体之间相似性,进而实现对于解个体之间距离的计算;最后,改进邻域搜索策略,采用精英存档和更新策略来得到多模态最优解集。基于典型数据集的仿真实验与分析结果表明,所提MDE算法寻优得到的平均最优解个数达到1.7434个,平均最优解与已知最优解的平均偏差为0.03%,而差分进化(DE)算法二者分别为0.8486和0.63%。可见,所提算法在求解CVRP上表现出较高的有效性和稳定性,能同时得到CVRP的多个近似最优解。 展开更多

关键词 车辆路径问题 多模态优化 差分进化 带容量约束 小生境

在线阅读 下载PDF 职称材料

求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法 被引量：9

5

作者 张瑾 洪莉 戴二壮 《计算机工程与科学》 CSCD 北大核心 2021年第8期1479-1487,共9页

带时间窗和容量约束的车辆路径问题是车辆路径问题重要的扩展之一,属于NP难题,精确算法的求解效率较低,且对于较大规模问题难以在有限时间内给出最优解。为了满足企业和客户快速有效的配送需求,使用智能优化算法可以在有限的时间内给出... 带时间窗和容量约束的车辆路径问题是车辆路径问题重要的扩展之一,属于NP难题,精确算法的求解效率较低,且对于较大规模问题难以在有限时间内给出最优解。为了满足企业和客户快速有效的配送需求,使用智能优化算法可以在有限的时间内给出相对较优解。研究了求解带容量和时间窗约束车辆路径问题的改进离散蝙蝠算法,为增加扰动机制,提高搜索速度和精度,在对客户点按其所在位置进行聚类的基础上,在算法中引入了变步长搜索策略和两元素优化方法进行局部搜索。仿真实验结果表明,所设计算法具有较高寻优能力和较强的实用价值。 展开更多

关键词 离散蝙蝠算法 车辆路径问题 时间窗和容量约束 变步长搜索 K-means运算

在线阅读 下载PDF 职称材料

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

6

作者 辜勇 刘迪 《东北大学学报（自然科学版）》 EI CAS CSCD 北大核心 2023年第12期1686-1695,1704,共11页

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

关键词 带容量约束车辆路径问题 子回路组合 近似解可行化 自适应混合蚁群算法 灵敏度分析

在线阅读 下载PDF 职称材料

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

7

作者 晁晓菲 杨晓龙 《价值工程》 2012年第5期16-17,共2页

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

关键词 带容量约束的车辆路径问题 物流配送 路径规划 确定算法 启发式算法

在线阅读 下载PDF 职称材料

自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题 被引量：13

8

作者 夏小云 庄鹤林 +2 位作者 杨火根 向毅 陈泽丰 《计算机集成制造系统》 EI CSCD 北大核心 2022年第11期3545-3557,共13页

为解决带容量约束的车辆路径问题(CVRP)求解时收敛能力与探索能力不足、耗时长等问题,提出一种基于大邻域搜索的人工蜂群优化算法。设计了5个移除算子和2个插入算子,采用算子区别应用机制、仔细侦查蜂机制、更新策略宽松机制优化算法。... 为解决带容量约束的车辆路径问题(CVRP)求解时收敛能力与探索能力不足、耗时长等问题,提出一种基于大邻域搜索的人工蜂群优化算法。设计了5个移除算子和2个插入算子,采用算子区别应用机制、仔细侦查蜂机制、更新策略宽松机制优化算法。所提算法能够快速搜索到可接受解,在实验数据集上能收敛到大部分已知最优解,并更新了4个已知最优精准解。实验结果表明,3种优化策略均能有效提升算法效率,算法具有较好的综合性能。 展开更多

关键词 带容量约束车辆路径问题 人工蜂群算法 自适应大邻域搜索 算子区别应用机制 宽松更新策略

在线阅读 下载PDF 职称材料

混合差分蜂群算法求解带容量约束车辆路径问题 被引量：3

9

作者 姜婷 《宜宾学院学报》 2017年第12期52-56,共5页

为求解带容量约束车辆路径问题,提出了一种差分算法改进的人工蜂群算法(DABC).针对人工蜂群算法开发能力较弱的缺陷,采用了全局最优解引导的邻域搜索策略.为避免早熟,引入差分算法的交叉更新策略进行局域优化.仿真实验结果证明,混合差... 为求解带容量约束车辆路径问题,提出了一种差分算法改进的人工蜂群算法(DABC).针对人工蜂群算法开发能力较弱的缺陷,采用了全局最优解引导的邻域搜索策略.为避免早熟,引入差分算法的交叉更新策略进行局域优化.仿真实验结果证明,混合差分蜂群算法在求解带容量约束车辆路径问题时,能较好地平衡了探索能力和开发能力,在求解速度和稳定性上有良好的效果. 展开更多

关键词 带容量约束车辆路径问题 人工蜂群算法 差分优化算法 邻域搜索策略 交叉更新策略

在线阅读 下载PDF 职称材料

求解带容量约束车辆路径问题的离散鲸鱼算法 被引量：5

10

作者 郭玉洁 张强 魏永和 《计算机与数字工程》 2021年第8期1543-1548,共6页

论文提出了一种离散鲸鱼算法求解带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem)。该算法对基本鲸鱼算法的包围捕食操作、泡泡网捕食操作、随机捕食操作进行重定义,并采用基于距离代价的K-means算法在满足车辆最大载... 论文提出了一种离散鲸鱼算法求解带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem)。该算法对基本鲸鱼算法的包围捕食操作、泡泡网捕食操作、随机捕食操作进行重定义,并采用基于距离代价的K-means算法在满足车辆最大载重约束条件下将客户划分到不同区域。并引入随机交换搜索、2-opt、3-opt优化方法对每次迭代过程中得到的最优解进行局部优化,扩大算法搜索空间算法。实验结果表明:所提算法能够有效解决带容量约束车辆路径问题,有较强的寻优能力,求解质量优于所对比算法。 展开更多

关键词 离散鲸鱼算法 容量约束车辆路径问题 K-MEANS 邻域搜索

在线阅读 下载PDF 职称材料

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

11

作者 夏茂庚 郑阳光 +2 位作者 兰延涛 王威 晁晓菲 《科学技术与工程》 北大核心 2012年第26期6849-6852,共4页

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

关键词 有容量约束的车辆路径问题 蒙特卡洛模拟 节省算法 路径规划 车辆调度

在线阅读 下载PDF 职称材料

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

12

作者 孙锡梅 林丹 黄庆伟 《计算机应用》 CSCD 北大核心 2013年第A01期62-65,共4页

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

关键词 带容量约束弧路径问题 同时配送和回收 启发式算法 变邻域搜索 混合局部搜索 分层搜索

在线阅读 下载PDF 职称材料

基于改进遗传算法求解容量约束车辆路径问题 被引量：1

13

作者 刘祥坤 李万龙 +1 位作者 李东升 牛家冰 《长春工业大学学报》 2023年第3期254-261,共8页

为克服传统遗传算法在求解容量约束路径问题时易收敛和搜索能力不足的缺点,提出了动态调参的方式对算法进行改进。首先采用局部搜索算法生成初始解,提高初始解的质量,并动态调整选择、交叉、变异操作的参数,既保留了种群多样性,又避免... 为克服传统遗传算法在求解容量约束路径问题时易收敛和搜索能力不足的缺点,提出了动态调参的方式对算法进行改进。首先采用局部搜索算法生成初始解,提高初始解的质量,并动态调整选择、交叉、变异操作的参数,既保留了种群多样性,又避免了优秀个体被破坏,最后通过变邻域搜索算法提高算法搜索能力。实验表明,所有算例实例求得的最优解误差不超1.0%,并与其他经典的启发式算法进行了比较。 展开更多

关键词 带容量车辆路径问题 遗传算法 变邻域搜索算法

在线阅读 下载PDF 职称材料

改进遗传算法在容量约束车辆路径问题中的应用研究 被引量：4

14

作者 李斌成 何国强 《供应链管理》 2020年第3期107-116,共10页

针对遗传算法求解带容量约束的车辆路径问题时,存在早熟收敛和易陷入局部最优的问题,提出了改进的遗传算法。该算法结合扫描算法思想将种群初始化进行改进,使种群从迭代之初就处于一种最优的状态,并改进了选择策略和交叉策略。通过标准... 针对遗传算法求解带容量约束的车辆路径问题时,存在早熟收敛和易陷入局部最优的问题,提出了改进的遗传算法。该算法结合扫描算法思想将种群初始化进行改进,使种群从迭代之初就处于一种最优的状态,并改进了选择策略和交叉策略。通过标准测试算例验证可知,该算法求解结果同测试算例给出的当前最优值之间的偏差在-0.24%以内,且求解结果和稳定性均由于对比算法,为求解此类问题给出了更加有效的解决方案。 展开更多

关键词 容量约束车辆路径问题 遗传算法 扫描算法 相似度 移民策略

在线阅读 下载PDF 职称材料

基于离散哈里斯鹰算法求解车辆路径问题

15

作者 郭玉洁 徐洪智 《计算机工程与设计》 北大核心 2024年第6期1764-1770,共7页

针对带容量约束车辆路径问题,提出一种离散哈里斯鹰算法。在哈里斯鹰算法的基础上,根据车辆路径的编解码特点,重新定义算法在全局搜索和局部开发阶段的更新策略;在全局搜索阶段利用随机插入和反转策略更新哈里斯鹰个体的位置,提高算法... 针对带容量约束车辆路径问题,提出一种离散哈里斯鹰算法。在哈里斯鹰算法的基础上,根据车辆路径的编解码特点,重新定义算法在全局搜索和局部开发阶段的更新策略;在全局搜索阶段利用随机插入和反转策略更新哈里斯鹰个体的位置,提高算法的全局开发能力;在局部开发阶段利用转移算子和移除算子设计哈里斯鹰个体的更新机制,提高算法的局部精细化搜索能力;通过改进逃逸能量平衡全局搜索和局部开发能力。实验结果表明,重定义的更新策略均能有效提升算法效率,将该算法和其它启发式算法的结果相比较,所提算法在求解精度和稳定性方面更具优势。 展开更多

关键词 离散哈里斯鹰算法 容量约束车辆路径问题 随机反转 插入操作 转移算子 移除算子 改进逃逸能量

在线阅读 下载PDF 职称材料

具有时间窗约束松弛的混合蚁群算法求解VRPTW

16

作者 骆维 陈仕军 吴华伟 《计算机系统应用》 2025年第2期281-291,共11页

为求解带时间窗的车辆路径问题,以最小化总行驶里程为目标建立混合整数规划模型,提出了一种具有时间窗约束松弛的混合蚁群算法.首先,提出改进的蚁群算法与“TSP-Split编码与解码”相结合的方法,来构建允许违反时间窗约束的解路径,以提... 为求解带时间窗的车辆路径问题,以最小化总行驶里程为目标建立混合整数规划模型,提出了一种具有时间窗约束松弛的混合蚁群算法.首先,提出改进的蚁群算法与“TSP-Split编码与解码”相结合的方法,来构建允许违反时间窗约束的解路径,以提高算法的全局寻优能力.然后,利用“及时返回”原则和惩罚函数方法,提出基于变邻域搜索的修复策略来修复不可行解.最后,对56个Solomon和12个Homberger基准算例进行试验计算,结果表明该算法的求解质量优于文献中的对比算法,且在50个测试实例上获得了已知最优解,其余实例也能在可接受计算时间内获得准最优解,验证了所提算法的有效性. 展开更多

关键词 蚁群算法 带时间窗的车辆路径问题(VRPTW) 时间窗约束松弛 TSP-Split 及时返回 变邻域搜索

在线阅读 下载PDF 职称材料

有时间窗的开放式车辆路径问题及其遗传算法 被引量：25

17

作者 钟石泉 杜纲 贺国光 《计算机工程与应用》 CSCD 北大核心 2006年第34期201-204,共4页

针对物流配送中的开放式车辆路径问题提出了OVRP的处理方法,并且根据容量和时间窗约束的特点设计了GA算法,设计了动态染色体,采用改进的交叉变异过程,利用随机参数的波动来协调容量约束和时间窗约束,并且加入了内部和外部扰动操作来跳... 针对物流配送中的开放式车辆路径问题提出了OVRP的处理方法,并且根据容量和时间窗约束的特点设计了GA算法,设计了动态染色体,采用改进的交叉变异过程,利用随机参数的波动来协调容量约束和时间窗约束,并且加入了内部和外部扰动操作来跳出局部收敛点。通过试验,表明用GA在优化有容量和时间窗约束的OVRP的有效性。 展开更多

关键词 开放式车辆路径问题 容量约束 时间窗约束 遗传算法

在线阅读 下载PDF 职称材料

单车场多送货点车辆路径问题的改进遗传算法 被引量：11

18

作者 屈援 汪波 钟石泉 《计算机工程与应用》 CSCD 北大核心 2007年第25期237-239,243,共4页

针对单车场多送货点容量约束的车辆路径问题提出了一种改进的遗传算法。该算法基于自然数编码的染色体,采用了改进的交叉和变异法、内部扰动和外部扰动等技术,提高了遗传算法的优化效率和优化效果。介绍了此算法的原理,给出了具有两个... 针对单车场多送货点容量约束的车辆路径问题提出了一种改进的遗传算法。该算法基于自然数编码的染色体,采用了改进的交叉和变异法、内部扰动和外部扰动等技术,提高了遗传算法的优化效率和优化效果。介绍了此算法的原理,给出了具有两个代表性算例试验结果和结果分析。试验结果表明了该改进遗传算法对求解单车场多送货点容量约束的车辆路径问题的有效性。 展开更多

关键词 车辆路径问题 遗传算法 容量约束

在线阅读 下载PDF 职称材料

绿色车辆路径问题的改进拉格朗日松弛算法 被引量：1

19

作者 徐林浩 钱斌 +1 位作者 胡蓉 于乃康 《广东工业大学学报》 CAS 2022年第5期61-67,共7页

针对绿色带容量的车辆路径问题(Green Capacitated Vehicle Routing Problem, GCVRP),建立了以最小化总运费为优化目标的混合整数规划(Mixed Integer Programming,MIP)模型,并提出一种改进拉格朗日松弛算法(Improved Lagrange Relaxatio... 针对绿色带容量的车辆路径问题(Green Capacitated Vehicle Routing Problem, GCVRP),建立了以最小化总运费为优化目标的混合整数规划(Mixed Integer Programming,MIP)模型,并提出一种改进拉格朗日松弛算法(Improved Lagrange Relaxation Algorithm, ILRA)进行求解。首先,通过拉格朗日松弛技术得到原问题的对偶问题,并运用次梯度法求解对偶问题获得原问题的下界;然后针对下界设计修复算法和邻域搜索算法获得原问题的上界,进而更新乘子迭代求解;最后进行仿真实验,实验结果表明:在相同实验环境下对19个不同规模算例进行10次测试,ILRA求取MIP的上下界平均间隙为7.61%,而Gurobi求解器求取的平均间隙为15.47%。可见,相较于Gurobi求解器,ILRA能够高效获得GCVRP的高质量解。 展开更多

关键词 绿色带容量的车辆路径问题 混合整数规划 改进拉格朗日松弛 下界

在线阅读 下载PDF 职称材料

基于遗传算法的车辆路径问题研究 被引量：1

20

作者 刘俐 《中国电子商务》 2014年第4期81-81,共1页

考虑车辆容量约束并建立数学模型，运用遗传算法求解该车辆路径问题。运用C语言编写算法程序，详细分析了遗传操作及算法参数。以某企业在天津的几家大型购物广场为例，分析了因配送问题给企业发展带来的局限性。求解出的适合该企业的... 考虑车辆容量约束并建立数学模型，运用遗传算法求解该车辆路径问题。运用C语言编写算法程序，详细分析了遗传操作及算法参数。以某企业在天津的几家大型购物广场为例，分析了因配送问题给企业发展带来的局限性。求解出的适合该企业的最优路径，与实际配送路径对比后显示出：最优路径大大缩短了车辆的总配送距离、节省了配送成本。 展开更多

关键词 车辆路径问题 容量约束 遗传算法 语言

在线阅读 下载PDF 职称材料