允许乘客步行至附近点乘车，提升拼车服务效率
Optimizing Ride-Pooling Operations with Extended Pickup and Drop-Off Flexibility
- 让乘客可前往附近点上下车，扩展匹配灵活性
- 在真实城市数据上，多接13%乘客，平均路程减少21%
- 适合优化共享出行平台的调度系统
拼车匹配问题（RMP）是按需拼车服务的核心，需在满足接送延迟、绕路限制和车辆容量等条件下，将车辆与多个需求匹配。现有方法通常假设乘客必须在原地点上下车，忽略了乘客步行至附近点与车辆会合的可能性，从而限制了优化空间。本文提出一种新匹配方法，引入乘客的扩展接送区域。首先设计基于树的算法高效生成可行匹配；其次优化车辆路径，覆盖所有指定接送点，同时最小化总行驶距离；最后采用动态分配策略实现最优匹配。在真实城市出租车数据集上的实验表明，相比领先方案，本方法可使服务请求量提升最多13%，平均行驶距离减少最多21%，证明利用乘客移动灵活性能显著提升拼车服务效率。
原文摘要 · Abstract (English)
The Ride-Pool Matching Problem (RMP) is central to on-demand ride-pooling services, where vehicles must be matched with multiple requests while adhering to service constraints such as pickup delays, detour limits, and vehicle capacity. Most existing RMP solutions assume passengers are picked up and dropped off at their original locations, neglecting the potential for passengers to walk to nearby spots to meet vehicles. This assumption restricts the optimization potential in ride-pooling operations. In this paper, we propose a novel matching method that incorporates extended pickup and drop-off areas for passengers. We first design a tree-based approach to efficiently generate feasible matches between passengers and vehicles. Next, we optimize vehicle routes to cover all designated pickup and drop-off locations while minimizing total travel distance. Finally, we employ dynamic assignment strategies to achieve optimal matching outcomes. Experiments on city-scale taxi datasets demonstrate that our method improves the number of served requests by up to 13\% and average travel distance by up to 21\% compared to leading existing solutions, underscoring the potential of leveraging passenger mobility to significantly enhance ride-pooling service efficiency.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。