Optimal Route Assignment in Large Scale Micro-Simulations

Michael Balmer, Torben Edelhoff, Rolf H. Möhring, and Heiko Schilling

submitted to TRB

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]