Ridesharing benefits the economy and the environment. In multi-hop ridesharing, passengers are permitted to switch vehicles within a single trip, extending the flexibility of conventional ridesharing. Nonetheless, vehicle dispatch is a difficult issue in multi-hop ridesharing. We subdivide the vehicle dispatching problem into the vehicle pairing problem and the request selection problem within a vehicle pair. To address these subproblems, we propose a two-stage framework for vehicle pair dispatching. In the initial stage, we model the vehicle pairing problem as a maximum vehicle-vehicle matching problem in a general graph, which differs from the conventional vehicle-request matching problem in a bipartite graph. The vehicle pairing algorithm is proposed to efficiently solve the vehicle pairing problem. In the second stage, we model the request selection problem as a multidimensional knapsack problem (d-KP) and propose an LP-relaxation request selection algorithm with an approximation ratio 1/5. Experiments conducted on a real-world dataset demonstrate the economic benefit of our proposed two-stage framework.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Two-stage Vehicle Pair Dispatch in Multi-hop Ridesharing


    Beteiligte:
    Wei, Xiaobo (Autor:in) / Li, Peng (Autor:in) / Huang, Weiyi (Autor:in) / Liu, Zhiyuan (Autor:in) / Liu, Qin (Autor:in)


    Erscheinungsdatum :

    24.05.2023


    Format / Umfang :

    2235362 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers

    Ma, Tai-Yu / Rasulkhani, Saeid / Chow, Joseph Y. J. et al. | ArXiv | 2018

    Freier Zugriff

    VEHICLE RIDESHARING ASSISTANCE SYSTEM

    TANABE HIROYUKI / SAITO YUJI / KIMURA TORU et al. | Europäisches Patentamt | 2019

    Freier Zugriff

    RIDESHARING SUPPORT SYSTEM, RIDESHARING SUPPORT METHOD, AND RIDESHARING SUPPORT DEVICE

    MORIOKA WATARU | Europäisches Patentamt | 2019

    Freier Zugriff

    Ridesharing management device, ridesharing management method, and program

    FUJIMOTO NAOTOSHI / ITO YO / IWAMOTO SUSUMU et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Ridesharing 1981

    D. W. Wiersig / F. W. Davis / D. A. Burkhalter et al. | NTIS | 1982