面向动态校车运输再优化的自适应实时决策支持框架

《Expert Systems with Applications》：An Adaptive Real-Time Decision-Support Framework for Dynamic School Transportation Reoptimization

　　

摘要

本文研究的是在动态运营条件下实时进行的学校交通重新优化问题。我们提出了动态学校交通重新优化问题（DSTRP），它在经典校车路线规划的基础上，纳入了时间依赖行驶时间、滚动时域决策、已硬承诺的路段、可配置的运输政策以及运营修改成本。

我们提出了一种自适应决策支持框架，称为ARTHGS，该框架结合了混合遗传搜索与基于自适应大邻域搜索（ALNS）的改进方法。我们评估了两种互补策略：局部滚动时域修复（ARTHGS），将重新优化限制在受影响的路线邻域范围内；以及全局重构（ARTHGS-GR），对剩余的活跃未承诺计划进行重新优化。

计算实验涵盖了三类运输政策、三类实例规模和五种运营场景。与无重新优化HGS相比，RH-ACS、ARTHGS和ARTHGS-GR分别将累计迟到时间减少了55.9%、59.0%和68.7%。相应的准点到站比率从使用无重新优化HGS时的28.06%提升至55.40%、62.31%和64.31%。与ARTHGS-GR相比，ARTHGS引入的运营变更更少。

非参数检验、消融研究和RH-CPLEX验证均支持了上述结论。在RH-CPLEX证明达到时间片级最优的可行子问题上，ARTHGS-GR、ARTHGS和RH-ACS的平均局部目标差距分别为0.20%、0.85%和1.65%。结果表明，局部修复策略提供了更高的计划稳定性，而全局重构策略在严重或连锁干扰下实现了更强的准点恢复能力。

引言

学校交通系统构成了城市日常出行和公共服务物流的重要组成部分。在许多城市中，数千名学生必须在严格的时间、运营和安全约束下被运送，同时保持准点、服务连续性和资源效率。与传统的货物运输不同，学校交通运营涉及额外的制度和乘客导向要求，包括学校铃时同步、学生乘车时间限制、异构运输政策、路线通信约束以及高运营可靠性期望。

经典校车路线问题涉及设计车辆路线，将学生在停靠点和学校之间运送，同时满足容量、时间窗、乘车时间和学校日程约束。大多数现有研究将此问题视为离线规划问题，在执行前已知需求、行驶时间和学校日程。相比之下，本文研究的是在路线执行期间的动态重新优化，即已经规划或已部分执行的运输计划必须在行驶时间变化、车辆延迟、停靠点更新或其他运营事件发生后进行更新。

所提出的DSTRP的创新性在于将学校特定的路线约束与滚动时域重新优化、时间依赖行驶时间、硬承诺路段、可配置的学校运输政策和运营修改成本相结合。这使其区别于静态校车路线模型和通用动态车辆路径模型。

传统的学校交通规划方法通常假设所有相关运营信息在提前已知，并且在执行期间保持不变。在此假设下，路线和调度决策在路线部署前离线计算。然而，现实中的学校交通系统在动态和不确定环境中运行，交通状况、运营事故、车辆延迟、停靠点取消、学生出勤更新和需求扰动可能在一天中持续演变。这些条件要求在执行期间修订交通计划，通常是在严格的运营和计算时间限制下。

实时交通信息、基于GPS的车队监控系统和智能交通基础设施的日益普及，加剧了对学校交通管理自适应决策支持框架的需求。在实践中，调度员必须决定是保留当前计划，仅修复受影响的路线邻域，还是重构大部分活跃交通计划。这些决策涉及相互冲突的标准：路线效率、服务准点、运营连续性、路线修改和计算响应速度。这产生了一个动态重新优化问题，仅凭静态校车路线模型无法充分解决。

动态学校交通重新优化引入了几个方法和运营挑战。首先，行驶时间是时间依赖的，可能产生跨多条路线和多个学校的延迟传播。其次，运营事件通常仅影响交通网络的局部，使得完整路线重构计算成本高昂，有时还会造成运营干扰。第三，适当的重新优化范围取决于事件严重性、当前路线执行状态和活跃运输政策。局部修复策略可能保留当前运营计划的更大部分，而全局重构策略可能在严重或连锁事件后提供更强的准点恢复。

大多数现有路径研究要么专注于静态校车路线优化，要么专注于通用动态车辆路径模型。尽管动态和时间依赖车辆路径问题在文献中已被广泛研究（Adamo, Gendreau, Ghiani, Guerriero, 2024, Gmira, Gendreau, Lodi, Potvin, 2021, Pillac, Gendreau, Guéret, Medaglia, 2013, Psaraftis, Wen, Kontovas, 2016），但很少有人关注专门为滚动时域学校交通重新优化设计的自适应实时决策支持框架。类似地，校车路线研究已处理了重要的规划问题，如停车点选择、路线生成、学校铃时调度、混合载重运输和多学校路线（Ellegood, Solomon, North, Campbell, 2020, Park, Kim, 2010），但大多数这些贡献仍然主要面向离线规划而非日内运营恢复。

为了解决这些局限性，本文引入了动态学校交通重新优化问题（DSTRP）。所提出的问题将动态学校交通重新优化形式化为一个加权多标准优化场景，整合了时间依赖行驶时间、滚动时域运营更新、可配置的单学校、混合载重和顺序多学校运输政策、硬承诺路段以及显式的运营修改成本。术语"多标准"的使用是因为实施的优化依赖于几个运营标准的加权标量化，包括距离、迟到、拥堵暴露、运营修改和重新分配成本。

为了解决DSTRP，本文开发了一种自适应实时混合遗传搜索框架，称为ARTHGS。所提出的框架在统一的动态优化架构中结合了混合遗传搜索、自适应大邻域搜索、政策感知解码、滚动时域群体投影、自适应惩罚控制、局部破坏修复机制和粗粒度后代级并行化。从决策支持的角度来看，ARTHGS利用当前运营状态生成可执行的恢复计划，同时考虑运输政策约束、时间依赖行驶条件和运营修改成本。

本文进一步在同一计算框架内研究了两种互补的重新优化策略。第一个变体ARTHGS通过聚焦于动态受影响的路线邻域执行局部滚动时域修复（尽可能做到）。第二个变体ARTHGS-GR在运营事件后对剩余的活跃交通计划执行全局重构。这两个变体允许在一致建模和评估条件下控制分析局部适应、全局恢复、服务准点、运营修改和计算响应速度之间的权衡。

本工作的主要贡献总结如下：

- 本文定义并形式化了动态学校交通重新优化问题（DSTRP），这是一个标量化加权多标准问题，整合了时间依赖行驶时间、滚动时域更新、可配置运输政策、硬承诺路段和运营修改成本。

- 本文开发了ARTHGS，一种基于自适应实时HGS/ALNS的决策支持框架，结合了政策感知Split解码、滚动时域群体投影、自适应惩罚控制和事件感知破坏修复机制。该框架实现了两种互补的重新优化策略：局部滚动时域修复（ARTHGS）和剩余活跃计划的全局重构（ARTHGS-GR）。

- 该框架在一个按运输政策类别、实例规模和运营场景构建的动态基准上进行了评估。ARTHGS和ARTHGS-GR与无重新优化HGS、贪心修复、独立ALNS以及从Montemanni, Gambardella, Rizzoli, & Donati (2005) 改编的RH-ACS基线进行了比较。评估辅以滚动时域CPLEX验证、组件消融、非参数统计检验和容量类敏感性分析。

本文其余部分组织如下。第2节回顾了动态车辆路径、学校交通优化、混合遗传搜索、自适应大邻域搜索和实时重新优化相关的研究工作。第3节介绍了DSTRP的问题定义和数学形式化。第4节描述了所提出的ARTHGS决策支持框架。第5节报告了实验结果和比较分析。最后，第6节总结了论文并讨论了未来研究方向。

第2节

文献综述

动态学校交通重新优化问题（DSTRP）位于运筹学和智能交通系统几个既有研究领域的交汇处，包括带时间窗的车辆路径问题（VRPTW）、动态和时间依赖车辆路径、校车路线和调度以及实时交通重新优化。本节回顾了这些领域的方法论基础，并定位了所提出的自适应实时...