Two-Level Optimization of Sensors Reposition

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.

Keywords

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

References

1. Anily S., Mosheiov G. The Traveling Salesman Problem with Delivery and Backhauls. Operations Research Letters, 1994, vol. 16, no. 1, pp. 11-18.
2. Gendreau M., Laporte G., Vigo D. Heuristics for the Traveling Salesman Problem with Pickup and Delivery. Computers & Operations Research, 1999, vol. 26, no. 7, pp. 699-714.
3. Hernandez-Perez H., Salazar-Gonzalez J.J. A Branch-and-Cut Algorithm for a Traveling Salesman Problem with Pickup and Delivery. Discret Applied Mathematics, 2004, vol. 145, pp. 126-139.
4. Ivanko E.E. [Dynamical Programming in One-Type Objects Reposition Problem]. Trudy Instituta matematiki i mekhaniki UrO RAN [Proceedings of Institute of Mathematics and Mechanics], 2013, vol. 19, no. 4, pp. 125-130. (in Russian)
5. Cherkassky B.V., Goldberg A.V., Radzik T. Shortest Paths Algorithms: Theory and Experimental Evaluation. Mathematical Programming, 1996, no. 73, pp. 129-174.
6. MacGregor J.N., Chu Y. Human Performance on the Traveling Salesman and Related Problems: A Review. Journal of Problem Solving, 2001, vol. 3, no. 2, pp. 1-29.