Robust Heuristics for a Multi-Constrained Stochastic Team Orienteering Problem with Heterogeneous Resources

In many practical applications, tasks have to be assigned to multiple resources. In a standard Team Orienteering Problem (TOP), the aim is to assign tasks to resources in such a way that the value of the scheduled tasks is maximized. We consider an extensive variant of the TOP, which incorporates constraints regarding time windows and endurance, and for which the heterogeneous resources are allowed to recharge at their depots during their routes. For this problem, we propose a heuristic that combines Lagrangian Relaxation and Column Generation (LRCG), and a Tabu Search heuristic. The latter heuristic can handle resource-dependent values and sets of recurrent tasks with a non-linear profit function as well. Due to stochasticity of travel and service times, we need to take the robustness of solutions into account as well. For this purpose, we introduce the risk function as a new robustness concept, which aims to avoid the execution of tasks with a low value at the cost of having to remove a more important task in the future. As an additional robustness concept, we discuss setting a lower bound on the worst-case performance of a solution. We generate regular and robust solutions using the Tabu Search heuristic, applied to several test instances. For adjusting the generated solutions in real-time scenarios implied by simulations of travel and service times, we apply passive rescheduling policies. The results show that incorporating the risk function leads to a significant improvement of the real-time performance. In particular, a higher objective value is obtained and fewer tasks have to be removed. Moreover, important tasks are performed in an early stage of the route more often. For some instances, combining the risk function with a requirement on the worst-case performance improves the real-time results even further. When applying the LRCG heuristic to the deterministic problem, improvements of the subgradient algorithm lead to better feasible solutions and stronger upper bound estimators for the optimal objective value.