Optimizing passenger group vehicle assignment in ride sharing systems using greatest common divisor approach

Abstract

Abstract With rising urban populations, optimizing passenger group-to-vehicle allocation (PGVA) is critical for enhancing ride-sharing efficiency, particularly when integrated with transit networks. Existing PGVA methods often underperform by overlooking arithmetic compatibility between passenger group sizes and vehicle capacities. Traditional approaches prioritize spatial or temporal factors but neglect structural relationships inherent in passenger group-vehicle matching. This study introduces the Greatest Common Divisor (GCD) method, a novel framework leveraging number-theoretic principles to optimize resource allocation. The GCD-based method addresses PGVA problem by decomposing passenger group sizes and vehicle capacities into prime factors, ensuring mathematically rigorous compatibility while minimizing wasted capacity and computational complexity. Under the tested simulation conditions, the GCD-based method demonstrated superior performance in reducing empty vehicle miles traveled (eVMT) and vehicle miles traveled (VMT) compared to the benchmark algorithms. It significantly reduced eVMT and VMT by over 70% and 85% respectively, compared to the Hungarian algorithm, while avoiding the inefficiencies of a first-come-first-served strategy. The GCD-based compatibility score successfully encodes the qualitative notion of a “good fit”, leading to more efficient resource utilization and directly contributing to the model’s performance. While relatively computationally more intensive, the proposed GCD-based model solves problems of realistic scale within a timeframe that is practical for operational deployment in modern ride-sharing platforms. The method bridges a critical gap in ridesharing optimization and aligns with sustainability goals through inherent resource efficiency. This study supports data-driven strategies for passenger-centric mobility systems that balance demand, capacity, and environmental impact by prioritizing arithmetic alignment.