Двухуровневая оптимизация перестановки сенсоров

Евгений Евгеньевич Иванко

doi:10.14529/mmp160311

Авторы

Евгений Евгеньевич Иванко Институт математики и механики им. Н.Н. Красовского УрО РАН, Уральский государственный университет им.первого Президента России Б.Н.Ельцина, Механнико-машиностроительный институт

DOI:

https://doi.org/10.14529/mmp160311

Ключевые слова:

перестановка сенсоров, оптимизация маршрута, задача коммивояжера, линейный порядок.

Аннотация

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

Биография автора

Евгений Евгеньевич Иванко, Институт математики и механики им. Н.Н. Красовского УрО РАН, Уральский государственный университет им.первого Президента России Б.Н.Ельцина, Механнико-машиностроительный институт

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

Библиографические ссылки

Anily S. The Traveling Salesman Problem with Delivery and Backhauls / S. Anily, G. Mosheiov // Operations Research Letters. - 1994. - V. 16, № 1. - P. 11-18.

Gendreau, M. Heuristics for the Traveling Salesman Problem with Pickup and Delivery / M. Gendreau, G. Laporte, D. Vigo // Computers & Operations Research. - 1999. - V. 26, № 7. - P. 699-714.

Hernandez-Perez, H. A Branch-and-Cut Algorithm for a Traveling Salesman Problem with Pickup and Delivery / H. Hernandez-Perez, J.J. Salazar-Gonzalez // Discret Applied Mathematics. - 2004. - V. 145. - P. 126-139.

Иванко, Е.Е. Динамическое программирование в задаче перестановки однотипных объектов / Е.Е. Иванко // Тр. Ин-та математики и механики УрО РАН. - 2013. - Т. 19, № 4. - С. 125-130.

Cherkassky, B.V. Shortest Paths Algorithms: Theory and Experimental Evaluation / B.V. Cherkassky, A.V. Goldberg, T. Radzik // Mathematical Programming. - 1996. - № 73. - P. 129-174.

MacGregor, J.N. Human Performance on the Traveling Salesman and Related Problems: A Review / J.N. MacGregor, Y. Chu // Journal of Problem Solving. - 2001. - V. 3, № 2. - P. 1-29.