To meet the Paris climate targets, greenhouse gas emissions in the transport sector must be significantly reduced. In addition to new, lower-emission types of propulsion, a traffic turnaround - away from motorized individual transport to collective public transport - is indispensable. The aim of SynphOnie is to develop a planning method for the integrated multi-criteria optimization of multimodal transport systems including public transport, ridepooling services and individual transport. For the first time
- different modes of transport are optimized as an overall system,
- consider travel time, energy demand, environmental impact and costs simultaneously in a multi-criteria approach, and
- passenger behavior is modeled by means of equilibrium conditions across all transport modes.
This multi-criteria, multi-modal approach allows urban and rural mobility to be realistically represented and a range of solutions to be designed that represent different trade-offs between travel time, energy demand, environmental impact, and cost.
To find such solutions, a two-step process is considered. Building on a coarse model motivated by physics and statistics, in a second step, a fine model using discrete
discrete optimization is used in a second step to design a transport offer consisting of stops, lines, timetable and ridepooling offer. Game-theoretic methods are used in both the coarse model and the fine model to determine
equilibria of the demand between the considered traffic modes are determined in the coarse model as well as in the fine model. Thus, effects such as congestion and ridepool capacity can be included in the modeling.
Foundational questions for dynamic flows in the context of equilibrium conditions are investigated. Several behavioral modes are considered including instantaneous dynamic equilibrium concept and classical dynamic equilibrium. Key questions range from convergence issues regarding possible discretization approaches to efficiency considerations of equilibria. We also address bilevel optimization approaches modeling mechanism design problems for dynamic equilibrium flows.
Strategic acts of sabotage and terrorism pose an increasing threat to important infrastructures and their users. This proposal aims at the design of models and algorithms for multi-level congestion and security games that allow for planning infrastructures that are robust against such attacks. In these models, we take the role of a planner, who in the first level designs the infrastructure, which is represented by a network (e.g., a public transit system or emergency exit ways in a stadium). Then, in the second level, users operate on this infrastructure according to their own selfish interests. Finally, an attacker, observing the distribution of users in the network, strategically attacks the infrastructure so as to cause as much harm as possible (e.g., affecting as many people as possible). Solving the resulting multi-level optimization problems is computationally very challenging, in particular due to non-convexities caused by the multi-level structure. We therefore propose a new concept of level-wise approximation that allows to relax optimality requirements at each level individually. Using this paradigm, we hope to devise algorithms that efficiently compute near-optimal solutions.An additional challenge arises when taking into account the interplay of congestion effects caused by the users’ selfish action and their anticipation of the attacker’s action. An important part of our project therefore is to investigate bilevel congestion games, i.e., congestion games in which users take their choices taking into account both congestion caused by other users and the actions of a lower level attacker who will strike at the most-frequented parts of the infrastructure. Combining the insights gained on approximating multi-level network problems and congestion games, we then aim to solve multi-level network security games with congestion effects using a mix of approximation algorithms, heuristics, and exact methods, which we finally investigate in a study based on realistic data sets.
Resource allocation problems play a key role for a wide range of applications including traffic networks and telecommunication networks. An intrinsic property of the above applications is that the allocation of resources cannotbe centrally enforced but is determined by independent users, each optimizing an individual objective function (e.g., selfish users evacuating a burning building, drivers choosing the fastest route, or routing protocols choosing the least delay path or least congested server). Designing mechanisms so that the resulting allocation of resources by selfish players is efficient constitutes a fundamental research challenge. From an abstract point of view, every resource incurs a cost or a utilityto its users and a mechanism defines the strategies available to players and the cost/utility shares for every player using a specific resource. Concrete examples of such mechanisms include the design of the network infrastructure in telecommunications and traffic. This proposal attempts to advance the algorithmic foundations for computingprovably optimal or approximatively optimal mechanisms in the context of network design, scheduling, and auction-based resource allocation problems.
Location routing integrates the two classical optimization problems of facility location and vehicle routing, addressing both location and tour planning decisions in a single step. There is a large number of different versions of location routing problems, incorporating different sets of constraints arising in real-world applications, such as vehicle and depot capacities or time windows.
NWO Exacte Wetenschappen kent aan 19 wetenschappers in de astronomie, informatica en wiskunde of een combinatie van deze disciplines (multidisciplinair) een TOP-subsidie toe. Acht wetenschappers zijn senior onderzoekers met een bewezen track record, de overige elf zijn junior onderzoekers die aan het begin van hun wetenschappelijke carrière staan. In totaal ontvangen de wetenschappers ruim 6 miljoen euro.
In a resource allocation game, the allocation of resources is determined by a finite number of independent players, each optimizing an individual objective function. Because selfish behavior of players usually leads to inefficient resource allocation with respect to predefined performance measures, the design of protocols as a way to improve the inefficiency of selfish resource allocation is of fundamental importance.
While numerous resource allocation games and corresponding resource allocation protocols have been analyzed in the last decade with respect to various performance indicators, there has been only recently some efforts to design optimal protocols for these indicators (Chen et al.(2008), Harks and von Falkenhausen (2011)).
This project intends to make progress in the design of optimal protocols.
When sociologist Thomas Schelling published his research on housing segregation in major US-American cities in 1971, he accomplished more than just contributing to a novel type of ›social mathematics‹. With Schellings interest in the mechanisms of social segregation and his respective models, the analysis of actual neighborhood dynamics converged with a ›neighborly‹ research method.
Participants: Tobias Harks, Sebastian Vehlken
The goals of the project MultiTrans (Multicriteria Optimization for Transportation Problems in Logistics) were the mathematical modeling of practical transportation problems, the development and analysis of efficient algorithms for the exact and heuristic solution of such optimization problems, and the implementation of the solution approaches in a demonstration software. The results of the research project were a significant reduction of the modeling effort in network optimization and a significant improvement of the optimization result due to the increased realism of the used models.
Congestion collapse on a network of one-way streets. The red cars are those causing the gridlock by stopping in the middle of the intersection, © en.wikipedia.org/wiki/Gridlock. Cooperation Partner Our cooperation partner, theptv AG from Karlsruhe, Germany, is one of Europe's leading traffic software developing companies.
Participants: Tobias Harks, Rolf H. Möhring
The aim of this project is to design, analyze and experimentally evaluate algorithms for fundamental combinatorial optimization problems. A particular focus will be given to optimization problems that arise in the application areas telecommunication, traffic and logistics.
Participants: Tobias Harks, G. Schäfer