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

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

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

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

Литература

1. Anily S. The Traveling Salesman Problem with Delivery and Backhauls / S. Anily, G. Mosheiov // Operations Research Letters. - 1994. - V. 16, № 1. - P. 11-18.
2. 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.
3. 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.
4. Иванко, Е.Е. Динамическое программирование в задаче перестановки однотипных объектов / Е.Е. Иванко // Тр. Ин-та математики и механики УрО РАН. - 2013. - Т. 19, № 4. - С. 125-130.
5. 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.
6. 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.