Metody sztucznej inteligencji w projektowaniu harmonogramu przewozów dla dynamicznych potrzeb transportowych

Problem skonstruowania optymalnego planu przewozów pomiędzy wieloma węzłami źródłowymi i wieloma węzłami docelowymi przy ograniczonej liczbie środków transportowych jest bardzo złożony obliczeniowo. Z reguły, w zależności od zakresu zadań są to problemy NP - zupełne. Opracowanie przybliżonej metody pozwalającej na znalezienie prawie optymalnego rozwiązania w krótkim czasie może mieć więc duże praktyczne znaczenie. W pracy zaproponowano zastosowanie metod sztucznej inteligencji do projektowania przebiegu linii autobusowych oraz planowania rozkładu jazdy autobusów. Porównano wyniki uzyskane przy użyciu algorytmu genetycznego i symulowanego wyżarzania. Opracowany model zakłada znajomość struktury sieci transportowej dostępnej dla komunikacji publicznej oraz ustaloną z góry liczbę środków transportu (autobusów). Dynamiczne potrzeby transportowe zadane są w postaci ciągu złożonego ze zgłoszeń zamiaru podróży pomiędzy parą przystanków przez różne grupy pasażerów w kolejnych chwilach czasowych. Minimalizowany jest sumaryczny czas podróży pasażerów uwzględniający oczekiwanie na przystankach.

The problem of constructing an optimal schedule for the multiple source nodes and destination nodes with a limited number of vehicles is computationally complex. In many cases, depending on the range of the tasks the problems as a rule are NP - hard. So, the development of a heuristic method to find the optimal solution in a short time can be of great practical importance. This paper proposes the use of the methods of artificial intelligence to design the course of bus routes and the timetables. The results obtained with the use of the genetic algorithm and the simulated annealing were compared. The model assumes the knowledge of the structure of the transport network and a predetermined number of means of transport (buses). Dynamic transportation needs are introduced as a series of requests of travel between pairs of bus stops for different groups of passengers in successive moments of time. The total travel time of all passengers including waiting time at bus stops is here the minimized value.