Poruchy v sítích se zahlcením

Disruption in Congested Networks

conference paper

en

The purpose of the paper is to introduce and discuss a special problem related to congested traffic networks. In 1968, Braess presented an example of careless network changes, which led in congested networks to higher density of traffic. Since then, various versions of network design problems have been studied and clarified. We focus on phenomena accompanying many network design applications, specifically, the reconstruction of a network and its partial closure. A bilevel structure of the studied problem is tackled by the use of Karush-Kuhn-Tucker conditions. The obtained nonlinear integer program can be solved by the use of modelling optimization software as, e.g., GAMS. However, only small instances can be successfully solved within the acceptable time limits. For the large model instances, as the considered modification of the known Sioux Falls test case, the hybrid algorithmic framework combining the use of deterministic solvers encapsulated in GAMS with the genetic algorithm has been designed.

Cílem příspěvku je představit a rozvést specifický problém spojený se zahlcením v dopravních sítích. V roce 1968 Braess představil příklad nešetrného zásahu do sítě, jež vedl v zahlcených sítích ke zvýšení hustoty provozu. Od té doby byly studovány některé významné problémy spojené s strukturou dopravních sítí. Zaměřujeme se zde na jev doprovázející mnoho aplikací strukturování sítě, konkrétně na rekonstrukci sítě a její částečné poruchy a uzavírky. Dvojúrovňový charakter studovaného problému je řešen za pomocí Karushový-Kuhnových-Tuckerových podmínek. Získáme problém nelineárnícho celočíselného programování, který lze řešit optimalizačním softwarem, např. použitím GAMS. I přesto, pouze malé instance problému jsou snadno řešitelné během rozumného výpočetního času. Pro problémy většího rozsahu (jako např. modifikace známého Sioux Falls) bylo vyvinuto hybridní rozhraní kombinující deterministické řešiče z GAMS spolu s genetickými algoritmy.

The purpose of the paper is to introduce and discuss a special problem related to congested traffic networks. In 1968, Braess presented an example of careless network changes, which led in congested networks to higher density of traffic. Since then, various versions of network design problems have been studied and clarified. We focus on phenomena accompanying many network design applications, specifically, the reconstruction of a network and its partial closure. A bilevel structure of the studied problem is tackled by the use of Karush-Kuhn-Tucker conditions. The obtained nonlinear integer program can be solved by the use of modelling optimization software as, e.g., GAMS. However, only small instances can be successfully solved within the acceptable time limits. For the large model instances, as the considered modification of the known Sioux Falls test case, the hybrid algorithmic framework combining the use of deterministic solvers encapsulated in GAMS with the genetic algorithm has been designed.

toky sítí, problém rozložení dopravy, network design, zahlcené sítě, nelineární celočíselné programování, nekooperativní rovnovážný bod, Karushovy-Kuhnovy-Tuckerovy podmínky, genetické algoritmy.

multicommodity network flow, traffic assignment problem, network design, congested network, nonlinnear integer programming, noncooperative equilibrium, Karush-Kuhn-Tucker condditions, genetic algorithms.

2013

26.06.2013

VUT v Brně

Brno

978-80-214-4755-4

1803-3814

Proceedings of 19th International Conference on Soft Computing MENDEL 2013

191–196

6