论文标题
高峰旅行期间的动态乘车共享
Dynamic Ridesharing in Peak Travel Periods
论文作者
论文摘要
在本文中，我们研究了动态乘车问题问题的变体，以特定的重点关注高峰时段：鉴于一组驱动程序和骑手请求，我们的目标是通过实现两个目标来使驱动程序与每个骑手请求匹配：最大化服务率并最大程度地减少额外的距离，并受到一系列时空限制的约束。我们的问题可以在三个方面与现有工作区分开：（1）以前的工作没有完全探讨骑手请求数量远大于可用驱动程序数量的高峰旅行期的影响。 （2）现有的解决方案通常依赖于单个目标优化技术，例如最大程度地减少总旅行成本。 （3）评估整体系统性能时，应合并用于更新驾驶员的行程时间表上的运行时，应合并，而大多数现有解决方案将其排除在外。我们提出了一个索引结构，以及一组修剪规则和有效的算法，将新车手纳入驾驶员现有的旅行时间表中。为了有效地回答新的骑手请求，我们提出了两种算法，将驱动程序与骑手请求匹配。最后，我们对大规模测试收集进行了广泛的实验，以验证所提出的方法。
In this paper, we study a variant of the dynamic ridesharing problem with a specific focus on peak hours: Given a set of drivers and rider requests, we aim to match drivers to each rider request by achieving two objectives: maximizing the served rate and minimizing the total additional distance, subject to a series of spatio-temporal constraints. Our problem can be distinguished from existing work in three aspects: (1) Previous work did not fully explore the impact of peak travel periods where the number of rider requests is much greater than the number of available drivers. (2) Existing solutions usually rely on single objective optimization techniques, such as minimizing the total travel cost. (3) When evaluating the overall system performance, the runtime spent on updating drivers' trip schedules as per incoming rider requests should be incorporated, while it is excluded by most existing solutions. We propose an index structure together with a set of pruning rules and an efficient algorithm to include new riders into drivers' existing trip schedule. To answer new rider requests effectively, we propose two algorithms that match drivers with rider requests. Finally, we perform extensive experiments on a large-scale test collection to validate the proposed methods.
