多车场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的框架为现有优化方法改进提供了一种有益借鉴。

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

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

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

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

一种求解多车型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,并且具有一定的实用价值。