知识卡片

普通读书笔记卡 · 3772.a.1

VRPTW求解方法分六类

理解等级:中级

带时间窗车辆路径(VRPTW)的求解方法按 Taillard 等的分类有六类:

类别 做法 书中例子
分枝界限精确法 搜索并证明精确最优 Kolen,仅 6–15 个节点
途程建构启发式 按选点或排线规则把需求点逐个插入路线 循序插入法
途程改善启发式 先有可行初始路线,反复改善到不能再改 节线交换、K-Optimal
合成启发式 建构后接改善 平行插入加路线改善
依据最佳化的启发式 借数学规划把问题分解为指派、分群、排程等子问题 混合整数规划模块
元启发式 允许跳出局部最佳的通用框架 禁忌搜索、模拟退火、遗传算法、门槛接受法

精确法能证明小规模问题的最优性,但规模受限;大规模应用通常要在可行解构造、局部改进与更广搜索之间取舍,具体选择仍依问题规模和约束而定。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 13 章《1 3 . 3 . 2 基 于 雨 滴 算 法 的 混 合 时 间 窗 车 辆 路 径 问 题》(源文件:`_epub-src/EPUB/xhtml/chapter13_0004.xhtml`) - 结论依据:原文逐项定义六类方法,并用分枝定界举例说明节点规模有限;分类来自 Taillard 的方法归类。 - 原始内容:根据Taillard等的分类,求解VRPTW的方法可以分为6种。