知识卡片

普通读书笔记卡 · 3739.b

大规模路由可先分任务再搜索

理解等级:中级

限量弧路由问题(CARP):若干辆有容量上限的车从车库出发,为图中所有需要服务的边(“任务”,如要清扫的街道)各服务一次后返回,目标是总消耗最小。任务一多,可选方案急剧增加,就成了大规模 CARP。

RDG-MAENS 的做法分两步:

  1. 用路由距离分组(RDG)把整个任务集合分成多个小任务集。
  2. 对每个小任务集,各自独立运行 MAENS(在模因算法框架里加入扩展步长邻域搜索的方法)求解。

分组让每次搜索只面对少量任务,范围变小;代价是跨组的车辆容量、路线衔接与总体目标仍需单独核对。本节只概述策略,没有给出完整算法和效果边界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 3 . 1 M e m e t i c 算 法 发 展 历 程 · 查看原书依据

      在该算法中,首先采用RDG策略将路由问题中的任务集合分为多个小的任务集,再使用MAENS独立处理每个子任务集合。并且,Memetic算法在多目标CARP的应用也越来越多,如2011年梅一等提出的D-MAENS算法[13]。

    参考来源

    - 位置:《智能算法导论》第 3 章 3.1 节“Memetic 算法发展历程”(`EPUB/xhtml/chapter3_0002.xhtml`);RDG-MAENS 段。 - 结论依据:原书描述 RDG 先分任务集,再由 MAENS 独立处理每个子集。 - 原始内容:首先采用RDG策略将路由问题中的任务集合分为多个小的任务集,再使用MAENS独立处理每个子任务集合。