MODELO DE PROGRAMAÇÃO LINEAR INTEIRA E HEURÍSTICA PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS ESCOLARES

O problema do roteamento de veículos no transporte escolar é um problema de otimização combinatória amplamente estudado nas últimas décadas. Sua importância reside na oportunidade de redução de custos para os órgãos responsáveis, assim como na diminuição dos tempos de transporte e dos deslocamentos para os pontos de parada por parte dos alunos. Tendo em vista que o problema em estudo é pertencente à classe NP-difícil, a proposição de algoritmos aproximados, tais como heurísticas construtivas, é de suma relevância para a resolução de instâncias de médio e grande porte em tempo computacional admissível. Um modelo de programação linear inteira e uma heurística construtiva foram desenvolvidos para o problema em estudo. Experimentos computacionais em um conjunto de 60 instâncias apontam para a necessidade do uso de meta-heurísticas para a resolução do problema, visto que o modelo proposto não conseguiu retornar soluções inteiras viáveis para todas as instâncias em um limite de tempo de 3600s.