Wykorzystanie algorytmów genetycznych w wybranych zagadnieniach inżynierii ruchu drogowego

• Autorzy: Kruszyna M.

Warianty tytułu

EN

Use of genetic algorithms in selected problems of traffic engineering

• Konferencja: Konferencja naukowa Komitetu Inżynierii Lądowej i Wodnej PAN i Komitetu Nauki PZITB (52 ; 11-16.09.2006 ; Gdańsk-Krynica, Polska)
• Języki publikacji: PL

Abstrakty

PL

Algorytmy bazujące na ewolucji lub zachowaniach populacji organizmów żywych określane są wspólnie jako algorytmy ewolucyjne (Evolutionary Algorithms, EAs). Wymienić można pięć podstawowych rodzajów algorytmów: genetyczne (GA), memetyczne (MA), "rój cząstek" (Particle Swarm, PS), "kolonia mrówek" (Ant Colony, AC) i "skaczące żaby" (Shuffled Frog Leaping, SFL). Jako heurystyki pokrewne EA, bazujące na podobnym podejściu do rozwiązania problemu, wymienić jeszcze można metody: symulowanego wyżarzania (Simulated Annealing, SA) i poszukiwanie tabu (Tabu Search, TS). Powstało także wiele metod hybrydowych, modyfikujących oryginalne podejścia i wykorzystujących elementy różnych algorytmów. Cechą wspólną wyżej wymienionych metod jest zastosowanie specyficznych sposobów przeszukiwania przestrzeni rozwiązań zadania optymalizacyjnego. Specyfika polega na losowym doborze i modyfikacji elementów rozwiązania, ale według określonych reguł wykorzystujących analogie do rozwoju organizmów, ich zachowań "społecznych", czy innych zjawisk o podobnym charakterze. Klasyczne zadania prowadzenia ruchu w sieci komunikacyjnej (Vehicle Routing Problem, VRP) są trudnymi zadaniami optymalizacyjnymi z uwagi na dużą złożoność (wiele zmiennych decyzyjnych i warunków ograniczających) oraz skomplikowane postacie funkcji celu. Dzięki wykorzystaniu algorytmów genetycznych szybciej (lub w ogóle) można uzyskać rozwiązanie optymalne albo zbliżone do optymalnego. Ponieważ w zadaniach z grupy VRP występują często nawzajem sprzeczne cząstkowe funkcje celu (co może być na przykład wynikiem uwzględnienia potrzeb różnych grup uczestników ruchu) konieczne jest stosowanie bardziej wyrafinowanych metod takich jak TS, SA, czy "lokalne poszukiwanie z przewodnikiem" (Guided Local Search) [2]. Podobne do powyższych są zagadnienia przydziału pojazdów do tras komunikacji zbiorowej lub w przewozie to-warów (Vehicle Scheduling Problem, VSP). Tu także do rozwiązania zadania optymalizacyjnego stosowane są algorytmy genetyczne.

EN

Problems of traffic engineering which are solved with use of Genetic Algorithms (GA) are presented in this paper. Steps of GA and methods of coding the variables are characterised. Variables used in traffic engineering are described. Application of GA in a certain problem of traffic engineering is presented at the end of paper.

• Wydawca: Wydawnictwo Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Politechniki Gdańskiej. Budownictwo Lądowe
• Rocznik: 2006
• Tom: nr 60
• Strony: 187--195
• Opis fizyczny: Bibliogr. 11 poz., 1 rys.

Twórcy

autor

Kruszyna M.

• Politechnika Wrocławska, Wydział Budownictwa Lądowego i Wodnego

Bibliografia

• [1] Azimi Z. N.: Hybrid heuristics for Examination Timetabling problem, Applied Mathematics and Computation 163,2005,705-733.
• [2] Backer B. De, Fumon V., Shaw P., Kilby P., Prosser P.: Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics, Joumal ofHeuristics, 6: 501-523,2000.
• [3] Baker B. M., Ayechew M. A: A genetic algorithm for the vehicle routing problem, Computers & Operations Research 30, 2003, 787-800.
• [4] Brandao J.: A tabu search algorithrn for the open vehicle routing problem, European Journal of Operational Research 157, 2004, 552-564.
• [5] Charon J., Hudry O.: Application of the noising method to the travelling salesman problem, European Journal of Operational Research 125,2000,266-277.
• [6] Elbeltagi E., Hegazy T., Grierson D.: Comparison among five evolutionary-based optimization algorithms, Advanced Engineering Informatics 19,2005,43-53.
• [7] Haldenbilen S., Ceylan H.: The development of a policy for road tax in Turkey, using a genetic algorithm approach for demand estimation, Transportation Research Part A39, 2005, 861-877.
• [8] Li J., Kwan R. S. K.: A fuzzy genetic algorithm for driver scheduling, European Journal of Operational Research 147,2003,334-344.
• [9] Moon C., Kim l, Choi G., Seo Y.: An efficient genetic algorithrn for the traveling salesman problem with precedence constraints, European Journal of Operational Research 140, 2002, 606-617.
• [10] Rutkowska D., Piliński M., Rutkowski L: Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. Warszawa: Wydawnictwo Naukowe PWN 1999.
• [11] Vlahogianni E. J., Karlaftis M. G., Golias J. C.: Optimized and meta-optimized neural networks for short-term traffic flow prediction: A genetic approach, Transportation Research Part C 13, 2005,211-234.