Number Theory Model Cuts Empty Miles in Simulated Ride-Sharing Fleets

A computational study evaluating urban transportation logistics has demonstrated that applying number-theoretic principles to passenger dispatching significantly reduces unnecessary fleet mileage in simulated ride-sharing operations. Researchers Emmanuel Kofi Gbey and Charles Atombo developed a mathematical allocation framework based on prime factorization and greatest common divisor calculations to address the passenger group-to-vehicle allocation problem. Under controlled urban simulation conditions, their proposed model decreased empty vehicle miles traveled by 72.1 percent compared to a traditional first-come-first-served strategy and by 72.2 percent compared to the Hungarian assignment algorithm. Concurrently, total vehicle miles traveled dropped by 61.0 percent relative to first-come-first-served dispatching and by 86.4 percent relative to the Hungarian method. These findings suggest that directly evaluating the arithmetic compatibility between passenger party sizes and vehicle seat capacities provides a robust mechanism for curtailing unproductive travel and operational overhead in automated mobility networks.

The central operational challenge investigated in the study, formally designated as the Passenger Group-Vehicle Allocation problem, involves matching multiple passenger groups of varying numbers and spatial coordinates to an active fleet of vehicles possessing diverse seating capacities. In conventional dispatch platforms such as Uber and Lyft, allocation algorithms frequently struggle to reconcile dynamic demand fluctuations, user behavior complexities, and city-scale transit integration. Standard dispatch heuristics, such as first-come-first-served mechanisms, assign arriving ride requests to the closest available vehicle with sufficient capacity without evaluating broader system-wide efficiency. Similarly, classical greedy algorithms prioritize instantaneous local improvements while overlooking downstream fleet utilization. While linear programming and integer programming provide rigorous analytical frameworks, integer programming models are fundamentally NP-hard, frequently encountering severe computational bottlenecks and combinatorial explosions when scaled to large urban transportation networks.

To overcome these structural limitations, the authors constructed an optimization framework grounded in elementary number theory, arguing that traditional matching schemes prioritize spatial and temporal factors while neglecting arithmetic compatibility. In typical ride-sharing fleets, matching passenger group sizes directly to vehicle capacities presents an integer packability problem. Tree-based algorithms, including branch-and-bound or hierarchical clustering trees, explore extensive combinatorial branches and derive feasibility bounds only after traversing numerous nodes or solving continuous relaxations. In contrast, evaluating the greatest common divisor between passenger demand and vehicle capacity delivers an immediate problem-level feasibility test and lower bound. This mathematical abstraction quantifies whether a passenger party can fully saturate a vehicle’s seating capacity and establishes the minimum unavoidable seat deficit prior to initiating intensive combinatorial searches, thereby compressing the downstream solution space.

The mathematical formulation operates by decomposing passenger group sizes and vehicle capacities into their constituent prime factor trees using a deterministic factorization algorithm. The algorithm divides out powers of two before iteratively testing odd integer divisors up to the square root of the target value, operating within an established computational time complexity of big-O of square root of n. Using these prime factorizations, the authors formulated a composite compatibility metric that couples the base greatest common divisor with structural similarity adjustments. For any given passenger group and vehicle, the compatibility score scales proportionally with the greatest common divisor, which serves as a foundational multiplier representing the maximum number of riders matched without fractional seat waste. This base value is subsequently refined by a similarity multiplier consisting of a baseline integer, a Jaccard similarity index calculated across distinct prime factor sets, and an additive frequency bonus reflecting the count of shared prime factors relative to total factor volume.

This multiplicative compatibility scoring structure prevents low-divisor pairings with superficial structural similarities from outranking higher divisor matches. For example, when comparing a passenger party of four with vehicles seating six and eight passengers, the greatest common divisor for both pairings is two. However, because four and eight share an identical base of two raised to differing powers, the Jaccard index and factor-frequency terms generate a higher composite compatibility score for the eight-seat vehicle. This quantitative bonus reflects a more natural structural fit that preserves four seats of usable residual capacity rather than leaving an awkward two-seat remainder. To eliminate highly incompatible combinations from downstream computation, the model incorporates a binary feasibility threshold set to two, which automatically excludes assignments failing to meet minimal divisor criteria, such as attempting to match a three-passenger group with a five-passenger vehicle.

The complete Passenger Group-Vehicle Allocation model was formalized as a Mixed Integer Linear Programming problem and solved computationally using the open-source PuLP library and the COIN-OR CBC branch-and-cut solver in Python 3.9. The model’s objective function balances four competing operational priorities: maximizing the compatibility-weighted ridership volume while subtracting weighted penalties for empty vehicle miles traveled, overall vehicle miles traveled, and passenger waiting time. Binary decision variables enforce that each passenger group is assigned to at most one vehicle, that active vehicles must not exceed their certified seating limits, and that vehicles cannot take on passenger assignments without being formally activated. Infeasible pairings excluded by the feasibility threshold are set strictly to zero. Furthermore, empty vehicle mileage is linearized through a Big-M formulation linked to remaining unused vehicle capacity, ensuring that surplus empty seating is penalized appropriately during solver execution.

The empirical experimental design evaluated the model across thirty independent simulation iterations representing a dense urban service area. The simulated geography comprised a bounded Euclidean space with a maximum transit radius of 8.0 kilometers, matching empirical operating metrics documented for commercial ride-hailing networks. Passenger origin coordinates and initial vehicle locations were distributed according to a Beta(2, 2) probability distribution scaled across the service area to simulate dense clustering around urban commercial centers. Each experimental run simulated three hundred passenger groups served by a fleet of one hundred and fifty vehicles, establishing an intentionally constrained supply-to-demand ratio of 0.5. Passenger group sizes were sampled from a categorical distribution reflecting real-world travel habits, where solo travelers comprised 65 percent of requests, pairs accounted for 25 percent, and larger parties of three, four, and five represented 8 percent, 1.5 percent, and 0.5 percent, respectively. Fleet capacity was modeled with 80 percent four-seat sedans and 20 percent six-seat larger vehicles.

Experimental outcomes were evaluated across thirty stochastic trials using five primary metrics: total ridership, empty vehicle miles traveled, total vehicle miles traveled, mean waiting duration, and solver runtime. The proposed model was benchmarked directly against the greedy first-come-first-served dispatch baseline and the canonical Hungarian assignment algorithm applied to inverted compatibility scores. The greatest common divisor model recorded a mean empty vehicle travel distance of 6.19 miles, representing a 72.1 percent reduction compared to the 22.21 miles observed under first-come-first-served dispatching and a 72.2 percent reduction relative to the 42.90 miles generated by the Hungarian algorithm. For total vehicle miles traveled, the number-theoretic approach achieved an 86.4 percent reduction against the Hungarian baseline and a 61.0 percent reduction against first-come-first-served. Paired t-tests demonstrated extreme statistical significance across all mileage metrics with p-values of 0.0000 and Cohen’s d effect sizes exceeding 10.0.

Service quality metrics revealed substantial improvements in passenger waiting periods alongside the reductions in vehicle movement. Passengers assigned under the greatest common divisor model experienced an average wait time of 0.35 minutes, representing a 27.1 percent decrease compared to the 0.48-minute wait under first-come-first-served dispatching and an 86.5 percent drop from the 2.59-minute delay recorded under the Hungarian algorithm. These differences were statistically significant with Cohen’s d values exceeding 5.1. The wait-time performance stems directly from the objective function’s distance penalty, which actively discourages assigning distant vehicles to passenger clusters. Conversely, the Hungarian baseline performed poorly across spatial and delay metrics because classical one-to-one assignment structures fail to model capacity constraints and many-to-one passenger groupings, yielding fragmented vehicle paths despite maximizing pairwise compatibility scores.

The study observed an explicit operational trade-off regarding aggregate passenger ridership. The naive first-come-first-served heuristic carried the largest overall volume of travelers, averaging 438.00 passengers per run, whereas the greatest common divisor model served 46.9 percent fewer passengers. Statistical analysis indicated that ridership between the greatest common divisor model and the Hungarian method exhibited no significant difference (t = 0.296, p = 0.7686, Cohen’s d = 0.076). The authors emphasize that higher raw ridership under first-come-first-served dispatching represents an artifact of unconstrained greedy matching that incurs disproportionately severe travel overhead, requiring 3.6 times more empty travel and 2.6 times more total travel. In commercial fleet operations, dispatching an incompatible vehicle over long empty distances to serve marginal demand yields negative operating margins where fuel and wear exceed trip revenue. The optimization model deliberately foregoes low-compatibility, long-distance requests to preserve fleet-wide efficiency.

Computational overhead constitutes the primary practical trade-off associated with the mathematical optimization model. Tested on a standard consumer laptop equipped with an Intel Core i7 processor and 12 gigabytes of RAM under Windows 10, the mixed-integer formulation exhibited an average execution runtime of 6.70 seconds per instance. While polynomial-time heuristics like first-come-first-served and the Hungarian method resolved almost instantaneously in approximately 0.01 and 0.00 seconds respectively, the mixed-integer model remained well within practical limits for real-world rolling dispatch intervals, which typically cycle every 30 to 60 seconds. The solver never approached the designated 300-second operational timeout, demonstrating that prime factor decomposition successfully bounds the combinatorial space to preserve real-time tractability for medium-scale urban fleet coordination.

The authors noted specific methodological limitations that define the scope of their findings. The objective weighting coefficients for empty travel, total travel, and passenger wait times were set to a balanced operational configuration of 0.33, 0.33, and 0.34, respectively, calibrated alongside a static feasibility threshold and empty-mileage penalty. While these parameters demonstrated strong convergence for the modeled urban scenario, their sensitivity under alternative operating strategies—such as pure cost minimization or aggressive service-level guarantees—requires further investigation. Additionally, the experimental wait-time metric utilized a simplified linear distance proxy that does not account for dynamic traffic congestion, signalized intersections, or time-of-day travel variations. Future research directions proposed by the authors include evaluating the model against dynamic datasets with fluctuating urban congestion and exploring how greatest common divisor matching could facilitate multimodal transfers connecting rideshare fleets with scheduled bus and rail networks.

Subject of Research: Optimization of passenger group to vehicle assignment in ride-sharing systems using greatest common divisor and prime factorization

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

Article References: Gbey, E. K., & Atombo, C. (2025). Optimizing passenger group vehicle assignment in ride sharing systems using greatest common divisor approach. Discover Analytics, 3(1), Article 19. https://doi.org/10.1007/s44257-025-00048-z

Image Credits: AI Generated

DOI: 10.1007/s44257-025-00048-z

Keywords: ride-sharing optimization, passenger group vehicle assignment, greatest common divisor, prime factorization, mixed integer linear programming, empty vehicle miles traveled, vehicle miles traveled, urban mobility, Hungarian algorithm, first-come-first-served, PuLP optimization library, COIN-OR CBC solver, capacity utilization, Jaccard similarity, fleet dispatching, shared transit