Zastosowanie zmodyfikowanego algorytmu symulowanego wyżarzania do określenia kierunków rozwoju sieci transportowej

W chwili obecnej obserwuje się gwałtowny wzrost komunikacyjnych potrzeb ludności związany z intensyfikacją rozwoju gospodarczego, wzrostem zamożności społeczeństwa oraz urbanizacją nowych terenów. Istnieje więc potrzeba opracowania metody umożliwiającej zdiagnozowanie stanu aktualnej struktury sieci transportowej na rozpatrywanym obszarze dla obecnych i prognozowanych potrzeb komunikacyjnych, umożliwiającej wskazanie tych jej elementów, które wymagają modyfikacji. Z reguły rozróżnia się dwa typy zadań: dyskretny (DNDP - Discrete Network Design Problem), gdzie rozpatruje się możliwości rozbudowy sieci przez dodawanie nowych połączeń oraz ciągły (CNDP - Continuous Network Design Problem), gdzie rozbudowa sieci osiągana jest przez zwiększanie przepustowości istniejących połączeń. Istnieje możliwość połączenia tych podejść przez jednoczesne dopuszczenie obu typów zmian, co prowadzi do modelu mieszanego (MDNP - Mixed Network Design Problem). Problemy tego rodzaju są dwupoziomowymi zadaniami optymalizacyjnymi. Głównym celem jest znalezienie takiej struktury sieci transportowej, aby jej impedancja wyrażona przez sumaryczne koszty lub czasy podróży wszystkich uczestników ruchu była jak najmniejsza. Optimum to jest poszukiwane przy dodatkowym założeniu o jednoczesnej minimalizacji kosztów realizacji wprowadzanych zmian albo, co jest bardziej realistyczne nakładane jest ograniczenie na budżet przeznaczony na te zmiany. Obliczenie sumarycznych kosztów lub sumarycznego czasu podróży wymaga znajomości obciążenia wszystkich połączeń sieci transportowej. Zatem w każdym kroku algorytmu wyższego poziomu istnieje potrzeba wyznaczenia rozkładu ruchu na sieć, zbliżonego do rzeczywistego. Tak zdefiniowany problem jest NP-trudny, tworzące go zależności są z reguły nieliniowe i nieróżniczkowalne, a prawdopodobieństwo istnienia wielu optimów lokalnych jest wysokie - problem jest więc niewypukły. Ponadto dane wejściowe (charakteryzujące środowisko naturalne, rozkład skupisk ludności oraz intensywność komunikacji pomiędzy nimi) często nie są zadane w postaci analitycznej, naturalne jest więc zaproponowanie metod sztucznej inteligencji jako narzędzi optymalizacyjnych. Dzięki takiemu podejściu można znaleźć rozwiązanie zbliżone do optymalnego w stosunkowo krótkim czasie, eksplorując jedynie znikomy fragment przestrzeni rozwiązań. Jedną z najprostszych takich technik jest algorytm symulowanego wyżarzania.

Model sieci transportowej
Reprezentacja struktury sieci transportowej
Oczywistym modelem sieci transportowej jest graf, którego wierzchołki odpowiadają skrzyżowaniom, a krawędzie połączeniom drogowym. Każda krawędź ma dodatkowy atrybut - klasę określającą przepustowość. Dla każdej z klas określono jednostkowy koszt budowy. Niektórych wierzchołki pełnią rolę "miast", dla których zadano potrzeby transportowe. Potrzeby transportowe są wyrażone w liczbie pojazdów przemieszczających się pomiędzy każdą parą miast. Dane te są zebrane w postaci macierzy źródło - cel, macierz ta nie musi być symetryczna.

Artykuł zawiera 22260 znaków.

Źródło: Czasopismo Logistyka