← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3738.g

大规模CARP搜索空间指数增长

理解等级:中级

限量弧路由问题(CARP):容量为 Q 的车辆从车库出发,为图中每条需要服务的边或弧(任务)恰好服务一次后回到车库,每条路线的消耗不得超过 Q,目标是总消耗最小。

任务越多,任务的分配和服务顺序组合越多,解空间随规模呈指数增长;任务数很大时称为大规模 CARP(LSCARP),车辆路径规划中这种情况很常见。精确求解已不现实,元启发式算法能在给定时间内找到次优解,但计算量大、耗时更长。模因算法加入局部改进,可帮助跳出局部最优、得到更好的解,但仍要按问题规模权衡解的质量与计算预算。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 3 . 4 基 于 M e m e t i c 算 法 的 限 量 弧 路 由 问 题 · 查看原书依据

      3.4 基于Memetic算法的限量弧路由问题 3.4 基于Memetic算法的限量弧路由问题 在对CARP求最优解的过程中,随着问题规模的增加,解空间的规模会成指数增长,所以又有了大规模的限量弧路由问题(Large-Scale Capacitated Arc Routing Problem,LSCARP)。在车辆路径规划这一问题中,通常任务数目都比较多。

    参考来源

    - 位置:《智能算法导论》第 3 章“基于 Memetic 算法的限量弧路由问题”(源文件:`_epub-src/EPUB/xhtml/chapter3_0009.xhtml`)。 - 结论依据:原文说明问题规模增大使解空间指数增长,并指出元启发式可在给定时间内取得次优解但计算成本较高;继而引出模因算法改善局部搜索。 - 原始内容:随着问题规模的增加,解空间的规模会成指数增长,所以又有了大规模的限量弧路由问题(Large-Scale Capacitated Arc Routing Problem,LSCARP)。