Transporte Escolar no Campus de Poços de Caldas da Universidade Federal de Alfenas: Otimização de Rotas

Resumo

Pode-se comparar o problema de roteamento de veículos ao Problema do Caixeiro Viajante (PCV) [3], um clássico exemplo de problema de otimização combinatória. A princípio, poder- se-ia reduzi-lo a um problema de enumeração: enumeram-se todas as rotas possíveis e, calcula- se o comprimento para cada uma das rotas, então seleciona-se a rota de menor caminho. Este problema, contudo, é NP-Hard, portanto, não há algoritmo determinístico que o resolva em tempo polinomial [2,4]. Para se determinar uma rota de menor caminho então, podem-se utilizar algoritmos metaheurísticos, que não apresentam necessariamente solução ótima, mas sim a melhor solução viável resultante da sequências de iterações executadas. Um dos algoritmos metaheurístico  para  resolução  do  PCV  é  o  da  Colônia  de  Formigas,  que  é  baseado  no comportamento biológico das formigas, atraídas por ferormônio na procura de alimentos [1]. Neste trabalho, desenvolveu-se um algoritmo de otimização de rotas baseado no algoritmo de colonia de formigas apresentado em [1]  para aplicação no roteamento de veículos de transporte que atendem aos alunos e funcionários do campus de Poços de Caldas da Universidade Federal de Alfenas. Para modelar o problema do transporte dos alunos, mapeou-se a cidade definindo vários  nós  (no  modelo  criado,  cada  cruzamento  de  ruas  da  cidade  representa  um  nó),  e interligações  entre  os  nós  (determinada  pela  existência  de  vias  entre  dois  cruzamentos), definindo assim um grafo em que a distância entre dois cruzamentos interligados define a distância entre dois nós. O algoritmo deve, então, ser capaz de buscar a menor rota entre um nó de partida e um nó de chegada passando por um conjunto de nós obrigatórios (que são definidos como pontos de embarque/desembarque dos alunos). O algoritmo desenvolvido consiste nos seguintes passos:

1. Lê-se a matriz D de distância entre nós (para nós que não são interligados a distância é consi - derada infinita) e definem-se os nós obrigatórios (informado pelo usuário).
2. Aplica-se o algoritmo de colônia de formigas apresentado em [1] ao grafo definido pela ma- triz D obtendo-se um ciclo passando por todos os nós do grafo (assumindo-se grafo conexo). Extrai-se a ordem em que os nós obrigatórios serão visitados de acordo com a ordem em que aparecem na solução.
   1. Com essa ordem, agora, constrói-se o roteamento combinando-se as melhores subrotas entre cada par desses nós obrigatórios, seguindo-se a ordem em que os mesmos devem ser visitados. Para se construir as subrotas entre cada par de nós obrigatórios, desenvolveu-se um algoritmo baseado no algoritmo de colônia de formigas para solucionar o PCV mas que não necessaria- mente visitasse todos os nós do grafo:

3.1.  Cada par de nós obrigatórios é tratado como par (origem, destino) da subrota, de acordo com a ordem obtida anteriormente;

3.2. Aplica-se a metaheurística da colônia de formigas alterada para gerar um caminho entre os nós do par (origem, destino);

3.3. Na primeira subrota, a origem é o ponto de partida do problema, e o destino é o primeiro nó obrigatório da sequência obtida em 2. Após determinar a subrota entre o primeiro par de nós, atualizamos o valor do par, o destino da iteração anterior é considerada origem da próxima ite- ração, e o próximo nó obrigatório da sequência se torna o novo destino; e assim sucessivamente, até que o ultimo nó obrigatório torna-se origem e o destino seja o ponto de chegada do proble - ma.

1. Une-se todas as subrotas previamente salvas para obter a rota final. Utilizou-se este algorit - mo com 10 formigas e 100 iterações para resolver o problema teste do seguinte grafo: [...]