A distributed algorithm for operating large-scale ridesourcing systems
A distributed algorithm for operating large-scale ridesourcing systems
复制标题
一种用于操作大型约车系统的分布式算法
DOI：
10.1016/j.tre.2021.102487
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Masoud, Neda
中科院分区：
文献类型：
--
作者：
Zhang, Ruolin;Masoud, Neda
随着乘车服务在过去几年中越来越受欢迎，人们对能够实现这些系统实时操作的算法越来越感兴趣。由于乘车外包系统依赖于独立实体来建立市场的供需双方，因此它们已被证明在大都市地区运营得更成功，这些地区对乘车需求高，驾驶员数量多，并且在地理限制区域内发生大量旅行。尽管大都市地区为乘车服务运营提供了合适的生态系统，但缺乏可以实时提供高质量匹配解决方案的方法。为了填补这一空白，本文介绍了一个框架，允许解决大规模的匹配问题，通过解决较小的问题，以分布式的方式。所提出的方法是基于构建近似均匀的集群的行程请求，其中车辆图尔斯形成集群中心。使用纽约出租车数据集，我们将所提出的方法的性能与三个基准方法进行比较，以展示其在解决方案质量和解决方案时间方面的优势。
With ridesourcing services gaining popularity in the past few years, there has been growing interest in algorithms that could enable real-time operation of these systems. As ridesourcing systems rely on independent entities to build the supply and demand sides of the market, they have been shown to operate more successfully in metropolitan areas where there is a high level of demand for rides as well as a high number of drivers, and a large volume of trips occurring within a geographically constrained region. Despite the suitable ecosystem that metropolitan areas offer for ridesourcing operations, there is a lack of methods that can provide high-quality matching solutions in real-time. To fill this gap, this paper introduces a framework that allows for solving the large-scale matching problems by means of solving smaller problems in a distributed fashion. The proposed methodology is based on constructing approximately-uniform clusters of trip requests, where vehicle tours form cluster centers. Using the New York Taxi dataset, we compare the performance of the proposed methodology against three benchmark methods to showcase its advantages in terms of solution quality and solution time.