Team Orienteering Problem with Communication Constraints: A Multi-Objective Approach for Multi-Robot Systems
DOI:
https://doi.org/10.5753/reic.2026.8485Keywords:
Team Orienteering, Communication Constraints, Multi-Robot Systems, Variable Neighborhood SearchAbstract
Multi-Robot Systems are essential for applications such as search and rescue and environmental monitoring. However, traditional Team Orienteering Problem (TOP) approaches neglect inter-agent communication constraints. This work introduces the TOP with Communication Constraints (TOP-CC), a multi-objective formulation that optimizes task coverage, energy efficiency, and connectivity preservation. Our Variable Neighborhood Search-based metaheuristic handles heterogeneous teams with varying speeds and budgets. Experiments on 278 benchmark instances demonstrate competitive reward collection while maintaining communication quality.
Downloads
References
Angelelli, E., Archetti, C., and Vindigni, M. (2014). The clustered orienteering problem. European Journal of Operational Research, 238(2):404–414.
Archetti, C., Carrabs, F., and Cerulli, R. (2018). The set orienteering problem. European Journal of Operational Research, 267(1):264–272.
Bayliss, C., Juan, A. A., Currie, C. S., and Panadero, J. (2020). A learnheuristic approach for the team orienteering problem with aerial drone motion constraints. Applied Soft Computing, 92:106280.
Campbell, A. M., Gendreau, M., and Thomas, B. W. (2011). The probabilistic orienteering problem. Computers & Operations Research, 81:269–281.
Chao, I.-M., Golden, B. L., and Wasil, E. A. (1996). The team orienteering problem. European Journal of Operational Research, 88(3):464–474.
El-Hajj, R., Dang, D.-C., and Moukrim, A. (2016). Solving the team orienteering problem with cutting planes. Computers & Operations Research, 74:21–30.
Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., and Vathis, N. (2015). Heuristics for the time dependent team orienteering problem. Computers & Operations Research, 62:36–50.
Geiger, M. J. (2008). Randomised variable neighbourhood search for multi objective optimisation. arXiv preprint arXiv:0809.0271.
Golden, B. L., Levy, L., and Vohra, R. (1987). The orienteering problem. Naval Research Logistics, 34(3):307–318.
Kantor, M. G. and Rosenwein, M. B. (1992). The orienteering problem with time windows. Journal of the Operational Research Society, 43(6):629–635.
Ke, L., Zhai, L., Li, J., and Chan, F. T. (2016). Pareto mimic algorithm: An approach to the team orienteering problem. Omega, 61:155–166.
Li, J., Zhu, J., Peng, G., Wang, J., Zhen, L., and Demeulemeester, E. (2024). Branch-price-and-cut algorithms for the team orienteering problem with interval-varying profits. European Journal of Operational Research, 319(3):793–807.
Liu, B., Xiao, X., and Stone, P. (2021). Team orienteering coverage planning with uncertain reward. In IEEE/RSJ IROS, pages 9728–9733.
Mansfield, A., Macharet, D. G., and Hsieh, M. A. (2023). Energy-efficient team orienteering problem in the presence of time-varying ocean currents. In IEEE/RSJ IROS, pages 838–843.
Mansfield, A., Manjanna, S., Macharet, D. G., and Hsieh, M. A. (2021). Multi-robot scheduling for environmental monitoring as a team orienteering problem. In IEEE/RSJ IROS, pages 6398–6404.
Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11):1097–1100.
Santos, R. F., Nascimento, E. R., and Macharet, D. G. (2021). Anytime fault-tolerant adaptive routing for multi-robot teams. In Proc. of IEEE ICRA, pages 7936–7942.
Shetty, A., Hussain, T., and Gao, G. (2023). Decentralized connectivity maintenance for multi-robot systems under motion and sensing uncertainties. NAVIGATION, 70(1).
Tristão, M. T. P. T. and Macharet, D. G. (2025). Team orienteering problem with communication constraints. In 2025 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). DOI: 10.1109/IROS60139.2025.11246209.
Vansteenwegen, P., Souffriau, W., and Van Oudheusden, D. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1):1–10.
Xu, W., Xu, Z., Peng, J., Liang, W., Liu, T., Jia, X., and Das, S. K. (2020). Approximation algorithms for the team orienteering problem. In IEEE INFOCOM, pages 1389–1398.
Yahiaoui, A.-E., Moukrim, A., and Serairi, M. (2019). The clustered team orienteering problem. Computers & Operations Research, 111:386–399.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 The authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
