Research On Publish/Subscribe For Ride-Sharing Services

Carpooling services means multiple passengers with the same or similar journey travels in the same vehicle.It as a green transport mode has many advantages,such as improving vehicle utilization,relieving traffic pressure,reducing travel cost and protecting the environment,and becoming tremendously popular worldwide.As shown in a recent study^[11],the potential urban traffic reduction can be as high as 59%if users are willing to share a ride with people whose trip patterns are similar,which is equivalent to 8 times of the average daily passengers carried by public transport in China.In general,there are two kinds of carpooling services:1)Ride Sharing^[18][19][32];2)Ride Hitching^[16][34][22].In this paper,we focus on ride hitching.Ride hitching is typically implemented as a publish/subscribe service.Drivers subscribe the ride orders published by riders and continuously receive the ride orders matching their trip plans until one is picked.This paper mainly studies the publish/subscribe carpooling matching algorithm in static and dynamic situations,aiming to improve the online matching efficiency of carpooling service by designing an efficient matching algorithm.The specific contents are summarized as follows:Firstly,in the static publish/subscribe by carpooling scenario,common reality applications such as Grab Hitch^[22],where drivers subscribe queries as ride offers and riders publish ride orders modeled as incessantly arriving stream in the publish/subscribe system.Drivers subscribe the ride requests published by riders and continuously receive the ride orders matching their trip plans until one is picked.Therefore,this paper proposes a static ride hitching algorithm based on publish/subscribe services.Real-time update of multiply matching results from two modules:new ride orders distribution and Top-k maintenance of subscribe queries.Based on carpooling pruning strategy,mixed index construction and buffer establishment,three kinds of carpooling matching algorithms are proposed:individual processing approach,index-based processing approach and optimization algorithm based on two-level buffers.Secondly,in the dynamic publish/subscribe carpooling scenario,the match of ride order and ride requests occurs during the driver's travel.Different from the static carpooling method,the matching result in the dynamic scenario is not only related to the journey of the driver and the passenger,but also related to the real-time position of the driver.The movement of the vehicle position at any time may cause the change of the Top-k results.Therefore,this paper proposes a ride hitching matching algorithm in dynamic publish/subscribe services,which can provide real-time carpooling matching results from two aspects:dynamic ride order distribution and the Top-k order maintain of dynamic subscription.Based on the spatial-temporal relationship of vehicle and ride orders,this paper constructs efficient spatial-temporal pruning and safe regional division strategies,and proposes two kinds of dynamic ride hitching matching algorithms,one based on edge index and the other based on grid index.Finally,a publish/subscribe services simulation experiment is carried out on real data sets.Based on the order data set of NYCTaxi in New York City in March 2017and the order data set of Didi Hitch in Chengdu in January 2016,this paper verifies the performance of the proposed combined ride algorithm.Experimental results show that the proposed combined ride matching algorithm is better than the current mainstream algorithm in terms of solving quality and solving efficiency.