混合分散搜索算法求解带容量约束车辆路径问题 被引量：14

1

作者 张晓楠 范厚明 《控制与决策》 EI CSCD 北大核心 2015年第11期1937-1944,共8页

设计一种解决带容量约束车辆路径问题的混合分散搜索算法.在基本分散搜索的基础上,保留参考集更新策略和组合策略的全局搜索能力.采用随机插入法作为解的多样性产生方法,以扩大搜索空间,避免陷入局部最优.应用简化的变邻域搜索作为改进... 设计一种解决带容量约束车辆路径问题的混合分散搜索算法.在基本分散搜索的基础上,保留参考集更新策略和组合策略的全局搜索能力.采用随机插入法作为解的多样性产生方法,以扩大搜索空间,避免陷入局部最优.应用简化的变邻域搜索作为改进策略进行局部开发,引入邻域半径减少策略提高开发效率.对改进后的新种群实施精英保留策略,保证算法收敛.实验结果分析表明,混合分散搜索算法优于所对比的算法,寻优能力可靠. 展开更多

关键词 带容量约束车辆路径问题 随机插入法 分散搜索 变邻域搜索

原文传递

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

2

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

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

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

下载PDF 职称材料

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

3

作者 辜勇 刘迪 《东北大学学报（自然科学版）》 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 职称材料

改进混合萤火虫算法求解CVRP

4

作者 白雪媛 张磊 +1 位作者 李琳 武文喆 《计算机技术与发展》 2023年第12期207-214,共8页

提出一种改进混合萤火虫算法(KM-HFA)来解决带容量约束的车辆路径问题。该算法利用K-Means聚类方法将客户集先进行分类,再构建初始解,以较好的初始解开始萤火虫算法的寻优过程,减少了算法的计算量。在萤火虫算法中引入部分匹配交叉算子,... 提出一种改进混合萤火虫算法(KM-HFA)来解决带容量约束的车辆路径问题。该算法利用K-Means聚类方法将客户集先进行分类,再构建初始解,以较好的初始解开始萤火虫算法的寻优过程,减少了算法的计算量。在萤火虫算法中引入部分匹配交叉算子,2H-opt交换算子,局部搜索算子和变异算子,这些方法加快了算法的收敛速度,提高了萤火虫算法跳出局部最优的能力。选取小规模及中规模数据集进行仿真实验,共94组标准算例。对于79组实例,KM-HFA得到的解优于对照的混合萤火虫算法和CC-CVRP所得的求解方案,KM-HFA所求方案的车辆行驶总距离更小。KM-HFA计算了5组小规模实例,即A-n33-k6,A-n37-k6,P-n16-k8,P-n19-k2和P-n20-k2,在不增加车辆配送路径数目的情况下,得到比经典解更好的配送方案。对于实例P-n22-k8和P-n23-k8,文中算法在比经典解路径数增加了一条的前提下,找到了车辆行驶总距离更小的解。仿真实验结果表明KM-HFA具有较好的稳定性和有效性。 展开更多

关键词 带容量约束车辆路径问题 改进混合萤火虫算法 K-MEANS聚类 局部搜索算子 交叉和变异算子

下载PDF 职称材料

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

5

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

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

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

下载PDF 职称材料

求解随机旅行时间的C-VRP问题的混合遗传算法 被引量：13

6

作者 李锋 魏莹 《系统管理学报》 CSSCI 2014年第6期819-825,831,共8页

现实中,行驶在道路上的车辆由于车流量等因素导致车辆通过时间随着时间的变化而波动较大。因此,标准车辆路径问题中关于车辆在道路上的行驶速度或通过时间恒定的假设前提通常不能得到满足。以标准的带容量约束的车辆路径问题为基准,研... 现实中,行驶在道路上的车辆由于车流量等因素导致车辆通过时间随着时间的变化而波动较大。因此,标准车辆路径问题中关于车辆在道路上的行驶速度或通过时间恒定的假设前提通常不能得到满足。以标准的带容量约束的车辆路径问题为基准,研究当道路的通过时间随着时间的变化而变化,并综合考虑行驶距离、行驶时间等多项目标下车队的最佳路线安排。为了求解所提出的扩展问题,设计了一个模拟退火与遗传算法相结合的多目标混合遗传算法,用于计算得到研究问题的最优Pareto集合。通过对多个基准问题的算法测试,验证了算法的有效性。 展开更多

关键词 带容量约束的车辆路径问题 随机旅行时间 遗传算法 模拟退火 多目标

下载PDF 职称材料

求解CVRP问题的改进和声算法 被引量：7

7

作者 颜腾威 王丽侠 +1 位作者 周杰 王基一 《计算机技术与发展》 2016年第9期187-191,共5页

车辆路径问题是典型的NP难解问题,大多用启发式算法求解。和声搜索算法是一种新颖的启发式算法,最近几年得到了迅速发展,但是新提出的和声算法在求解车辆路径问题方面研究并不充分。针对现有的和声算法在求解车辆路径问题(CVRP)效率上... 车辆路径问题是典型的NP难解问题,大多用启发式算法求解。和声搜索算法是一种新颖的启发式算法,最近几年得到了迅速发展,但是新提出的和声算法在求解车辆路径问题方面研究并不充分。针对现有的和声算法在求解车辆路径问题(CVRP)效率上的不足,提出了面向CVRP问题的改进的和声算法,对带有容量限制的CVRP,提出了一种改进的和声搜索算法。该算法采用自然数编码,在新和声的生成过程中,对和声音调的生成策略进行了改进,增加了和声约束,避免了不可行解的生成,并利用2-opt算子对新的和声进行了优化,从而压缩了搜索空间,提高了搜索效率。实验结果表明,算法的效率优于现有的CVRP求解算法。 展开更多

关键词 车辆路径优化问题 容量约束的车辆路径问题 和声算法 组合优化

下载PDF 职称材料

聚类蚁群混合算法求解CVRP

8

作者 何通尧 李琳 郑学东 《沈阳航空航天大学学报》 2024年第1期90-96,共7页

针对带容量约束的车辆路径问题,提出了一种聚类蚁群混合算法,将车辆路径问题拆分成数个旅行商问题进行求解。首先,改进了蚁群算法中信息素和路径的生成方式,使其能够对车辆路径问题进行有效的拆分求解;然后通过对种群进行分级,加快了蚁... 针对带容量约束的车辆路径问题,提出了一种聚类蚁群混合算法,将车辆路径问题拆分成数个旅行商问题进行求解。首先,改进了蚁群算法中信息素和路径的生成方式,使其能够对车辆路径问题进行有效的拆分求解;然后通过对种群进行分级,加快了蚁群算法的收敛速度,并设置3种邻域搜索算子来避免蚁群算法陷入局部最优;最后,设计了仿真实验对算法的部分参数进行合理设计,选取50个Solomon基准算例对算法进行实验验证。实验结果表明,算法收敛速度快,稳定性较高,求解结果较好。 展开更多

关键词 带容量约束的车辆路径问题 聚类分析 改进蚁群算法 信息素 邻域搜索

下载PDF 职称材料

一种基于CVRP的改进蚁群算法 被引量：3

9

作者 王书勤 黄茜 《甘肃科技》 2011年第3期23-26,共4页

针对有容量约束的车辆路径优化问题(Capacity Vehicle Routing Problem,CVRP)的特点,提出了一种改进的蚁群算法。算法中,首先让蚂蚁找到需求量满足要求的客户点集,再在选定的客户集中以选择概率选择客户点,改变了基本蚁群算法的信息素... 针对有容量约束的车辆路径优化问题(Capacity Vehicle Routing Problem,CVRP)的特点,提出了一种改进的蚁群算法。算法中,首先让蚂蚁找到需求量满足要求的客户点集,再在选定的客户集中以选择概率选择客户点,改变了基本蚁群算法的信息素更新规则,限定了路线上信息素的浓度,调整了蚂蚁的选择概率,动态改变了算法主要参数等,从而优化了其搜索解的能力和收敛速度,实例仿真证明了改进的蚁群算法对小规模CVRP的解决是有效的。 展开更多

关键词 蚁群算法 有容量约束的车辆路径问题 信息素 优化

下载PDF 职称材料

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

10

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

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

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

下载PDF 职称材料

RSB-CWS算法解决CVRP问题

11

作者 晁晓菲 韩安 《价值工程》 2012年第20期221-222,共2页

RSB-CWS算法结合了蒙特卡洛模拟和CWS节省算法,利用蒙特卡洛模拟对CWS算法节省列表中顾客对间的边进行模拟,模拟过程中采用基于类几何分布的直接抽样方法进行路径采样。对模拟得到的边序列应用CWS算法,所得解的质量能达到或者优于当前... RSB-CWS算法结合了蒙特卡洛模拟和CWS节省算法,利用蒙特卡洛模拟对CWS算法节省列表中顾客对间的边进行模拟,模拟过程中采用基于类几何分布的直接抽样方法进行路径采样。对模拟得到的边序列应用CWS算法,所得解的质量能达到或者优于当前最优解.与其他CVRP问题算法相比具有高效、高质量的特点,且可以解决规模较大的CVRP问题。 展开更多

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

下载PDF 职称材料