提出高效网约车拼车算法与优化框架,显著提升服务率与计算效率。
Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics
- 基于交换启发式设计多轮线性分配算法,提升拼车匹配效率。
- 在曼哈顿真实数据上实现最优服务率,计算时间大幅降低。
- 开源模块化代码库,便于算法扩展与公平对比测试。
按需拼车已成为解决传统网约车效率瓶颈的主流城市交通方案,通过将时空相近的多个乘车请求合并至同一车辆来提升资源利用率。尽管已有多种拼车分配算法被提出,但缺乏公开可复现的实现,难以在统一数据集和目标下进行有效比较。本文介绍了包含多种核心拼车分配算法的网约车仿真器实现,涵盖车辆路径规划与调度重平衡等组件,并开源了高度优化、模块化的 C++ 代码库,支持新算法与功能的快速扩展。此外,我们提出一类基于交换的局部搜索启发式方法,显著提升了现有算法在性能与计算效率间的平衡。在纽约曼哈顿大规模真实数据上的实验表明,所有选中算法表现接近,而新提出的多轮线性分配-循环交换(LA-MR-CE)算法达到当前最优服务率,且计算时间显著减少。深入分析揭示,所有仅依赖即时信息的拼车算法均受限于系统容量瓶颈,引入未来信息可能是突破该性能极限的关键。
原文摘要 · Abstract (English)
On-demand ride-pooling has emerged as a popular urban transportation solution, addressing the efficiency limitations of traditional ride-hailing services by grouping multiple riding requests with spatiotemporal proximity into a single vehicle. Although numerous algorithms have been developed for the Ride-pool Assignment Problem (RAP) -- a core component of ride-pooling systems, there is a lack of open-source implementations, making it difficult to benchmark these algorithms on a common dataset and objective. In this paper, we present the implementation details of a ride-pool simulator that encompasses several key ride-pool assignment algorithms, along with associated components such as vehicle routing and rebalancing. We also open-source a highly optimized and modular C++ codebase, designed to facilitate the extension of new algorithms and features. Additionally, we introduce a family of swapping-based local-search heuristics to enhance existing ride-pool assignment algorithms, achieving a better balance between performance and computational efficiency. Extensive experiments on a large-scale, real-world dataset from Manhattan, NYC reveal that while all selected algorithms perform comparably, the newly proposed Multi-Round Linear Assignment with Cyclic Exchange (LA-MR-CE) algorithm achieves a state-of-the-art service rate with significantly reduced computational time. Furthermore, an in-depth analysis suggests that a performance barrier exists for all myopic ride-pool assignment algorithms due to the system's capacity bottleneck, and incorporating future information could be key to overcoming this limitation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。