论文标题
一种动态的树算法，用于点对点到对点之间的乘车共享匹配
A Dynamic Tree Algorithm for On-demand Peer-to-peer Ride-sharing Matching
论文作者
论文摘要
创新的共享出行服务提供了按需灵活的移动性选择，并有可能减轻交通拥堵。从不同的角度来看，这些有吸引力的服务具有挑战性。在这样的系统中，一个主要的挑战是在系统目标和约束方面找到驾驶员和乘客之间合适的乘车共享匹配，并为驾驶员提供最佳的接送和下车序列。在本文中，我们开发了一种有效的动态树算法，以找到最佳的拾取和下降序列。该算法找到了问题的初始解决方案，跟踪先前探索的可行解决方案，并在考虑新请求时减少解决方案搜索空间。此外，提出了有效的预处理程序，以选择候选乘客请求，从而进一步改善了算法性能。数值实验是在实际尺寸网络上进行的，以说明我们算法的效率。灵敏度分析表明，小型车辆容量和散落的旅行时间限制不足并不能保证在车辆公里的总体上节省。
Innovative shared mobility services provide on-demand flexible mobility options and have the potential to alleviate traffic congestion. These attractive services are challenging from different perspectives. One major challenge in such systems is to find suitable ride-sharing matchings between drivers and passengers with respect to the system objective and constraints, and to provide optimal pickup and drop-off sequence to the drivers. In this paper, we develop an efficient dynamic tree algorithm to find the optimal pickup and drop-off sequence. The algorithm finds an initial solution to the problem, keeps track of previously explored feasible solutions, and reduces the solution search space when considering new requests. In addition, an efficient pre-processing procedure to select candidate passenger requests is proposed, which further improves the algorithm performance. Numerical experiments are conducted on a real size network to illustrate the efficiency of our algorithm. Sensitivity analysis suggests that small vehicle capacities and loose excess travel time constraints do not guarantee overall savings in vehicle kilometer traveled.
