Multi-vehicle ride-pooling system using reinforcement learning

Abstract

Ride-pooling services have surged in popularity in recent years due to them being more efficient, convenient, and cost-effective than alternative traditional methods such as taxis. Leveraging mobile technologies, ride pooling services use the location of drivers and customers to assign a shared vehicle to passengers travelling in the same direction, reducing the number of vehicles on the road and, therefore, helping reduce traffic congestion. Such services require algorithms that dynamically match passengers with nearby drivers and optimise routes. Ride-pooling can be considered a variant of the Vehicle Routing Problem (VRP), which is a combinatorial NP-hard problem as it involves finding an efficient set of routes for a fleet of vehicles to serve customers while satisfying constraints such as customers’ time windows and vehicle capacity. Literature shows how the use of various metaheuristic algorithms to solve the VRP, such as tabu search (TS), can provide good solutions in terms of quality but suffer from scalability. With the recent advances in artificial intelligence, Reinforcement Learning (RL) is also being applied to capture the dynamic and stochastic nature of the VRP. In this research, we propose to use RL to solve the Multi-Vehicle Routing for Ride-Pooling Problem (MVRRPP) and generate solutions faster than the traditional metaheuristic methods. This algorithm aims to optimise passenger allocation to vehicles and vehicle routing while minimising the overall waiting time, travel time and total driving distance. We first implemented a baseline algorithm that uses TS with an initial solution consisting of equally distributed customers along the routes to solve the MVRRPP and establish its performance. We then model the MVRRPP as an RL problem and solve it using the REINFORCE algorithm with a dynamic attention model consisting of a dynamic encoder-decoder architecture. The performance of this model was compared with the results achieved using TS. Finally, we evaluate the effect of using an RL solution as input for the TS algorithm. The results of the three models showed that TS found higher-quality solutions than RL and TS with RL; however, its computational complexity resulted in longer computation times when solving large problem instances. Using RL involved a trade-off between solution quality and computation time, where it was quicker to find a solution even for problems on a large scale. On the other hand, performance using TS with RL showed minimal improvement except for reducing the distance travelled by vehicles, which suggests that the RL solution, used as the initial solution for TS, was in a region of the search space that had an inferior local optimum then the initial solution used in the TS without RL. The choice between TS and RL for solving the MVRRPP depends on the application’s requirements and the problem’s complexity.