ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ ДЛЯ ОПТИМИЗАЦИИ ГРУЗОВЫХ ПЕРЕВОЗОК

О.А. Александрова

Источник: Інформаційні системи та технології / Тезисы конференции. - Одесса: ОГАХ. - 2009. - С. 66-67

Использование оптимизированных маршрутов и проектов планов перевозок способствует своевременному и бесперебойному выполнению поставок продукции и эффективному взаимодействию организаций-поставщиков, организаций-получателей и автотранспортных организаций. Для решения данной задачи был использован ряд методов, алгоритмов и подходов. Среди них можно выделить метод Кларка-Райта, эвристические методы вставок, табу-поиск, метод ветвей и границ, метод ветвей с отсечениями, муравьиные и генетические алгоритмы. Однако все они обладают рядом недостатков таких, как время поиска решения, недостаточное качество решений, невозможность применения к задачам большой размерности и др.

Задача маршрутизации транспортных средств (ЗМТ) является NP-сложной задачей, которая может быть сформулирована как минимизация общей стоимости всех маршрутов с учетом грузоподъемности и временных ограничений. Для решения предложенной задачи был разработан модифицированный генетический алгоритм. Идея данного подхода заключается в нахождении методом Кларка-Райта и эвристическими методами близкого к оптимальному начального решения задачи и его дальнейшем развитии и приближении к оптимальному, используя генетический алгоритм с модифицированными проблемно-ориентированными операторами кроссинговера и мутации. Учитывая характер задачи генетический материал особи должен содержать несколько маршрутов, каждый из которых составлен из упорядоченного подмножества клиентов. В качестве фитнесс-функции используется сумма общей стоимости всех маршрутов особи и штрафа в денежном эквиваленте за невыполнение временных ограничений.

Программная реализация предложенного алгоритма была выполнена на языке высокого уровня в среде С++ Builder 6.0. Результатом работы алгоритма и собственно программы является оптимизированный набор маршрутов, которые представляются в виде маршрутных листов с указанием необходимых данных о заказах и клиентах.