ВИЗНАЧЕННЯ ОПТИМАЛЬНОГО КІЛЬЦЕВОГО МАРШРУТУ, ЩО ПРОХОДИТЬ ЧЕРЕЗ ЗАДАНУ МНОЖИНУ ПУНКТІВ НА КАРТІ

Анотація

Предметом досліджень є методи та інформаційні технології транспортної логістики. Мета – зниження витрат і скорочення часу на доставку товарів автомобільним транспортом за рахунок розробки і впровадження ефективних методів і алгоритмів пошуку оптимального маршруту розвезення товарів. У статті розглядається завдання пошуку оптимального кільцевого маршруту розвезення товарів зі складу, що проходить через задану множину пунктів на карті. Для вирішення завдання використовуються методи і алгоритми дискретної математики. Отримані наступні результати. Виконаний аналіз проблеми та існуючих методів дискретної математики для її вирішення, визначено недоліки цих методів. Запропоновано метод вирішення завдання, що усуває ці недоліки. Розроблено евристичний алгоритм розв'язання задачі, що реалізує запропонований метод розв'язання. Рішення задачі, що розглядається, зводиться до задачі пошуку гамільтонова циклу на новому графі меншої розмірності. Новий граф будується з початкового графа, що описує карту, і складається з вершин заданої множини пунктів на карті, через які повинен пройти маршрут. Кожна дуга в новому графі з'єднує пару вершин, якщо в початковому графі існує шлях між цими вершинами. Дуга зважується числом, яке визначає мінімальну відстань між вершинами в початковому графі, які вона з'єднує. Для побудови графа використовується алгоритм Дейкстри. Висновки: запропонований метод вирішення розглянутої задачі виконує її приведення до класичної задачі дискретної математики пошуку гамільтонова циклу в графі. Тестування розробленої програми показало працездатність запропонованого методу і алгоритму вирішення завдання. Розроблений метод дозволяє знизити розмірність розв'язуваної задачі, оскільки рішення шукається на новому графі меншої розмірності на відміну від графа, що описує вихідну карту. Фактор зниження розмірності значно зменшує витрати на пошук рішення і підвищує шанси знайти оптимальний маршрут розвезення товарів.