Solving the stochastic team orienteering problem: comparing simheuristics with the sample average approximation method
Fecha
2023Versión
Acceso abierto / Sarbide irekia
Tipo
Artículo / Artikulua
Versión
Versión publicada / Argitaratu den bertsioa
Identificador del proyecto
Impacto
|
10.1111/itor.13302
Resumen
The team orienteering problem (TOP) is anNP-hardoptimization problem with an increasing number of po-tential applications in smart cities, humanitarian logistics, wildfire surveillance, etc. In the TOP, a fixed fleetof vehicles is employed to obtain rewards by visiting nodes in a network. All vehicles share common originand destination locations. Since each vehicle has a limitation in time or tra ...
[++]
The team orienteering problem (TOP) is anNP-hardoptimization problem with an increasing number of po-tential applications in smart cities, humanitarian logistics, wildfire surveillance, etc. In the TOP, a fixed fleetof vehicles is employed to obtain rewards by visiting nodes in a network. All vehicles share common originand destination locations. Since each vehicle has a limitation in time or traveling distance, not all nodes inthe network can be visited. Hence, the goal is focused on the maximization of the collected reward, takinginto account the aforementioned constraints. Most of the existing literature on the TOP focuses on its de-terministic version, where rewards and travel times are assumed to be predefined values. This paper focuseson a more realistic TOP version, where travel times are modeled as random variables, which introduces reli-ability issues in the solutions due to the route-length constraint. In order to deal with these complexities, wepropose a simheuristic algorithm that hybridizes biased-randomized heuristics with a variable neighborhoodsearch and MCS. To test the quality of the solutions generated by the proposed simheuristic approach, weemploy the well-known sample average approximation (SAA) method, as well as a combination model thathybridizes the metaheuristic used in the simheuristic approach with the SAA algorithm. The results showthat our proposed simheuristic outperforms the SAA and the hybrid model both on the objective functionvalues and computational time. [--]
Materias
Team orienteering problem,
Random travel times,
Biased-randomized algorithms,
Simheuristics,
Sample average approximation
Editor
Wiley
Publicado en
International Transactions in Operational Research. 0 (2023)
Departamento
Universidad Pública de Navarra. Departamento de Estadística, Informática y Matemáticas /
Nafarroako Unibertsitate Publikoa. Estatistika, Informatika eta Matematika Saila /
Universidad Pública de Navarra/Nafarroako Unibertsitate Publikoa. Institute of Smart Cities - ISC
Versión del editor
Entidades Financiadoras
This work has been partially supported by the Spanish Ministry of Science, Innovation, and Universities (PID2019-111100RB-C21/C22/AEI/10.13039/501100011033). Similarly, we appreciate
the financial support of the Barcelona City Council and “La Caixa” (21S09355-001).
Aparece en las colecciones
Los documentos de Academica-e están protegidos por derechos de autor con todos los derechos reservados, a no ser que se indique lo contrario.
La licencia del ítem se describe como © 2023 The Authors. This is an open access article under the terms of the Creative Commons Attribution-NonCommercial-NoDerivs License, which permits use and distribution in any medium, provided the original work is properly cited, the use is non-commercial and no modifications or adaptations are made.