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
- See also
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe