Um importante ramo do estudo de logística é aquele que se preocupa com a otimização da eficiência do uso de recursos de transporte. No segmento de aviação da Petrobras, que transporta cerca de 20 por cento de todos os passageiros offshore do planeta, otimizações são bastante significativas e podem gerar importantes benefícios econômicos (menor custo total), logísticos (maior disponibilidade de recursos), ambientais (menores emissões de gases poluentes) e de segurança (menor exposição aos riscos da atividade). Por estes motivos, é imperativo que se busque formas de aumentar a eficiência do uso das aeronaves contratadas, maximizando sua utilização dentro de limites permitidos por normas de voo offshore, limites de fadiga de tripulantes, limites operacionais dos aeroportos de origem e destino, além de limites de capacidades de cada aeronave. Neste sentido, o objetivo deste estudo é apresentar o desenvolvimento de soluções para redução dos custos da operação aérea, buscando o máximo aproveitamento das aeronaves contratadas, a partir de uma proposta de otimização da programação de voos através da resolução de um resolução de uma formulação de Programação Linear Inteira, que estende um Problema de Múltiplas Mochilas, respeitando as limitações impostas por regulamentação e necessidades operacionais. Foi desenvolvida uma ferramenta computacional e os resultados obtidos a partir deste trabalho foram implementados nas operações da Petrobras e fazem parte do Plano de Resiliência desta empresa. Os ganhos econômicos obtidos representam uma redução de 100 milhões de reais no quinquênio do Plano de Negócios e Gestão 2020-2024, o que comprova o benefício das soluções implementadas.