direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 658-1999

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
Optimal Routing of Traffic Flows with Length Restrictions in Networks with Congestion
Authors
Publication
to appear in Proceedings of the Symposium on Operations Research, Magdeburg, 1999, (SOR 99)
Classification
MSC:
primary: 90C35 Programming involving graphs or networks
secondary: 90B20 Traffic problems
90C25 Convex programming
90C27 Combinatorial optimization
90C90 Applications of mathematical programming
Keywords
Frank-Wolfe, Dantzig-Wolfe, Traffic Flows, Route Guidance, Traffic Routing, System Optimum, Constrained Shortest Path Problem, Multicommodity Flow
Abstract
When traffic flows are routed through a road network it is desirable to minimize the total road usage. Since a route guidance system can only recommend paths to the drivers, special care has to be taken not to route them over paths they perceive as too long. This leads in a simplified model to a nonlinear multicommodity flow problem with constraints on the available paths. In this article an algorithm for this problem is given, which combines the convex combinations algorithm by Frank and Wolfe with column generation and algorithms for the constrained shortest path problem. Computational results stemming from a cooperation with DaimlerChrysler are presented.
Source
Download as [PDF] [ps.gz]
See also
Title: Our route guidance page

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe