知识卡片
时间窗让车辆路线同时受排程约束
VRPTW(带时间窗的车辆路径问题)在车辆路线之外,为顾客服务加入最早开始时间与最晚期限;场站也可能受时间窗限制,因此路径选择同时变成排程问题。评价方案时,运输成本之外还要考虑时间成本与未按窗送达的处罚,单看里程会漏掉准时性约束。
示例(补充教学示例,非书中数据):顾客要求 9:00–11:00 送达。路线地理上更短、但 8:30 到达,须等待到 9:00 才服务;若 11:30 才到,则计入违约处罚。另一条略长的路若 10:00 到达,总巡航成本可能反而更低。场站若 18:00 关门,过长路线即使顾客窗都满足也可能不可行。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 3 . 3 . 2 基 于 雨 滴 算 法 的 混 合 时 间 窗 车 辆 路 径 问 题 · 查看原书依据
VRPTW必须额外考虑运送时间与时间窗口,其主要的原因来自顾客有服务时间的最后期限和最早开始服务时间的限制。故在此限制条件之下,原本VRP问题除了空间方面的路径(Routing)考虑之外,还必须要加上时间上的排程(Scheduling)考虑,同时由于场站也有时间窗的限制,也间接造成路径长度的限制,由此可知VRPTW的总巡航成本不仅包含运送成本,还需要考虑时间成本,以及未在时间窗限制内送达的处罚成本。
参考来源
- 位置:《智能算法导论》第 13 章《1 3 . 3 . 2 基 于 雨 滴 算 法 的 混 合 时 间 窗 车 辆 路 径 问 题》(源文件:`_epub-src/EPUB/xhtml/chapter13_0004.xhtml`)
- 结论依据:原文将时间窗拆为最早服务与最后期限,指出场站限制会影响路径长度,并把运输、时间和违约处罚都纳入巡航成本。9:00–11:00 的等待/处罚对照是补充教学示例,非书中数据。
- 原始内容:VRPTW必须额外考虑运送时间与时间窗口,其主要的原因来自顾客有服务时间的最后期限和最早开始服务时间的限制。