A Graph-Based Approach to Measuring the Efficiency of an Urban Taxi Service System
A Graph-Based Approach to Measuring the Efficiency of an Urban Taxi Service System
复制标题
DOI：
10.1109/tits.2016.2521862
复制
发表时间：
2016-04
影响因子：
8.5
通讯作者：
Xianyuan Zhan;Xinwu Qian;S. Ukkusuri
中科院分区：
文献类型：
--
作者：
Xianyuan Zhan;Xinwu Qian;S. Ukkusuri
由于出租车司机和乘客之间的互动和自组织，大城市的出租车服务系统非常复杂。效率低下的出租车服务系统导致司机更多的空车和乘客更长的等待时间，并给道路网带来不必要的拥堵。在本文中，我们使用真实的大规模出租车出行数据来调查出租车服务系统的效率水平。通过假设一个全系统推荐系统，提出了两种方法来寻找理论上的最优策略，使空行成本和满足所有观察到的出行所需的出租车数量最小。将优化问题转化为等价的图问题，并用多项式时间算法进行求解。利用纽约市出租车出行数据，定量考察了当前系统性能与理论上最优系统之间的差距。数值结果表明，如果出租车司机和乘客之间共享系统范围内的信息，则可以根据不同的目标减少总空行成本的60%-90%，并且三分之一的出租车需要为所有观察到的出行提供服务。出租车司机之间破坏性竞争的存在也在实际的出租车服务系统中暴露出来。巨大的性能差距表明，在设计出租车推荐系统时，迫切需要重新考虑系统。
Taxi service systems in big cities are immensely complex due to the interaction and self-organization between taxi drivers and passengers. An inefficient taxi service system leads to more empty trips for drivers and longer waiting time for passengers and introduces unnecessary congestion on the road network. In this paper, we investigate the efficiency level of the taxi service system using real-world large-scale taxi trip data. By assuming a hypothetical system-wide recommendation system, two approaches are proposed to find the theoretical optimal strategies that minimize the cost of empty trips and the number of taxis required to satisfy all the observed trips. The optimization problems are transformed into equivalent graph problems and solved using polynomial time algorithms. The taxi trip data in New York City are used to quantitatively examine the gap between the current system performance and the theoretically optimal system. The numerical results indicate that, if system-wide information between taxi drivers and passengers was shared, it is possible to reduce 60%-90% of the total empty trip cost depending on different objectives, and one-third of all taxis required to serve all observed trips. The existence of destructive competition among taxi drivers is also uncovered in the actual taxi service system. The huge performance gap suggests an urgent need for a system reconsideration in designing taxi recommendation systems.