带有异质固定车队的能力约束弧路径问题

研究了带有异质固定车队的能力约束弧路径问题(CARP).为了在可接受时间里求得较理想的解,提出了基于Route-First,Cluster-Second思想的两阶段启发式算法,并使用局域搜索(LS)和加强的局域搜索(ELS)进行改善.基于标准CARP算例生成了HFFCARP测试数据,算法结果表明了LS和ELS的有效性,且ELS具有更好的效果.

加强的混合遗传算法求解能力约束弧路径问题

为了在可接受的时间里求解具有NP-hard性质的能力约束弧路径问题(CARP),提出了加强的混合遗传算法(EHGA).该算法是在遗传算法框架里嵌入加强的局域搜索算子来强化搜索,充分发挥了遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力.同时,在进行种群替代时,二元锦标赛替代被提出,并使用了种群管理来保持种群的多样性.测试了标准CARP算例,并给出了算法效果比较.结果表明,加强的混合遗传算法胜出一般的Memetic算法,是有效的求解CARP的方法.

城市垃圾收集车辆弧路径问题研究

考虑部分街道单行及转向限制等状况,采用带有转向禁忌条件的垃圾收集车辆弧路径问题模型对城市垃圾收运路线进行优化.通过建立将其转换为对应的点路径问题的求解模型以减少问题规模,并利用一种聚类蚁群算法对该问题进行求解.实例优化结果表明,有、无转向约束的路线优化后,总路程分别减少了89 984.96 m和92 330.04 m,分别节约了31.1%和31.9%.优化效果明显.此外,优化后减少了需求车辆数,减少了车辆使用成本和人员雇佣成本.

多起始点进化算法在容量约束弧路径问题上的应用

容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.

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

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

带转向约束的城市垃圾收集车辆弧路径问题研究

考虑部分街道单行及转向限制等状况,采用带有转向禁忌条件的垃圾收集车辆弧路径问题模型对城市垃圾收运路线进行优化。建立将其转换为对应的点路径问题的求解模型,以减少问题规模;并使用聚类蚁群算法对该问题进行求解。成都市双楠辖区的实例优化结果表明,有/无转向约束的路线优化后,总路程分别减少了89984.96 m和92 330.04 m,节约了31.1%和31.9%。效果明显。此外,优化后减少了需求车辆数,减少了车辆使用成本和人员雇佣成本。

道路养护中的带随机时间变量的弧路径规划问题

研究高速路网日常维护中的养护车辆路径优化问题,考虑车辆养护服务时间和移动时间的不确定性,通过科学的规划手段和精确有效的决策方法,可以减少以前依赖人工决策导致的资源浪费。将问题定义为一个带随机时间变量的限容量弧路径规划问题,分别使用机会约束规划模型和带修正的随机规划模型进行描述。针对问题的随机性,提出自适应大规模邻域搜索算法,在优化过程中根据各个删除策略和插入策略对解的表现对其进行评分,根据轮盘赌原则自适应地选择删除策略和插入策略。与分支切割算法进行比较,解的差距只有1.45%~3.15%,但计算时间有显著提升,证明了自适应大规模邻域搜索算法的有效性,能够适用于中大规模问题。通过真实路网算例,显示了带修正的随机规划模型在特定情况下相对于机会约束规划模型的优越性。还对置信水平α和变异系数CV这2个重要变量进行了敏感性分析,显示了其对解的影响程度。

考虑倒伏与粮仓容积的再生稻头季机收路径规划

为提升机具作业效率和质量、减少土壤碾压等,该研究提出一种同时考虑作物倒伏状态、碾压面积和收获机粮仓容积的路径规划算法(harvester grain bin capacitated arc routing problem,HGBCARP)。该算法由作业信息处理模块和作业路径规划模块组成,作业信息处理模块将农田边界、卸粮点位置、作物倒伏方向及面积、位置等信息转化成可处理的数据形式并传输给路径规划模块,然后由路径规划模块进行作业行方向划分、作业行遍历顺序寻优、转弯方式生成、碾压面积计算等,最终得到最优路径规划结果。采用改进遗传算法,分别以3种再生稻收获机、2种传统水稻收获机和3种不同田块为对象,以行驶路径长度、碾压面积、收获粮食量为评价指标,采用回转式收获路径和HGBCARP式收获路径规划开展对比试验。结果表明,HGBCARP式比回转式收获路径碾压面积每公顷减少11.79%~27.20%,可使倒伏的机收头季稻增收1.64%~1.95%;同时在3种不同田块条件下进行仿真试验,HGBCARP式比回转式收获路径可使碾压面积每公顷减少7.25%~20.09%。使用电动无人履带式底盘对不同收获路径进行田间模拟收获试验,HGBCARP式收获路径与传统牛耕往复式及回转式收获路径相比,碾压面积减少约11.21%~28.03%,在路径长度减少约6.81%~23.46%,验证了HGBCARP式路径规划方法的有效性,研究结果可为智能化作业路径规划研究提供参考。

多次需求的特殊路段限容量弧路径问题研究

限容量弧路径问题在城市生活当中具有一定的普遍性,引起广泛的关注。本文所关注的焦点是针对CARP问题的一种拓展问题:考虑了特殊路段的多次需求情况下的路径优化问题。首先提出了此类问题的背景和意义,然后针对该问题中的容量约束和需求次数两个方面进行了分析,最后建立模型,并用模拟退火算法进行求解,然后对结果进行分析。

基于油耗的带有车容限制弧路径问题的模型及优化

提出了一种基于油耗的带有车容限制的弧路径问题(Capacitated Arc RoutingProblem,CARP),建立了以降低油耗为目标的问题模型,构造了相应的遗传算法.基于标准测试问题,同传统以距离为优化目标的遗传算法求得的油耗进行比较,实验结果表明,此算法可以快速、有效的求得以油耗为优化目标的CARP问题的优化解,为实际中降低车辆运输服务成本提供了较好方案.

基于免疫拉马克的道路洒水车路径问题优化

高效节能地完成道路洒水作业对改善城市环境、节约资源有着非常重要的意义.将道路洒水车路径问题转化为带容量约束的弧路径优化问题,并建立相应的数学模型.根据问题的NP难特性,提出了一种拉马克免疫算法进行求解.算法有效利用了免疫算法全局优化和拉马克学习局部搜索的优势;设计了适合问题求解的锦标赛选择法、顺序交叉法、自适应变异等免疫算子,并设计了拉马克局部搜索策略,避免算法陷入局部最优.实验结果表明,所提算法能得到代价最小的洒水路径.

基于进化计算的多车场洒水车路径优化问题求解

在利用进化计算对多车场带有容量限制的弧路径规划问题(multiple depot capacitated arcrouting problem,MDCARP)进行研究的基础上,对其数学模型进行改进,以适应现实生活中洒水车路径优化问题的需要。针对此问题,将传统遗传算法的种群结构进行改进,采用有效的种群初始化策略并设计出新颖且高效的进化算子,通过进化计算对数据的求解,得到了满意的结果,从而证明了该算法能解决一定规模的MDCARP问题。

考虑容量限制的弧路径优化研究综述

弧路径优化问题作为经典的组合优化问题,在近40年内受到广泛关注,并产生了大量的研究成果.基于此,从问题、算法和应用三个角度对考虑容量限制的弧路径优化问题(capacitated arc routing problem,CARP)的研究现状进行综述.首先,基于问题特征对问题进行分类并介绍其常见数学模型.其次,综述求解CARP的精确算法、构造启发式算法及元启发式算法,并根据基准算例求解结果对比算法效果.再者,归纳垃圾回收、道路管理等CARP常见应用场景.最后,展望未来研究发展方向.

社区疫情防控的消杀作业路径优化问题研究

针对社区疫情防控的消杀作业路径优化问题,设计了一种基于模拟退火算法的启发式算法.首先,提出用于面型消杀任务的作业工艺,建立了问题的整数规划模型;然后,针对问题特点开发了基于模拟退火算法的启发式算法,使用一种可以根据问题规模改变解空间大小的解结构,设计了多种类型的解更新操作,利用Floyd算法计算优化目标值,通过Metropolis准则接受新解.多规模对比计算实验表明:所提出的模拟退火算法在小规模算例的平均求解结果与精确解相差在4%以内,在中规模算例的求解结果比CPLEX平均优化10%~40%,在大规模算例的求解结果比贪婪算法平均优化60%~80%,因此当求解此类问题时该算法能在合理的时间内取得较优的结果.

求解CARP-RP-ML问题的改进算法

传统方法无法有效求解交通道路维护运作中的有补给点及多装载的容量约束弧路径(CARP-RP-ML)问题。为此,提出改进的启发式算法和遗传算法。启发式算法将不同的分割算法用于由所有需求弧随机排序得到的个体上,构造问题的可行解;遗传算法利用分割算法计算其个体适应值,确定对应的可行车辆路径及补给位置,并用局部搜索作为变异算子,进一步扩大搜索空间。数值实验结果表明,与启发式算法相比,遗传算法能更有效地求解CARP-RP-ML问题。

求解UCARPP问题的变邻域搜索算法

针对无向网络中带有收益值有容限的弧路径问题,提出一种变邻域搜索算法。生成需求边的有序列,以相同概率初始化每条边的方向,采用分割算法构造初始解,运用6种邻域结构进行广域搜索,使用局部搜索算法改进解,利用旋轮法选择邻域结构。实验结果表明,该算法能提高效率,避免早期陷入局部最优,稳定性较好。

多约束条件下城市道路环卫车优化配置与路径规划

为有效解决当前城市环卫车调度决策过度依赖人工主观经验造成的车辆配置不合理和作业效率低下问题,本文提出一种多约束条件下的城市道路环卫车优化配置与路径规划方法。通过综合考虑环卫车在现实作业中的作业时限、服务次数、行驶速度和车辆退出节点等多种约束条件,将物理道路网络拓展为时空网络,刻画车辆在路网上的时空运行轨迹,进而将环卫车优化配置与路径规划问题从数学上描述为带多类约束条件的弧路径问题(Arc Routing Problem, ARP)。在此基础上,构建以车辆配置与出行总成本最小化为目标函数的环卫车优化配置与路径规划模型,并通过设计分支定价算法精确求解模型。将所提方法应用于苏州工业园区19个区域路网的环卫车辆配置与调度管理,从经济成本、作业效率和环保效益这3方面评估所提方法的可行性和有效性。结果表明:本文所提方法能够显著节约环卫运营成本,提升环卫车辆作业效率;同时,可有效降低环卫车辆碳排放量,形成良好的经济和社会效益,为智慧环卫提供了行之有效的新方案。

CARP问题的小环路启发式求解方法

弧路径规划问题(Arc Routing Problem,ARP)来源于回收垃圾,清洒街道,扫雪以及投递邮件等实际问题.CARP是车辆带有容积限制的ARP问题.本文研究了CARP与CVRP的转换,并提出了一种小环路方法来求解CARP.该方法先将CARP中所有弧分割为不同区域,每个区域会形成一个小环路,从而转换为CVRP问题进行求解.然后将CVRP求解结果释放为CARP的初始解,再用Tabu禁忌搜索方法进行优化.通过一个假设例子和两组标准算例的求解,结果验证了该算法的求解效率和精度,并为实际应用奠定了基础.

求解CARP车场选址问题的混合随机搜索算法

针对环保车车场选址问题,提出了一种混合随机搜索算法(HRSA)。新算法利用当车场已知时计算环保车优化行使路线的CARP算法作为车场选址评估函数,为加快收敛速度采用改进的Dijkstra算法计算初始车场地址,进而采用一种局部搜索策略寻找当前车场附近的更优地址,同时为避免陷入局部最优采用一种随机跳变策略探测其他更优地址,实现对解空间的高效搜索。在洒水车车场选址问题上的实验表明,HRSA求解此类问题是有效的。

多车场CARP问题的改进遗传算法求解

带有容量限制的弧路径规划问题来源于城市垃圾回收、街道清扫、邮件投递、校车路线安排和洒水车路线安排等实际问题,多车场CARP问题是具有多个车场的CARP问题。提出了一种先划分区域后进行路径规划的方法来求解多车场CARP问题。该方法先将各服务弧按照离车场距离的远近归并到距离最近的车场,从而转化为单车场CARP问题,然后用改进的遗传算法进行求解;在求解过程中,用模拟退火算法对部分服务弧进行局部调整,使服务弧在一定的范围内在不同的车场之间进行调换,从而避免局部收敛,达到全局优化的效果。以洒水车路线安排为实例,实验结果表明,该算法能有效求解一定规模的多车场CARP问题,为实际应用奠定了基础。