A Quantum Optimization Algorithm to Efficiently Route Public Transportation in Cities

Cars are one of the biggest polluters of greenhouse gases and to reduce their impact on the environment, there needs to be a nation-wide shift towards the use of public transportation - specifically the use of buses. Designing new bus routes can help buses arrive more frequently on time, especially during rush hour, which is an incentive for people to use buses. The Urban Transit Routing Problem (UTRP) is an NP-hard optimization problem, solved with heuristic algorithms that output approximate solutions, that focuses on constructing bus routes from an existing road network. The purpose of this project is to use quantum computing to solve the UTRP by minimizing a road network’s average travel time (ATT), a measure of the average travel time for all passengers to travel between all pairs of bus stops. My engineering goal was to use quantum computing, which has a theoretical advantage over heuristics in solving NP-hard problems, to produce routes with a lower ATT than heuristics for Mandl’s Swiss benchmark and existing bus routes in downtown Seattle.  My algorithm achieved an ATT of 10.11 minutes for the benchmark, which is an improvement over current UTRP solvers. Additionally, my algorithm decreased the ATT in a section of downtown Seattle by 53%. This research supported my engineering goals by showing the feasibility of using quantum computers to develop routes with a lower ATT than both classical heuristic methods for a benchmark and existing bus routes in downtown Seattle.