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

1

作者 方伟 朱建阳 《控制与决策》 EI CSCD 北大核心 2023年第12期3571-3577,共7页

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

关键词 限量弧路由问题 组合优化 分治策略 大规模优化 路径切割 自适应

原文传递

考虑人车混采的道路信息采集的路径规划研究 被引量：2

2

作者 许保光 常嘉欣 高敏刚 《中国管理科学》 CSSCI CSCD 北大核心 2022年第4期218-227,共10页

本文考虑了道路信息外业采集的任务要求,人车混采的采集方式以及路网特性等方面,为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型;提出了分阶段的转化算法,将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCAR... 本文考虑了道路信息外业采集的任务要求,人车混采的采集方式以及路网特性等方面,为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型;提出了分阶段的转化算法,将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCARP问题是一种NP-hard问题,精确求解算法无法在合理时间内得到问题的最优解,因此本文设计了求解TCARP问题的两种快速启发式算法TPS和TUH及其随机化版本;考虑到实际采集问题的大规模特性,在两种快速启发式算法的基础上构造GRASP-PA寻优算法。最后分别结合不同规模的基准算例和实际采集算例证明了本文所构造的算法的有效性。 展开更多

关键词 时间容量限制 弧路径优化 道路信息采集 启发式算法

原文传递

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

3

作者 孙锡梅 林丹 黄庆伟 《计算机应用》 CSCD 北大核心 2013年第A01期62-65,共4页

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

关键词 带容量约束弧路径问题 同时配送和回收 启发式算法 变邻域搜索 混合局部搜索 分层搜索

下载PDF 职称材料

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

4

作者 张炜 王原 +1 位作者 何永明 邢立宁 《中国管理科学》 CSSCI 北大核心 2015年第S1期137-142,共6页

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

关键词 分割算法 弧路径规划问题 先排序后聚类方法 多标号算法

原文传递

基于进化计算的多车场洒水车路径优化问题求解 被引量：1

5

作者 李小花 朱征宇 夏梦霜 《交通与计算机》 2008年第3期55-59,64,共6页

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

关键词 进化计算 多车场 带有容量限制的弧路径规划问题

下载PDF 职称材料

CARP问题的构造型启发式算法研究 被引量：1

6

作者 李庆华 林丹 《河南师范大学学报（自然科学版）》 CAS CSCD 北大核心 2011年第3期148-152,共5页

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

关键词 CARP问题 构造型启发式算法 综述

下载PDF 职称材料

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

7

作者 林丹 梁桉洋 《天津理工大学学报》 2015年第3期59-64,共6页

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

关键词 容量约束弧路径问题 组合优化 进化算法 局部搜索

下载PDF 职称材料

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

8

作者 张卫星 林丹 《数学的实践与认识》 CSCD 北大核心 2012年第18期168-175,共8页

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

关键词 带有车容限制的弧路径规划问题 油耗 遗传算法 车辆运输 服务成本 优化目标

原文传递

大城市邮政投递问题及其算法探讨 被引量：6

9

作者 忻展红 《北京邮电大学学报》 EI CAS CSCD 1994年第3期50-55,共6页

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

关键词 邮递员问题 车辆运行问题 算法

下载PDF 职称材料

多车场CARP问题的改进遗传算法求解 被引量：4

10

作者 李小花 朱征宇 夏梦霜 《计算机工程与应用》 CSCD 北大核心 2009年第11期230-234,共5页

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

关键词 多车场 带有容量限制的弧路径规划问题 遗传算法 模拟退火算法

下载PDF 职称材料

洒水车作业路线规划的复杂CARP问题求解 被引量：2

11

作者 朱征宇 谢志华 +2 位作者 杨永 夏梦霜 李小花 《计算机应用》 CSCD 北大核心 2008年第3期768-772,共5页

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

关键词 复杂容量限制弦路径车辆行驶问题 多车型 高性能遗传算法 重优化

下载PDF 职称材料

一种求解多车型CARP的有效memetic算法 被引量：4

12

作者 张玉州 刘晓飞 +1 位作者 黄师化 梅俊 《中国科学技术大学学报》 CAS CSCD 北大核心 2017年第7期583-593,共11页

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

关键词 限量弧路由问题 多车型 MEMETIC算法 同档路径交换车辆

下载PDF 职称材料

求解CARP-RP-ML问题的改进算法 被引量：3

13

作者 胡珊 林丹 《计算机工程》 CAS CSCD 2012年第7期168-170,共3页

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

关键词 容量约束弧路径问题 组合优化 启发式算法 遗传算法 适应值 局部搜索

下载PDF 职称材料

带有异质固定车队的能力约束弧路径问题 被引量：3

14

作者 刘天堂 江志斌 +2 位作者 耿娜 刘冉 刘树军 《上海交通大学学报》 EI CAS CSCD 北大核心 2012年第11期1759-1763,共5页

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

关键词 能力约束弧路径问题 异质固定车队 启发式算法 加强的局域搜索

下载PDF 职称材料

求解UCARPP问题的变邻域搜索算法 被引量：3

15

作者 金倩倩 林丹 《计算机工程》 CAS CSCD 2012年第21期290-292,F0003,共4页

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

关键词 带有收益有容量限制的弧路径问题 变邻域搜索算法 局部搜索 分割算法 邻域结构 旋轮法

下载PDF 职称材料

基于进化计算的洒水车路径优化问题的求解 被引量：1

16

作者 邓欣 朱征宇 +1 位作者 杨永 曾凡超 《计算机工程与应用》 CSCD 北大核心 2007年第26期212-216,共5页

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

关键词 容量限制弦路径车辆行驶问题 进化计算 局部搜索

下载PDF 职称材料

求解双层CARP优化问题的演化学习型遗传算法 被引量：2

17

作者 邢立宁 姚锋 《系统工程与电子技术》 EI CSCD 北大核心 2012年第6期1187-1192,共6页

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

关键词 组合优化 有能力约束的弧路径优化问题 演化学习型遗传算法

下载PDF 职称材料

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

18

作者 刘天堂 江志斌 +1 位作者 胡鸿韬 刘冉 《上海交通大学学报》 EI CAS CSCD 北大核心 2013年第4期619-625,共7页

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

关键词 能力约束弧路径问题 元启发式算法 混合遗传算法 二元锦标赛替代

下载PDF 职称材料

求解CARPSD问题的自适应局部搜索算法 被引量：2

19

作者 王立斌 林丹 《计算机工程》 CAS CSCD 2013年第2期211-215,共5页

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

关键词 带有容量限制的弧路径规划问题 局部搜索 随机路径扫描 自适应性 随机需求 权重

下载PDF 职称材料