ДОСЛІДЖЕННЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ ДЛЯ ПОШУКУ ОПТИМАЛЬНИХ ШЛЯХІВ В СИСТЕМІ ПРОВЕДЕННЯ МЕТРОМАРАФОНІВ
DOI:
https://doi.org/10.30837/bi.2019.2(93).09Ключові слова:
ГЕНЕТИЧНИЙ АЛГОРИТМ, ГРАФ, ЗАДАЧА КОМІВОЯЖЕРА, МАТЕМАТИЧНА МОДЕЛЬ, МЕТРОМАРАФОН, ПОШУК ОПТИМАЛЬНОГО ШЛЯХУ, ПРОБЛЕМА СТАНЦІЙ, СХРЕЩУВАННЯ ГЕНОМІВ.Анотація
Робота присвячена дослідженню генетичних алгоритмів на прикладі пошуку оптимальних шляхів для підтримки проведення метромарафонів в системах типу «Transit Challenge» або «Subway Challenge». На основі правил проведення метромарафонів та задачі комівояжера сформульована проблема станцій — пошуку оптимального шляху, який би дозволив відвідати всі станції метрополітену за найкоротший час. На базі теорії графів розроблена математична модель системи метромарофону. Для вирішення проблеми станцій розроблено генетичний алгоритм: обрано спосіб представлення геному, правила мутації популяцій і схрещування геномів. На основі експериментального дослідження генетичного алгоритму підібрано найбільш ефективні параметри та розроблено рекомендації стосовно вирішення проблеми станцій для метромарафонів різної розмірності.Посилання
Murat Albayrak and Novruz Allahverdi, Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms. // Expert Systems with Applications, vol. 38, no. 3, 2011 – pp. 1313–1320.
Chakroborty, P., and Dwivedi, T. Optimal route network design for transit system using genetic algorithms. Optimization and Engineering. – 34(1), 200 с. – 2003.
Dijkstra, E.W. A note on two problems in connexion with graphs. Numerische Mathematik. 1, 471 с. – 1959.
Fan L. and Mumford C. L. A Metaheuristic Approach to the Urban Transit Routing Problem. Journal of Heuristic. – 16, 372 с. – 2010.
Ngamchai, S. and Lovell, D. Optimal time transfer in bus transit route network design using a genetic algorithm, Journal of Transportation Engineering. – 129 (5), 2003. – 510–521 с.
Baaj, M. H., and Mahmassani, H. S. An AIbased approach for transit route system planning and design. Journal of Advanced Transportation. – 25(2), 287 c. – 1990.
