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

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.