In this paper, we study the challenging problem of how to balance taxi distribution across a city in a dynamic ridesharing service. First, we introduce the architecture of the dynamic ridesharing system and formally define the performance metrics indicating the efficiency of the system. Then, we propose a hybrid solution involving a series of algorithms: the Correlated Pooling collects correlated rider requests, the Adjacency Ride-Matching based on Demand Learning assigns taxis to riders and balances taxi distribution locally, the Greedy Idle Movement aims to direct taxis without a current assignment to the areas with riders in need of service. In the experiment, we apply city-scale data sets from the city of Chicago and complete a case study analyzing the threshold of correlated rider requests and the average online running time of each algorithm. We also compare our hybrid solution with multiple other methods. The results of our experiment show that our hybrid solution improves customer serving rate without increasing the number of taxis in operation, allows both drivers to earn more and riders to save more per trip, and all with a small increase in calling and extra trip time.
翻译:在本文中,我们研究了如何在动态搭车服务中平衡城市间出租车分配的棘手问题。首先,我们引入了动态搭车共享系统的架构,并正式定义了显示系统效率的性能衡量标准。然后,我们提出了一个包含一系列算法的混合解决方案: " 相关搭载 " 收集了相关驾驶员请求, " 基于需求学习的 " 相配搭配 " 收集了相关驾驶员请求, " 基于需求学习的 " 匹配 " 分配了出租车司机的出租车,平衡了出租车的当地分配, " 贪婪的游轮运动 " 的目标是将出租车直接派到需要司机的地区,而没有当前指派给需要司机的地区。在实验中,我们采用了芝加哥市的市级数据集,并完成了分析相关驾驶员请求的门槛和每种算法的平均在线运行时间的案例研究。我们还将我们的混合解决方案与其他多种方法进行了比较。我们的实验结果表明,我们的混合解决方案提高了客户服务率,但不会增加运行中的出租车数量,使司机和骑车者都能节省每次行程,而且都小幅增加出程时间。