Ride sharing has a tremendous potential to reduce the number of vehicles needed to serve a certain mobility demand. However, although ride sourcing services have flourished in recent years and are widely available worldwide (e.g. Uber, Didi, Lyft, Via), known ride sharing techniques still suffer severe scalability limitations, especially if the goal is combining multiple on-demand ride requests into a single trip within a large urban area. In the context of on-demand mobility systems, a complete enumeration of all candidate trip requests is unfortunately not a practical approach to find the optimal ride sharing solution. An efficient filtering approach is therefore needed in order to avoid both the storage of quadratic shortest-path lookup tables, as well as the exhaustive pairwise comparison of all mobility requests, with their GPS coordinates and time constraints. In this paper we present a ride sharing algorithm, which combined with the shareability networks method, is able to substantially speed up known approaches while only minimally impacting on the quality of the computed solution. The key building block is a novel locality filter, which allows to build a pruned version of the shareability network more efficiently in time and space than previous works. We corroborate this novel proposal with a large set of experiments executed over a dataset consisting of one month of trip requests (~106) performed in two different urban areas, namely Manhattan (NYC) and Singapore. Our experiments show that our approach achieves a $5\times $ speed-up, or even more during so-called “rush times”, and it is robust under different traffic conditions.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Locality Filtering for Efficient Ride Sharing Platforms


    Contributors:


    Publication date :

    2022-07-01


    Size :

    1748946 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Ride-sharing system and ride-sharing method

    MATSUO YOSHIAKI | European Patent Office | 2023

    Free access

    JOINT ORDER DISPATCHING AND FLEET MANAGEMENT FOR ONLINE RIDE-SHARING PLATFORMS

    YAN JIAO / QIN ZHIWEI | European Patent Office | 2020

    Free access

    RIDE-SHARING ASSISTANCE SYSTEM, RIDE-SHARING ASSISTANCE APPARATUS AND RIDE-SHARING ASSISTANCE METHOD

    SEKI YUSHI / HASHIMOTO RYOKO / TERAHATA KATSUYA et al. | European Patent Office | 2019

    Free access

    RIDE-SHARING SYSTEM AND RIDE-SHARING METHOD

    MATSUO YOSHIAKI | European Patent Office | 2022

    Free access

    Ride-sharing assistance system, ride-sharing assistance apparatus and ride-sharing assistance method

    SEKI YUSHI / HASHIMOTO RYOKO / TERAHATA KATSUYA et al. | European Patent Office | 2023

    Free access