← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3739.b.1

分治拆解大规模路由问题

理解等级:中级

大规模限量弧路由问题(LSCARP)指待服务任务很多的车辆弧路由问题,解空间随规模指数增长,整体搜索代价太高。RDG-MAENS 采用分治策略:

  1. 分解:按路由距离分组(RDG)把任务拆成多个子问题。
  2. 求解:对每个子问题分别求解。
  3. 合成:由各子问题的解拼出完整方案。

拆分把一次大搜索变成多次小搜索,于是“怎么分”和“怎么合”成了设计重点。原书提到的后续改进 IRDG-MAENS,针对的正是 RDG-MAENS 把个体分配到子种群的方式不合理,改进后收敛性明显提高。分组方法见 [[按路由距离聚类任务]],子问题解的共享见 [[子问题好解应即时共享]]。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 3 章“基于 Memetic 算法的限量弧路由问题”(源文件:`_epub-src/EPUB/xhtml/chapter3_0009.xhtml`)。 - 结论依据:原文将 RDG-MAENS 的分治流程概括为拆分子问题、分别求解并由子题解构成完整解。 - 原始内容:为了解决LSCARP,2014年提出的RDG-MAENS采用了一种分治策略 [ 3 0 - 3 1 ] ,把问题分解成很多子问题,分别予以解决,然后再由子问题的解得到完整的解。