A Biased-Randomized Learnheuristic for Solving the Team Orienteering Problem with Dynamic Rewards

Abstract

In this paper we discuss the team orienteering problem (TOP) with dynamic inputs. In the static version of the TOP, a fixed reward is obtained after visiting each node. Hence, given a limited fleet of vehicles and a threshold time, the goal is to design the set of routes that maximize the total reward collected. While this static version can be efficiently tackled using a biased-randomized heuristic (BR-H), dealing with the dynamic version requires extending the BR-H into a learnheuristic (BR-LH). With that purpose, a ‘learning’ (white-box) mechanism is incorporated to the heuristic in order to consider the variations in the observed rewards, which follow an unknown (black-box) pattern.

En este artículo, analizamos el problema de orientación en equipo (TOP) con entradas dinámicas. En la versión estática del TOP, se obtiene una recompensa fija tras visitar cada nodo. Por lo tanto, dada una flota limitada de vehículos y un tiempo límite, el objetivo es diseñar el conjunto de rutas que maximice la recompensa total obtenida. Si bien esta versión estática puede abordarse eficientemente mediante una heurística aleatoria sesgada (BR-H), abordar la versión dinámica requiere extender la BR-H a una heurística de aprendizaje (BR-LH). Para ello, se incorpora a la heurística un mecanismo de aprendizaje (caja blanca) para considerar las variaciones en las recompensas observadas, que siguen un patrón desconocido (caja negra).