Optimal assignment of buses to bus stops in a loop by reinforcement learning

Bus systems involve complex bus-bus and bus-passengers interactions. In this paper, we study the problem of assigning buses to bus stops to minimise the waiting time of passengers.
We formulate an analytical theory for two specific cases of interactions: all the buses interact with each other via the boarding/alighting of passengers (regular buses) and disjoint subsets of non-interacting buses. The second case is a novel configuration where disjoint subsets of buses serve disjoint subsets of bus stops and we call it “express bus”. Our formulation allows for the exact calculation of the average waiting time for general bus loops in the two cases examined. Compared with regular buses, we show scenarios where “express buses” show an improvement in terms of average waiting time. From the theory we can obtain simple insights: there is a minimum number of buses needed to serve a bus loop, splitting a crowded bus stop into two less crowded ones always increases the average waiting time for regular buses, changing the destination of passengers and displacement of bus stops does not influence the average waiting time.
In the second part, we introduce a platform based on reinforcement learning that can overcome the limitations of our analytical method to search for better allocations of buses to bus stops that minimise the average waiting time. Compared to the previous cases, any possible interaction between buses is allowed, unlocking novel emergent strategies. We apply this tool to a simple toy model and three empirically-motivated bus loops, based on data collected from the NTU shuttle bus system. In the simplified model, we observe an unexpected strategy emerging that could not be analysed with our mathematical formulation and displays chaotic behaviour. The possible configurations in the three empirically-motivated cases are approximately 10^8, 10^10 and 10^17, so a brute-force approach is impossible. Our algorithm can reduce the average waiting time by 12% to 32% compared to regular buses and significantly outperforms express buses. This tool can have practical applications because it works independently of the specific characteristics of a bus loop.