The Robust Steiner Team Orienteering Problem with Decreasing Priorities under budgeted uncertainty

Post-disaster relief operations have gained attention over the past decade, focusing on enhancing resilience in labor and social environments. This work introduces the Robust Steiner Team Orienteering Problem with Decreasing Priorities (R-STOP-DP) to model emergency rescue operations where several locations might need relief shuttles, but exact demands cannot be foreseen. R-STOP-DP is a variation of the vehicle routing problem with location priorities that applies robust optimization to model the variability on service times incurred by visiting locations. Locations are sub-divided into mandatory and optional, being the latter linked to priorities that linearly decrease over time. The goal is to find robust feasible routes maximizing the priorities collected, while considering the worst-case conditions of service times within an uncertainty budget and a routes’ duration limit. We propose two compact formulations – reinforced by valid inequalities adapted from the literature – and solve them in a cut-and-branch fashion. In addition, we propose a kernel search mat-heuristic and a simulated annealing heuristic. Computational experiments suggest the strict dominance of one formulation, improving dual bounds by 12.29% on average over the 360 instances tested. The cut-and-branch algorithm based on the stronger model also stands out, solving 20 more instances than the other. The simulated annealing heuristic obtains a remarkable performance by improving over and/or reaching the best-known bounds for the complete benchmark, within an average execution time of 2.52 s. In turn, the kernel search mat-heuristic reaches or improves the bounds for 81% of the instances within 4.5 min of average running time.