  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.
