车辆路径问题与时间窗

车辆路径问题（VRP）决定每辆车按什么顺序访问哪些地点，并检查容量、工时和道路限制。加入时间窗后，客户只允许在指定时段开始服务；车可以早到等待，却不能把晚到的服务硬记成准时。单独求各地点到仓库的最短路径，并不会自动给出一条可执行的整车路线。

一辆车、两个客户

一条直线上，仓库 $O$ 在零千米，客户 $A$ 在二千米，客户 $B$ 在五千米。车辆行驶一千米用一分钟，在每个客户处服务一分钟；出发时间为零，最晚必须在第十三分钟回仓。 $A$ 的服务开始时间须在第 $2$ 至 $4$ 分钟， $B$ 须在第 $7$ 至 $9$ 分钟。两处货量分别为二和三件，车辆容量五件。

按 $O \to A \to B \to O$ 行驶：第 $2$ 分钟到 $A$ 并服务到 $3$ ；再行驶三分钟，第 $6$ 分钟到 $B$ ，等待到 $7$ 分钟才开始服务，到 $8$ 分钟结束；再行驶五分钟，恰在 $13$ 分钟回仓。货量 $2 + 3 = 5$ 没有超过容量。若先去 $B$ ，第 $5$ 分钟到达后要等到 $7$ 分钟，服务完第 $8$ 分钟，再去 $A$ 至少第 $11$ 分钟，已经超过 $A$ 的最晚开始时间四。两种访问顺序的纯路程都为十千米，时间窗却只允许第一种。

路线O到A到B再到O的时间轴依次标出行驶两分钟、在A服务一分钟、行驶三分钟、在B等候一分钟并服务一分钟、返程五分钟，十三分钟回仓 — 总路程相同的访问顺序不一定都可行；等待和服务时间必须进入到达时刻。

把路程变成约束

令 $c_{i j}$ 为从地点 $i$ 到 $j$ 的行车成本， $τ_{i j}$ 为行车时间， $s_{i}$ 为在 $i$ 的服务时长， $[e_{i}, l_{i}]$ 为服务开始时间窗， $d_{i}$ 为交付货量。对每辆车 $k$ ，二元变量 $x_{i j}^{k} = 1$ 表示它直接从 $i$ 驶向 $j$ 。常见目标是 $min \sum_{k, i, j} c_{i j} x_{i j}^{k}$ ，同时要求每个客户恰访问一次，车辆从仓库出发并回到仓库，中间每到一处就有一条离开的弧。

给车 $k$ 在客户 $i$ 的服务开始时刻记 $t_{i}^{k}$ 。若 $x_{i j}^{k} = 1$ ，时间必须满足 $t_{j}^{k} \geq t_{i}^{k} + s_{i} + τ_{i j}, e_{j} \leq t_{j}^{k} \leq l_{j} .$ 若弧没被选，上述递推不应约束这辆车，可用足够大的常数 $M$ 写成 $t_{j}^{k} \geq t_{i}^{k} + s_{i} + τ_{i j} - M (1 - x_{i j}^{k})$ ，但 $M$ 过大会使整数规划数值松弛、计算变慢；应由仓库营业时间与时间窗推得有效上界。还要把载货量沿选中弧递推，或直接对每条已构成路线检查 $\sum_{i \in 路线} d_{i} \leq Q_{k}$ 。只对总需求检查 $\sum_{i} d_{i} \leq \sum_{k} Q_{k}$ 不足以保证每辆车都装得下。

上面简单例子之所以允许在 $B$ 等一分钟，是因为时间变量表示服务开始，不是刚到门口的时刻。若客户要求服务完成不晚于 $l_{i}$ ，则约束改为 $t_{i} + s_{i} \leq l_{i}$ ；不能沿用开始时间窗并声称满足了完成时限。若道路单行、早晚高峰不同， $τ_{i j}$ 也未必等于 $τ_{j i}$ ，更不能把地图上的直线距离直接代入。

求解和验收

对少量客户可枚举访问顺序并逐条模拟服务时间与载重；规模增大后用整数规划、约束规划或专门的路径搜索。启发式求解器返回的是可行方案还是已证明最优，须看求解状态和最优界，不能因路径看起来短就自称最优。逐车验收应打印访问序列、抵达与服务开始时刻、等待、服务结束、剩余载重和回仓时刻；若任何时窗或容量不满足，就不是合法解。

需求、路况和客户可服务时间带有不确定性时，可按不同交通时段模拟路线，报告延误次数与备用车辆成本。硬时窗与可付罚金的软时窗代表不同合同，不应混用。若允许客户不服务，也要在目标里明确未服务的损失，而不是让求解器悄悄丢掉难送的地点。

参考资料与相关词条