Im Augsburger Zeughaus findet schon seit dem Jahr der Mathematik 2008 vierteljährlich die an ein breites Publikum gerichtete Vortragsreihe „Faszination Mathematik und Physik“ statt (Flyer)
Diesen Donnerstag ging es um die Mathematik des Straßenverkehrs. Es wurde erklärt, wie der Verkehrsfluß mathematisch modelliert wird, wie dann kürzeste Wege berechnet werden und wie dabei die von den gerade aktiven Navis neu erhaltenen Anfragen jederzeit zur Aktualisierung kürzester Wege genutzt werden.
Im Bild zeigt an jeder Kante das Paar (a,b) die Länge a und die Kapazität b der jeweiligen Straße an. Wenn mehrere Autos oben links ankommen, werden zunächst einige nach rechts geschickt werden, denn der Weg rechtsherum ist ja genauso lang wie der ganz links. Wenn aber in der Zwischenzeit auch Autos rechts unten ankommen, ist es aber für die ankommenden Autos besser, auf der Diagonale wieder nach links oben zu fahren (und erst danach die Kante ganz links zu nehmen). Diese Autos sind also einmal im Kreis gefahren. Und wenn inzwischen links oben neue Autos angekommen sind, werden sie vielleicht vom Navi noch ein zweites Mal im Kreis geführt.
(Man kennt solche Situationen ja eher von der Parkplatzsuche in Innenstädten, aber gelegentlich passieren sie auch im Fernverkehr.)
Da fragt man sich dann natürlich, ob es passieren kann, dass ein Auto vom Navigationsgerät in eine Endlosschleife geschickt wird, also immer wieder im Kreis fährt.
Unter der nicht besonders realistischen Annahme, dass es nur eine „Senke“ gibt, also alle Autos zum selben Ziel fahren, haben Graf, Harks und Sering in Dynamic Flows with Adaptive Route Choice bewiesen, dass so etwas nicht passieren kann.
Für Flüsse mit mehreren Senken, wenn also nicht alle Autos zum selben Ziel fahren, können solche Endlosschleifen aber tatsächlich passieren. Ein einfaches (theoretisches) Beispiel aus der Arbeit von Graf-Harks-Sering zeigt das Bild unten.
Kommentare (8)