«Автоматизация и информатизация ТЭК»

Оптимизация маршрутизации бригад на основе эвристических методов решения вариации задачи коммивояжера

УДК: 004.023
DOI: 10.33285/2782-604X-2023-9(602)-34-40

Авторы:

¹ РГУ нефти и газа (НИУ) имени И.М. Губкина, Москва, Россия

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

Аннотация:

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

Список литературы:

1. Цифровая экономика нефтяного производства / Г.И. Шмаль, Л.И. Григорьев, В.Я. Кершенбаум, Д.Г. Леонов // Нефт. хоз-во. – 2019. – № 1. – С. 100–103. – DOI: 10.24887/0028-2448-2019-1-100-103
2. Ковалевский П.Г. Автоматизация построения календарного плана проведения ремонтно-восстановительных работ на линейной части магистрального газопровода с использованием методов математического программирования // Автоматизация и информатизация ТЭК. – 2023. – № 1(594). – С. 13–19. – DOI: 10.33285/2782-604X-2023-1(594)-13-19
3. Тенденции развития интегрированных автоматизированных систем управления в газодобыче / С.П. Чистиков, В.К. Лаврухин, Л.И. Григорьев [и др.] // Газовая пром-сть. – 2006. – № 5. – С. 199–203.
4. Мудров В.И. Задача о коммивояжере. – М.: Знание, 1969. – 64 с.
5. Соломатин А.Н. Оптимизация стратегий разработки группы газовых месторождений // Автоматизация и информатизация ТЭК. – 2022. – № 10(591). – С. 45–51. – DOI: 10.33285/2782-604X-2022-10(591)-45-51
6. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro: Математика в приложениях. – 2003. – № 4. – С. 70–75.
7. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учеб. пособие. – 2-е изд. – М.: Физматлит, 2006. – 320 с.
8. Кирсанов М.Н. Графы в Maple: задачи, алгоритмы, программы. – М.: Физматлит, 2007. – 168 с.