The Batch Insertion Operator for Shared Mobility Route Planning on Time-Dependent Road Networks
Aaditya Mukherjee, Sean Chester, Mário A. Nascimento · 2025
Effective route planning for shared mobility is crucial for user experience in transportation services such as ridesharing, logistics, and food delivery.However, in high-volume applications with travel times that depend on the time of day, high computational complexity can impair route planning throughput.This paper proposes a batch insertion operator that handles multiple concurrent requests.It proposes a novel partitioning solution that uses route length rather than spatial proximity as a partitioning criterion, then adaptively assigns workers to larger partitions.Compared to a greedy solution that repeatedly applies the standard, i.e., non-batched, insertion operator, query processing is significantly accelerated with minor to no degradation in solution quality.Extensive experiments using three city-scale datasets demonstrate that this approach can provide speedups up to 15× and is also amenable to parallelisation.