'
Научный журнал «Вестник науки»

Режим работы с 09:00 по 23:00

zhurnal@vestnik-nauki.com

Информационное письмо

  1. Главная
  2. Архив
  3. Вестник науки №1 (58) том 2
  4. Научная статья № 41

Просмотры  58 просмотров

Ершова К.А.

  


ЗАДАЧА ОПТИМИЗАЦИИ МАРШРУТА ДВИЖЕНИЯ ВЫЕЗДНОЙ МЕТРОЛОГИЧЕСКОЙ ГРУППЫ *

  


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

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


УДК 78.21.35

Ершова К.А.

младший научный сотрудник

Главный научный метрологический центр

(Россия, г. Мытищи)

 

ЗАДАЧА ОПТИМИЗАЦИИ МАРШРУТА ДВИЖЕНИЯ

ВЫЕЗДНОЙ МЕТРОЛОГИЧЕСКОЙ ГРУППЫ

 

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

 

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

 

Поверка средств измерений (СИ), являющаяся совокупностью операций, выполняемых в целях подтверждения соответствия средств измерений метрологическим требованиям, может осуществляться как в стационарных условиях (местах осуществления деятельности метрологических лабораторий, установленных при их аккредитации), так и в местах эксплуатации поверяемых СИ по средствам применения мобильных метрологических комплексов.

В целях уменьшения продолжительности изъятия из эксплуатации СИ наиболее предпочтительно осуществлять поверку СИ в местах их эксплуатации. Как правило, в данном случае формируется выездная метрологическая группа (ВМГ), которая последовательно объезжается места эксплуатации СИ и осуществляет их поверку.

В процессе планирования работы ВМГ возникает необходимость формирования оптимального маршрута движения ВМГ по пунктам осуществления поверочных работ в местах эксплуатации СИ.

Постановка задачи. Допустим, что имеется  мест эксплуатации СИ, пронумерованных от 1 до . Известны расстояния между любой парой мест эксплуатации СИ, которые составляют . Если между местами эксплуатации СИ  и  нет дороги, то . По тем же соображениям . А также  (путь в одну сторону не обязательно совпадает с путем, пройденным в обратную сторону). ВМГ, выезжая из какого-либо места эксплуатации СИ, должна посетить все места, побывав в каждом ровно один раз, и вернуться в пункт постоянной дислокации. Объезд мест эксплуатации СИ, удовлетворяющий этим требованиям, называется маршрутом коммивояжера. Под длиной маршрута понимается сумма длин всех входящих в него переездов из одного места эксплуатации СИ в другое. Необходимо определить минимальный (по расстоянию) маршрут движения ВМГ по пунктам осуществления поверочных работ в местах эксплуатации СИ.

Метод. Пусть  – некоторый допустимый маршрут ВМГ, где числа  указывают порядок обхода мест эксплуатации СИ. Переезды ВМГ  называются дугами маршрута. Через  обозначено множество всех допустимых маршрутов ВМГ, а через  – длина маршрута , которая равна .

  1. Вычисление оценки для множества .

Положим . Тогда  для любого  и .

Положим . Тогда  для любого  и .

Матрицу  – называют приведенной, операцию ее построения – приведением матрицы , а величины  –  константами приведения. Таким образом, приведенная матрица  получается вычитанием из всех элементов каждой строки матрицы  минимального элемента этого столбца. Отметим, что в каждой строке и в каждом столбце матрицы  имеется хотя бы один нулевой элемент. Положим .

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

  1. Выбор множества для ветвления. На первом шаге это множество . Его нижняя оценка . На остальных шагах из числа кандидатов на ветвление (из множества висячих вершин дерева ветвления) выбирается множество с наименьшей оценкой.
  2. Разбиение множества на подмножества (ветвление). Через обозначим приведенную матрицу, соответствующую множеству . Описанным ниже в п. 5 способом выбирается дуга . Множество  разбивается на два подмножества  и  и исключается из числа кандидатов на ветвление. Подмножество  состоит из всех маршрутов множества , не содержащих дугу ; подмножество  – из всех маршрутов, содержащих дугу .
  3. Преобразование матрицы стоимостей и вычисление оценок. Матрица , соответствующая множеству , получается из заменой . Для множества соответствующая матрица  получается из  вычёркиванием -й строки и -го столбца. Кроме того, как правило, требуется запрещение некоторого элемента для исключения из  замкнутого маршрута, проходящего по уже включенным в маршрут дугам, но не являющегося полным (т.е. не содержащим все  мест эксплуатации СИ).

Оценки для вновь образованных множеств вычисляются следующим образом:

где  и  есть суммы констант приведения матриц  и .

Легко показать, что

.                                              (1)

  1. Выбор дуги для ветвления. По-прежнему – приведенная матрица, соответствующая множеству . Выбор дуги для ветвления основан на стремлении сделать оценку – побольше для того, чтобы увеличить вероятность выбора для дальнейшего ветвления множества . Исходя из первого условия, будем рассматривать лишь дуги , для которых

.                                                     (2)

Чтобы выполнить второе условие, среди дуг, удовлетворяющих (2), выберем дугу , для которой значение  будет максимальным. Для этого, используя (1), вычислим функцию

для каждой дуги  такой, что . В качестве дуги  выберем ту, для которой .

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

.

  1. Вычисление оценки . Выполним операцию приведения матрицы .

Отсюда .

  1. Выбор дуги для ветвления. Для всех нулей приведенной матрицы вычислим :

Максимальное значение равно 6 и достигается на дугах  и . Выберем для ветвления, например, дугу , потому что .

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

 

Рис. 1 – Графическое решение задачи

  1. Вычисление оценки . Выполним операцию приведения матрицы, соответствующей . Она получается из приведенной матрицы заменой элемента на .

Получаем:

Замечаем, что . Значит оценку для  можно вычислить проще, а именно .

  1. Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы вычеркиванием 1-й строки, 2-го столбца и запрещением элемента .

Итак, .

  1. Выбор множества для ветвления. Так как , то ветвим множество .
  2. Выбор дуги ветвления. Для приведенной матрицы из п. 5 вычислим

.

Максимальное значение достигается на дугах  и . Выберем для ветвления дугу .

  1. Ветвление. Множество разбиваем на два подмножества и . Множество  состоит из всех маршрутов множества , не содержащих дугу , а  – из всех маршрутов множества , содержащих дугу  (смотрите рисунок 1).
  2. Вычисление оценки .

.

  1. Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы, найденной в п. 5, вычеркиванием 3-й строки, 4-го столбца и запрещением элемента .

.

Значит .

  1. Допустимое решение задачи. В п. 10 получена матрица размером с двумя незапрещенными элементами и . Это означает, что множество  состоит из единственного маршрута, который содержит дуги . Его длина равна 23, т.е. .
  2. Отсев неперспективных множеств. Так как , то множество не содержит оптимального решения и выбывает из числа кандидатов на ветвление.
  3. Выбор множества для ветвления. Кандидатом на ветвление является только множество .
  4. Выбор дуги ветвления. Для приведенной матрицы из п. 4 вычислим

.

Выберем для ветвления дугу .

  1. Ветвление. Множество разбиваем на два подмножества и .
  2. Вычисление оценки . . Так как , то объявляется неперспективным.
  3. Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы, найденной в п. 4, вычеркиванием 2-й строки, 1-го столбца и запрещением элемента .

.

Итак, .

  1. Выбор множества для ветвления. Единственным кандидатом на ветвление является .
  2. Выбор дуги ветвления. Для приведенной матрицы из п. 18 вычислим . Выберем для ветвления дугу .
  3. Ветвление. Множество разбивается на и .
  4. Вычисление оценки . .
  5. Вычисление оценки . Матрица, соответствующая , получается из приведенной матрицы, найденной в п. 18, вычеркиванием 1-й строки, 3-го столбца и запрещением элемента (исключаем цикл ).

Значит .

  1. Выбор множества для ветвления. Кандидатами на ветвление являются и . Так как для обоих множеств нижняя оценка больше рекорда целевой функции, то они являются неперспективными. Других кандидатов на ветвление нет. Следовательно, процесс решения задачи окончен. Оптимальным решением является маршрут , его длина равна 23.

Таким образом, в работе представлен пример решения задачи коммивояжера применительно к процессу формирования оптимального маршрута движения выездной метрологической группы по пунктам осуществления поверочных работ в местах эксплуатации средств измерений.

 

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

 

  1. Тюхтина А.А. Методы дискретной оптимизации: Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2014 – 62 с.
  


Полная версия статьи PDF

Номер журнала Вестник науки №1 (58) том 2

  


Ссылка для цитирования:

Ершова К.А. ЗАДАЧА ОПТИМИЗАЦИИ МАРШРУТА ДВИЖЕНИЯ ВЫЕЗДНОЙ МЕТРОЛОГИЧЕСКОЙ ГРУППЫ // Вестник науки №1 (58) том 2. С. 236 - 245. 2023 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/6980 (дата обращения: 29.03.2024 г.)


Альтернативная ссылка латинскими символами: vestnik-nauki.com/article/6980



Нашли грубую ошибку (плагиат, фальсифицированные данные или иные нарушения научно-издательской этики) ?
- напишите письмо в редакцию журнала: zhurnal@vestnik-nauki.com


Вестник науки СМИ ЭЛ № ФС 77 - 84401 © 2023.    16+




* В выпусках журнала могут упоминаться организации (Meta, Facebook, Instagram) в отношении которых судом принято вступившее в законную силу решение о ликвидации или запрете деятельности по основаниям, предусмотренным Федеральным законом от 25 июля 2002 года № 114-ФЗ 'О противодействии экстремистской деятельности' (далее - Федеральный закон 'О противодействии экстремистской деятельности'), или об организации, включенной в опубликованный единый федеральный список организаций, в том числе иностранных и международных организаций, признанных в соответствии с законодательством Российской Федерации террористическими, без указания на то, что соответствующее общественное объединение или иная организация ликвидированы или их деятельность запрещена.