This talk will focus on the problem of finding a routing strategy that maximizes the probability of on-time arrival in a road network with probabilistic edge weights, also known as the stochastic on-time arrival (SOTA) problem. We will explore the SOTA problem from an algorithm engineering perspective and discuss some techniques for improving the computationally tractability of solving it, with the objective of enabling practical applications. Experimental results on models of real-world road networks and data will validate the effectiveness of the proposed strategies.

In the second part of the talk, we will also briefly discuss the problem of fleet management for autonomous or centrally managed Mobility-on-Demand (MoD) systems. While simple algorithms exist for managing these fleets in the case of a single request per vehicle, the problem gets significantly harder as the ability to pool rides is incorporated, which is required to scale these systems effectively. We will explore some approaches for solving the pooling problem and experimentally validate their performance using real-world data from car2go and the NYC taxi dataset.