Algorithms for large-scale dynamic ridesharing systems
Urbanization has been leading to a considerable increase in mobility demand causing many urban transportation systems to operate near their capacity limits. As the potential for scaling-up the infrastructure is limited, solutions for a more efficient utilization of existing resources need to be developed. A possibility for mitigating the strain on urban infrastructures while preserving the beneﬁts of individual mobility are transport services which leverage on the growing availability of pervasive real-time information. An example of such individualized services is real-time ridesharing which includes different variants such as peer-to-peer ride sharing, taxi sharing and smart on-demand buses.
A key challenge common to all variants of real-time ridesharing is maximizing the capacity utilization of vehicles while minimizing the inconvenience resulting from detours. This is particularly challenging in large-scale systems with high tempo-spatial dynamics of transportation demand and supply (N. Agatz et al., 2012). The purpose of this work therefore is to develop practically feasible solutions for the operation of large-scale ridesharing systems. Crucial components of such solutions are algorithms which match multiple passengers to share a ride. These algorithms need to consider the passengers' origins and destinations with the objective of minimizing vehicle detours. At the same time, inconvenience constraints such as waiting and travel time need to be taken into consideration. In a large-scale system, the combinatorial complexity of possible solutions is extremely large, making it difficult to identify good matches in a reasonable time. Addressing this issue therefore requires reducing the size of the space in which the algorithm searches for feasible solutions. Addressing this issue therefore requires reducing the size of the space in which the algorithm searches for feasible solutions.
We recently developed a concept which addresses this issue (illustrated in video below). This is done by partitioning the road network into distinct regions in which the probability for finding feasible matches is high. The search space of the algorithm can then be constrained to these partitions. This allows performing the ride matching on the scale of an entire mega-city in real-time.
In a case study, we used SEMSim to assess the improvements of transport system performance which could be achieved through shared mobility in Singapore. The investigated setting consisted of a dynamic taxi sharing problem with about 110,000 daily trips. By allowing up to two passengers to share a ride, the number of trips could be reduced by 42%. Overall, this resulted in a reduction of total daily system mileage by 230,000 km. This case study indicates that a more intelligent allocation of transport resources could have a considerable impact on both traffic flow and emissions. This concept is discussed in more detail in (D. Pelzer et al., 2015) . Based on these findings, the effect of larger vehicle capacities including the investigation of smart buses will be subject to future work