知识卡片
VRPTW求解方法分六类
带时间窗车辆路径(VRPTW)的求解方法按 Taillard 等的分类有六类:
| 类别 | 做法 | 书中例子 |
|---|---|---|
| 分枝界限精确法 | 搜索并证明精确最优 | Kolen,仅 6–15 个节点 |
| 途程建构启发式 | 按选点或排线规则把需求点逐个插入路线 | 循序插入法 |
| 途程改善启发式 | 先有可行初始路线,反复改善到不能再改 | 节线交换、K-Optimal |
| 合成启发式 | 建构后接改善 | 平行插入加路线改善 |
| 依据最佳化的启发式 | 借数学规划把问题分解为指派、分群、排程等子问题 | 混合整数规划模块 |
| 元启发式 | 允许跳出局部最佳的通用框架 | 禁忌搜索、模拟退火、遗传算法、门槛接受法 |
精确法能证明小规模问题的最优性,但规模受限;大规模应用通常要在可行解构造、局部改进与更广搜索之间取舍,具体选择仍依问题规模和约束而定。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 3 . 3 . 2 基 于 雨 滴 算 法 的 混 合 时 间 窗 车 辆 路 径 问 题 · 查看原书依据
由于VRPTW比VRP问题多考虑了时间窗的因素,因此在解法上较VRP问题更为复杂,而根据Taillard等的分类,求解VRPTW的方法可以分为6种。 (1)基于分枝界限法的精确解法(Exact Algorithm Based on Branch-and-Bound Techniques)。
参考来源
- 位置:《智能算法导论》第 13 章《1 3 . 3 . 2 基 于 雨 滴 算 法 的 混 合 时 间 窗 车 辆 路 径 问 题》(源文件:`_epub-src/EPUB/xhtml/chapter13_0004.xhtml`)
- 结论依据:原文逐项定义六类方法,并用分枝定界举例说明节点规模有限;分类来自 Taillard 的方法归类。
- 原始内容:根据Taillard等的分类,求解VRPTW的方法可以分为6种。