Doing the Math: Optimizing Routing and Scheduling for UAM Fleet Management Using Quantum Annealing

Writing in Scientific Reports, seven researchers from Japan’s Tohuku University and Sumitomo Corporation proposed a plan to optimize how urban air mobility (UAM) operators, infrastructure managers, and others in the UAM ecosystem manage routing and scheduling using quantum annealing.

Quantum annealing, a quantum computing process, uses quantum fluctuations to find the best solution to an optimization problem. Using it, the Japanese team sought to plan efficient, deconflicted routing and scheduling management systems for operating large UAM fleets in high-density metropolitan air traffic environments.

By formulating route planning as a maximum weighted independent set problem enabled the group to utilize various algorithms and specialized optimization hardware. To validate their proposal, the scientists used OneSky’s urban traffic management (UTM) simulator designed for Singapore’s airspace where they distributed traffic throughout the region.

The simulator generated requests every 30 seconds by randomly selecting a pair of airports in the routing network as the source and destination. The system updated every 30 seconds and used an air speed of 10 meters per second for all the UAM vehicles and separated any two vehicles by 100 meters. The system generated five candidate routes for routing and scheduling for each request.

The study evaluated their optimization frameworks by comparing several methods against a non-optimized baseline strategy, which they called the shortest first-in, first-out (FIFO) method assigning each request the shortest available route and scheduling flights in the order of arrival, provided the route is deemed safe. The scheduling and routing framework approves more requests than the shortest FIFO method, demonstrating that route optimization in fleet management effectively increases the number of approved flights. The difference between the new approach and the shortest FIFO method diminishes when the request rate is high because when the request rate is dense, the airspace becomes heavily congested, and the routing network reaches full capacity, leaving little room for further route adjustments.

Some detours may be necessary — and advantageous

Under the shortest FIFO method, the usage of edges is highly skewed and some edges remain completely unused, while a few are used disproportionately often. In contrast, quantum annealing yields a more balanced usage, including edges located away from central regions. We also present the average number of active aircraft at any given time in Fig. 6. Our approach shows a more significant increase in active aircraft than the shortest FIFO method. This suggests that routes are more evenly distributed throughout the airspace, leading to more efficient utilization of available space. This implies that some routes may require detours to achieve the best combination of deconflicted paths, allowing for higher air traffic capacity while maintaining safety.

The findings revealed that some routes may require detours to achieve the best combination of deconflicted paths, allowing for higher air traffic capacity while maintaining safety. It also identified quantum annealing as a promising candidate for solving combinatorial optimization problems. To utilize quantum annealing, problems must first be encoded as QUBO formulations, and the effectiveness of this formulation directly influences the performance of the quantum annealing process.

We’re still early on in the development of UAM, its practices and protocols, but when you consider UAM is just an extension of more than 120 years of aviation, the prospects are bright for the routes and schedules to come.

Top 3 Takeaways