Reservation‐based intersection scheduling using dynamic programming with dominance pruning

Abstract

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 () that simultaneously achieves optimal batch formation, polynomial‐time complexity, and superior solution quality. 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, integrates optimal batching decisions directly into the scheduling algorithm. The proposed method achieves a substantial improvement over existing exact algorithms with worst‐case and best‐case time complexity. Extensive experiments demonstrate that 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, outperforms heuristic algorithms in achieving better solution quality and comparative computational efficiency. Sensitivity analysis reveals that ’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.