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

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

洒水车作业路线规划的复杂CARP问题求解

作为容量限制弦路径车辆行驶问题(CARP)的一种实际应用,洒水车路线规划涉及多车型、多路型、转弯限制等因素,属于复杂的CARP问题。对此,提出了一种高性能遗传算法(HEGA),以传统遗传算法为基础,对种群机制和染色体结构及交叉操作进行改进,并引入局部搜索(LS)操作增强算法的寻优能力。根据真实数据进行实验,获得了比人工更优的解决方案。最后的对比实验验证了算法具有较高的求解精度。

求解双层CARP优化问题的演化学习型遗传算法

双层有能力约束的弧路径优化问题(capacitated arc routing problem,CARP)的研究对象通常是某个城市或地区,首先聚焦于该地物流系统的宏观配置,然后考虑相关服务的完成问题。针对双层CARP优化问题,提出了一种演化学习型遗传算法(learnable genetic algorithm,LGA)。建立了LGA的基本框架,设计了构件知识和算子知识等知识形式。在LGA中,采用扩展启发式方法辅助生成初始种群,使用算子知识为选择、交叉和变异选择操作算子,应用构件知识为交叉和变异操作选择断点位置,同时借助局部替换程序不断地向当前种群中注入新个体。LGA的框架为现有优化方法改进提供了一种有益借鉴。

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

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

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

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

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

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

CARP问题的构造型启发式算法研究

全面综述了国内外用于求解容量约束弧路径问题(CARP问题)的构造型启发式算法的研究现状,指出了构造型启发式算法与元启发式算法相比而言的优点所在.将求解算法分为3类并且分别进行简要介绍,最后展望了构造型启发式算法的研究前景.

一种求解多车型CARP的有效memetic算法

鉴于多车型限量弧路由问题(heterogeneous vehicle capacitated arc routing problem,HVCARP)广泛的应用,研究了其优化模型及求解算法.首先将HVCARP的路径费用分为可变费用和固定费用,通过车辆惩罚系数将车型和路径紧密相连,形成费用计算公式.针对HVCARP的特点,提出了一种针对车型的同档路径交换车辆算子,该算子根据路径负载以及车队情况,调整服务车型,以实现服务费用的最优化;然后以其为局部搜索算子,设计了用于求解HVCARP的memetic算法;最后,以CARP标准测试集的修改算例进行实验验证,实验结果表明,基于同档路径交换车辆算子memetic算法是有效的.

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

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

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

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

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

在利用进化计算对容量限制弦路径车辆行驶问题(Capacitated Arc Routing Problem,CARP)进行研究的基础上,对其数学模型、可行化算子进行改进,以适应实际生活中洒水车车辆路径优化问题。针对此问题,设计了局部搜索(Local Search)算子,此算子在染色体进化中有着显著的作用。来自于现实生活中的某市政环卫部门的实验数据真实可靠。通过进化计算对数据的求解,不仅得到了满意的结果,而且证明了该算法的可靠性及稳定性。在把计算后得出的优化路径用于实际洒水车线路安排后,其环卫部门节约了一定的人力物力,取得了一定的经济效益。根据实验分析,该算法能有效求解一定规模的CARP,并且具有一定的实用价值。

大城市邮政投递问题及其算法探讨

对大城市邮政投递问题进行了描述，给出了单局多投递路段优化数学模型，并提出了分解算法，把原问题分解为有容约束弧路由和装箱二个子问题。对有容约束弧路由问题提出了随机回路点扫描法，同时给出了联合二个子问题求解原问题次最优解的策略。

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

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

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

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

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

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

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

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

Crossover Iterated Local Search for SDCARP

This paper introduces a new algorithm based on local search for the capacitated arc routing problem(CARP)and the split-delivery capacitated arc routing problem(SDCARP).We present a intermediate model to transfer CARP to SDCARP and then solve the two problems by an algorithm which combines the iterated local search and the memetic algorithm.We use crossovers to perform fully reproducible initializations in each local search iteration and edge-marking to save computation time.The computational results on 63 instances of standard benchmarks show that the proposed algorithm outperforms most of the existing best-known solutions obtained by other heuristics within a reasonable computing time.Furthermore,compared with the CARP solutions,our algorithm finds three optimums for the SDCARP.

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

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

洗扫车路径规划问题及求解算法

洗扫车路径规划问题是一类容量约束弧路径问题(CARP),具有NP-hard性质。为了提升求解CARP的能力,本文提出一种模拟退火算法与混合遗传算法的结合算法,简称为模拟退火混合遗传算法(SAHGA)。该算法在混合遗传算法中的局部搜索操作之后加入模拟退火算法的思想,在一定程度上优化了算法在洗扫车优化调度中求解能力。同时改进算法中的选择算法,使用更加有效的锦标赛算法。使用标准CARP算例集进行了测试,并给出了改进算法与传统混合遗传算法和其他启发式算法的效果比较。结果表明,SAHGA改进效果明显,是有效的求解CARP的方法。使用算法对杭州电子科技大学周边街道的洗扫车规划问题进行求解,验证了算法的可靠性。

基于路径切割和自适应检测的大规模限量弧路由问题求解

大规模限量弧路由问题(large scale capacitated arc routing problem,LSCARP)是一个组合优化问题,应用广泛,采用分治策略是解决LSCARP的有效方法之一.首先,为了利用分治策略取得更优的分解结果,提出改进路径切割算子来求解LSCARP,其能够自动识别路径集合中形态较差的路径并对其有针对性地进行切割,从而在迭代中通过将切割后的路径进行重组以获得更优的分解,有利于算法跳出局部最优取得更小的最终费用;然后,针对LSCARP的结构会影响算法最终效果的问题,设计一种自适应数据集检测算子,其能够根据LSCARP中任务边与非任务边的关系来进行参数分配从而提高分解质量;最后,将以上2个算子应用于SHAiD算法,并与当前主流相关算法进行对比.实验结果表明了所提出算法的有效性.