ЗАДАЧА ОПТИМИЗАЦИИ МАРШРУТА ДВИЖЕНИЯ ВЫЕЗДНОЙ МЕТРОЛОГИЧЕСКОЙ ГРУППЫ *
Аннотация: в работе представлен пример решения задачи коммивояжера применительно к процессу формирования оптимального маршрута движения выездной метрологической группы по пунктам осуществления поверочных работ в местах эксплуатации средств измерений
Ключевые слова: оптимизация, задача коммивояжера, поверка, планирование, логистика
УДК 78.21.35
Ершова К.А.
младший научный сотрудник
Главный научный метрологический центр
(Россия, г. Мытищи)
ЗАДАЧА ОПТИМИЗАЦИИ МАРШРУТА ДВИЖЕНИЯ
ВЫЕЗДНОЙ МЕТРОЛОГИЧЕСКОЙ ГРУППЫ
Аннотация: в работе представлен пример решения задачи коммивояжера применительно к процессу формирования оптимального маршрута движения выездной метрологической группы по пунктам осуществления поверочных работ в местах эксплуатации средств измерений.
Ключевые слова: оптимизация, задача коммивояжера, поверка, планирование, логистика.
Поверка средств измерений (СИ), являющаяся совокупностью операций, выполняемых в целях подтверждения соответствия средств измерений метрологическим требованиям, может осуществляться как в стационарных условиях (местах осуществления деятельности метрологических лабораторий, установленных при их аккредитации), так и в местах эксплуатации поверяемых СИ по средствам применения мобильных метрологических комплексов.
В целях уменьшения продолжительности изъятия из эксплуатации СИ наиболее предпочтительно осуществлять поверку СИ в местах их эксплуатации. Как правило, в данном случае формируется выездная метрологическая группа (ВМГ), которая последовательно объезжается места эксплуатации СИ и осуществляет их поверку.
В процессе планирования работы ВМГ возникает необходимость формирования оптимального маршрута движения ВМГ по пунктам осуществления поверочных работ в местах эксплуатации СИ.
Постановка задачи. Допустим, что имеется мест эксплуатации СИ, пронумерованных от 1 до . Известны расстояния между любой парой мест эксплуатации СИ, которые составляют . Если между местами эксплуатации СИ и нет дороги, то . По тем же соображениям . А также (путь в одну сторону не обязательно совпадает с путем, пройденным в обратную сторону). ВМГ, выезжая из какого-либо места эксплуатации СИ, должна посетить все места, побывав в каждом ровно один раз, и вернуться в пункт постоянной дислокации. Объезд мест эксплуатации СИ, удовлетворяющий этим требованиям, называется маршрутом коммивояжера. Под длиной маршрута понимается сумма длин всех входящих в него переездов из одного места эксплуатации СИ в другое. Необходимо определить минимальный (по расстоянию) маршрут движения ВМГ по пунктам осуществления поверочных работ в местах эксплуатации СИ.
Метод. Пусть – некоторый допустимый маршрут ВМГ, где числа указывают порядок обхода мест эксплуатации СИ. Переезды ВМГ называются дугами маршрута. Через обозначено множество всех допустимых маршрутов ВМГ, а через – длина маршрута , которая равна .
Вычисление оценки для множества .
Положим . Тогда для любого и .
Положим . Тогда для любого и .
Матрицу – называют приведенной, операцию ее построения – приведением матрицы , а величины – константами приведения. Таким образом, приведенная матрица получается вычитанием из всех элементов каждой строки матрицы минимального элемента этого столбца. Отметим, что в каждой строке и в каждом столбце матрицы имеется хотя бы один нулевой элемент. Положим .
Для любого допустимого маршрута . Очевидно, что после операции приведения длины всех маршрутов уменьшаются на одну и ту же величину . Следовательно, оптимальный маршрут, найденный с использованием приведенной матрицы, оптимален и для исходной задачи. При этом длины оптимальных маршрутов задачи с матрицей и задачи с матрицей связаны соотношением .
Выбор множества для ветвления. На первом шаге это множество . Его нижняя оценка . На остальных шагах из числа кандидатов на ветвление (из множества висячих вершин дерева ветвления) выбирается множество с наименьшей оценкой.
Разбиение множества на подмножества (ветвление). Через обозначим приведенную матрицу, соответствующую множеству . Описанным ниже в п. 5 способом выбирается дуга . Множество разбивается на два подмножества и и исключается из числа кандидатов на ветвление. Подмножество состоит из всех маршрутов множества , не содержащих дугу ; подмножество – из всех маршрутов, содержащих дугу .
Преобразование матрицы стоимостей и вычисление оценок. Матрица , соответствующая множеству , получается из заменой . Для множества соответствующая матрица получается из вычёркиванием -й строки и -го столбца. Кроме того, как правило, требуется запрещение некоторого элемента для исключения из замкнутого маршрута, проходящего по уже включенным в маршрут дугам, но не являющегося полным (т.е. не содержащим все мест эксплуатации СИ).
Оценки для вновь образованных множеств вычисляются следующим образом:
где и есть суммы констант приведения матриц и .
Легко показать, что
. (1)
Выбор дуги для ветвления. По-прежнему – приведенная матрица, соответствующая множеству . Выбор дуги для ветвления основан на стремлении сделать оценку – побольше для того, чтобы увеличить вероятность выбора для дальнейшего ветвления множества . Исходя из первого условия, будем рассматривать лишь дуги , для которых
. (2)
Чтобы выполнить второе условие, среди дуг, удовлетворяющих (2), выберем дугу , для которой значение будет максимальным. Для этого, используя (1), вычислим функцию
для каждой дуги такой, что . В качестве дуги выберем ту, для которой .
Пример. Решим задачу формирования оптимального маршрута движения ВМГ по пунктам осуществления поверочных работ в местах эксплуатации СИ со следующей матрицей расстояний:
.
Вычисление оценки . Выполним операцию приведения матрицы .
Отсюда .
Выбор дуги для ветвления. Для всех нулей приведенной матрицы вычислим :
Максимальное значение равно 6 и достигается на дугах и . Выберем для ветвления, например, дугу , потому что .
Ветвление. Множество разбиваем на два подмножества и . Верхний индекс указывает на номер итерации, а нижний – на наличие выбранной дуги в маршрутах данных множеств. Множество состоит из всех маршрутов ВМГ, не содержащих дугу . Весь процесс решения данной задачи изображен на рисунке 1. Рядом с каждой вершиной указано значение оценки целевой функции для соответствующего множества маршрутов.
Рис. 1 – Графическое решение задачи
Вычисление оценки . Выполним операцию приведения матрицы, соответствующей . Она получается из приведенной матрицы заменой элемента на .
Получаем:
Замечаем, что . Значит оценку для можно вычислить проще, а именно .
Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы вычеркиванием 1-й строки, 2-го столбца и запрещением элемента .
Итак, .
Выбор множества для ветвления. Так как , то ветвим множество .
Выбор дуги ветвления. Для приведенной матрицы из п. 5 вычислим
.
Максимальное значение достигается на дугах и . Выберем для ветвления дугу .
Ветвление. Множество разбиваем на два подмножества и . Множество состоит из всех маршрутов множества , не содержащих дугу , а – из всех маршрутов множества , содержащих дугу (смотрите рисунок 1).
Вычисление оценки .
.
Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы, найденной в п. 5, вычеркиванием 3-й строки, 4-го столбца и запрещением элемента .
.
Значит .
Допустимое решение задачи. В п. 10 получена матрица размером с двумя незапрещенными элементами и . Это означает, что множество состоит из единственного маршрута, который содержит дуги . Его длина равна 23, т.е. .
Отсев неперспективных множеств. Так как , то множество не содержит оптимального решения и выбывает из числа кандидатов на ветвление.
Выбор множества для ветвления. Кандидатом на ветвление является только множество .
Выбор дуги ветвления. Для приведенной матрицы из п. 4 вычислим
.
Выберем для ветвления дугу .
Ветвление. Множество разбиваем на два подмножества и .
Вычисление оценки . . Так как , то объявляется неперспективным.
Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы, найденной в п. 4, вычеркиванием 2-й строки, 1-го столбца и запрещением элемента .
.
Итак, .
Выбор множества для ветвления. Единственным кандидатом на ветвление является .
Выбор дуги ветвления. Для приведенной матрицы из п. 18 вычислим . Выберем для ветвления дугу .
Ветвление. Множество разбивается на и .
Вычисление оценки . .
Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы, найденной в п. 18, вычеркиванием 1-й строки, 3-го столбца и запрещением элемента (исключаем цикл ).
Значит .
Выбор множества для ветвления. Кандидатами на ветвление являются и . Так как для обоих множеств нижняя оценка больше рекорда целевой функции, то они являются неперспективными. Других кандидатов на ветвление нет. Следовательно, процесс решения задачи окончен. Оптимальным решением является маршрут , его длина равна 23.
Таким образом, в работе представлен пример решения задачи коммивояжера применительно к процессу формирования оптимального маршрута движения выездной метрологической группы по пунктам осуществления поверочных работ в местах эксплуатации средств измерений.
Список литературы:
Тюхтина А.А. Методы дискретной оптимизации: Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2014 – 62 с.
Ершова К.А. ЗАДАЧА ОПТИМИЗАЦИИ МАРШРУТА ДВИЖЕНИЯ ВЫЕЗДНОЙ МЕТРОЛОГИЧЕСКОЙ ГРУППЫ // Вестник науки №1 (58) том 2. С. 236 - 245. 2023 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/6980 (дата обращения: 29.03.2024 г.)
Нашли грубую ошибку (плагиат, фальсифицированные данные или иные нарушения научно-издательской этики) ? - напишите письмо в редакцию журнала:
zhurnal@vestnik-nauki.com
*В выпусках журнала могут упоминаться организации (Meta, Facebook, Instagram) в отношении которых судом принято вступившее в законную силу решение о ликвидации или запрете деятельности по основаниям, предусмотренным Федеральным законом от 25 июля 2002 года № 114-ФЗ 'О противодействии экстремистской деятельности' (далее - Федеральный закон 'О противодействии экстремистской деятельности'), или об организации, включенной в опубликованный единый федеральный список организаций, в том числе иностранных и международных организаций, признанных в соответствии с законодательством Российской Федерации террористическими, без указания на то, что соответствующее общественное объединение или иная организация ликвидированы или их деятельность запрещена.