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

Optimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems: A Prime Factorization and Greatest Common Divisor (GCD) Approach | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Method Article Optimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems: A Prime Factorization and Greatest Common Divisor (GCD) Approach Emmanuel Gbey, Charles Atombo This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6520660/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version 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 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. Civil Engineering Ridesharing prime factor tree Hungarian algorithm ride allocation optimization logical compatibility vehicle utilization Full Text Additional Declarations The authors declare no competing interests. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-6520660","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Method Article","associatedPublications":[],"authors":[{"id":447463338,"identity":"1edfd99d-5fb9-4ce4-99f6-4ab2e7445ad5","order_by":0,"name":"Emmanuel Gbey","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA5UlEQVRIiWNgGAWjYDACCTiL+QCIK0OKFrYEEJeHFC08BmCSoA756OZjEgwV26L5Z/d8fnWjxoKHgf3w0Q34tBjeOZYmwXDmdu6MO2e3WeccAzqMJy3tBl4tM3LMJBjbbuc23MjdZpzDBtQiwWNGQEv+NwnGf7dz59/IeWac848ILfISQJMZG27nbriRw/w4t40ILQYyx4wtEo7dzt14I82MObdPgoeNkF/kZzc/vPGh5nbuvBvJjz/nfKuT42c/fAy/LQcYWCQSIGw2cByx4VMOtqWBgfkDlA1njIJRMApGwShAAQDyFkuGfn+T7gAAAABJRU5ErkJggg==","orcid":"https://orcid.org/0000-0002-9573-6744","institution":"Allgemeine Vehicle Services Ltd","correspondingAuthor":true,"prefix":"","firstName":"Emmanuel","middleName":"","lastName":"Gbey","suffix":""},{"id":447463406,"identity":"8d9012a4-ae94-4a49-a599-1f169388fd78","order_by":1,"name":"Charles Atombo","email":"","orcid":"","institution":"Ho Technical University","correspondingAuthor":false,"prefix":"","firstName":"Charles","middleName":"","lastName":"Atombo","suffix":""}],"badges":[],"createdAt":"2025-04-24 12:12:50","currentVersionCode":1,"declarations":{"humanSubjects":false,"vertebrateSubjects":false,"conflictsOfInterestStatement":false,"humanSubjectEthicalGuidelines":false,"humanSubjectConsent":false,"humanSubjectClinicalTrial":false,"humanSubjectCaseReport":false,"vertebrateSubjectEthicalGuidelines":false},"doi":"10.21203/rs.3.rs-6520660/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6520660/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":81696002,"identity":"b528df21-46c9-4e62-a6b4-3f0567daa8f1","added_by":"auto","created_at":"2025-04-30 12:09:00","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":874082,"visible":true,"origin":"","legend":"","description":"","filename":"Manuscript23042025.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6520660/v1_covered_88a8fdfd-04ec-43d3-82be-d5ddf6c3fb60.pdf"}],"financialInterests":"The authors declare no competing interests.","formattedTitle":"\u003cp\u003e\u003cstrong\u003eOptimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems: A Prime Factorization and Greatest Common Divisor (GCD) Approach\u003c/strong\u003e\u003c/p\u003e","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":true,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Ridesharing, prime factor tree, Hungarian algorithm, ride allocation optimization, logical compatibility, vehicle utilization","lastPublishedDoi":"10.21203/rs.3.rs-6520660/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6520660/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eWith 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\u0026mdash;prime factorization and greatest common divisor (GCD)\u0026mdash;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.\u003c/p\u003e","manuscriptTitle":"Optimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems: A Prime Factorization and Greatest Common Divisor (GCD) Approach","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-04-25 05:05:14","doi":"10.21203/rs.3.rs-6520660/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"c77603ef-1b9c-4629-897b-e44ccd3d04cc","owner":[],"postedDate":"April 25th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":47628479,"name":"Civil Engineering"}],"tags":[],"updatedAt":"2025-09-07T21:36:20+00:00","versionOfRecord":[],"versionCreatedAt":"2025-04-25 05:05:14","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-6520660","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6520660","identity":"rs-6520660","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}