Scalable real-time ride-sharing with meeting points for flexible on-demand public transportation

Gökay, Sevket; Jarke, Matthias (Thesis advisor); Walther, Grit (Thesis advisor)

Aachen : RWTH Aachen University (2021)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2021

Abstract

The landscape of personal transportation is colorful and ever-changing. Even though personal transportation modes can generally be categorized as private and public, many intermediate forms exist by selecting and combining aspects. In this sense, ride-sharing — a member of the on-demand transportation family — sits in between, since it can transport multiple passengers with similar journeys in the same vehicle, but is also flexible and convenient, since passengers can determine time and location parameters of their rides. Therefore, we believe that it has a potential that is yet to receive enough attention. This work explores real-time ride-sharing by addressing issues that might hinder the realization of its potential. After the introduction of the underlying theoretical research problem, Dial-a-Ride Problem (DARP), we examine the research on it. Depending on the real-world requirements, DARP can take many forms with growing diversity of constraints and features. We present the variants, models, objective functions and solution approaches. Consequently, we take a look at the practical applications and identify the research gap. Based on this acquired knowledge, we target a DARP variant with its implications on the modeling and chosen solution approach. It provides the basis for the subsequent explorations. The initial use case is a small-scale realization: rural areas where the population suffers from the service quality of traditional bus services. Hereby, we propose a dynamic (i.e. flexible, on-demand) bus-like service as an alternative to the traditional bus service, which operates with fixed bus lines, stations and timetables. The evaluation simulates the transportation behaviour in a rural area of Aachen, and then in the small to medium-sized city Ulm. The results indicate that both the providers and the customers might benefit from this alternative. In the next step, we address the computational scalability issue of the service in large-scale deployments: urban areas with high demand. Route calculation on the road network is a performance bottleneck when processing real-time trip requests and exploring possible trip-vehicle assignments. We present an approach to reduce processing time by employing a trip-vehicle fitness estimation framework that can work with any fitness measure and is self-adjusting through feedback loops. The evaluation uses publicly available New York City taxi trip data and simulates a select subset of trips in a ride-sharing context. The results exhibit significant performance improvement, but also improvements w.r.t. customer satisfaction and vehicle costs. Finally, we investigate the possibility of spatial flexibility of trip requests in order to reduce small detours of vehicles. The approach analyzes historical demand data, calculates hot spots within the operation area depending on the time of the day, and treats them as virtual stations that can move over time. The idea, by design, diminishes customer convenience to a degree, but can be employed in peak-time contexts to merge many location visits with close proximity into one. The evaluation methodology is the simulation-based comparison of this approach with the previous one based on the same data set. The results hint at a significant increase in the number of satisfied trip requests even with a small customer inconvenience without increasing vehicle costs.