Danke euch beiden, ich habe jetzt ne gute Idee, wie ich meine Straßenprojekte erstellen könnte:
(Die folgende Beschreibung setzt ein elementares Grundverständnis von Flussalgorithmen voraus)
Jedes Gebiet bildet einen Knoten der Sorte G (ebiet)
Jeder Straßenknoten bildet einen Knoten der Sorte S (traßenknoten)
Alle G-Knoten sind mit allen in diesem Gebiet enthaltenen S-Knoten mit einer Kante der Sorte V (erkehrsaufkommen) verbunden.
Alle S-Knoten sind mit allen angrenzenden S-Knoten über die jeweiligen Straßen (Kante der Sorte S) verbunden.
Alle S-Knoten sind mit dem G-Knoten in ihrem Gebiet über eine Kante der Sorte Z (ielverkehr) verbunden.
V-Kanten haben als Kapazität jeweils das Verkehrsaufkommen, das an dem S-Knoten in dem Gebiet "freigesetzt" wird (also quasi die Leute, die dort losfahren).
Z-Kanten haben als Kapazität jeweils das Verkehrsaufkommen, das an dem S-Knoten in dem Gebiet "aufgesogen" wird (also quasi die Leute, die dort hinwollen).
S-Kanten haben als Kapazität je nach Ausbau, Straßenzustand, Topologie und Höchstgeschwindigkeit das maximale Verkehrsaufkommen, dass durch diese Straße "fließen" kann.
Optimalerweise ist Summe der Kapazitäten aller V-Kanten gleich der Summe der Z-Kanten (jeder will irgendwo hin), aber es sollte auch gehen, wenn es nur ungefähr gleich ist.
Die G-Knoten fungieren über die V-Kanten als Quellen und über die Z-Kanten als Senken (ist ne Variante der eigentlichen Flussproblematik).
Angenommen, ich habe nun einen maximalen Fluss auf diesem Straßen/Gebietsgraphen:
Ist der maximale Fluss kleiner als die Summe der Kapazitäten der V- bzw. Z-Kanten, so können die Straßen das benötigte Verkehrsaufkommen nicht aufnehmen.
Der andere Fall (maximale Fluss größer als die Summe => Straßen haben genügend Kapazität) ist uninteressant, weil Ideal-/Endzustand
Wenn es also Kapazitätsengpässe gibt, dann gibt es S-Kanten, deren Flusswert gleich ihrer Kapazität ist. Dies sind Engpassstraßen, die entweder ausgebaut werden müssen, oder der Verkehr umgeleitet werden muss. Wenn es S-Kanten gibt, die in einer Richtung stark belastet sind und in die andere Richtung kaum, dann könnte man z. B. in die eine Richtung 3 Spuren und in die andere 1 Spur "schalten", bei Bedarf sogar tageszeitenabhängig.
Mit dieser Methode könnte ich inkrementell mein Straßensystem verbessern und anpassen (die Stadt wächst ja im nachhinein, also während des Spiels, immer noch).
Die Laufzeit ist vergleichsweise gut, nämlich O(n² * m), bei n Knoten und m Kanten und ordentlicher Dinic-Implementierung.
Ich müsste mir noch überlegen, ob man einige Erweiterungen (verschiedene Verkehrsarten, Vorfahrtsregelungen, Ampeln, Kreisel) einbauen kann, ohne das Problem nach NP zu schieben.
Für Leute die sich fragen, warum ich nicht einfach kürzeste Wege ausrechne und darauf entscheide, ob und wo ich neubauen will: Erstens sind die Flussalgorithmen für diese Art von Problemen wesentlich besser, da sie auch alternative Wege berücksichtigen und zweitens, kürzeste Wege zwischen allen Knoten (Floyd-Warshall z. B.) ist O(n³), was in meinem Straßennetz nicht wesentlich weniger als O(n² * m) ist und somit keinen Geschwindigkeitsvorteil.
