In rider demand responsive systems riders submit requests to demand transit services and the incoming requests and vehicles are matched by the system. This demand-responsive transport problem is viewed by existing research as a kind of spatial matching problem between vehicles and riders. However, existing schemes mainly focus on maximizing the number of matching pairs. It neglects other factors like the length of pickup trajectories and riders’ waiting time. And the matching is not revocable, which loses the chance for further optimizations. Moreover, there is still not much work on handling and matching the appointment-based requests that play a key role in the demand-responsive transport market. In this article, we propose an algorithm called BMCF (Bipartite Minimal-Cost Flow) to solve the taxi-rider matching problem with appointment-based rider requests on a time-dependent road network. Unlike existing solutions that map the problem into the max flow problem, we transform the optimal matching to a minimal cost flow problem which aims to maximize a utility value and could be solved efficiently. Riders and vehicles are modeled as vertices in a bipartite graph, and factors like the length of pickup trajectories, riders’ waiting time, etc. are abstracted as utilities and denoted as weights of the edges which are taken into account during the matching process. To the best of our knowledge, the proposed scheme is the first to efficiently integrate and process both the real-time and appointment-based requests within the same framework, and the assignments between vehicles and requests could be dynamically adjusted and revoked to maximise the overall utility. Experimental results show that the proposed algorithm can effectively increase the appointment-based matching ratio and decrease the riders’ waiting time (> 10.4%) and vacant vehicles’ picking up time (> 60.9%) compared with existing schemes, while at the cost of acceptable increase on the running time.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Utility-Based Matching of Vehicles and Hybrid Requests on Rider Demand Responsive Systems


    Contributors:
    Lai, Yongxuan (author) / Yang, Shipeng (author) / Xiong, Anshu (author) / Yang, Fan (author) / Li, Lei (author) / Zhou, Xiaofang (author)


    Publication date :

    2022-02-01


    Size :

    3004365 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    RIDER-POWERED VEHICLES AND MECHANISMS THEREOF

    BEZZERA WILSON X / BEZERRA SILVANA A / NAGY GABOR | European Patent Office | 2017

    Free access

    Systems and methods for matching transportation requests to personal mobility vehicles

    WHITT CARLOS ELLIS / MARTISAUSKAS STEVEN JAMES / LEVI DOR | European Patent Office | 2021

    Free access

    ENHANCED RIDER PAIRING FOR AUTONOMOUS VEHICLES

    GAO SHENGLONG / KOSITSKY ISRAEL MARC / HUKKERI RAMADEV BURIGSAY et al. | European Patent Office | 2022

    Free access

    RIDER-POWERED VEHICLES AND MECHANISMS THEREOF

    BEZERRA SILVANA A / NAGY GABOR / BEZERRA WILSON X | European Patent Office | 2019

    Free access