Uma aplicação do problema do carteiro chinês direcionado na coleta de lixo urbano / An application of the chinese wallet problem targeted in urban waste collection

Andersson Alves da Silva, Sóstenes Luiz Soares Lins, Amanda da Silva Xavier

Abstract


Otimizar rotas para caminhões de lixo urbano contribuem para a redução de custos dos cofres públicos. Este trabalho objetiva apresentar um programa simples para resolução do Problema do Carteiro Chinês Direcionado atuando na determinação de rotas mínimas para veículos coletores de lixo e aplicado em dois bairros na cidade de Recife-PE. O programa recebe a matriz de distâncias do grafo e determina a rota ótima em 3 etapas: escrever o modelo matemático que resolve o PCCD, resolvê-lo por um solver e traçar a rota em um grafo Euleriano. O resultado do programa foi comparado com as rotas atuais: redução da distância total de 12,7% (Engenho do Meio) e 8,86% (Cordeiro). O tour para o caminhão de lixo obteve redução na distância total, embora algumas ruas precisassem ser percorridas mais de uma vez para alcançar certos segmentos de ruas, ainda assim garantiu melhor solução do que a rota atual.

 

 


Keywords


Problema do Carteiro Chinês, Grafos Eulerianos. Coleta de lixo urbano, Algoritmo de Fleury.

References


ABRELPE – Associação Brasileira de Empresas de Limpeza Pública e Resíduos Especiais. (2017). Panorama dos resíduos sólidos no Brasil. Disponível em: . Acessado: 2019-02-01.

Ahuja, R., Magnanti, T. e Orlin, J. (1993). Network Flow: theory, algorithms, and applications. Upper Saddle River, New Jersey: Prentice Hall.

Assad, A. A. e Golden, B. L. (1995). Arc routing methods and applications. Handbooks in operations research and management science, 8:375-483.

Baker, E. K. (1983). An exact algorithm for the time constrained travelling salesman problem. Operations Research, 31(5):938-945.

Beliën, J., De Boeck, L. e Van Ackere, J. (2012). Municipal solid waste collection and management problems: a literature review. Transportation Science, 48(1):78–102.

Beltrami, E. e Bodin, L. (1974). Networks and vehicle routing for municipal waste collection. Networks, 4:65-94.

Bertsekas, D. P. (1998). Network Optimization: Continuous and Discrete Models. Belmont: Athena Scientific.

Christofides, N. (1975). Graph Theory: An Algorithmic Approach. Academic Press, London.

Dos Santos, C. G. (2016). Uma proposta de modelagem matemática para um problema de roteirização periódica em arcos capacitados com múltiplas tarefas. Tese (Doutorado) – Programa de Pós-Graduação em Métodos Numéricos em Engenharia, Universidade Federal do Paraná. Curitiba (PR).

Dror, M. (Ed.). (2012). Arc routing: theory, solutions and applications. Springer Science & Business Media, New York.

Edmonds, J. (1965). The Chinese postman problem. Operations Research, 13, Supplement 1, B-73.

Edmonds, J. e Johnson, E. L. (1973). Matching, Euler tours and the Chinese postman. Mathematical programming, 5(1):88-124.

Eiselt, H.A., Gendreau, M. e Laporte, G. (1995). Arc routing problems. Part I: The Chinese postman problem. Operations Research, 43(2):231-242.

Ganga, G. M. D. (2012). Trabalho de conclusão de curso (TCC) na engenharia de produção: um guia prático de conteúdo e forma. São Paulo: Atlas.

Grakova, E. et al. (2018). Waste Collection Vehicle Routing Problem on HPC Infrastructure. In: IFIP International Conference on Computer Information Systems and Industrial Management, Springer, Cham, p. 266-278.

Guan, M. (1962). Graphic programming using odd or even points. Chinese Math, l:273-277.

Hannan, M. A. et al. (2018). Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm. Waste Management, 71:31-41.

Hochbaum, D. S., Lyu, C. e Ordóñez, F. (2014) Security routing games with multivehicle Chinese postman problem. Networks, 64(3):181-191.

Irnich, S. (2008). Solution of real-world postman problems. European Journal of Operational Research, 190:52–67.

Jacinto, J. P., Rosa, R. A. e Banos, R. S. (2014). Heurística para solução do problema da coleta de resíduos sólidos domiciliares (RSD) com base no problema do carteiro chinês capacitado com múltiplas viagens (PCCC-MV). TRANSPORTES, 22(1):44-55.

Kauffman, A. (1967). Graphs, Dynamic Programming and Finite Games. Academic Press, New York.

Keller, M.T. e Trotter, W.T. (2015). Applied Combinatorics. Georgia Institute of Technology: Preliminary Edition.

Konowalenko, F., Benevides, P. F., Costa, D. M. B., Barboza, A. O. e Nunes, L. F. (2012). Aplicação de um algoritmo genético para o problema do carteiro chinês em uma situação real de cobertura de arcos. Revista Ingeniería Industrial, 11(1).

Lin, Y. e Zhao, Y. (1988). A New Algorithm for the directed Chinese Postman Problem. Computers & Operations Research, 15(6):577-584.

Lukman, R. K., Cerinšek, M., Virtič, P. e Horvat, B. (2018). Improving efficient resource usage and reducing carbon dioxide emissions by optimizing fleet management for winter services. Journal of cleaner production, 177:1-11.

Moro, M. F., Andrade, F. A., Dos Santos, B. M., Neto, C. R. P. e Battisti, J. F. (2018). O problema do carteiro chinês aplicado na otimização das rotas de coleta de resíduos recicláveis: um estudo de caso. Tecno-Lógica, 22(2):128-135.

Saoub, K. R. (2017). A Tour Through Graph Theory. Chapman and Hall/CRC.

Schrijver, A. (2003). Combinatorial Optimization: polyhedra and efficiency. Algorithms and Combinatorics. v. 24. Springer Science & Business Media, Berlin.

Shafahi, A. e Haghani, A. (2015). Generalized maximum benefit multiple chinese postman problem. Transportation Research Part C: Emerging Technologies, 55:261-272.

Souza, P. S., Gonçalves, N. A. L. e Curi, R. C. (2018). Gestão dos resíduos sólidos no Município de Queimadas (Estado da Paraíba, Nordeste do Brasil) segundo a Política Nacional de Resíduos Sólidos. Revista Brasileira de Gestão Ambiental e Sustentabilidade, 5(10):739-752.

Tucker, A. (2012). Applied combinatorics. Wiley, 6 ed. New York.

Usberti, F. L., França, P. M. e França, A. L. M. (2008). Roteamento de leituristas: Um problema NP-difícil. In: Anais do XL SBPO, João Pessoa-PB. SOBRAPO.

Vecchi, T. P. B. et al. (2015). Uma abordagem sequencial para otimização de rotas dos caminhões de coleta de resíduos sólidos. In: Congresso de Métodos Numéricos em Engenharia, Lisboa. Disponível em: . Acessado: 2019-03-03.

Wang, H. F. e Wen, Y. P. (2002). Time-constrained Chinese postman problems. Computers and Mathematics with applications, 44:375-387.

Wøhlk, S. e Laporte, G. (2018). A fast heuristic for large-scale capacitated arc routing problems. Journal of the Operational Research Society, 68(12):1877-1887.

Yilmaz, M., Çodur, M. K. e Yilmaz, H. (2017). Chinese postman problem approach for a large-scale conventional rail network in Turkey. Tehnicki Vjesnik-Technical Gazette, 24(5):1471-1477.




DOI: https://doi.org/10.34117/bjdv6n5-062

Refbacks

  • There are currently no refbacks.