Algorithm Engineering for Software-Defined Public Transportation (PTaxi: Combining Taxi-sharing and Public Transit)

Mobility plays a pivotal role in our daily lives, enabling con- nectivity with the world. Traffic problems have long been a topic of discussion and remain relevant to this day. One critical issue is traffic congestion, due to the high number of private vehicles, especially dur- ing rush hours. To address this issue, our research focuses on two key solutions: taxi-sharing and public transit. Taxi-sharing, where multiple passengers with different origins and destinations share a taxi, offers the flexibility of on-demand rides while optimizing the number of vehicles on the road. Public transit, on the other hand, leverages well-built in- frastructure, allowing passengers to travel from one station to another on dedicated lanes. With recent technological advances, such as real- time data processing and advanced routing algorithms, it is possible to incorporate multiple modalities of transport within a single trip. Our research targets the multi-modal transportation problem by combining taxi-sharing and public transit to provide users with flexibility while uti- lizing the static public transit network. We focus on a particularly appli- cable scenario, where taxi-sharing is employed at the beginning and end of a public transit journey, connecting users from their exact locations to public transit stations and from public transit stations to their desired destination. To accomplish this, we introduce PTaxi, an algorithm that combines existing state-of-the-art algorithms for taxi-sharing and public transit into a single framework. Although several studies have aimed to achieve this combined mode of transport, most do not calculate exact routes or offer real-time responses. Our project fills this gap by design- ing, developing, and evaluating the PTaxi algorithm to find an optimal multi-modal route.