A Simheuristic-Learnheuristic Algorithm for the Stochastic Team Orienteering Problem with Dynamic Rewards

In this paper, we consider the stochastic team orienteering problem with dynamic rewards (STOPDR) and stochastic travel times. In the STOPDR, the goal is to generate routes for a fixed set of vehicles such that the sum of the rewards collected is maximized while ensuring that nodes are visited before a fixed time limit expires. The rewards associated with each node are dependent upon the times at which they are visited. Also, the dynamic reward values have to be learnt from simulation experiments during the search process. To solve this problem, we propose a biased-randomized learnheuristic (BRLH), which integrates a learning module and a simulation model. Randomization is important for generating a wide variety of solutions that capture the trade-off between reward and reliability. A series of computational experiments are carried out in order to analyze the performance of our BRLH approach.