知识卡片
大规模路由可先分任务再搜索
限量弧路由问题(CARP):若干辆有容量上限的车从车库出发,为图中所有需要服务的边(“任务”,如要清扫的街道)各服务一次后返回,目标是总消耗最小。任务一多,可选方案急剧增加,就成了大规模 CARP。
RDG-MAENS 的做法分两步:
- 用路由距离分组(RDG)把整个任务集合分成多个小任务集。
- 对每个小任务集,各自独立运行 MAENS(在模因算法框架里加入扩展步长邻域搜索的方法)求解。
分组让每次搜索只面对少量任务,范围变小;代价是跨组的车辆容量、路线衔接与总体目标仍需单独核对。本节只概述策略,没有给出完整算法和效果边界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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独立处理每个子任务集合。