Reservation-based intersection scheduling using dynamic programming with dominance pruning

doi:10.1111/itor.70223

Reservation-based intersection scheduling using dynamic programming with dominance pruning

2026-06-30

0

PRE

AI

DOI：10.1111/itor.70223

原文链接

原文求助

摘要

En 中文

在基于预约的交叉口调度联网和自动化车辆（CAVs）面临一个根本性的权衡：现有方法要么为了计算效率而牺牲最优性，要么为了最优解而牺牲实时适用性。我们通过提出一种具有支配性剪枝的动态规划（DP）算法（DP²）来弥合这一差距，该算法同时实现了最优批次形成、多项式时间复杂度和卓越的解质量。DP²引入了一种新颖的支配规则，通过比较解析推导的下界来消除次优子节点，从而在保证最优性的同时实现CAVs的批次处理。与假设预定批次或牺牲最优性的现有方法不同，DP²将最优批次决策直接集成到调度算法中。所提出的方法在O(n²)最坏情况和Ω(n)最佳情况时间复杂度下，相较于现有精确算法实现了显著改进。大量实验表明，DP²相较于最先进的DP算法和Gurobi求解器，计算时间分别减少了91%和99%，同时在各种交通场景下在完工时间、平均延误和最大延误指标上持续表现出更优性能。此外，DP²在实现更优解质量和相当的计算效率方面优于启发式算法。敏感性分析显示，DP²的支配规则在变化的平均车头时距、CAV数量和批次比例下仍然有效，其性能优势不仅限于简单批次处理，还延伸至复杂交通模式。

Keyword:

dynamic programming

dominance pruning

time complexity

scheduling

connected and automated vehicles

Reservation-based intersection scheduling using dynamic programming with dominance pruning

摘要

期刊

机构