汇报目录
从业务问题到可计算输入
先说明题目真正困难在哪里，再交代数据和预处理链路。
原问题不是送餐路径，而是带时间窗的资源调度
业务背景
校外骑手不能进校，外卖集中到校门，由校内配送员送到宿舍楼。
硬性时限
每单从到达校门开始，必须在 10 分钟内送达。
资源限制
配送员单次最多携带 5kg，送完后必须回校门才能继续。
优化目标
在所有订单准时送达的前提下，求全天最少配送员人数。
固定参数统一成算法约束
由 15 km/h 转换，用于距离到时间的换算。
deadline = arrival + 10。
限制单批订单数量，使小规模枚举可行。
每送达一单加上下楼固定耗时。
所有订单时间被转换为分钟数，所有路径距离统一为米，后续批次评估直接计算送达时刻和回场时刻。
前期准备：从原始订单到展示数据
解析订单编号、到达时间、重量、目标宿舍楼。
转换为 Order 对象，并生成 deadline_minute。
校门、宿舍、路口作为节点，道路距离作为边权。
输出 assignment、decision、utilization 等结构化 JSON。
离线、在线、对比三类可视化页面均可点击查看。
实验数据规模与高峰特征
订单规模
| 数据集 | 订单数 | 峰值压力 | 最少人数 |
|---|---|---|---|
| NPU Mon | 801 | 51 单 / 10 分钟 | 21 |
| NPU Tue | 785 | 36 单 / 10 分钟 | 19 |
| NPU Wed | 786 | 42 单 / 10 分钟 | 19 |
| CDUT Mon | 850 | 33 单 / 10 分钟 | 24 |
| CDUT Tue | 839 | 34 单 / 10 分钟 | 24 |
| CDUT Wed | 861 | 44 单 / 10 分钟 | 30 |
峰值压力
让路径、订单和批次都可计算
把校园地图和订单时限转化为图论模型与时间窗模型。
校园地图抽象为带权无向图
道路网络建模
- 节点表示校门、宿舍楼、道路转折点和必要连接点。
- 边表示校园内可通行道路。
- 边权表示两点之间的道路长度，单位为米。
- 右侧只是局部示意，不按完整地图节点数量绘制。
- 完整路径计算以后端建图数据为准。
Dijkstra 预处理最短路
距离表
校门到宿舍、宿舍到宿舍的最短距离被预处理保存。
路径表
最短路径的节点序列会用于前端绘制实际路线。
时间换算
travel_time = shortest_distance / 250。
复用优势
批次评估阶段只需查表，不再重复考虑路径怎么走。
为什么重要
路径层做准确之后，调度层才能专心处理“哪些订单一起送、什么时候发车、人员何时回场”。
订单对象与时间窗
dᵢ = rᵢ + 10
rᵢ
订单到达校门的分钟数。
wᵢ
订单重量，用于载重约束。
vᵢ
目标宿舍楼，用于路径计算。
dᵢ
最晚送达时间，形成时间窗约束。
批次可行性：从经验判断到安全出发区间
- 给定一个订单组合和访问顺序，计算第 i 单从出发到送达的累计耗时 cᵢ。
- 所有订单出发前必须已经到达，因此 t ≥ max(rᵢ)。
- 每单都必须在截止时间前送达，因此 t + cᵢ ≤ dᵢ。
- 若这个区间非空，则该顺序可执行；否则该顺序不可执行。
已知全天订单时，求最少可行人数
主模型：先精确判断单趟配送，再在全天时间轴上验证给定人数是否足够。
离线方案的四步结构
把校园道路转成可查表的最短路距离和路径。
判断一组订单是否满足载重、送达顺序、准时送达和回场约束。
给定配送员人数，在订单到达、人员回场等关键事件点重新决策。
不断试更少或更多的人，找到能完成全天订单的最少人数。
先把“一趟配送”算准
一趟最多考虑 4 单，因为 5kg 载重和 10 分钟时限会自然限制批次大小。
总重量超过 5kg 的组合直接排除，不进入路径计算。
对剩余组合尝试不同宿舍访问顺序，找出能准时送达的路线。
得到“最早能出发”和“最晚必须出发”的时间段。
既保留更早回场的路线，也保留时间余量更大的路线，供调度层选择。
这一层只回答一个问题：这几单能不能由同一个配送员一次送完；至于什么时候派、派谁去，由后面的全天模拟负责。
人数验证：给定人数，模拟一整天
| 系统里维护什么 | 直观含义 | 为什么需要 |
|---|---|---|
| 当前时间 | 模拟已经推进到几点 | 判断订单是否到达、是否还能继续等。 |
| 还没到的订单 | 后面才会出现在校门的订单 | 离线算法可以用它做短前瞻。 |
| 已到但未送订单 | 此刻堆在校门、等待安排的订单 | 候选批次只从这里和短前瞻可见订单中生成。 |
| 空闲配送员 | 已经在校门、能立刻出发的人 | 决定当前能不能发车。 |
| 在路上的配送员 | 每个人预计几点回到校门 | 若最早回场也赶不上急单，说明当前人数不够。 |
| 已派出批次 | 每次出发、回场、送哪些单 | 最终用于结果表和前端可视化。 |
人数验证只在关键事件点做决策
为什么不逐分钟模拟
- 两个订单到达之间，如果没有配送员回场，系统状态其实没有变化。
- 固定每分钟扫一遍会产生大量无意义判断。
- 真正需要重新计算的时刻，是订单池或可用配送员发生变化的时候。
三个关键事件
- 新订单到达：校门等待池变大，可能出现更好的拼单。
- 配送员回场：可用人手增加，可以重新派车。
- 订单快到最晚出发时刻：不能再为了拼单继续拖延。
核心机制：seed 池 + 标准池如何组批
哪些订单会成为 seed
seed 的判定逻辑
- 先计算每个订单“如果单独送，最晚几点必须从校门出发”。
- 最晚出发时间越早，说明这个订单越不能继续拖。
- 若最晚出发时间相同，再看订单截止时间、到达时间和订单编号，保证排序稳定。
- 默认每轮取前 4 个高风险订单作为 seed；兜底重试时才扩到更多。
为什么不是只看一个最急单
- 高峰期可能同时有多单接近最晚出发时刻。
- 只围绕一个最急单，会让第二、第三急的订单被普通拼单带偏。
- 多个 seed 并行扩展，可以同时保护多个风险点。
- 每个批次都包含 seed，保证局部搜索始终围绕准时风险展开。
标准池订单如何匹配当前 seed
伙伴池从哪里来
- 标准池里的 8 个次紧急订单是第一来源。
- 在离线前瞻里，未来真实到达的新单会先进入待送池，再参与 seed 和标准池重选。
- 如果局面困难，再补一部分同样紧急的订单，用来保护多个风险点。
- 再补离 seed 目的地更近的订单，提高顺路拼单机会。
- 最后按匹配得分补充最契合 seed 的订单。
匹配得分看什么
两单一起送能比各自单独送少走多少路。
两单允许出发的安全区间是否重叠。
普通订单本身是不是也快到最晚出发点。
和 seed 合起来是否接近但不超过 5kg。
什么时候扩池：本轮组批与失败重试
第一层：每个 seed 的伙伴池
- 先取 8 个次紧急订单，作为所有 seed 共用的标准池。
- 如果待送订单超过标准池，就围绕当前 seed 补充三类伙伴：同样紧急、目的地近、匹配分高。
- 补充后会重新排序，只留下最契合当前 seed 的订单。
- 常规组批最多从 8 个看到 12 个，避免漏掉标准池外更顺路的订单。
第二层：验证失败后的扩大搜索
- 如果默认参数验证失败，不能立刻认为这个人数不可行。
- 系统会再放宽一次：标准池从 8 扩到 12，seed 数量从 4 扩到 6。
- 无论哪一层扩池，每个 seed 最多只保留 14 个伙伴，防止变成全量暴力枚举。
- 因此扩池分两种：本轮组批为了找更合适的伙伴，失败重试为了降低误判不可行的风险。
如何枚举候选批次
本轮先选择一个高风险订单，后续组合都必须包含它。
从 seed 的伙伴池里再选 0、1、2、3 个普通订单。
总重量超过 5kg 的组合立即丢弃，不再试路线。
对剩下组合尝试不同宿舍访问顺序，检查每单能否准时。
多个 seed 生成的可行批次去重后，交给发车评分统一选择。
离线前瞻如何调用核心机制
不是全量搜索
- 先用当前已到订单跑一次核心组批器，得到“现在发车”的具体批次。
- 离线只看未来 3 分钟内真实会到达的新单时刻。
- 每个未来时刻只重跑一次受限的 seed + 标准池，不展开全天等待决策树。
- 因此复杂度增加的是少量试算次数，不是指数级全局搜索。
前瞻在哪里生效
- 未来新单不是给当前批次额外加分，而是先进入新的候选订单池。
- 候选池变了，seed 池、标准池、伙伴池都会重新选择。
- 未来新单可能成为 seed，也可能成为某个 seed 的标准池伙伴。
- 最后比较的是“现在发车批次”和“未来重组批次”两个具体方案。
当前批次和未来批次如何比较
先过资格线
- 比较对象都是具体批次，不是单个订单，也不是抽象的分数奖励。
- 未来批次必须仍然满足不超过 5kg、10 分钟送达和回场可行性。
- 未来批次覆盖的当前已到订单不能更少，不能为了新单牺牲老单。
- 通过资格线后，才比较当前批次分和未来批次分；提升至少 0.18 才允许等。
发车倾向来自哪里
最急订单离最晚出发点越近，越倾向发车。
能多带一单会加分，但不是必须凑满。
等待订单相对空闲人手越多，越倾向发车。
未来重组批次没有明显更好时，越倾向发车。
人数搜索：用全天模拟做二分验证
当前人数不能完成 → 增加人数
为什么可以二分
如果 k 个配送员能完成任务，那么多一个配送员也一定不会更差。因此最少人数可以通过“不断试中间值”的方式搜索。
未来订单未知时的实时调度
在线策略不偷看未来订单，只能在当前可见信息下做滚动决策。
在线调度的核心差异：看不见未来
当前能看到什么
已经到达校门、正在等待配送的订单，以及哪些配送员在校门空闲。
不可见信息
未来几分钟是否会来新单、来几单、去哪里，都未知。
主要矛盾
立即出发更安全；等待可能拼单，但会推迟回场。
策略定位
不是替代离线结果，而是模拟真实系统执行成本。
在线意义
离线结果回答“已知历史数据时能做到多好”；在线结果回答“真实执行中未知未来会多用多少人”。
在线策略：先保证不超时，再考虑等一等
有订单已经接近最晚出发时间时，不再等待，直接派出当前可行批次。
校门等待订单明显多于空闲配送员时，先发一批，避免后面越来越堵。
当前批次已经凑到 4 单时，继续等的收益很低，直接出发。
如果订单还安全、批次还不满，就短暂等待新单，提高拼单率。
等待不是无限等；到达复核时刻、新订单到达或配送员回场，都重新判断。
在线：哪些情况直接走
有订单只剩约 1 分钟安全余量，直接走。
等待订单数比空闲配送员明显更多，直接走。
一趟已经 4 单，直接走。
继续等会把安全余量压得太低，直接走。
如果之前选择等待，到了复核时刻就按当前最优批次发车。
在线：哪些情况可以等
可以等的情况
- 当前没有急单逼近最晚出发时间。
- 当前批次还没凑满，等待有机会提升拼单率。
- 校门订单没有明显积压。
- 即使等一小段时间，所有可见订单仍然保有安全余量。
等多久
- 最多只等安全余量的一半，避免把时间窗用满。
- 单次等待不超过 3 分钟。
- 新订单到达、配送员回场、或到达复核时间，就立即重新判断。
- 如果复核后仍然不适合等，就直接派出当前最好批次。
离线与在线策略对照
| 维度 | 离线策略 | 在线策略 |
|---|---|---|
| 能看到的信息 | 知道全天订单，可以判断未来几分钟是否值得等。 | 只知道当前已经到达校门的订单。 |
| 等待方式 | 已知未来订单表，所以只在短前瞻试算明确改进时等待。 | 不知道未来订单，只做很短的保守等待，并且随时复核。 |
| 发车原则 | 急单、满批、压力大、离线试算无改进时直接发。 | 急单、积压、满批、安全余量过小时直接发。 |
| 结果用途 | 作为本题最终最少人数结果。 | 衡量真实执行时因为看不见未来会多用多少人。 |
为什么这个算法能跑得动
关键不是全量搜索，而是用候选池限制组合爆炸。
复杂度里每个符号是什么意思
| 符号 | 含义 | 在复杂度里起什么作用 |
|---|---|---|
| V、E | 校园图的节点数和道路边数。 | 决定一次最短路计算的开销。 |
| R | 需要预处理最短路的关键地点数量，如校门和宿舍楼。 | 需要跑多少次最短路。 |
| N | 全天订单数。 | 决定外层人数搜索上界。 |
| M | 一天中需要重新决策的事件数量。 | 决定全天模拟要循环多少轮。 |
| p | 标准池大小，默认看 8 个次紧急订单。 | 控制每个 seed 周围先从多大的订单池里找伙伴。 |
| s | seed 池大小，默认 4 个高风险订单。 | 决定每轮围绕多少个急单分别扩展。 |
| p′ | 读作 p-prime，表示每个 seed 的伙伴池大小；默认最多 12，兜底最多 14。 | 决定单个 seed 周围要枚举多少候选组合。 |
| b | 一趟最多带几单，默认 4。 | 组合和排列的阶数，影响最大。 |
复杂度来源一：地图最短路
这部分为什么存在
- 每次判断一个批次是否可行，都要知道校门到宿舍、宿舍到宿舍、宿舍回校门的最短路。
- 如果每次派单时临时算，会重复很多次。
- 所以先把关键点之间的最短路算好，后面直接查表。
一次决策的局部枚举复杂度
从一次人数验证到总复杂度
为什么实际运行可控
图规模可控
校园道路图远小于订单调度规模；最短路预处理一次完成，后续主要查表。
批次规模小
5kg 载重和 10 分钟时限让一趟很难带很多单，默认最多 4 单。
候选池有限
标准池默认 8 单，seed 伙伴池默认最多 12 单，兜底最多 14 单。
事件数有限
只在订单到达、配送员回场和安全边界附近重算，不做逐分钟全量扫描。
从数字结果跳到交互前端
结果不只是表格，还能点击查看每批装载、路径和在线对比。
离线最少人数结果
| 数据集 | 订单 | 批次 | 均批量 | 最少人数 | 峰值订单 | 前端 |
|---|---|---|---|---|---|---|
| NPU Mon | 801 | 443 | 1.81 | 21 | 51 | 打开 |
| NPU Tue | 785 | 451 | 1.74 | 19 | 36 | 打开 |
| NPU Wed | 786 | 442 | 1.78 | 19 | 42 | 打开 |
| CDUT Mon | 850 | 558 | 1.52 | 24 | 33 | 打开 |
| CDUT Tue | 839 | 531 | 1.58 | 24 | 34 | 打开 |
| CDUT Wed | 861 | 544 | 1.58 | 30 | 44 | 打开 |
在线与离线对比结果
前端展示入口
现场演示建议：先点离线总览，再打开 NPU 周一或 CDUT 周三；最后用对比页解释在线策略的额外成本。
高峰批次案例：NPU 周一
短时高峰
典型三单批次
校门 → 订单 335 → 订单 334 → 订单 336 → 校门
