Recasting and optimizing intersection automation as a connected-and-automated-vehicle (CAV) scheduling problem: A sequential branch-and-bound search approach in phase-time-traffic hypernetwork

- Introduce a phase-time-traffic hypernetwork model to model intersection automation.
- Develop scheduling-oriented formulations to define the intersection automation problem.
- Develop a sequential branch-and-bound algorithm to search the optimal solution.
- Enhance solution search with efficient dominance rule and phase-time prism.

It is a common vision that connected and automated vehicles (CAVs) will increasingly appear on the road in the near future and share roads with traditional vehicles. Through sharing real-time locations and receiving guidance from infrastructure, a CAV's arrival and request for green light at intersections can be approximately predicted along their routes. When many CAVs from multiple approaches at intersections place such requests, a central challenge is how to develop an intersection automation policy (IAP) to capture complex traffic dynamics and schedule resources (green lights) to serve both CAV requests (interpreted as request for green lights on a particular signal phase at time t) and traditional vehicles. To represent heterogeneous vehicle movements and dynamic signal timing plans, we first formulate the IAP optimization as a special case of machine scheduling problem using a mixed integer linear programming formulation. Then we develop a novel phase-time-traffic (PTR) hypernetwork model to represent heterogeneous traffic propagation under traffic signal operations. Since the IAP optimization, by nature, is a special sequential decision process, we also develop sequential branch-and-bound search algorithms over time to IAP optimization considering both CAVs and traditional vehicles in the PTR hypernetwork. As the critical part of the branch-and-bound search, special dominance and bounding rules are also developed to reduce the search space and find the exact optimum efficiently. Multiple numerical experiments are conducted to examine the performance of the proposed IAP optimization approach.