BalSAM: Balanced and Staggered Routing for Autonomous Mobility on Demand Systems

• Applicant: Professor Dr. Maximilian Schiffer
• Subject Area: Operations Management and Computer Science for Business Administration
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 449261765

Cities worldwide struggle with overloaded transportation systems and related negative externalities: CO2 emissions cause environmental harm; health hazards arise from particulate matter and NOx emissions; and economic harm stems from congestion-induced lost working hours. With the advent of self-driving vehicles and major players operating first pilot fleets, scientists and practitioners envision autonomous mobility-on-demand (AMoD) systems as a viable option to realize sustainable transportation in urban areas. AMoD systems, i.e., a fleet of self-driving cars controlled by a central operator that offers a ride-hailing service, promise to increase the efficiency of today’s ride-hailing services while at the same time being accessible to a larger public as they can be offered at a lower cost. Municipalities, practitioners, and scientists share high hopes that such AMoD systems will contribute significantly to reducing the above-mentioned negative externalities by allowing, among others, for efficient pooling of passenger requests, congestion aware routing, and convenient feeding to public transport lines. However, these improvement potentials can only be unlocked if the respective AMoD system is operated efficiently, which depends heavily on appropriate algorithmic solutions. Against this background, BALSAM develops new state-of-the-art algorithms for request pooling, vehicle to (pooled) request dispatching and rebalancing, as well as balanced routing i.e., distributing vehicle flows over alternative routes, and staggered routing, i.e., purposely delaying request departures from a system perspective while meeting customer time windows. By developing these algorithms, BALSAM contributes to realizing sustainable AmoD systems through increased utilization and reduced congestion. The first phase of BALSAM focused on exploring the interdependencies between the respective planning tasks and scalable algorithms for large-scale offline planning problems. The second phase of BALSAM connects seamlessly with its first phase, but shifts the project’s focus to developing a new state of the art for the related online control problems by developing novel contextual optimization-augmented machine learning (COAML) algorithms that combine machine learning (ML) and combinatorial optimization (CO) to allow for orchestrated decision-making when operating an AMoD system. The project has the potential to lead to a paradigm shift on how to combine ML and CO for online decision-making in contextual multi-stage stochastic optimization for AMoD systems.

• DFG Programme: Research Grants