КОМП’ЮТЕРНА ПРОГРАМА РІШЕННЯ РІЗНИХ ВАРІАНТІВ ЗАДАЧІ КОМІВОЯЖЕРА З ДОПОМОГОЮ ГЕНЕТИЧНОГО АЛГОРИТМУ

Анотація

У наш час інтенсивно розвивається транспортна логістика. Оптимальні маршрути руху транспортних засобів, для певного набору пунктів комунікації: транзитних, вихідного та кінцевого пункту, можуть бути знайдені при рішенні різних варіантів задачі комівояжера.Задача комівояжера – класична задача оптимізації. У випадку її замкнутого варіанта, комівояжер, рухаючись із вихідного пункту (ВП), однократно відвідує всі транзитні пункти та вертається у ВП. У випадку незамкнутого варіанта, комівояжер рухається з ВП, однократно відвідує всі транзитні пункти та прибуває у кінцевий пункт.Маршрути руху для замкнутого та незамкнутого варіанта задачі можуть бути визначені за допомогою комп’ютерних програм, які використовують для рішення генетичний алгоритм (ГА).При застосуванні ГА для рішення задачі комівояжера, при великій кількості транзитних пунктів, можлива ситуація вибору оптимального маршруту з декількох, отриманих при різних параметрах генетичного алгоритму. У цьому випадку необхідно оперативна інтерактивна взаємодія із програмою для зміни параметрів ГА. Як відомо, інтерактивність мають комп’ютерні програми із графічним інтерфейсом користувача.У роботі на мові програмування Java розроблена кросплатформна комп’ютерна програма рішення різних варіантів задачі комівояжера з допомогою генетичного алгоритму. Вона має графічний інтерфейс користувача та дозволяє визначити оптимальний маршрут руху, як для замкнутого, так і незамкнутого варіанту задачі комівояжера. У той час, графічний інтерфейс додатка дає можливість змінювати параметри ГА у процесі його роботи та відображати знайдені маршрути руху у графічному вигляді.Попередньо дані про розташування пунктів руху, у вигляді їх назв та відповідних значень географічних координат широти та довготи, вводяться у програму з *.csv файлу.Програма при функціонуванні використовує генетичний алгоритм на основі методів, які для кожного варіанта задачі комівояжера реалізовували кросовер, мутацію хромосом, механізми елітизма та турнірного відбору особин, оцінку придатності популяції (методи реалізації кросовера і мутації хромосом для різних варіантів задачі відрізнялися). Для оцінки відстані між містами та довжини маршруту додаток використовує формулу гаверсинусів.