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

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

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

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

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

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

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

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

求解带容量约束车辆路径问题的离散布谷鸟算法

提出一种离散布谷鸟算法(DCA)求解带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem)。该算法采用轮盘赌机制增强初始解选择的随机性,对基本布谷鸟算法的莱维飞行操作中,使用2-opt法和exchange法进行位置更新;在寄生巢位置更新中,使用shift法和reverse法增强最优解的局部开发能力。选取augerat标准数据集测试算法,并比较BA、ACO、SA及PSO算法结果。实验结果表明:离散布谷鸟算法能够有效解决带容量约束车辆路径问题,有较强的寻优能力,求解质量优于其他4种对比算法。

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

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

基于改进蚁群算法的带容量约束车辆路径问题求解

随着市场经济快速发展和现代技术的不断演变,现代物流业也得到了空前的发展。在物流配送活动的各个环节中,配送路径优化对企业提高服务质量、降低物流成本、提高经济效益起到至关重要的作用。蚁群优化算法作为群智能算法的典型代表,在路径规划求解中表现出良好的效果。本文研究了带容量约束车辆路径问题(Capacitated Vehicle Routing Problem,CVRP),并采用蚁群优化算法进行优化求解。实验结果表明,蚁群优化算法能够有效地求解带容量约束车辆路径问题。

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

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

求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法

针对带容量约束的车辆路径问题,提出一种混合变邻域生物共栖搜索算法.设计基于客户点优先序列及车辆参考点模拟信息的有序编码,该编码方案使生物共栖搜索算法可以参与CVRP的离散优化;为了提高算法的全局搜索能力,根据有序编码特点构造3种共栖搜索算子,扩大搜索空间;同时,结合变邻域搜索算法设计客户点重置、交换和2-OPT三种局部搜索策略,以提高解方案质量.算例验证分析表明,所提算法能够有效地解决容量约束车辆路径问题,求解质量优于所对比算法,具有可靠的全局稳定性.

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

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

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

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

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

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

基于遗传算法的带时间约束的车辆路径问题优化

基于遗传算法的车辆路径优化问题,虽然已经被提出过多种思想方法,但仍有较大的改进余地.而且具体的车辆路径优化问题,往往在时间和路程两方面都有限制和要求,而在这方面的研究相对较少.针对这种问题,在传统遗传计算基础上,加入了时间约束算法,对算法的实时实现作出保证;同时根据客户点的位置改进初始群,提高了变异率,减少低效计算,极大提高了寻优速度,为多计算点的遗传操作提供有力的支持.计算机仿真实现的结果和物流公司的实际运作都证明了算法的有效性.

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

针对多车场带时间窗车辆路径问题(MDVRPTW),提出一种改良自适应大邻域搜索算法(IALNS)。首先,在构造初始解阶段改进一种路径分割算法;其次,在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子,为各算子引入评分机制,采用轮盘赌方式选取启发式算子;同时,将迭代周期分段,动态调整各周期内的算子权重信息,有效避免算法陷入局部最优;最后,采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验,确定IALNS的相关参数,将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明,所提算法与变邻域搜索(VNS)算法的求解误差不超过0.8%,在某些算例上甚至更优;与多相位改进的蛙跳算法相比,算法的平均耗时减少12.8%,所提算法在绝大多数算例上运行时间更短。因此,验证了所提算法是求解MDVRPTW的有效算法。

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

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

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

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

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

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

求解带能力约束车辆路径优化问题的改进模拟退火算法

为高效求解带能力约束的车辆路径优化问题,提出一种带有回火操作的改进模拟退火算法。解析多约束条件下的路径优化特点,构建了结构简单且功能模块相对独立的模拟退火框架,以便相关约束及其算法的耦合嵌套。在此基础上,改变较优解在迭代过程中的接受规则,引入回火操作使全局搜索与局部搜索实现平衡;设计强制的随机邻域变换策略,以提高多约束条件下的新解生成质量。结合初始解生成方法,构建了整体算法。通过不同类型算例的对比实验表明,所提算法具有优越的求解性能,相应的求解框架与优化方法研究,能够为相关的多约束耦合求解提供参考。

基于改进的禁忌搜索算法求解带2维装箱约束的低碳车辆路径问题

同时考虑2维装箱和车辆路径2个NP难问题,以碳排放量为目标函数,对低碳环境下带2维装箱约束的车辆路径问题进行研究.求解思路是以禁忌搜索算法(Tabu Search,TS)为主要框架,然后基于贪心的思想采用4种启发式装箱策略生成初始解,并通过改进编码解码方式以及使用动态增长的禁忌长度对TS算法进行改进;由给出算例的计算结果可知,改进的禁忌搜索算法对于求解该类问题具有一定的优越性.

容量约束的车辆路径问题研究现状综述

带有容量约束的车辆路径问题(CVRP)是车辆路径(VRP)衍生问题的一种。为了理清国内外研究现状,对CVRP发表文献进行检索和归纳,总结CVRP基本类型和CVRP衍生问题。通过对CVRP的研究现状和求解方法的总结和分析,展望CVRP未来的研究趋势,并为交通运输、物流配送领域的学者提供一些见解和启示。