Este artigo busca solucionar um problema de roteamento aeroterrestre de transporte de cargas, com linhas aéreas predeterminadas e frotas próprias e heterogêneas. Para tanto, foram incluídos a um modelo tradicional do problema de roteamento de veículos arcos que representam as possíveis linhas aéreas. O modelo foi aplicado em um órgão governamental que possui 25 locais de entrega. Primeiramente foi realizado um teste com preenchimento total das demandas de todos os locais para fins de validação do modelo e, em seguida, foi aplicado no planejamento real de rotas de três períodos distintos. Em comparação com as rotas efetivamente realizadas, o modelo trouxe redução de 7% a 55% dos custos com transportes.