.png){kind=icon}
.png){kind=icon}
Return
Reservation-based intersection scheduling using dynamic programming with dominance pruning
.png){kind=icon}
PRE
AI
DOI：10.1111/itor.70223.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Scheduling connected and automated vehicles (CAVs) at reservation-based intersections faces a fundamental trade-off: existing methods sacrifice either optimality for computational efficiency or real-time applicability for optimal solutions. We bridge this gap by proposing a dynamic programming (DP) algorithm with dominance pruning ( DP 2 $\rm{DP}^2$ ) that simultaneously achieves optimal batch formation, polynomial-time complexity, and superior solution quality. DP 2 $\rm{DP}^2$ introduces a novel dominance rule that eliminates suboptimal child nodes by comparing analytically derived lower bounds, enabling batch-based processing of CAVs while guaranteeing optimality. Unlike existing approaches that assume predetermined batches or sacrifice optimality, DP 2 $\rm{DP}^2$ integrates optimal batching decisions directly into the scheduling algorithm. The proposed method achieves a substantial improvement over existing exact algorithms with O ( n 2 ) $\mathcal {O}(n^2)$ worst-case and Ω ( n ) $\Omega (n)$ best-case time complexity. Extensive experiments demonstrate that DP 2 $\rm{DP}^2$ reduces computation time by 91% and 99% compared to a state-of-the-art DP algorithm and Gurobi solver, respectively, while consistently delivering superior performance in makespan, average delay, and maximum delay metrics across diverse traffic scenarios. Furthermore, DP 2 $\rm{DP}^2$ outperforms heuristic algorithms in achieving better solution quality and comparative computational efficiency. Sensitivity analysis reveals that DP 2 $\rm{DP}^2$ ’s dominance rule remains effective across varying mean headways, CAV counts, and batch proportions, with performance benefits extending beyond simple batch processing to complex traffic patterns.
Keywords:
dynamic programming
dominance pruning
time complexity
scheduling
connected and automated vehicles
Journal
IF:
2.9
Papers:
1.8K
Citations:
3.7K