The matching problem of empty vehicle redistribution in autonomous taxi systems

This article discusses empty vehicle redistribution algorithms for PRT and autonomous taxi services from a passenger service perspective. In modern literature reactive methods such as nearest neighbours are commonly used. In this article we first formulate the general matching problem on a bipartite graph of available vehicles and stations. In addition, we propose a new index-based proactive redistribution (IBR) algorithm based on predicted near-future demand at stations. Test results of six variations of combined proactive and reactive strategies on a test case in Saclay, France with 20 stations and 100 vehicles are given. The combined Nearest Neighbour / IBR provides a promising solution for both peak and off-peak demand, significantly outperforming all other methods considered, in terms of passenger waiting time (both average and maximum) as well as in terms of station queue lengths.