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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Two-stage Vehicle Pair Dispatch in Multi-hop Ridesharing


    Contributors:
    Wei, Xiaobo (author) / Li, Peng (author) / Huang, Weiyi (author) / Liu, Zhiyuan (author) / Liu, Qin (author)


    Publication date :

    2023-05-24


    Size :

    2235362 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    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

    Free access

    VEHICLE RIDESHARING ASSISTANCE SYSTEM

    TANABE HIROYUKI / SAITO YUJI / KIMURA TORU et al. | European Patent Office | 2019

    Free access

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

    MORIOKA WATARU | European Patent Office | 2019

    Free access

    Ridesharing management device, ridesharing management method, and program

    FUJIMOTO NAOTOSHI / ITO YO / IWAMOTO SUSUMU et al. | European Patent Office | 2024

    Free access

    Ridesharing 1981

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