« search calendars« 12th DIMACS Implementation Challenge: Vehicle Routing Problems

« A Novel Repositioning Strategy for Ride-Hailing Problems

A Novel Repositioning Strategy for Ride-Hailing Problems

April 05, 2022, 10:00 AM - 10:20 AM


Online Event

Christian Ackermann, University of Hildesheim

We propose a novel repositioning strategy that is combined with a nearest assignment heuristic to solve the dynamic ride-hailing problem. The service area is divided into multiple overlapping circular zones, representing the potential customer locations that can be reached from a given parking lot within the required pickup time of 5 minutes. For each zone, a demand estimation and a supply calculation are performed. Based on a Poisson distribution, the undersupply probability for each zone can be determined. Combined with the expected reward per request in each zone and the repositioning costs of any available vehicle, strategic repositioning can be performed to balance supply and demand. The results show the effectiveness of the proposed approach, especially for small fleets.

[Challenge Paper]  [Video]