VNS algorithm for the periodic pick-up and delivery helicopter routing problem in oil and gas offshore

Abstract

In offshore field development projects, the operating and transport expenses are crucial part of the total budget. In this paper, we introduce a new helicopter routing problem with splitting demands and a time horizon. A fleet of identical helicopters with known capacity should server predefined demands to deliver employees at the offshore platforms and return other employees to depot for every day of time horizon. All routes start and finish at the depot, the length of each route cannot exceed a given threshold. Our goal is to find the routes to satisfy all demands with minimal total length. To tackle this pick-up and delivery problem, we design the MILP model and adopt the VNS-algorithm. Some hard constraints are relaxed and included into the objective function with penalties. Computational results for real-world test instances of the JV «Vietsovpetro» Company illustrate ability for reduction the transport expenses up to 5-10%.

Keywords

• periodic vrp
• split delivery
• simultaneous delivery and pick up
• variable neighborhood search