Este artigo descreve uma forma de solucionar o Problema de Alocação de Frota no planejamento operacional de uma empresa de transporte coletivo e urbano, sob o ponto de vista dos custos improdutivos. Durante o processo de alocação de frota devem-se reduzir os custos improdutivos, que são os tempos parados em garagens ou realizando deslocamentos sem passageiros. Para isso é proposto um modelo que utiliza grafos e caminhos mínimos. Os resultados obtidos com dados reais comprovaram o bom desempenho do procedimento