direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 14-2006

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Optimal Route Assignment in Large Scale Micro-Simulations
submitted to TRB
primary: 90C27 Combinatorial optimization
secondary: 90B10 Network models, deterministic
90B20 Traffic problems
90C35 Programming involving graphs or networks
05C85 Graph algorithms
90C59 Approximation methods and heuristics
68W25 Approximation algorithms
37M05 Simulation
graph algorithms, network flow, routing, traffic models, agent-based micro simulation
Traffic management and route guidance are optimization problems by nature. In this article, we consider algorithms for centralized route guidance and discuss fairness aspects for the individual user resulting from optimal route guidance policies. The first part of this article deals with the mathematical aspects of these optimization problems from the viewpoint of network flow theory. We present algorithms which solve the constrained multicommodity minimum cost flow problem (CMCF) to optimality. A feasible routing is given by a flow x, and the cost of flow x is the total travel time spent in the network. The corresponding optimum is a restricted system optimum with a globally controlled constrained or fairness factor . This approach implements a compromise between user equilibrium and system optimum. The goal is to find a route guidance strategy which minimizes global and community criteria with individual needs as constraints. The fairness factor L restricts the set of all feasible routes to the subset of acceptable routes. This might include the avoidance of routes which are much longer than shortest routes, the exclusion of certain streets, preferences for scenic paths, or restrictions on the number of turns to be taken. Most remarkably is that the subset of acceptable routes can also be interpreted as a mental map of routes. ()cx1L> In the second part we apply our CMCF algorithms in a large scale multi-agent transportation simulation toolkit, which is called MATSIM-T. We use as initial routes the ones computed by our CMCF algorithms. This choice of initial routes makes it possible to exploit the optimization potential within the simulation much better then it was done before. The result is a speed up of the iteration process in the simulation. We compare the existing simulation toolkit with the new integration of CMCF to proof our results.
Download as [PDF] [ps.bz2]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe