A MILP Model and a GRASP Algorithm for the Helicopter Routing Problem with Multi-Trips and Time Windows

摘要

This work presents a new mixed-integer linear programming (MILP) model and a GRASP algorithm for the Helicopter Routing Problem (HRP) with multi-trips and time windows. The HRP consists of serving a set of transportation requests, defined as a pair of boarding and landing locations, where helicopters are used as transportation mode. This novel model incorporates the characteristics present in routing helicopters for offshore platforms and, also, a new set of constraints is proposed to handle an issue unnoticed so far for the HRP: offshore platforms can be visited by helicopters one at a time. The main goal of the presented HRP is to minimize the cost of meeting the set of transportation requests. We provide computational experiments for well-known instances available in the literature with up to 80 requests. On average, our GRASP algorithm is capable to solve all instances, whereas CPLEX found solutions only for small instances, lower bounds for small to medium instances and no lower bounds for medium to large instances.