Optimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems: A Prime Factorization and Greatest Common Divisor (GCD) Approach

Abstract

<title>Abstract</title> 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 group sizes and vehicle capacities. Traditional approaches prioritize spatial or temporal factors but neglect structural relationships inherent in group-vehicle matching. This study introduces the Prime Factor Tree (PFT) method, a novel framework leveraging number-theoretic principles—prime factorization and greatest common divisor (GCD)—to optimize resource allocation. The PFT method addresses PGVA by decomposing passenger group sizes and vehicle capacities into prime factors, ensuring mathematically rigorous compatibility while minimizing wasted capacity and computational complexity. Unlike heuristic or integer programming approaches, PFT achieves polynomial-time scalability. Computational experiments demonstrate a 12% increase in ridership, 15% reduction in vehicle miles travelled (VMT), 7% decrease in empty VMT, and 13% shorter passenger wait times compared to non-optimized baseline. The method bridges a critical gap in ridesharing optimization, aligning with sustainability goals through inherent resource efficiency. For academia, it offers a novel integration of logical compatibility metrics into transportation models, advancing theoretical foundations for sustainable mobility. Practically, it provides ride-hailing firms and urban planners with a scalable tool to reduce operational costs and improve service efficiency. This study supports data-driven strategies for passenger-centric mobility systems that balance demand, capacity, and environmental impact by prioritizing arithmetic alignment.