The matching problem of empty vehicle redistribution in autonomous taxi systems

Babicheva, Tatiana; Burghout, Wilco; Andreasson, Ingmar; Faul, Nadege · 2019 · Crossref

DOI: 10.5383/jttm.01.01.001

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of empty vehicle redistribution in Personal Rapid Transit (PRT) and autonomous taxi systems, aiming to minimize passenger waiting times and queue lengths while optimizing fleet efficiency. The authors identify that asymmetric demand creates supply-demand imbalances, necessitating efficient redistribution strategies. They categorize existing methods into reactive approaches, which assign vehicles upon passenger arrival (e.g., nearest neighbor heuristics), and proactive approaches, which redistribute vehicles based on predicted future demand. The study specifically evaluates and compares these strategies, proposing a novel Index-Based Redistribution (IBR) algorithm that utilizes a passenger disutility function to prioritize stations with the highest expected maximum waiting times. The methodology involves formulating the redistribution problem as a dynamic matching problem on a bipartite graph of available vehicles and stations. The authors first evaluate three specific algorithms—Simple Nearest Neighbors (SNN), Send The Nearest (STN), and IBR—on a simplified linear network with two stations and two vehicles. This theoretical analysis demonstrates that no single pure strategy is optimal across all vehicle placement scenarios, suggesting that mixed strategies may offer greater robustness. Subsequently, the authors simulate six variations of combined proactive and reactive strategies on a realistic test case in Paris Saclay, France. This network consists of 20 stations and a fleet of 100 vehicles, using historical demand data from the Ile de France Transport Authority for both off-peak and rush-hour conditions. The simulations average results over 100 runs to assess performance metrics including average and maximum waiting times, queue lengths, and total vehicle run time. The results indicate that combined strategies significantly outperform pure reactive or proactive methods. Specifically, the mixed SNN/IBR strategy provided the best performance in both off-peak and rush-hour scenarios. In off-peak conditions, the SNN/IBR combination achieved a maximum waiting time of 5.1 minutes and an average waiting time of 0.25 minutes, with an average queue length of 15 passengers. During rush hours, it recorded a maximum waiting time of 13 minutes and an average of 2.4 minutes. These figures were superior to other combinations, such as SNN/SDR (Surplus/Deficit Redistribution) and HNN/IBR (Heuristic Nearest Neighbors/IBR). The study also explores multi-matching algorithms using the Hungarian algorithm to optimize vehicle-station pairings, noting that while computationally more complex, these methods can reduce total empty vehicle run distances compared to greedy sequential assignments. The significance of this work lies in its demonstration that hybrid redistribution strategies are essential for efficient autonomous taxi operations. By combining reactive responsiveness with proactive prediction, operators can mitigate the limitations of individual heuristics, ensuring lower passenger waiting times and better service equity. The findings provide a practical framework for designing dispatch algorithms in on-demand transportation systems, highlighting that the integration of index-based proactive measures with nearest-neighbor reactive assignments offers a robust solution for varying demand patterns. This contributes to the broader field of traffic management by offering evidence-based strategies for optimizing shared autonomous vehicle fleets.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• driverless ads