论文题目：Is waiting worth it? the value of delaying time window assignment in vehicle routing problems

第一/通讯作者：Şifanur Çelik 埃因霍芬理工大学研究人员，研究聚焦车辆路径规划，结合混合整数规划、聚类等优化方法及场景法等，开展相关优化问题研究与数值分析。

E-mail：s.celik@tue.nl


即时沟通与等待决策：动态时间窗车辆路由的权衡

论文摘要

本文关注物流服务提供商在次日服务中及时告知送达时间窗与降低运输成本之间的矛盾。作者提出动态延迟时间窗口分配车辆路径规划问题（DDTWAVRP），允许在预设截点前决定是否立即分配时间窗或者延迟决策。该问题被建模为有限时域的半马尔可夫决策过程（SMDP）。作者设计了两种在线启发式算法：一是基于一步前瞻的Rollout算法，通过仿真近似价值函数并在每个决策时段选择成本最小的决策；二是多场景法（MSA），通过采样未来需求场景并选择在多数场景中可行的时间窗决策。数值实验表明：允许延迟分配时间窗能使路程时长平均缩短约11.82%，Rollout算法在综合考虑等待与路线成本时表现优异，而MSA能进一步缩短路线但需承担更长的客户等待时间。研究不仅桥接了即时指派与完全后推两类时间窗研究；还揭示了延迟决策在客户服务公平性上的影响，为日后在多仓库、提送货、随机路况等扩展研究奠定基础。

一、研究背景与问题

1.1 客户服务与运输成本的矛盾

  • 即时沟通的价值：客户在下单时希望尽快获得狭窄且准确的送达时间窗。及时沟通能让客户安排生产或生活，减少错过配送的风险，提升忠诚度和满意度。
  • 信息不完备带来的挑战：一开始并不知道未来所有订单的位置和需求；如果过早锁定时间窗，车辆线路可能无法最优。
  • 传统策略的局限性：完全即时指派导致路线效率低下，而等到所有需求确认后再一次性指派则严重损害客户体验。因此需要在两者之间寻找平衡。

1.2 动态延迟时间窗口分配车辆路径问题（DDTWAVRP）

作者将服务区域表示为有向网络 。车辆集  从单一仓库出发，随机到达的客户集合  的数量及位置均为随机变量。决策分两阶段进行：

  • 第一阶段（预订阶段 ）：客户陆续到达，且所有请求均被接受。对于每个到达的客户，服务商可以立即分配时间窗或推迟至下一个决策点。推迟会累积“等待成本” 。
  • 第二阶段（服务阶段 ）：在截点  后，不再接受新的订单，决策者生成车辆路线并服务所有已分配时间窗的客户。若路线导致迟到，可允许软性违反时间窗，但会产生违约成本。

问题目标是在满足车辆容量和时间窗限制的条件下，最小化期望的运输成本、时间窗违反成本和延迟分配成本。与传统车辆路径问题相比，本问题既要动态作出时间窗指派决策，又要考虑客户服务质量的公平性。

1.3 示意例子

下图给出了 DDTWAVRP 的决策过程示意。上部为预订阶段，展示客户1–8的到达时间和时间窗分配；下部为服务阶段，展示车辆按已分配的时间窗服务客户。图中可见客户2和3的时间窗在第5个客户到来时才被确定，因此在此之前需要支付等待成本；客户7需等待到第8个客户到来时才确定时间窗。

  • 动态到达：客户到达触发决策点，未知未来订单数量。

  • 延迟指派：可推迟时间窗分配以获得更多信息，但会产生等待成本。

  • 服务阶段：路线规划需兼顾时间窗，允许柔性违规并支付罚金。

图1 动态延迟时间窗分配的决策示意（取自 Fig.1）
图1 动态延迟时间窗分配的决策示意（取自 Fig.1）

二、建模与算法框架

2.1 半马尔可夫决策过程建模

为了在动态环境中做出最优决策，作者将 DDTWAVRP 建模为有限时域的半马尔可夫决策过程（SMDP）。关键组成包括：

  • 状态变量  ：在第  个决策点包含当前时间、已分配的客户位置及时间窗矩阵、未分配客户的位置等信息。
  • 决策变量：对于每个未分配客户 ，选择时间窗指派决策 （取值 0 表示继续推迟）以及相应的开始与结束时刻 。
  • 转移函数：给定当前状态和决策，通过仿真未来客户到达、更新未分配集合和路线，得到下一决策点的状态。
  • 即时奖励：包括在当前决策点形成的新路线成本及时间窗违约成本。

由于状态空间和动作空间巨大，无法求解精确的动态规划。为此作者提出两种在线启发式算法。

2.2 Rollout（RO）算法

Rollout 算法是一种一步前瞻算法，利用仿真近似价值函数并选取期望成本最低的动作。其核心思路如图2所示：

  1. 选择基线策略  ：在模拟未来时采用的简单策略（例如始终采用某一固定的时间窗宽度）。

  2. 采样场景：从当前状态开始，采样  个未来情景（包含未来客户到达序列），在每个场景中按照基线策略逐步决策，累计未来  个决策点的成本。

  3. 评估候选动作：对于当前可行的时间窗宽度组合 ，在每个场景中以  开始，后续按基线策略模拟，计算未来成本 。

  4. 选择最小成本动作：在所有候选动作中选择 ，即构成新的决策。

图2 Rollout算法的决策树示意（取自 Fig.2）
图2 Rollout算法的决策树示意（取自 Fig.2）

RO 的优势是能综合考虑等待成本与路线成本，在时间窗宽度较大时仍保持较高的路线效率。缺点在于需要选择合适的基线策略和场景数量，计算量相对较大。

2.3 多场景法（MSA）算法

MSA 算法的核心思想是寻求在多个未来场景中均可行的时间窗。其步骤如下：

  1. 暂定时间窗：对于每个未分配客户，预先按照不同的时间窗宽度  生成多个候选时间窗 。
  2. 生成未来场景：采样  个未来客户到达序列，每个场景包含未来可能出现的客户及其到达时间。
  3. 构建路线并记录到达时间：在每个场景下使用最便宜插入（Cheapest Insertion）启发式将未分配客户插入当前路线，记录各客户在该场景下的到达时间序列 。
  4. 评估候选时间窗：按照从最窄到最宽的顺序检查候选时间窗，若在超过半数的场景中客户的到达时间落入时间窗内，则选择该时间窗；若无候选时间窗满足条件，则继续推迟。

MSA 聚焦于时间窗的稳健性，即在多数可能的未来中时间窗仍能被满足。该算法忽略等待成本，但能生成路径最短的结果，因此适用于对路线效率要求更高、容忍等待较长的场景。

2.4 随机最便宜插入的时间窗构造

无论采用 RO 还是 MSA，确定时间窗宽度后，需要为客户选择具体的开始和结束时刻 。作者采用随机最便宜插入算法：

  • 在每个决策点按照随机顺序插入需分配时间窗的客户，将其插入到现有路线的最便宜位置；
  • 插入时考虑车辆容量、路程增加和潜在的时间窗违约成本；
  • 新插入客户的时间窗使其预计抵达时间恰好位于时间窗中心。

该方法速度快、计算量小，适合作为在线算法的子模块。

三、数值实验与结果分析

3.1 实验设计与评价指标

作者在模拟环境中评估了 RO、MSA 以及多种基准策略的表现。实验设置包含：

  • 时间窗宽度：候选值为 0.5 h、1.0 h 和 1.5 h。

  • 客户到达率与拓扑：考虑随机、集群和随机–集群等不同地理布局以及高、中、低三个到达率。

  • 评价指标：

    • 总路程时长与运输成本；
    • 平均等待时间：从客户下单到收到时间窗的时间；
    • 时间窗违反量（单位时间违约成本）；
    • 加班时间：服务延伸至计划外时间的时长。

除 RO 与 MSA 外，还对比了即时指派（IA）、预定的离散时间指派（DT）等基准策略。

3.2 参数敏感性分析

3.2.1 违约成本系数的影响

实验发现，提高时间窗违约成本系数 会显著降低时间窗违反量，但同时增加路线时长；过高的违约成本会让策略趋向于提前分配宽时间窗，以保证不违反。在下图中，横轴为 ，纵轴为各运营指标，可看到随着  上升，平均路程时长增长而违约次数下降：

图3 违约成本对运营指标的影响（取自 Fig.3）
图3 违约成本对运营指标的影响（取自 Fig.3）

3.2.2 等候成本与时间窗宽度成本的影响

另一组实验探究了等候成本系数 和时间窗宽度成本系数的权衡。结果表明：适当提高等候成本可以缩短客户等待时间，但过高的等候成本会导致过早分配宽时间窗，从而增加路线成本；提高时间窗宽度成本可以鼓励选用更窄的时间窗，减少客户等待，但也增加违约风险和路程。

图4 等候成本与时间窗宽度成本对运营指标的影响（取自 Fig.4）
图4 等候成本与时间窗宽度成本对运营指标的影响（取自 Fig.4）

综合来看，中等的违约成本与时间窗宽度成本组合可以在等待时间、路线长度和违约次数之间取得较好平衡。

3.3 策略比较

实验结果表明：

  • Rollout vs MSA：RO 在平均等待时间与路线效率之间取得良好平衡；MSA 能生成最短路线，但等待时间长且很多客户要等到截点前才收到时间窗。
  • Rollout vs 基准方法：RO 能减少约 11.82% 的路程时长，同时客户平均等待约48分钟，相比即时指派大幅降低运输成本。
  • MSA vs 基准方法：MSA 几乎所有客户都要等待约2.18小时；虽然路线更短，但牺牲了客户体验。
  • 公平性观察：RO 策略下，客户等待时间不因距离远近或到达顺序而显著不同，表现较为公平；而 MSA 在中心区域的等待时间更长。
  • 地理布局与到达率影响：随机与随机–集群布局下，路线较长、等待时间更长；集群布局能充分利用车辆集中服务，显著提升效率。

四、创新亮点与未来研究

4.1 创新贡献

  • 提出全新问题：首次在序贯决策框架下正式定义了动态延迟时间窗分配车辆路径问题，填补了即时指派和完全后推两类研究之间的空缺。
  • 半马尔可夫建模：将时间窗指派和车辆路径决策统一建模为有限时域的 SMDP，刻画了决策时效、状态转移和奖励函数。
  • 两种在线启发式：基于神经动态规划思想的 Rollout 策略和基于场景共识的 MSA 策略分别代表了成本最小化和稳健性两类前瞻决策思想。
  • 系统性数值分析：通过大量模拟从等待成本、违约成本、时间窗宽度成本、到达率与地理布局等方面全面评估各策略的表现，为业界提供了可操作的参数建议。
  • 公平性研究：分析不同策略在客户等待时间和时间窗宽度上的空间分布，为理解服务公平性提供了见解。

4.2 局限与未来拓展

尽管本文取得了重要进展，仍存在一些局限和潜在的研究方向：

  • 多仓库与提货–送货：当前模型仅考虑单仓库配送，可扩展到多仓库或考虑取送货相结合的情景。
  • 随机旅行时间：实际路网存在拥堵和不确定性，未来研究可纳入随机旅行时间以及其与时间窗指派的互动。
  • 客户拒绝与取消：现有模型假定所有订单都被接受；实际中可能需要拒绝无法满足的订单，或者客户取消订单，需引入接受/拒绝决策。
  • 学习型策略：结合强化学习或深度学习，提高对未来需求和可行性的预测能力。

结语

DDTWAVRP 探讨的核心是等待是否值得。研究证明，适度延迟时间窗分配可以在不显著增加运输成本的前提下大幅提升线路效率；同时，通过前瞻性算法和合理参数设置，可以在等待时间、服务质量与成本之间寻求平衡。本文的建模框架和算法思路为动态配送领域提供了新范式，也为物流企业在面临越来越苛刻的客户需求时提供了决策依据和优化方向。

文章须知 

链上镖师团队：常文婕（AEIC）、祁园园、汪朝杰、王一航、张仁义（EIC）、张晓乐

原文链接：https://doi.org/10.1016/j.trb.2025.103381

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。