A new hierarchical matheuristic applied to the helicopter routing problems (HRP)

Full abstract

Read the full abstract

Abstract This paper proposes a hierarchical matheuristic for the Helicopter Routing Problem (HRP) with the Greedy Randomized Adaptive Search Procedure (GRASP), mathematical models, and Variable Neighborhood Search (VNS). The HRP focuses on fulfilling transportation requests, defined by embarkation and disembarkation pairs, with helicopters as the transport mode. The proposed method uses constructive heuristics and the Set-Covering Problem (SCP) for routing. SCP utilizes local optima from earlier VNS iterations to form a partial tour, which a constructive heuristic may complete. The solution then undergoes local search via VNS, iteratively applied as the main GRASP loop. Finally, the Set-Partitioning Problem (SPP) provides a superior solution to those found in the GRASP. The hierarchical approach is applied to HRP challenges across varied search spaces. A new operator is introduced to efficiently map between these search spaces. Additionally, a new SPP model for HRP is presented, including constraints focused on secure vehicle landings. This integrated approach aims to optimize HRP processes by navigating different search spaces, enhancing adaptability, and addressing safety in landings. Computational results on two HRP instance sets, HRPS and HRPM, demonstrate the algorithm’s competitiveness in solution quality.