RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication
Artículo científico (JournalArticle)
A sim-learnheuristic algorithm for the stochastic and context-aware team orienteering problem
[EN] This paper addresses the Team Orienteering Problem (TOP) with stochastic, context-aware travel times. Traditionally, simheuristics have been used to address stochastic variants of TOP and related routing problems. Simheuristics combine metaheuristics and simulation to deal with stochastic inputs, but they often rely on generic, independent random sampling which ignores that travel times in real traffic networks are dynamic and depend on contextual factors, such as congestion or weather conditions. We propose to extend the traditional simheuristic concept by integrating a machine learning component to overcome this limitation. To apply this novel methodology, models are trained on historical data to predict context-aware travel times. In addition, this historical data and clustering models are used to generate context-aware probability distributions. These customized distributions provide the simulation step with more realistic inputs, ensuring that the evaluation of candidate solutions reflects actual dynamic conditions. We compare a deterministic metaheuristic, a standard simheuristic approach, and the proposed sim-learnheuristic approach on extended benchmark instances. Computational experiments show that the sim-learnheuristic consistently outperforms both the traditional simheuristic and the deterministic metaheuristic, achieving average improvements of approximately 18% and 30%, respectively, under stochastic-dynamic evaluation., This work has been partially supported by the Spanish Ministry of Science, Innovation and Universities/AEI (PID2025-169830NB-I00, PID2022-138860NB-I00, AIA2025-163553-C44) and the Generalitat Valenciana (2024 CIAICO 117), by Comunidad Autonoma de Madrid (grant ref. TEC-2024/COM-404), Ministerio de Economia y Competitividad (grant ref. PID2024-160226OB-C22), and Ministerio para la Transformacion Digital y de la Funcion Publica (Catedra ENIA AI4DDS, grant ref. TSI-100930-2023-3). Funding was also received from the "Agencia Estatal de Investigacion" through the "Ayudas para contratos para la formacion de doctores y doctoras en empresas y otras entidades (Doctorados Industriales) 2024" (grant ref. DIN2024-013339), through the company OGA (qosITconsulting, S.L).
Project:
Agencia Estatal de Investigación / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2022-138860NB-I00
,
Agencia Estatal de Investigación / Plan Estatal de Investigación Científica y Técnica y de Innovación 2024-2027 AIA2025-163553-C44
,
Agencia Estatal de Investigación / Plan Estatal de Investigación Científica y Técnica y de Innovación 2024-2027 PID2024-160226OB-C22
,
Generalitat Valenciana CIAICO/2024/117
,
Caja de Ahorros del Mediterráneo TEC-2024/COM-404
,
Agencia Estatal de Investigación DIN2024-013339
,
Agencia Estatal de Investigación PID2025-169830NB-I00
,
Universitat Politècnica de València TSI-100930-2023-3