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

Optimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems Using Greatest Common Divisor 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 Research Article Optimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems Using Greatest Common Divisor 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-8008306/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 passenger group sizes and vehicle capacities. Traditional approaches prioritize spatial or temporal factors but neglect structural relationships inherent in passenger group-vehicle matching. This study introduces the Greatest Common Divisor (GCD) method, a novel framework leveraging number-theoretic principles to optimize resource allocation. The GCD-based method addresses PGVA problem by decomposing passenger group sizes and vehicle capacities into prime factors, ensuring mathematically rigorous compatibility while minimizing wasted capacity and computational complexity. Under the tested simulation conditions, the GCD-based method demonstrated superior performance in reducing eVMT and VMT compared to the benchmark algorithms. It significantly reduced empty and total vehicle miles travelled by over 70% and 85% respectively, compared to the Hungarian algorithm, while avoiding the inefficiencies of a first-come-first-served strategy. The GCD-based compatibility score successfully encodes the qualitative notion of a “good fit”, leading to more efficient resource utilization and directly contributing to the model’s performance. While relatively computationally more intensive, the proposed GCD-based model solves problems of realistic scale within a timeframe that is practical for operational deployment in modern ride-sharing platforms. The method bridges a critical gap in ridesharing optimization and aligns with sustainability goals through inherent resource 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 Applied Mathematics Operations Research Mechanical Engineering Ridesharing Greatest common divisor Hungarian algorithm Ride allocation optimization First-come-first-serve 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-8008306","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":538575894,"identity":"d286cd58-4450-433e-8163-5f611b5a9e34","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":"","institution":"Allgemeine Vehicle Services Ltd","correspondingAuthor":true,"prefix":"","firstName":"Emmanuel","middleName":"","lastName":"Gbey","suffix":""},{"id":538575895,"identity":"445c68d1-230b-43f2-8dbe-b7bd1bbda3b7","order_by":1,"name":"Charles Atombo","email":"","orcid":"","institution":"Ho Technical University","correspondingAuthor":false,"prefix":"","firstName":"Charles","middleName":"","lastName":"Atombo","suffix":""}],"badges":[],"createdAt":"2025-11-02 01:30:12","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-8008306/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8008306/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":95223219,"identity":"96c22ac5-88f5-494e-9d0b-893e6c2754f4","added_by":"auto","created_at":"2025-11-05 16:21:51","extension":"docx","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":2008673,"visible":true,"origin":"","legend":"","description":"","filename":"ManuscriptfinalR2.docx","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/6200116d58d888d0df0c2925.docx"},{"id":95068942,"identity":"aca2dc08-cc28-43e9-9268-56d7cb95afc0","added_by":"auto","created_at":"2025-11-04 02:36:45","extension":"json","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":342,"visible":true,"origin":"","legend":"","description":"","filename":"rs8008306.json","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/e31b9518df398ff4e18b1c3b.json"},{"id":95068949,"identity":"f1437a9e-6923-4b1e-bc7f-5265fcd66b2d","added_by":"auto","created_at":"2025-11-04 02:36:45","extension":"xml","order_by":2,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":144385,"visible":true,"origin":"","legend":"","description":"","filename":"rs80083060enriched.xml","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/8a6177405df406f831419057.xml"},{"id":95223402,"identity":"7baf4d89-9340-4ed0-bac1-18629230ab69","added_by":"auto","created_at":"2025-11-05 16:22:12","extension":"png","order_by":3,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":535720,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/ad53ba6980710e64eb60bd8d.png"},{"id":95068952,"identity":"2c98cdf7-1ecd-475a-adea-681ef95f892e","added_by":"auto","created_at":"2025-11-04 02:36:46","extension":"png","order_by":4,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":561275,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage2.png","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/10a946be30eb0bf941f888e8.png"},{"id":95223416,"identity":"c3bd592a-68d8-44fb-8be6-5d399907cbf8","added_by":"auto","created_at":"2025-11-05 16:22:13","extension":"jpeg","order_by":5,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":192265,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage3.jpeg","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/162e3dfa83fe7a658ffd872b.jpeg"},{"id":95068945,"identity":"92761d47-ea20-4f47-b470-7c1a7a2f98c6","added_by":"auto","created_at":"2025-11-04 02:36:45","extension":"png","order_by":6,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":174440,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage4.png","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/b823babc7f53b87bc951710c.png"},{"id":95222852,"identity":"3db1a991-4fdf-4576-93c4-cecaa99b96c1","added_by":"auto","created_at":"2025-11-05 16:21:15","extension":"png","order_by":7,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":103907,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/a8f4dd2344351bba0e6941d2.png"},{"id":95068948,"identity":"92792ffa-8a88-4a56-b4f6-0964cef473f9","added_by":"auto","created_at":"2025-11-04 02:36:45","extension":"png","order_by":8,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":128593,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage2.png","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/76d4f8da72ea52cda5155c1c.png"},{"id":95222935,"identity":"3f81f1a3-15e8-457b-afc3-54dc9b175774","added_by":"auto","created_at":"2025-11-05 16:21:23","extension":"png","order_by":9,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":93411,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage3.png","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/220a200b4687bc72218655db.png"},{"id":95068954,"identity":"cf7070ef-8c10-4e7b-a564-d284cbb38cc1","added_by":"auto","created_at":"2025-11-04 02:36:46","extension":"png","order_by":10,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":48129,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage4.png","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/7f46285f098b66424f038bbd.png"},{"id":95068953,"identity":"2511e4c9-12c1-4ef9-931d-843a3d4c002e","added_by":"auto","created_at":"2025-11-04 02:36:46","extension":"xml","order_by":11,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":143536,"visible":true,"origin":"","legend":"","description":"","filename":"rs80083060structuring.xml","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/0680e7470185d7cd876566b3.xml"},{"id":95068950,"identity":"82a452c1-b505-4634-8401-e6fff96e398a","added_by":"auto","created_at":"2025-11-04 02:36:45","extension":"html","order_by":12,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":160389,"visible":true,"origin":"","legend":"","description":"","filename":"earlyproof.html","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1/ba9c9fa60b6d7324cafadee5.html"},{"id":95229970,"identity":"2527b1c7-bf6d-4b9d-8f60-3d40a0f23222","added_by":"auto","created_at":"2025-11-05 16:36:46","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":975863,"visible":true,"origin":"","legend":"","description":"","filename":"ManuscriptfinalR2.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8008306/v1_covered_6bca29a9-96d9-46a2-abe3-a743eabafda5.pdf"}],"financialInterests":"The authors declare no competing interests.","formattedTitle":"\u003cp\u003eOptimizing Taxi-Passenger Group Assignment in Ride-Sharing Systems Using Greatest Common Divisor Approach\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":false,"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, Greatest common divisor, Hungarian algorithm, Ride allocation optimization, First-come-first-serve, Vehicle utilization","lastPublishedDoi":"10.21203/rs.3.rs-8008306/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8008306/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 passenger group sizes and vehicle capacities. Traditional approaches prioritize spatial or temporal factors but neglect structural relationships inherent in passenger group-vehicle matching. This study introduces the Greatest Common Divisor (GCD) method, a novel framework leveraging number-theoretic principles to optimize resource allocation. The GCD-based method addresses PGVA problem by decomposing passenger group sizes and vehicle capacities into prime factors, ensuring mathematically rigorous compatibility while minimizing wasted capacity and computational complexity. Under the tested simulation conditions, the GCD-based method demonstrated superior performance in reducing eVMT and VMT compared to the benchmark algorithms. It significantly reduced empty and total vehicle miles travelled by over 70% and 85% respectively, compared to the Hungarian algorithm, while avoiding the inefficiencies of a first-come-first-served strategy. The GCD-based compatibility score successfully encodes the qualitative notion of a \u0026ldquo;good fit\u0026rdquo;, leading to more efficient resource utilization and directly contributing to the model\u0026rsquo;s performance. While relatively computationally more intensive, the proposed GCD-based model solves problems of realistic scale within a timeframe that is practical for operational deployment in modern ride-sharing platforms. The method bridges a critical gap in ridesharing optimization and aligns with sustainability goals through inherent resource 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 Using Greatest Common Divisor Approach","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-11-04 02:36:41","doi":"10.21203/rs.3.rs-8008306/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":"November 4th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":57282169,"name":"Civil Engineering"},{"id":57282170,"name":"Applied Mathematics"},{"id":57282171,"name":"Operations Research"},{"id":57282172,"name":"Mechanical Engineering"}],"tags":[],"updatedAt":"2025-11-04T02:36:41+00:00","versionOfRecord":[],"versionCreatedAt":"2025-11-04 02:36:41","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8008306","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8008306","identity":"rs-8008306","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}