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

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

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

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

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

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

深度强化学习求解车辆路径问题的研究综述

车辆路径问题在物流配送优化系统中起着至关重要的作用。如何有效地寻求最佳的路径,也已经成为当今研究的热点话题。常见的车辆路径问题包含有容量限制的车辆路径问题、带时间窗的车辆路径问题、多车场车辆路径问题以及其他车辆路径问题。随着学者们的不断挖掘以及社会的不断发展,其他类型的车辆路径问题也逐渐进入大众视野,其中包括绿色车辆路径问题、电动车辆路径问题等。本文回顾每一类问题下应用深度强化学习方法求解车辆路径问题的研究文献,对深度强化学习的方法和模型进行描述和总结,评价其优缺点,最后对求解基于深度强化学习的车辆路径问题的未来研究方向进行展望。

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

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

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

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

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

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

基于多目标模拟退火的带容量限制车辆路径问题

车辆路径问题是运筹学中著名的NP问题。带容量限制的车辆路径问题作为最基本的车辆路径问题,其研究对其它类型的车辆路径问题具有重要的借鉴作用。论文首先从物流企业和客户两个不同的角度考察4个优化目标,将带容量限制的车辆路径问题推广到高维多目标领域。然后运用基于Pareto支配接受准则的多目标模拟退火算法在单数组和多数组两种不同的编码方式下进行求解,并通过实验分析对比两种编码方式的优劣。在9个Augerat数据集上的实验结果表明,单数组编码方式在IGD和HV指标下不如多数组编码方式。单数组编码方式得到的Pareto解集具有更好的多样性,而多数组编码方式得到的Pareto解集具有更好的收敛性。

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

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

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

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

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

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

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

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

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

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

距离受限车辆路径问题的近似算法

针对无向完全图上以极小化行驶路线(环游)总距离为目标函数的距离受限车辆路径问题,将最小二元2-匹配问题与环游拆分和环游整合相结合,提出了一种近似算法。该算法将松弛问题最小二元2-匹配的最优解中距离超过限制的环游进行拆分,距离未超过限制的环游进行整合,以得到距离受限车辆路径问题的环游集合。针对该近似算法,首先通过分析该问题最优解下界与近似算法的上界,证明了算法参数形式的近似比上界;然后通过对近似比上界的证明,说明最大行驶距离与顾客点规模的取值对算法参数近似比的影响较小;最后通过构造实例,进一步说明该算法在此种情况下性能更优。该算法可为城市无人物流配送高效快速算法的设计提供参考。

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

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

单车场多送货点车辆路径问题的改进遗传算法

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

蚁群优化算法下农村生鲜配送车辆路径对比研究

近几年,美团优选、多多买菜等生鲜电商涌入农村市场,开始针对性地解决农村生鲜物流配送的“最后一公里”的难题。文章通过引入生鲜电商的“社区团购”配送模式,综合考虑农村用户的商品需求量、生鲜商品送达用户时的鲜活度、商品履约率、容量受限开放式路径规划配送车辆等因素,以总配送成本最小为目标构建开放式带时间窗容量受限车辆路径优化模型,利用蚁群优化算法对该模式求解。通过算法求解的结果表明:在农村生鲜产品配送中,开放式容量受限车辆路径规划,能有效地降低农村生鲜物流配送的总成本,缩短车辆行驶距离,提高商品履约率。

绿色车辆路径问题的改进拉格朗日松弛算法

针对绿色带容量的车辆路径问题(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的高质量解。

基于遗传算法的车辆路径问题研究

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

基于改进双种群混合遗传算法的车辆路径问题研究

针对传统遗传算法求解带容量约束的车辆路径问题,存在早熟收敛、易陷入局部最优等问题,设计了双种群混合遗传算法。种群I在传统遗传算法中引入模拟退火思想及变邻域搜索策略,增强算法局部搜索性能。种群II在迭代过程中,通过设定阈值判断当种群达到早熟收敛状态时,利用"移民策略"植入外部个体,达到增加种群多样性、增强算法全局搜索和开发的能力。每次迭代完成后采用"移民算子"进行种群间的信息交流。最近邻插入方法在算法迭代结束之后对求解所得最好解的各子路径进行再优化。算例验证分析可知,所提算法计算结果同算例给出的最好解之间的偏差均在-1.00%以内,求解质量优于所有对比的算法,表明所提算法能有效解决容量约束的车辆路径问题,具有可靠的全局稳定性。