Clustered Orienteering Problem with Function-Based Rewards
Keywords:
Autonomous Agents, Orienteering Problem, Vehicle Routing, Evolutionary AlgorithmsAbstract
The Orienteering Problem is a well-studied problem that aims to determine an optimal route that maximizes the cumulative rewards while attaining a predefined travel budget. This classical formulation has been generalized in many forms, including grouping customers (locations) into clusters. However, such cluster-based formulation typically demands visiting all customers to collect the reward, thereby restricting its applicability. In this paper, we introduce a novel variant in which rewards associated with a cluster can be partially collected following a function that correlates with the number of customers attended within the cluster. This new formulation is a suitable alternative to model scenarios where the reward of the clusters can exhibit distinct and unique scaling patterns. We propose using an evolutionary algorithm to solve this problem and evaluate its performance considering different scenarios and aspects. The results demonstrate that our method effectively selects an appropriate number of clients to attend to based on the assigned function for each cluster.
Downloads
References
B. L. Golden, L. Levy, and R. Vohra, “The orienteering problem,” Naval Research Logistics (NRL), vol. 34, no. 3, pp. 307–318, 1987. https://doi.org/10.1002/1520-6750(198706)34:3<307::AIDNAV3220340302>3.0.CO;2-D.
E. Angelelli, C. Archetti, and M. Vindigni, “The clustered orienteering problem,” European Journal of Operational Research, vol. 238, no. 2, pp. 404–414, 2014. https://doi.org/10.1016/j.ejor.2014.04.006.
A. Mor and M. G. Speranza, “Vehicle routing problems over time: a survey,” 4OR, vol. 18, pp. 129–149, Jun 2020. https://doi.org/10.1007/s10288-020-00433-2.
K. L. Hoffman, M. Padberg, and G. Rinaldi, Traveling Salesman Problem, pp. 1573–1578. Boston, MA: Springer US, 2013. https://doi.org/10.1007/978-1-4419-1153-7_1068.
C. Archetti, F. Carrabs, and R. Cerulli, “The set orienteering problem,” European Journal of Operational Research, vol. 267, no. 1, pp. 264–272, 2018. https://doi.org/10.1016/j.ejor.2017.11.009.
I.-M. Chao, B. L. Golden, and E. A. Wasil, “The team orienteering problem,” European Journal of Operational Research, vol. 88, pp. 464–474, 2 1996. https://doi.org/10.1016/0377-2217(94)00289-4.
A. Mansfield, S. Manjanna, D. G. Macharet, and M. A. Hsieh, “Multi-robot scheduling for environmental monitoring as a team orienteering problem,” in 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 6398–6404, IEEE, 2021. https://doi.org/10.1109/IROS51168.2021.9636854.
M. G. Kantor and M. B. Rosenwein, “The Orienteering Problem with Time Windows,” Journal of the Operational Research Society, vol. 43, no. 6, pp. 629–635, 1992. https://doi.org/10.1057/jors.1992.88.
R. F. dos Santos, E. R. Nascimento, and D. G. Macharet, “Anytime Fault-tolerant Adaptive Routing for Multi-Robot Teams,” in 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 7936–7942, 2021. https://doi.org/10.1109/ICRA48506.2021.9561944.
A. Mansfield, D. G. Macharet, and M. A. Hsieh, “Energy-efficient Orienteering Problem in the Presence of Ocean Currents,” in 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 10081–10087, 2022. https://doi.org/10.1109/IROS47612.2022.9981818.
D. G. Macharet, A. Alves Neto, and D. Shishika, “Minimal Exposure Dubins Orienteering Problem,” IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 2280–2287, 2021. https://doi.org/10.1109/LRA.2021.3061004.
J. Yu, M. Schwager, and D. Rus, “Correlated Orienteering Problem and its Application to Persistent Monitoring Tasks,” IEEE Transactions on Robotics, vol. 32, pp. 1106–1118, 10 2016. https://doi.org/10.1109/TRO.2016.2593450.
J. Karbowska-Chilinska and P. Zabielski, Genetic Algorithm Solving the Orienteering Problem with Time Windows, vol. 240. 09 2013. https://doi.org/10.1007/978-3-319-01857-7_59.
M. Tasgetiren and A. Smith, “A genetic algorithm for the orienteering problem,” in Proceedings of the 2000 Congress on Evolutionary Computation.
CEC00 (Cat. No.00TH8512), vol. 2, pp. 910–915 vol.2, 2000. https://doi.org/10.1109/CEC.2000.870739.
C. Archetti, F. Carrabs, and R. Cerulli, “The set orienteering problem,” European Journal of Operational Research, vol. 267, no. 1, pp. 264–272, 2018. https://doi.org/10.1016/j.ejor.2017.11.009.
R. Pˇeniˇcka, J. Faigl, and M. Saska, “Variable neighborhood search for the set orienteering problem and its application to other orienteering problem variants,” European Journal of Operational Research, vol. 276, no. 3, pp. 816–825, 2019. https://doi.org/10.1016/j.ejor.2019.01.047.
Q. Wu, M. He, J.-K. Hao, and Y. Lu, “An effective hybrid evolutionary algorithm for the clustered orienteering problem,” European Journal of Operational Research, 2023. https://doi.org/10.1016/j.ejor.2023.08.006.
K. D. Mukhina, A. A. Visheratin, and D. Nasonov, “Orienteering problem with functional profits for multi-source dynamic path construction,” PLOS ONE, vol. 14, pp. 1–15, 04 2019. https://doi.org/10.1371/journal.pone.0213777.
M. Mitchell, An Introduction to Genetic Algorithms. Cambridge, MA, USA: MIT Press, 1998. https://doi.org/10.7551/mitpress/3927.001.0001.
K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints,” IEEE Transactions on Evolutionary Computation, vol. 18, pp. 577–601, 08 2014. https://doi.org/10.1109/TEVC.2013.2281535.
F.-A. Fortin, F.-M. De Rainville, M.-A. Gardner, M. Parizeau, and C. Gagné, “DEAP: Evolutionary algorithms made easy,” Journal of Machine Learning Research, vol. 13, pp. 2171–2175, jul 2012. https://api.semanticscholar.org/CorpusID:15629107.
M. Fischetti, J. J. Salazar González, and P. Toth, “A branch-and-cut algorithm for the symmetric generalized traveling salesman problem,” Operations Research, vol. 45, pp. 378–394, 06 1997. https://doi.org/10.1287/opre.45.3.378.
L. E. Almeida and D. G. Macharet, “Clustered Orienteering Problem with Subgroups,” CoRR, vol. abs/2312.16154, 2023. https://doi.org/10.48550/arXiv.2312.16154.
