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

Gbey, Emmanuel Kofi; Atombo, Charles · 2025 · Crossref

DOI: 10.1007/s44257-025-00048-z

archive: archived pipeline: cataloged verified

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

Summary

This paper 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 environmental impact. The authors argue that existing methods, such as First-Come-First-Served (FCFS), greedy algorithms, and traditional linear or integer programming, often fail to account for the arithmetic compatibility between passenger group sizes and vehicle capacities. This oversight leads to suboptimal resource utilization, increased empty vehicle miles traveled (eVMT), and computational inefficiencies, particularly in large-scale, dynamic environments. To bridge this gap, the study 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 involves decomposing passenger group sizes and vehicle capacities into prime factors to compute a compatibility score ($\theta_{ij}$). This score combines the GCD of the group size and vehicle capacity with a Jaccard similarity index and a frequency bonus, creating a multiplicative structure that prioritizes matches with high arithmetic alignment. The optimization model seeks to maximize compatibility-weighted ridership while minimizing eVMT, total vehicle miles traveled (VMT), and passenger waiting times, subject to constraints on vehicle capacity and assignment feasibility. The model was implemented in Python using the PuLP library and evaluated through simulations comparing its performance against benchmark algorithms, including the Hungarian algorithm and FCFS strategies. The results demonstrate that the GCD-based method significantly outperforms traditional approaches under the tested conditions. Specifically, the proposed model reduced eVMT by over 70% and VMT by over 85% compared to the Hungarian algorithm. It also avoided the inefficiencies inherent in FCFS strategies by ensuring that assignments were based on structural compatibility rather than arrival order. Although the method is computationally more intensive than simple heuristics due to the prime factorization process, it solves problems of realistic scale within timeframes practical for operational deployment. The compatibility score effectively encoded the qualitative notion of a “good fit,” leading to superior resource utilization. The significance of this work lies in its introduction of a number-theoretic approach to ridesharing optimization, offering a scalable and provably optimal alternative to complex tree-based or heuristic methods. By prioritizing arithmetic alignment, the method enhances vehicle utilization and reduces operational costs and carbon emissions, aligning with sustainability goals. The study provides a robust framework for data-driven, passenger-centric mobility systems, demonstrating that integrating mathematical compatibility measures can substantially improve the efficiency and environmental performance of shared transportation networks.

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