Answers are grounded in this paper and cite their sources.
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. • Introducing the Robust Steiner Team Orienteering problem with decreasing priorities to model disaster relief situations. • Proposal of two compact formulations and valid inequalities, experimentally showing the dual bound dominance of one formulation over the other. • Cut-and-branch approach based on the stronger model solves to optimality 20 more instances. • Simulated annealing heuristic improves over and/or reaches the best-known bounds for all the instances tested, with 2.52 s of average execution time.
No takes yet. Share an insight, caveat, or question.
Assunção et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: