Improving Vehicle Detour in Dynamic Ridesharing using Transfer Stops

Ridesharing companies like Uber or Lyft provide an alternative to classic public transport, in which you can order a ride from anywhere to anywhere within the service area via an app. A vehicle will be assigned to you, pick you up and drive you to your destination. In services like UberXShare or LyftShared, other passengers might also be picked up on the way, causing a small detour. The process of matching your ridesharing request to some vehicle in the set of available vehicles is resolved using a dispatching algorithm.

Buchhold et al. in [3] developed the dispatching algorithm LOUD for the dynamic ridesharing scenario. It is able to find the optimal solution to a ridesharing request (based on a given cost function) in only a few milliseconds on realistically sized scenarios. In this thesis, we aim to add transfer stops to ridesharing by extending the LOUD-algorithm. We present multiple transfer-dispatching algorithms and implement and evaluate each of these algorithms thoroughly, analyzing their runtime performance and dispatching quality on various different scenarios.

Our best algorithm, where transfer vertices are sampled by betweenness, is able to find a better solution to a ridesharing request than LOUD in up to 20% of all requests, while only increasing the required runtime by about one order of magnitude. ... mehrFurthermore, we are able to show that multi-transfer routes can bring substantial improvements over no- or one-transfer-routes on long-distance requests, and we show that runtime performance scales well with the number of requested transfer stops.