Open AccessThe matching problem of empty vehicle redistribution in autonomous taxi systems
Author(s) -
Tatiana Babicheva,
Wilco Burghout,
Ingmar Andréasson,
Nadège Faul
Publication year - 2019
Publication title -
international journal of traffic and transportation management
Language(s) - English
Resource type - Journals
ISSN - 2371-5782
DOI - 10.5383/jttm.01.01.001
Subject(s) - bipartite graph , queue , redistribution (election) , computer science , mathematical optimization , matching (statistics) , graph , operations research , engineering , mathematics , computer network , statistics , theoretical computer science , politics , political science , law
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 an index-based proactive redistribution (IBR) 18,19 algorithm based on predicted near-future demand at stations. The results of different redistribution methods implemented on a simple line test case show that none of the proposed methods are optimal in all cases. Test results of six variations of combined proactive and reactive strategies on a test case in Paris 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.