DInAMO
Project: Data-driven Intermodal Autonomous Mobility: Operations and strategic control
Collaborating Departments: Business Analytics & Intelligent Systems (TUM); Department of Computing (Imperial)
Transportation systems face unprecedented challenges due to rising congestion, users’ dissatisfaction, pollution, and health risks. Simultaneously, the advent of autonomous vehicles, big data, and sharing economies provide remarkable opportunities to tackle these challenges through novel mobility paradigms. Intermodal autonomous mobility on demand (AMoD) systems – fleets of robot-taxis servicing travel demand jointly with public transport – are a promising solution to achieve sustainable mobility, as they combine the high-efficiency of public transport with fine-grained services of robot-taxis. However, realizing such systems hinges crucially on developing innovative mathematical tools and algorithms for the joint operation of robot-taxis and public transport. Our research combines recent advances in learning theory and big data with classical approaches in optimal control, operations research and game theory.
One project of our research is the exploration of Autonomous Mobility-on-Demand (AMoD) systems integrated with public transportation from a systematic optimization perspective. The framework uses a multi-commodity network flow model and column generation algorithms to efficiently manage large passenger volumes and congested networks. The other project studies an exact algorithm for the second-best toll pricing in multi-stakeholder transportation systems, in which a central authority designs road pricing schemes to manage traffic congestion. The focus is on using tolls from game theory to influence customer choices and optimize system performance. Through a combination of optimal control, game theory, and operations research, we are committed to redefining the future of urban mobility, making it more sustainable, efficient, and responsive to the needs of modern cities.
Our first project, "Integration of Public Transportation and Autonomous Mobility-on-Demand Systems with Congestion-Aware Modeling and Efficient Rounding," presents an algorithmic framework for optimizing passenger routings in intermodal transportation systems. This study uses a partially time-expanded digraph and column generation algorithms for solving large instances.We simplify the integration of a nonlinear congestion model into the optimization process by transforming it into a linear form. Rapid-costed and randomized rounding techniques further speed up the optimization process. Our Munich case study exemplifies our methods' potential to address real-world transportation inefficiencies, significantly reducing traffic congestion and passenger travel time, and enhancing overall societal benefits.
Our second project, “An Exact Algorithm to the Second-best Toll Pricing Problem”, is a bilevel optimization program in which a central authority designs road pricing schemes to manage traffic congestion. In SBTP, the aim is to identify the optimal tolls for a user-specified subset of roads. Unlike the celebrated marginal cost toll mechanism, SBTP is more realistic and feasible. Nonetheless, computational challenges severely limit the solution of the resulting program, which remains NP-hard even when there are only two origin-destination pairs and for which no exact algorithm has been developed. Our work fills this gap and proposes an exact branch-and-cut algorithm. The effectiveness of our solution approach is evaluated using the widely used Sioux Falls dataset.
Team
Principal Investigator (Imperial)
Dr. Dario Paccagnan
Lecturer in Department of Computing | Imperial
Principal Investigator (TUM)
Prof. Maximilian Schiffer
Professorship for Operations and Supply Chain Management.
Doctoral Candidate (Imperial)
Onur Demiray