Groupe d’études et de recherche en analyse des décisions

Column Generation Based Heuristic for a Helicopter Routing Problem

Marcus V.S. Poggi De Aragao Pontifícia Universidade Católica do Rio de Janeiro, Brésil

This work presents a column generation based heuristic algorithm for the problem of planning the flights of helicopters to attend transport requests among airports in the continent and offshore platforms on the Campos basin for the Brazilian State Oil Company (Petrobras). We start from a previous MIP based heuristic for this Helicopter Routing Problem and add column generation procedures that improve the solution quality. This is done by extending the earlier formulation and providing an algorithm to find optimal passenger allocation to fixed helicopter routes. A post optimization procedure completes the resulting algorithm, which is more stable and allows consistently finding solutions that improve the safety and the cost of the one done by the oil company experts.