The hazardous team orienteering problem
摘要
This paper presents the Hazardous Team Orienteering Problem (HTOP), an extension of the Hazardous Orienteering Problem designed for multiple vehicles. In HTOP, visiting certain customers exposes the vehicle to a time-dependent risk of catastrophic loss. Each hazardous customer has an associated exponential failure rate, meaning that if an explosion occurs, the entire profit earned from that route is lost. The goal is to maximize the total expected profit collected by a fleet of vehicles while adhering to time constraints and ensuring customer exclusivity. We introduce two solution approaches. First, we develop an exact Branch-and-Price algorithm based on a set-partitioning reformulation, where each column corresponds to a feasible hazardous route valued by its expected profit. Second, we create an Adaptive Large Neighborhood Search (ALNS) metaheuristic tailored to the nonlinear expected-profit structure of the problem. Computational experiments on benchmark instances derived from the existing literature on the Hazardous Orienteering Problem demonstrate that the pricing phase is the main computational bottleneck of the exact approach. Nevertheless, our method successfully solves small and medium-sized instances to optimality. The ALNS consistently generates high-quality solutions in a short amount of time and matches the optimal solutions for single-vehicle benchmarks while showing strong scalability in multi-vehicle scenarios.