《Future Generation Computer Systems》：Efficient vehicle patrol scheduling for urban safety: Optimization and heuristic approaches
编辑推荐：
高效车辆巡逻调度（Vehicle Patrol Scheduling, VPS）对于提升城市安全、保障安全以及优化运营性能至关重要。传统的调度方法通常难以平衡多个目标和约束，例如在动态交通条件下有限的车辆、强制休息期和严格的再访周期。为应对这些挑战，研究人员提
高效车辆巡逻调度（Vehicle Patrol Scheduling, VPS）对于提升城市安全、保障安全以及优化运营性能至关重要。传统的调度方法通常难以平衡多个目标和约束，例如在动态交通条件下有限的车辆、强制休息期和严格的再访周期。为应对这些挑战，研究人员提出了一种双重方法论：首先，引入了一个形式化的优化模型（Optimization Model, OP），以获取小规模实例的精确解；其次，开发了两种新型可扩展启发式算法，即自适应爬山巡逻调度（Adaptive Hill-Climbing-Based Patrol Scheduling, AHBPS）和基于遗传的动态车辆巡逻调度（Genetic-Based Dynamic Vehicle Patrol Scheduling, GDVPS），旨在处理大规模动态城市网络。使用真实城市地图进行的广泛模拟表明，GDVPS在解质量和可扩展性方面均持续优于AHBPS，在包含1000个位置的网络中实现了高达80%的覆盖率，同时保持了实时可行性。结果证实，GDVPS提供了一种稳健、动态且可扩展的调度解决方案，使其成为现代城市安全运营中一个很有前景的候选方案。
**论文解读：面向城市安全的高效车辆巡逻调度——优化与启发式方法**
**研究背景与问题**
城市安全是现代社会运行的基础，而车辆巡逻调度（Vehicle Patrol Scheduling, VPS）是提升公共安全、保障人员与财产安全的核心手段。VPS通过部署受过训练的巡逻人员和遥测设备（如GPS），在特定区域内执行巡逻任务，以威慑犯罪并快速响应事件。然而，传统的调度方法往往难以在动态交通条件下平衡多个冲突目标与约束，例如：有限数量的巡逻车辆、驾驶员强制性休息时间、以及对特定地点严格的再访间隔。这些约束使得VPS成为一类复杂的组合优化问题，被证明是NP-hard的。现有研究大多基于静态旅行时间或单次访问假设，忽略了巡逻网络中固有的动态性、频繁再访的约束以及操作规则（如轮班周期、休息时间）的完整性。因此，急需开发能够同时处理大规模、动态环境与严格约束的高效调度方法。该论文发表在《Future Generation Computer Systems》上，旨在填补这一空白。
**研究人员开展的研究与结论**
针对上述问题，研究人员提出了一种双管齐下的方法论：首先，构建了一个形式化的数学优化模型（Optimization Model, OP），用于在小规模、静态实例中获取精确最优解，作为基准参考；其次，针对大规模动态场景，开发了两种新型可扩展启发式算法——自适应爬山巡逻调度（Adaptive Hill-Climbing-Based Patrol Scheduling, AHBPS）和基于遗传的动态车辆巡逻调度（Genetic-Based Dynamic Vehicle Patrol Scheduling, GDVPS）。通过从Open Source Maps（OSM）提取的加拿大安大略省滑铁卢市真实城市地图进行广泛模拟，研究人员发现GDVPS在解质量和可扩展性方面均显著优于AHBPS，在包含1000个位置的网络中实现了高达80%的覆盖率，同时保持了实时可行性。结论确认GDVPS提供了一种稳健、动态且可扩展的调度解决方案，使其成为现代城市安全运营中一个很有前景的候选方案。
**主要关键技术方法**
研究人员主要采用了以下关键方法：第一，形式化优化模型（OP）——将VPS问题建模为数学规划，通过线性约束和分支定界框架求解，适用于小规模实例（最多15个位置）。第二，自适应爬山巡逻调度（AHBPS）——基于局部搜索的启发式方法，通过模拟交通波动（随机扰动旅行时间）和邻域搜索，快速生成可行调度，时间复杂度为O(|S|·|C|·|N|·I)。第三，基于遗传的动态车辆巡逻调度（GDVPS）——基于遗传算法（GA）的元启发式方法，通过移位保持交叉（Shift-Preserving Crossover）和时间窗交换变异（Time-Window Swap Mutation）算子，结合精英保留策略和动态变异率，进化优化大规模调度。数据来源：从Open Source Maps（OSM）提取的真实城市地图，通过NetworkX和OSMNX库转化为图结构，旅行时间基于正态分布（均值15分钟，标准差5分钟）模拟，并在25%的模拟中动态调整±2分钟以反映交通波动。
**研究结果**
**1. 小网络评估（Evaluation over small networks）**
在节点数5、10、15和车辆数1-4的小规模场景中，OP方法始终达到最高访问次数，验证了其最优性。但OP的执行时间随网络规模指数增长，15节点4车辆时超过4000秒，而AHBPS和GDVPS分别仅需约0.01秒和0.3秒，显示启发式方法的高效性。GDVPS的解质量接近OP，优于AHBPS。
**2. 大网络评估（Evaluation over large networks）**
在节点数500-1000、车辆数10-20的大规模场景中，GDVPS持续优于AHBPS。例如，20车辆1000节点时，GDVPS覆盖约80%的位置，而AHBPS仅覆盖约45%。GDVPS的执行时间线性增长（约120秒），而AHBPS几乎恒定（小于0.1秒），但GDVPS提供了更高的覆盖效率。
**3. 与传统元启发式方法的对比基准（Comparative benchmarking against classical metaheuristics）**
在最复杂的大规模场景（1000节点、20车辆）中，GDVPS的覆盖率为78.6%，执行时间120秒；传统蚁群优化（Ant Colony Optimization, ACO）覆盖率为62.4%，执行时间194.2秒；AHBPS覆盖率为45.0%，执行时间0.05秒。GDVPS在解质量和计算效率上均优于ACO，验证了其定制遗传算子的优越性。
**4. 参数工程（Parameters engineering）**
在10车辆1000节点场景下，归一化分析显示：巡逻时间从5分钟增至15分钟时，覆盖下降约20个单位；休息时间从10分钟减至5分钟时，覆盖提升约4个单位；平均旅行时间从15分钟降至10分钟时，覆盖显著提升；操作时间从12小时减至8小时时，覆盖下降。GDVPS在所有参数变化下均优于AHBPS，表现出健壮性。
**总结与讨论**
研究人员在论文中成功解决了城市安全运营中的关键车辆巡逻调度（VPS）问题，旨在平衡区域覆盖与巡逻效率。通过采用双重方法——优化模型（OP）用于小规模静态实例以保证最优性，以及两种启发式方法（AHBPS和GDVPS）用于大规模动态场景——研究验证了GDVPS在复杂网络中的显著优势。GDVPS利用遗传算法的交叉和变异算子高效探索大规模解空间，同时保持多样性和可扩展性。广泛模拟表明，GDVPS在覆盖率和操作效率上远超AHBPS，且适应不同的城市布局和巡逻需求，成为大规模城市安全运营的潜力工具。此外，该模型的可适应性还暗示了在物流和灾难响应等领域的潜在应用。未来工作将纳入紧急事件以创建更动态的环境，并探索深度强化学习及多智能体强化学习（Multi-Agent Reinforcement Learning, MARL）以优化实时响应和智能体协调。
