An agile optimization algorithm for the tourist trip design problem with type-covering constraints

Xabier A. Martin; Javier Panadero; Angel A. Juan; Xabier A. Martin; Javier Panadero; Angel A. Juan

doi:10.3934/math.2026100

AIMS Mathematics

2026, Volume 11, Issue 1: 2458-2480. doi: 10.3934/math.2026100

Previous Article Next Article

Research article

An agile optimization algorithm for the tourist trip design problem with type-covering constraints

1.
CIGIP - ValgrAI, Universitat Politècnica de València, Alcoy, Spain
2.
Dept. of Computer Architecture and Operating Systems, Universitat Autònoma de Barcelona, Bellaterra, Spain

Received: 18 September 2025 Revised: 29 December 2025 Accepted: 16 January 2026 Published: 26 January 2026
MSC : 90C27, 90C59

The tourist trip design problem with type-covering constraints (TTDP-TC) is a novel variant of the well-established orienteering problem (OP) designed to address the complex preferences of tourists planning multi-day trips. Unlike classical routing problems, which require visiting all points of interest (POIs), the TTDP-TC allows selective visitation based on perceived value, subject to a maximum travel time constraint. This variant introduces a type-covering requirement, ensuring that each trip includes at least one POI of every specified type, adding a layer of complexity to the optimization process. In this paper, an agile optimization algorithm to solve the TTDP-TC efficiently is proposed, which aims to maximize the total profit collected from visited POIs while ensuring compliance with type-covering requirements and travel time limits. Our approach applies the coverage rules to the overall routing plan, instead of just to singular itineraries as in other recent studies. The algorithm's performance is validated through extensive computational experiments, demonstrating its ability to generate high-quality solutions within short computational times. To further validate the competitiveness of our approach, an exact method to compare the results of our approach is also implemented. The proposed approach showcases significant potential for practical applications in tourist decision support systems, offering a flexible and robust solution for planning enriched and diverse tourist experiences.
- tourism planning,
- orienteering problem,
- heuristics,
- biased-randomization,
- agile optimization
Citation: Xabier A. Martin, Javier Panadero, Angel A. Juan. An agile optimization algorithm for the tourist trip design problem with type-covering constraints[J]. AIMS Mathematics, 2026, 11(1): 2458-2480. doi: 10.3934/math.2026100

Related Papers:

Abstract

The tourist trip design problem with type-covering constraints (TTDP-TC) is a novel variant of the well-established orienteering problem (OP) designed to address the complex preferences of tourists planning multi-day trips. Unlike classical routing problems, which require visiting all points of interest (POIs), the TTDP-TC allows selective visitation based on perceived value, subject to a maximum travel time constraint. This variant introduces a type-covering requirement, ensuring that each trip includes at least one POI of every specified type, adding a layer of complexity to the optimization process. In this paper, an agile optimization algorithm to solve the TTDP-TC efficiently is proposed, which aims to maximize the total profit collected from visited POIs while ensuring compliance with type-covering requirements and travel time limits. Our approach applies the coverage rules to the overall routing plan, instead of just to singular itineraries as in other recent studies. The algorithm's performance is validated through extensive computational experiments, demonstrating its ability to generate high-quality solutions within short computational times. To further validate the competitiveness of our approach, an exact method to compare the results of our approach is also implemented. The proposed approach showcases significant potential for practical applications in tourist decision support systems, offering a flexible and robust solution for planning enriched and diverse tourist experiences.

References

[1]	J. Ruiz-Meza, J. R. Montoya-Torres, A systematic literature review for the tourist trip design problem: Extensions, solution techniques and future research lines, Oper. Res. Perspect., 9 (2022), 100228. https://doi.org/10.1016/j.orp.2022.100228 doi: 10.1016/j.orp.2022.100228
[2]	P. Vansteenwegen, W. Souffriau, Trip planning functionalities: State of the art and future, Inf. Technol. Tour., 12 (2010), 305–315. https://doi.org/10.3727/109830511X13049763021853 doi: 10.3727/109830511X13049763021853
[3]	T. Tsiligirides, Heuristic methods applied to orienteering, J. Oper. Res. Soc., 35 (1984), 797–809. https://doi.org/10.1057/jors.1984.162 doi: 10.1057/jors.1984.162
[4]	R. Gama, H. L. Fernandes, A reinforcement learning approach to the orienteering problem with time windows, Comput. Oper. Res., 133 (2021), 105357. https://doi.org/10.1016/j.cor.2021.105357 doi: 10.1016/j.cor.2021.105357
[5]	S. W. Lin, V. F. Yu, Solving the team orienteering problem with time windows and mandatory visits by multi-start simulated annealing, Comput. Ind. Eng., 114 (2017), 195–205. https://doi.org/10.1016/j.cie.2017.10.020 doi: 10.1016/j.cie.2017.10.020
[6]	M. Khodadadian, A. Divsalar, C. Verbeeck, A. Gunawan, P. Vansteenwegen, Time dependent orienteering problem with time windows and service time dependent profits, Comput. Oper. Res., 143 (2022), 105794. https://doi.org/10.1016/j.cor.2022.105794 doi: 10.1016/j.cor.2022.105794
[7]	H. Kim, B. I. Kim, D. jin Noh, The multi-profit orienteering problem, Comput. Ind. Eng., 149 (2020), 106808. https://doi.org/10.1016/j.cie.2020.106808 doi: 10.1016/j.cie.2020.106808
[8]	C. Bayliss, A. A. Juan, C. S. Currie, J. Panadero, A learnheuristic approach for the team orienteering problem with aerial drone motion constraints, Appl. Soft Comput., 92 (2020), 106280. https://doi.org/10.1016/j.asoc.2020.106280 doi: 10.1016/j.asoc.2020.106280
[9]	A. Estrada-Moreno, A. Ferrer, A. A. Juan, J. Panadero, A. Bagirov, The non-smooth and bi-objective team orienteering problem with soft constraints, Mathematics, 8 (2020), 1461. https://doi.org/10.3390/math8091461 doi: 10.3390/math8091461
[10]	L. Evers, K. Glorie, S. van der Ster, A. I. Barros, H. Monsuur, A two-stage approach to the orienteering problem with stochastic weights, Comput. Oper. Res., 43 (2014), 248–260. https://doi.org/10.1016/j.cor.2013.09.011 doi: 10.1016/j.cor.2013.09.011
[11]	J. Panadero, A. A. Juan, C. Bayliss, C. Currie, Maximising reward from a team of surveillance drones: a simheuristic approach to the stochastic team orienteering problem, Eur. J. Ind. Eng., 14 (2020), 485. https://doi.org/10.1504/EJIE.2020.108581 doi: 10.1504/EJIE.2020.108581
[12]	J. Panadero, M. Ammouriova, A. A. Juan, A. Agustin, M. Nogal, C. Serrat, Combining parallel computing and biased randomization for solving the team orienteering problem in real-time, Appl. Sci., 11 (2021), 12092. https://doi.org/10.3390/app112412092 doi: 10.3390/app112412092
[13]	T. İlhan, S. M. R. Iravani, M. S. Daskin, The orienteering problem with stochastic profits, IIE Trans., 40 (2008), 406–421. https://doi.org/10.1080/07408170701592481 doi: 10.1080/07408170701592481
[14]	P. Vansteenwegen, W. Souffriau, D. V. Oudheusden, The orienteering problem: A survey, Eur. J. Oper. Res., 209 (2011), 1–10. https://doi.org/10.1016/j.ejor.2010.03.045 doi: 10.1016/j.ejor.2010.03.045
[15]	A. Gunawan, H. C. Lau, P. Vansteenwegen, Orienteering problem: A survey of recent variants, solution approaches and applications, Eur. J. Oper. Res., 255 (2016), 315–332. https://doi.org/10.1016/j.ejor.2016.04.059 doi: 10.1016/j.ejor.2016.04.059
[16]	C. Archetti, F. Carrabs, R. Cerulli, The set orienteering problem, Eur. J. Oper. Res., 267 (2018), 264–272. https://doi.org/10.1016/j.ejor.2017.11.009
[17]	F. Carrabs, A biased random-key genetic algorithm for the set orienteering problem, Eur. J. Oper. Res., 292 (2021), 830–854. https://doi.org/10.1016/j.ejor.2020.11.043 doi: 10.1016/j.ejor.2020.11.043
[18]	R. Pěnička, J. Faigl, M. Saska, Variable neighborhood search for the set orienteering problem and its application to other orienteering problem variants, Eur. J. Oper. Res., 276 (2019), 816–825. https://doi.org/10.1016/j.ejor.2019.01.047 doi: 10.1016/j.ejor.2019.01.047
[19]	M. Dontas, G. Sideris, E. G. Manousakis, An adaptive memory matheuristic for the set orienteering problem, Eur. J. Oper. Res., (2023). https://doi.org/10.1016/j.ejor.2023.02.008
[20]	T. D. Nguyen, R. Martinelli, Q. A. Pham, M. H. Hà, The set team orienteering problem, Eur. J. Oper. Res., 321 (2025), 75–87. https://doi.org/10.1016/j.ejor.2024.09.021 doi: 10.1016/j.ejor.2024.09.021
[21]	A. Gunawan, V. F. Yu, A. N. Sutanto, P. Jodiawan, Set team orienteering problem with time windows, in Learning and Intelligent Optimization: 15th International Conference, LION 15, Athens, Greece, June 20–25, 2021, Revised Selected Papers 15. Springer, 2021,142–149. https://doi.org/10.1007/978-3-030-92121-7_12
[22]	E. Angelelli, C. Archetti, M. Vindigni, The clustered orienteering problem, Eur. J. Oper. Res., 238 (2014), 404–414. https://doi.org/10.1016/j.ejor.2014.04.006 doi: 10.1016/j.ejor.2014.04.006
[23]	A. E. Yahiaoui, A. Moukrim, M. Serairi, Hybrid heuristic for the clustered orienteering problem, in Computational Logistics: 8th International Conference, ICCL 2017, Southampton, UK, October 18-20, 2017, Proceedings 8. Springer, 2017, 19–33. https://doi.org/10.1007/978-3-319-68496-3_2
[24]	Q. Wu, M. He, J. K. Hao, Y. Lu, An effective hybrid evolutionary algorithm for the clustered orienteering problem, Eur. J. Oper. Res., 313 (2024), 418–434. https://doi.org/10.1016/j.ejor.2023.08.006 doi: 10.1016/j.ejor.2023.08.006
[25]	A. E. Yahiaoui, A. Moukrim, M. Serairi, The clustered team orienteering problem, Comput. Oper. Res., 111 (2019), 386–399. https://doi.org/10.1016/j.cor.2019.07.008 doi: 10.1016/j.cor.2019.07.008
[26]	T. Derya, E. Dinler, B. Keçeci, Selective generalized travelling salesman problem, Math. Comput. Model. Dynam. Syst., 26 (2020), 80–118. https://doi.org/10.1080/13873954.2019.1705496 doi: 10.1080/13873954.2019.1705496
[27]	K. Ameranis, N. Vathis, D. Fotakis, Minimum and maximum category constraints in the orienteering problem with time windows, in International Symposium on Experimental Algorithms. Springer, 2019,343–358. https://doi.org/10.1007/978-3-030-34029-2_23
[28]	C. Panagiotakis, E. Daskalaki, H. Papadakis, P. Fragopoulou, An expectation-maximization framework for personalized itinerary recommendation with poi categories and must-see pois, ACM Trans. Recom. Syst., 3 (2024), 1–33. https://doi.org/10.1145/3696114 doi: 10.1145/3696114
[29]	A. Expósito, S. Mancini, J. Brito, J. A. Moreno, A fuzzy grasp for the tourist trip design with clustered pois, Expert Syst. Appl., 127 (2019), 210–227. https://doi.org/10.1016/j.eswa.2019.03.004 doi: 10.1016/j.eswa.2019.03.004
[30]	D. Jriji, S. Krichen, F. Madany, A memetic algorithm for the tourist trip design with clustered points of interests, in 2020 International Multi-Conference on: "Organization of Knowledge and Advanced Technologies"(OCTA). IEEE, 2020, 1–6. https://doi.org/10.1109/OCTA49274.2020.9151767
[31]	N. Bianchessi, R. Mansini, M. G. Speranza, A branch-and-cut algorithm for the team orienteering problem, Int. T. Oper. Res., 25 (2018), 627–635. https://doi.org/10.1111/itor.12422 doi: 10.1111/itor.12422
[32]	H. R. Lourenço, O. C. Martin, T. Stützle, Iterated local search: Framework and applications, in Handbook of Metaheuristics, Springer, 2018,129–168. https://doi.org/10.1007/978-3-319-91086-4_5
[33]	E. G. Talbi, Metaheuristics: from design to implementation, John Wiley & Sons, 2009. https://doi.org/10.1002/9780470496916
[34]	S. Ropke, D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transport. Sci., 40 (2006), 455–472. https://doi.org/10.1287/trsc.1050.0135 doi: 10.1287/trsc.1050.0135
[35]	A. A. Juan, P. Keenan, R. Martí, S. McGarraghy, J. Panadero, P. Carroll, et al., A review of the role of heuristics in stochastic optimisation: From metaheuristics to learnheuristics, Ann. Oper. Res., 320 (2023), 831–861. https://doi.org/10.1007/s10479-021-04142-9 doi: 10.1007/s10479-021-04142-9
[36]	L. Ke, W. Yang, Reformulation and metaheuristic for the team orienteering arc routing problem, in Advances in Swarm Intelligence: 8th International Conference, ICSI 2017, Fukuoka, Japan, July 27–August 1, 2017, Proceedings, Part II 8. Springer, 2017,494–501. https://doi.org/10.1007/978-3-319-61833-3_52
[37]	I. M. Chao, B. L. Golden, E. A. Wasil, The team orienteering problem, Eur. J. Oper. Res., 88 (1996), 464–474. https://doi.org/10.1016/0377-2217(94)00289-4 doi: 10.1016/0377-2217(94)00289-4

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)