VIII Simpósio Brasileiro de Engenharia Ambiental 04 a 08 de setembro, 2015
PROBLEMA DO CARTEIRO CHINÊS APLICADO AO ROTEAMENTO DA COLETA SELETIVA DE UMA COOPERATIVA EM SOROCABA/SP
César de Oliveira Ferreira Silva (1) Universidade Estadual Paulista “Júlio de Mesquista Filho” – Campus Sorocaba Luiza Amália Pinto Cantão Universidade Estadual Paulista “Júlio de Mesquista Filho” – Campus Sorocaba Email (1):
[email protected] Telefone para contato (1): (11) 99135-2485
PROBLEMA DO CARTEIRO CHINÊS APLICADO AO ROTEAMENTO DA COLETA SELETIVA DE UMA COOPERATIVA EM SOROCABA/SP 1. RESUMO Dentro de questões ligadas à Engenharia Ambiental, o Problema do Carteiro Chinês pode ser aplicado à otimização de rotas na coleta seletiva. Nessa aplicação, os custos associados aos arcos orientados são as distâncias percorridas pelos caminhões entre os pontos de coleta e buscasse um caminho ótimo, onde o caminhão sai do depósito, passa uma única vez por cada um dos pontos de coleta e retorna ao depósito com o material recolhido. Cerca de 6500 pontos de coleta da cooperativa REVIVER foram agrupados em 74 nós e foi feito o roteamento entre os 74 nós e também um roteamento dentro do agrupamento que compõe cada nó. A otimização entre os 74 nós resultou numa distância percorrida de 121.65 km e a soma das rotas internas aos nós foi de 135.75 km. A metodologia permitiu um bom tempo computacional de solução do problema. 2. OBJETIVO O objetivo desse trabalho é a aplicação do Problema do Carteiro Chinês Orientado na coleta de resíduos sólidos recicláveis realizada pela cooperativa REVIVER, em Sorocaba/SP, buscando uma rota que percorra uma distância percorrida mínima, porém, passando por todos os pontos de coleta da cooperativa. 3. METODOLOGIA O problema do Carteiro Chinês, introduzido na literatura científica em Kwan (1962), se propõe a buscar um caminho dentro de um grafo tal que todos os nós do grafo sejam visitados e que o caminho, feito dentro dos arcos do grafo, seja mínimo (já que cada arco tem um peso associado). Aqui se aplica esse problema na criação de uma rota para a coleta seletiva, onde, os nós do grafo são os pontos de coleta da cooperativa e os custos associados aos arcos orientados são as distâncias percorridas pelos caminhões na coleta de lixo entre os pontos de coleta, ou seja, o caminho ótimo obtido será o percurso feito pelos caminhões com distância mínima, onde se passa por cada ponto de coleta uma única vez, saindo do depósito, passando por todos os pontos de coleta, uma única vez por cada um, e retornando finalmente ao depósito com o material recolhido. O fato do grafo ser euleriano (cada nó tem um número par
de arcos ligados a ele) e fortemente conectado (partindo-se de um nó é possível alcançar qualquer outro), segundo Gomes et al (2009), garante que existe um caminho ótimo. Assim, o problema pode ser modelado da seguinte maneira: Dado um grafo G(N,A), onde os nós (conjunto N) são os pontos de coleta e os arcos orientados (conjunto A) são os percursos entre os vértices. Modelo matemático – PCC Orientado: Variáveis: (
{
)
(
)
Mininimizar: ∑ (
)
Sujeito a: ∑ (
)
∑ (
)
Onde a primeira sentença matemática é a função objetivo, que calcula a distância percorrida pelo caminhão, com
sendo a variável binária já citada e cij um elemento da
matriz com as distâncias entre os nós; a segunda equação rege que um nó seja visitado uma vez e em seguida um próximo nó seja visitado partindo do nó que foi visitado anteriormente utilizando um arco que os ligue; e a terceira equação garante que não existam sub-rotas no percurso, sendo ui e uj variáveis de decisão e n é o número de nós. A cooperativa possui cerca de 6500 pontos de coleta, que foram agrupados em 73 nós mais o depósito, definido como o “nó 0”, totalizando 74 nós, assim como apresentados em PALMA (2013). O parâmetro de otimização desse trabalho foi a distância. As coordenadas dos nós foram obtidas pelo Google Earth e as distâncias entre os nós pelo Google Maps. O grafo é euleriano, pois, para cada par de nós serão coletados um par de arcos, podendo-se dizer que esses dois arcos são a “ida e volta” entre os nós, já que são arcos orientados, porém, com direção contrária entre eles, assim, para cada arco que entra em um nó, há outro que sai desse mesmo nó, então, isso garante que existe um caminho ótimo. Assim, o número de arcos orientados desse problema é
, onde
é o número de nós e a
subtração por
ocorre, pois a diagonal principal da matriz é nula (já que a distância entre um
ponto e ele mesmo é zero). Para a implementação do modelo matemático foi utilizado o software GAMS (General Algebraic Modeling System), que é uma linguagem de programação para modelagem de problemas de otimização. 4. RESULTADOS E DISCUSSÃO Utilizando Google Maps, foram obtidas as distâncias entre os 74 nós (totalizando 5402 arcos). A opção feita foi a de apenas realizar a otimização utilizando a variável distância e encontrar formas de se reduzir a quantidade de nós para estabelecer uma implementação computacional que atingisse um tempo computacional viável, por isso inicialmente foram utilizados os agrupamentos iniciais, que formaram o grafo principal (a partir de agora trataremos com esse nome o grafo com os 74 nós que representam todos os pontos de coleta da cooperativa) e em seguida o mesmo modelo matemático foi utilizado em grafos com nós que representam apenas os pontos de coleta que foram agrupados dentro de um nó do grafo principal (ou seja, cada um desses novos grafos representam a área de influência interna a um dos nós do grafo principal), esses grafos são nomeados tomando como referência o número do nó que ele representa no grafo principal. A otimização da rota no grafo principal, segundo os dados coletados, produz a distância percorrida total de 121.65 km, sendo que o software GAMS levou 11 minutos para encontrar a solução ótima. A rota obtida é ótima, pois passa uma única vez por cada nó, a seguir a rota encontrada para o grafo principal foi: 0 → 41 → 39 → 38 → 40 → 37 → 35 → 34 → 36 → 31 → 28 → 29 → 32 → 20 → 19 → 18 → 14 → 7 → 2 → 1 → 5 → 3 → 4 → 6 → 8 → 9 → 10 → 11 → 12 → 13 → 15 → 16 → 17 → 22 → 72 → 71 → 21 → 24 → 23 → 25 → 26 → 27 → 30 → 33 → 73 → 52 → 44 → 43 → 42 → 46 → 45 → 50 → 53 → 58 → 61 → 59 → 57 → 67 → 68 → 69 → 70 → 65 → 66 → 64 → 62 → 63 → 60 → 56 → 55 → 54 → 51 → 49 → 48 → 47 → 0 Em seguida foi feita a otimização interna dos nós internos, sendo que o número de nós desses grafos varia de 5 a 15 nós e são resolvidos em aproximadamente 1 segundo, geram distâncias percorridas entre 1 e 7 km. Assim, como esperado, as rotas fazem o percurso ótimo. Somando-se as distâncias percorridas dentro de cada nó, a distância percorrida total foi de 135.75 km. É possível unir as duas otimizações, seguindo-se a ordem da rota do grafo
principal, unindo as rotas internas aos nós. A figura 1 expõe, como exemplo, a rota encontrada dentro do nó 57, em sua visualização no Google Maps.
Figura 1 – Rota interna ao nó 57. A implementação do modelo matemático apresentado foi utilizado tanto para o grafo principal como para os grafos menores, internos a alguns nós do grafo principal, para testar sua eficiência computacional e aplicabilidade aos dois casos. Conclui-se que o modelo matemático, apesar de ser bastante simples, foi eficiente para os dois casos, e pôde ser aplicado nos dois casos, retornando rotas factíveis (ao se analisar e comparar as ruas percorridas pela rota com a área de influência dos nós e verificar-se que foram percorridas exatamente os trechos de rua onde se encontram a grande maioria dos pontos de coleta reais). O software GAMS se mostrou eficiente para resolução desse tipo de problema em relação ao tempo computacional para convergir ao resultado ótimo mesmo existindo um grande número de variáveis (74 nós e 5402 arcos), como no caso do grafo principal e para o grafo menor o tempo computacional foi insignificante (menor que um segundo). Utilizou-se uma abordagem diferente em relação a aplicação na coleta seletiva, utilizando dados reais (pontos de coleta reais e distância reais) e realizando agrupamentos desses dados para tornar a aplicação computacional viável, a partir desses agrupamentos pôde ser realizada um refinamento (para compensar a simplificação feita no agrupamento) por meio da otimização interna ao nó, que, utilizando como parâmetro a distância, se mostrou viável
computacionalmente e factível, pois contemplou as ruas no seu percurso de forma a abranger os pontos de coleta reais que estão espalhados pela área de influência do grafo interno ao nó. 5. CONCLUSÕES/RECOMENDAÇÕES O modelo matemático implementado convergiu à solução ótima assim como esperado. Criou-se uma metodologia de coleta de dados que gera grafos eulerianos, ou seja, com garantia de existência de um caminho ótimo, que propiciou um melhor tempo computacional para o projeto, pois, permitiu o uso de um algoritmo mais simples sem causar um gasto computacional excessivo. O parâmetro utilizado na otimização foi a distância entre os pontos de coleta, entretanto, é possível futuramente utilizar um número maior de parâmetros utilizando essa mesma metodologia de coleta de dados, pois facilita um futuro acréscimo de parâmetros de otimização sem que haja um aumento de demanda computacional que torne o projeto inviável. O software GAMS mostrou-se eficiente, pois encontrou a solução ótima rapidamente. Uma metodologia que torne o tempo computacional menor é importante para um futuro acréscimo de restrições e variáveis, já que é possível acrescentar ao problema outros parâmetros de otimização junto à distância, como janela de tempo, capacidade dos caminhões, quantidade média de resíduos coletados em cada ponto de coleta, entre outros, desde que dados consistentes por parte da cooperativa para que essa modelagem seja feita e aplicada. 6. REFERÊNCIAS BIBLIOGRÁFICAS GOMES, M. J. N., COELHO, JUNIOR, W. R., PALHANO, A. W. de C., COUTINHO, E. F., CASTRO, G. A., GOMES, F. J. N., BARCELLOS G. C., REZENDE, B. F.,PEREIRA, L. W. L. O Problema do Carteiro Chinês, algoritmos exatos e um ambiente MVI para análise de suas instâncias: sistema XNÊS. Pesquisa Operacional , vol. 29, n. 2, pp. 323–363, 2009. KWAN, M.K. Graphic programming using odd or even points. Chinese Mathematics, v. 1, p. 273–277, 1962. PALMA, P. M. M. de; Coleta Seletiva e o Problema de Roteamento de Veículos. Sorocaba: Universidade Estadual Paulista “Júlio de Mesquisa Filho”, 2013. Relatório Final de Projeto de Pesquisa.
