Разработка алгоритмов для информационной системы построения оптимального маршрута доставки

Брыкин Дмитрий Олегович, Пестова Светлана Юрьевна

В статье представлены результаты выполнения исследования скорости и оптимальности работы алгоритмов по решению задачи коммивояжера для фирм, которым необходимо оптимизировать собственную службу доставки. Проведен анализ 5 алгоритмов и были сравнены 3 из них. Для последующей работы решено использовать алгоритм полного перебора для коротких маршрутов и комбинацию алгоритмов имитации отжига и генетического для маршрутов большей протяженности. Тесты алгоритмов показали их сильные и слабые стороны. Алгоритмы были оценены по их скорости работы и получившейся длинны маршрута. Генетический алгоритм и алгоритм имитации отжига показали хорошую эффективность, если количество точек в маршруте велико. Для коротких маршрутов лучше подходит алгоритм полного перебора. Было решено использовать их комбинации в зависимости от рассчитываемого маршрута.

Ключевые слова:логистика, маршрутизация, оптимизация, задача коммивояжёра, метаэвристические алгоритмы