Loading...
Please wait, while we are loading the content...
Transporte Escolar no Campus de Poços de Caldas da Universidade Federal de Alfenas: Otimização de Rotas
| Content Provider | Semantic Scholar |
|---|---|
| Author | Lago, César Ambrogi Ferreira Do Turci, Luiz Felipe R. |
| Copyright Year | 2015 |
| Abstract | Pode-se comparar o problema de roteamento de veiculos ao Problema do Caixeiro Viajante (PCV) [3], um classico exemplo de problema de otimizacao combinatoria. A principio, poder- se-ia reduzi-lo a um problema de enumeracao: enumeram-se todas as rotas possiveis e, calcula- se o comprimento para cada uma das rotas, entao seleciona-se a rota de menor caminho. Este problema, contudo, e NP-Hard, portanto, nao ha algoritmo deterministico que o resolva em tempo polinomial [2,4]. Para se determinar uma rota de menor caminho entao, podem-se utilizar algoritmos metaheuristicos, que nao apresentam necessariamente solucao otima, mas sim a melhor solucao viavel resultante da sequencias de iteracoes executadas. Um dos algoritmos metaheuristico para resolucao do PCV e o da Colonia de Formigas, que e baseado no comportamento biologico das formigas, atraidas por ferormonio na procura de alimentos [1]. Neste trabalho, desenvolveu-se um algoritmo de otimizacao de rotas baseado no algoritmo de colonia de formigas apresentado em [1] para aplicacao no roteamento de veiculos de transporte que atendem aos alunos e funcionarios do campus de Pocos de Caldas da Universidade Federal de Alfenas. Para modelar o problema do transporte dos alunos, mapeou-se a cidade definindo varios nos (no modelo criado, cada cruzamento de ruas da cidade representa um no), e interligacoes entre os nos (determinada pela existencia de vias entre dois cruzamentos), definindo assim um grafo em que a distância entre dois cruzamentos interligados define a distância entre dois nos. O algoritmo deve, entao, ser capaz de buscar a menor rota entre um no de partida e um no de chegada passando por um conjunto de nos obrigatorios (que sao definidos como pontos de embarque/desembarque dos alunos). O algoritmo desenvolvido consiste nos seguintes passos: Le-se a matriz D de distância entre nos (para nos que nao sao interligados a distância e consi - derada infinita) e definem-se os nos obrigatorios (informado pelo usuario). Aplica-se o algoritmo de colonia de formigas apresentado em [1] ao grafo definido pela ma- triz D obtendo-se um ciclo passando por todos os nos do grafo (assumindo-se grafo conexo). Extrai-se a ordem em que os nos obrigatorios serao visitados de acordo com a ordem em que aparecem na solucao. Com essa ordem, agora, constroi-se o roteamento combinando-se as melhores subrotas entre cada par desses nos obrigatorios, seguindo-se a ordem em que os mesmos devem ser visitados. Para se construir as subrotas entre cada par de nos obrigatorios, desenvolveu-se um algoritmo baseado no algoritmo de colonia de formigas para solucionar o PCV mas que nao necessaria- mente visitasse todos os nos do grafo: 3.1. Cada par de nos obrigatorios e tratado como par (origem, destino) da subrota, de acordo com a ordem obtida anteriormente; 3.2. Aplica-se a metaheuristica da colonia de formigas alterada para gerar um caminho entre os nos do par (origem, destino); 3.3. Na primeira subrota, a origem e o ponto de partida do problema, e o destino e o primeiro no obrigatorio da sequencia obtida em 2. Apos determinar a subrota entre o primeiro par de nos, atualizamos o valor do par, o destino da iteracao anterior e considerada origem da proxima ite- racao, e o proximo no obrigatorio da sequencia se torna o novo destino; e assim sucessivamente, ate que o ultimo no obrigatorio torna-se origem e o destino seja o ponto de chegada do proble - ma. Une-se todas as subrotas previamente salvas para obter a rota final. Utilizou-se este algorit - mo com 10 formigas e 100 iteracoes para resolver o problema teste do seguinte grafo: [.] |
| File Format | PDF HTM / HTML |
| DOI | 10.5540/03.2015.003.01.0404 |
| Volume Number | 3 |
| Alternate Webpage(s) | https://proceedings.sbmac.org.br/sbmac/article/download/716/722 |
| Alternate Webpage(s) | https://doi.org/10.5540/03.2015.003.01.0404 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
