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

E. E. Ivanko

doi:10.14529/mmp160311

Authors

E. E. Ivanko Krasovskii Institute of Mathematics and Mechanics

DOI:

https://doi.org/10.14529/mmp160311

Keywords:

sensors reposition, route optimization, traveling salesman problem, linear order.

Abstract

The problem of optimal measurements planning with regularly repositioning sensors is considered. This abstract problem may serve as a mathematical model for a variety of different applied problems connected with cost optimization in the experiments where sensors are used for the estimation of the environment parameters. There are two levels of optimization in the considered problem: movement optimization in the process of sensors reposition from one group of points to another and order optimization in which the groups of positions follow each other. The exact solution of the two-level problem is proposed and supported by the results of computation experiment.

Author Biography

E. E. Ivanko, Krasovskii Institute of Mathematics and Mechanics

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

References

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.