Optimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems Using Greatest Common Divisor Approach

Gbey, Emmanuel; Atombo, Charles · 2025 · Crossref

DOI: 10.21203/rs.3.rs-8008306/v1

archive: archived pipeline: cataloged verified

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

Summary

This study addresses the Passenger Group-Vehicle Allocation (PGVA) problem in ride-sharing systems, aiming to optimize the assignment of passenger groups to vehicles to enhance efficiency and reduce operational costs. The authors identify a critical gap in existing methods, which often prioritize spatial or temporal factors while neglecting the arithmetic compatibility between passenger group sizes and vehicle capacities. Traditional approaches, such as First-Come-First-Served (FCFS), greedy algorithms, and linear or integer programming, are criticized for either yielding suboptimal results or suffering from high computational complexity. To resolve this, the paper introduces a novel Greatest Common Divisor (GCD)-based Mixed Integer Linear Programming (MILP) framework that leverages number-theoretic principles to ensure mathematically rigorous compatibility. The methodology centers on a compatibility score derived from the prime factorization of passenger group sizes and vehicle capacities. This score combines the GCD of the two values with a Jaccard similarity index and a frequency bonus to quantify the "good fit" between a group and a vehicle. The optimization model seeks to maximize compatibility-weighted ridership while minimizing empty vehicle-miles traveled (eVMT), total vehicle-miles traveled (VMT), and passenger waiting times. The model was implemented in Python using the PuLP library and evaluated through a simulation framework involving 150 vehicles and 300 passenger groups. Passenger locations were generated using a Beta distribution to mimic urban clustering, with group sizes and vehicle capacities sampled from realistic categorical distributions. The GCD-based method was benchmarked against FCFS heuristics and the Hungarian algorithm across 30 independent iterations. The results demonstrate that the GCD-based method significantly outperforms the benchmark algorithms. Compared to the Hungarian algorithm, the proposed approach reduced empty vehicle-miles traveled by over 70% and total vehicle-miles traveled by over 85%. It also avoided the inefficiencies inherent in the FCFS strategy. Although the method is computationally more intensive than simple heuristics due to the NP-hard nature of the underlying assignment problem, it solves realistic-scale problems within timeframes practical for operational deployment. The compatibility score successfully encoded qualitative fit into a quantitative metric, leading to superior resource utilization. The significance of this work lies in its introduction of a number-theoretic approach to ride-sharing optimization, bridging a gap in current literature by prioritizing arithmetic alignment over purely spatial matching. The findings suggest that leveraging structural relationships between demand and capacity can lead to substantial reductions in operational costs and environmental impact, such as fuel consumption and carbon emissions. By balancing computational efficiency with rigorous optimization, the GCD-based method offers a scalable solution for modern ride-sharing platforms, supporting data-driven strategies that enhance both system efficiency and passenger satisfaction.

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.

• passenger motion sickness comfort