Flexible bus assignment and routing for carpooling fleets

Abstract

On‐demand transport is rapidly gaining popularity as a commercial and public transport service. This shift, particularly in public transport and urban mobility, is evidenced by the rise of ride‐splitting on‐demand services which utilise smaller buses, known as flexible buses. Customers can make requests through online platforms, requiring real‐time handling. A customer will specify pick‐up and drop‐off points, and they need to be efficiently grouped with other ongoing requests to minimise distance while ensuring that a customer is delivered within a reasonable time frame. The problem of efficiently routing a fleet of flexible buses with stochastic re‐ quests with time windows in real‐time is referred to as the dynamic flexible bus routing problem (DFBRP). This problem is classified as an NP‐hard problem. Currently, little re‐ search exists on the problem; with the current algorithms being search‐based, they fail to efficiently provide a suitable real‐time response. This research aims to tackle these issues by developing a Reinforcement Learning environment and an Advantage Actor‐Critic (A2C) algorithm to train multiple policies to provide a real‐time solution to the DFBRP. Furthermore, a state‐of‐the‐art Tabu Search algorithm known as the Multi‐Objective Tabu Search Algorithm (MOSTA) commonly used for demand‐responsive transit was implemented to ensure proper comparisons between search‐based methods and more novel Reinforcement Learning algorithms. Additionally, this research aims to evaluate the effect of clustering pick‐up points with Reinforcement Learning as commonly used with search‐based methods in similar problems to the dynamic flexible bus routing problem (DFBRP). The A2C algorithm was trained on several demand levels and multiple numbers of vehicles, each producing a separate model. The MOSTA provided more efficient solutions across the varying demand levels. However, it did so within unreasonable time frames. On the other hand, the A2C algorithms were able to provide promising solutions in a matter of seconds or less. The effect of clustering aided the A2C to complete requests in shorter distances and smaller exceeded time windows on average.