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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Locality Filtering for Efficient Ride Sharing Platforms


    Beteiligte:
    Tosoni, Francesco (Autor:in) / Ferragina, Paolo (Autor:in) / Marino, Andrea (Autor:in) / Resta, Giovanni (Autor:in) / Santi, Paolo (Autor:in)


    Erscheinungsdatum :

    01.07.2022


    Format / Umfang :

    1748946 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Ride-sharing system and ride-sharing method

    MATSUO YOSHIAKI | Europäisches Patentamt | 2023

    Freier Zugriff

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

    YAN JIAO / QIN ZHIWEI | Europäisches Patentamt | 2020

    Freier Zugriff

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

    SEKI YUSHI / HASHIMOTO RYOKO / TERAHATA KATSUYA et al. | Europäisches Patentamt | 2019

    Freier Zugriff

    RIDE-SHARING SYSTEM AND RIDE-SHARING METHOD

    MATSUO YOSHIAKI | Europäisches Patentamt | 2022

    Freier Zugriff

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

    SEKI YUSHI / HASHIMOTO RYOKO / TERAHATA KATSUYA et al. | Europäisches Patentamt | 2023

    Freier Zugriff