A Kernel Search Heuristic for the Robust Team Orientation Problem with Steiner vertices and decreasing priorities as a function of time

We introduce the Robust Steiner Team Orienteering Problem with Decreasing Priorities to model disaster relief operations. Locations in need of rescue shuttles are sub-divided into mandatory and optional, being the latter linked to priorities that decrease over time. We aim to find routes that maximize the priorities collected, while considering uncertain service times and a route duration limit. Additionally, the number of serviced locations that assume their maximum service times is subject to a robust uncertainty budget. We propose a model for the problem and solve it via CPLEX and a Kernel Search heuristic. The results suggest the difficulty of the problem to be solved to optimality and highlight the proposed heuristic as a promising alternative, being able to find, within five minutes of average time execution, solutions better than or equal to the ones found by CPLEX (in up to one hour) for 83% of the instances tested.