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

研究高速路网日常维护中的养护车辆路径优化问题,考虑车辆养护服务时间和移动时间的不确定性,通过科学的规划手段和精确有效的决策方法,可以减少以前依赖人工决策导致的资源浪费。将问题定义为一个带随机时间变量的限容量弧路径规划问题,分别使用机会约束规划模型和带修正的随机规划模型进行描述。针对问题的随机性,提出自适应大规模邻域搜索算法,在优化过程中根据各个删除策略和插入策略对解的表现对其进行评分,根据轮盘赌原则自适应地选择删除策略和插入策略。与分支切割算法进行比较,解的差距只有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式路径规划方法的有效性,研究结果可为智能化作业路径规划研究提供参考。

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

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

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问题,为实际应用奠定了基础。

求解CARPSD问题的自适应局部搜索算法

针对带有随机需求的弧路径规划问题,提出一种自适应局部搜索算法。采用随机路径扫描算法产生初始种群,选出最优者作为初始解,以自适应的方式进行局部搜索,并设计2种局部搜索机制。实验结果表明,与自适应大邻域搜索算法相比,该算法的最优解得到改进,运行时间平均缩短60%。

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

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

基于先排序后聚类原则下解决CARP问题的分割算法

弧路径规划问题(CARP)是物流科学研究的热点问题之一。CARP问题可以通过转换为路径规划问题(CVRP)问题来进行求解,将CARP的弧段等效于CVRP问题的点进行处理,具体求解过程中可以使用先排序后聚类(RFCS)方法,先对所有弧段当做节点来处理进行(TSP)排序,运用分割算法将完整的TSP回路,分割为多条满足背包限制的TSP路径,形成优化方案。本研究提出了一种全新的分割算法-多标号算法,在完整TSP回路的基础上得到较优的满足背包限制的TSP路径。并通过对标准问题库中问题与几种使用较为普遍的分割算法进行对比试验,数据验证结果显示多标号算法较之于其他分割算法有更好的分割效率,并通过结合蚁群算法验证了多标号算法在RFCS方式解决CARP问题中具有较好的性能与应用前景。