The design of the public transport lines with the use of the fast genetic algorithm

• Autorzy: Król A.

Identyfikatory

DOI

10.17270/J.LOG.2015.3.7

Warianty tytułu

PL

Projektowanie przebiegu linii komunikacji publicznej za pomocą szybkiego algorytmu genetycznego

• Języki publikacji: EN

Abstrakty

EN

Background: The growing role of public transport and the pressure of economic criteria requires the new optimization tools for process of public transport planning. These problems are computationally very complex, thus it is preferable to use various approximate methods, leading to a good solution within an acceptable time. Methods: One of such method is the genetic algorithm mimicking the processes of evolution and natural selection in the nature. In this paper, the different variants of the public transport lines layout are subjected to the artificial selection. The essence of the proposed approach is a simplified method of calculating the value of the fit function for a single individual, which brings relatively short computation time even for large jobs. Results: It was shown that despite the introduced simplifications the quality of the results is not worsened. Using the data obtained from KZK GOP (Communications Municipal Association of Upper Silesian Industrial Region) the described algorithm was used to optimize the layout of the network of bus lines located within the borders of Katowice. Conclusion: The proposed algorithm was applied to a real, very complex network of public transportation and a possibility of a significant improvement of its efficiency was indicated. The obtained results give hope that the presented model, after some improvements can be the basis of the scientific method, and in a consequence of a further development to find practical application.

PL

Wstęp: Rosnąca rola komunikacji publicznej przy jednoczesnym nacisku kryteriów ekonomicznych wymaga zastosowania nowych narzędzi optymalizacyjnych do procesu planowania transportu publicznego. Problemy te są bardzo złożone obliczeniowo, więc korzystne jest zastosowanie różnych metod przybliżonych, prowadzących do uzyskania dobrych rozwiązań w akceptowalnym czasie. Metody: Jedną z takich metod jest algorytm genetyczny, naśladujący procesy ewolucji i doboru naturalnego w przyrodzie. W prezentowanej pracy sztucznemu doborowi podlegają różne warianty układu linii komunikacji publicznej. Istotą proponowanego podejścia jest uproszczony sposób obliczania wartości funkcji dostosowania pojedynczego osobnika, co przynosi stosunkowo krótki czas obliczeń nawet dla dużych zadań. Wyniki: Pokazano, że mimo wprowadzonych uproszczeń, jakość uzyskanych rezultatów nie ulega pogorszeniu. Korzystając z danych uzyskanych od KZK GOP (Komunikacyjny Związek Komunal ny Górnośląskiego Okręgu Przemysłowego) zastosowano opisywany algorytm do optymalizacji układu części sieci linii autobusowych znajdujących się w obrębie miasta Katowice. Wnioski: Zaproponowany algorytm zastosowano do rzeczywistej, bardzo złożonej sieci komunikacji publicznej uzyskując znaczącą poprawę jej efektywności. Otrzymane rezultaty dają nadzieję, że prezentowany model po udoskonaleniu i może być podstawą naukowej metody, a w konsekwencji dalszego rozwoju znaleźć praktyczne zastosowanie.

Słowa kluczowe

EN

genetic algorithm; public transport; optimization; bus lines

PL

algorytm genetyczny; transport publiczny; optymalizacja; linie autobusowe

• Wydawca: Wyższa Szkoła Logistyki
• Czasopismo: LogForum
• Rocznik: 2015
• Tom: Vol. 11, no. 3
• Strony: 275--282
• Opis fizyczny: Bibliogr. 15 poz., rys., tab. , wykr.

Twórcy

autor

Król A.

• Faculty of Transport, Silesian University of Technology, 44-100 Katowice, Krasińskiego 8, Poland

Bibliografia

• Arabas J., 2004, Wykłady z algorytmów ewolucyjnych [Lectures on evolutionary algorithms], WNT, Warszawa.
• Baaj M.H., Mahmassani H.S., 1995, Hybrid route generation heuristic algorithm for the design of transit network,Transportation Research, C 3, 31-50.
• Bielli M., Caramia M., Carotenuto P., 2002, Genetic algorithms in bus network optimization, Transportation Research, C 10, 19-34.
• Ceder A., Wilson N. H. M., 1986, Bus network design, Transportation Research, B 20, 331-344.
• Chakroborty P., Dwivedi T., 2002, Optimal route network design for transit systems using genetic algorithm, Engineering Optimization 34/1, 83-100.
• Fusco G., Gori S., Petrelli M., 2002, An heuristic transit network design algorithm for medium size towns, Proceedings of the 13th Mini-EURO Conference, Bari.
• Giejsztor K., 2014, Zastosowanie metod sztucznej inteligencji do projektowania linii komunikacji publicznej. praca dyplomowa magisterska [The application of the artificial intelligence methods for the design of public transportation lines. Master's thesis], Katowice.
• Król A., 2013, Metody sztucznej inteligencji w projektowaniu harmonogramu przewozów dla dynamicznych potrzeb transportowych [Artificial intelligence methods in the design of scheduling for dynamic transportation needs], Autobusy 3/2013, 1369–1384.
• Król A., 2012, Zastosowanie algorytmu genetycznego do projektowania harmonogramu przewozów [Application of the genetic algorithm to design of the transportation scheduling], Technika Transportu Szynowego 9/2012, 569-581.
• Magnanti T.L., Wong R.T., 1984, Network design and transportation planning: models and algorithms, Transportation Science 18/1, 1-55.
• Ngamchai S., Lovell D., 2003, Optimal time transfer in bus transit route network design using a genetic algorithm, Journal of Transportation Engineering 129/5, 510-521.
• Patz A., 1925, Die richtige Auswahl von Verkehrslinien bei großen Straßenbahnnetzen [The proper choice of transport lines for large tram networks], Verkehrstechnik 50/51.
• Quak C. B., 2003, Bus line planning. Master's Thesis, Delft University of Technology, The Netherlands.
• Yu B., Yang Z., Cheng C., Liu C., 2005, Optimizing bus transit network with parallel ant colony algorithm, Proceedings of the Eastern Asia Society for Transportation Studies, 5, 374-389.
• Zhao F., 2006, Large-scale transit network optimization by minimizing user cost and transfers, Journal of Public Transportation 9/2, 107-129.