The Chinese Postman Problem and Simulated Annealing applied to urban forest inventory

Autores

DOI:

https://doi.org/10.5380/rf.v54i1.93565

Palavras-chave:

Simulated annealing. Network optimization. Meta-heuristics. Operational research. Integer Linear Programming.

Resumo

Routing is the process of defining paths between geographically distinct points, and it has been applied in decision-making processes for services that include displacement, with potential application in the planning of urban forest inventories. Linear Programming is an operations research technique often applied to solve complex problems, such as those related to routing. Thus, the objective of this study was to verify whether the application of a routing model via Integer Linear Programming (ILP) increases the efficiency of an urban forest inventory using real data. First, we compared the empirical division used in the inventory with the application of the ILP method for routing. We also tested an approximate method (Simulated Annealing, SA) to solve the routing problem and reduce the processing time. Finally, we simulated the consequences of applying ILP in different scenarios. The results showed that the ILP improved the inventory efficiency by 6.36%, and the use of SA reduced the processing time by 43,200 times for the most complex scenario, resulting in a solution that was 1.87% of the ILP response value. Our findings show the potential application of ILP in the planning of urban forest inventories, with gains directly proportional to the number of lots in the inventory.

Biografia do Autor

Carlos Delano Cardoso de Oliveira, Universidade federal de Lavras (UFLA), Lavras, Minas Gerais

Bacharel em Engenharia Florestal pela Universidade Federal de Lavras (UFLA), mestre em Engenharia Florestal pela mesma universidade e doutor em Ciência Florestal pela Universidade Estadual Paulista "Júlio de Mesquita Filho" (UNESP), com doutorado sanduíche na Universidade da Flórida (EUA) financiado pelo programa CAPES Print. Desenvolveu atividades de pesquisa nas áreas de Manejo Florestal, Ecologia Florestal, Sensoriamento Remoto e Sistemas de Informação Geográfica, Silvicultura, Genética da Conservação e Restauração Ecológica. Foi membro do Núcleo de Estudos em Manejo de Unidades de Conservação (NEUC-UFLA) e do Engenheiros Sem Fronteiras - Núcleo Lavras, além de voluntário no Projeto Rondon. No mercado de trabalho, atuou na regularização ambiental de imóveis rurais, atuando tanto na realização quanto na análise do Cadastro Ambiental Rural (CAR). Tem experiência em restauração florestal e ecológica, ecologia de florestas tropicais, manejo adaptativo, sensoriamento remoto e Sistemas de Informações Geográficas (SIG). É membro da Sociedade Brasileira de Restauração Ecológica (SOBRE) e atua como pesquisador (bolsista de Pós-Doutorado) na UFLA em pesquisa focada na estimativa do estoque de carbono de fragmentos de vegetação nativa usando dados de sensores remotos e de inventários florestais.

Carolina Souza Jarochinski e Silva, Department of Forest Sciences, Federal University of Lavras

Possui graduação em Engenharia Florestal (2009), mestrado em Engenharia Florestal (2011) e doutorado em Engenharia Florestal (2019), todos pela Universidade Federal de Lavras. Atuou por 6 anos nas áreas de Planejamento Estratégico e Planejamento e Controle da Produção Florestal (PCP) na Fibria Celulose S/A, onde foi responsável pela otimização dos recursos florestais e pela sustentabilidade do abastecimento de madeira no longo, médio e curto prazo. Na Fibria, participou da implantação e modelagem do sistema de planejamento florestal (Estratégico e Tático) em parceria com a empresa canadense Remsoft. Atualmente é professora Adjunta do Departamento de Ciências Florestais na Universidade Federal de Lavras, ministrando as disciplinas de Economia Florestal e Projetos Florestais. Na pós graduação atua no Programa de Engenharia Florestal desde 2021. Tem experiência na área de Recursos Florestais e Engenharia Florestal, com ênfase em Economia Florestal, atuando principalmente nos seguintes temas: planejamento estratégico, planejamento da produção florestal, modelos estocásticos para tomadas de decisão via simulação de Monte Carlo, análise econômica e financeira de projetos florestais e fomento florestal.

José Roberto Soares Scolforo, Department of Forest Sciences, Federal University of Lavras

É professor titular da Universidade Federal de Lavras em Biometria, Inventário e Manejo Florestal desde 1995. Tem longa experiência na área de Recursos Florestais e Engenharia Florestal. Tem o prazer de atuar na Graduação e na Pós graduação em Engenharia Florestal. Na administração foi Chefe de Departamento na Universidade Federal da Paraíba onde iniciou a carreira em 01/02/1980, foi também Chefe de Departamento na Universidade federal de Lavras, assim como Coordenador de Pós graduação Stricto Sensu em Engenharia Florestal, Coordenador de cursos Latu sensu em Manejo de Florestas Plantadas e florestas Nativas, foi Pró reitor de Pesquisa, Pró reitor de Administração, Pró reitor de Planejamento e Gestão, Vice Reitor e Reitor da Universidade Federal de Lavras por dois mandatos, 2012-2020. Na Pesquisa atua em duas grandes áreas. A área de Produção Florestal, e a Área de Manejo da Biodiversidade de Florestas e Gestão do Território. É líder de grupo de pesquisa cadastrado no CNPq em Biometria, Inventário e Manejo de Florestas. Coordenou e coordena, em florestas plantadas, inúmeros projetos sobre modelos de crescimento e produção, manejo e inventário florestal para as espécies dos gêneros, Eucalyptus, Pinus, Teca, entre outras. Em florestas nativas é um dos precursores da pesquisa em manejo para usos múltiplos da vegetação do cerrado; atuou em grandes programas de pesquisa na região amazônica, com destaque para o sistema integrado de controle de produtos florestais da Amazônia; coordenou o Inventário, Mapeamento e Monitoramento da Flora Nativa e dos Reflorestamentos no Estado de Minas Gerais; coordenou o Zoneamento Ecológico e Econômico -ZEE do Estado de Minas Gerais e também o ZEE do Estado do Espírito Santo. Iniciou e desenvolveu a alternativa técnico científica das pesquisas que viabilizaram o manejo da Candeia em bases totalmente sustentáveis. Hoje essas tecnologias são realidade para várias empresas do país e para os agricultores, principalmente, do Estado de Minas Gerais. Participou do desenvolvimento da plataforma do Cadastro Ambiental Rural CAR, em suas várias nuances. Apesar da grandiosidade dos demais projetos, esse último, é com certeza o de maior amplitude que já executou, comtemplando integralmente todo território brasileiro. O foco do projeto e dos estudos e desenvolvimentos estão centrados na conservação e preservação do ambiente, na produção agrícola e no alto impacto positivo para a sociedade. Além desses, vários outros projetos relevantes foram desenvolvidos nos temas florestas plantadas e Florestas nativas ao longo de sua carreira, até então. É pesquisador de forma ininterrupta, em Produtividade de Pesquisa do CNPq desde 1983. Foi membro e coordenador da Câmara de Ciências Agrárias da FAPEMIG; membro do Conselho Assessor de Recursos Florestais do CNPq; membro da Câmara de Biodiversidade do Conselho de Política Ambiental do Estado de Minas Gerais; é componente do Comitê Assessor da Rede de Parcelas Permanentes para o Brasil; foi presidente do fórum das Instituições Públicas de Ensino técnico e Superior do Estado de Minas Gerais, foi segundo Vice Presidente da Associação Nacionais do Reitores das Universidades Federais, entre outras relevantes representações junto a outras instituições públicas. Publicou ao todo 815 artigos científicos e técnicos, sendo 222 em periódicos especializados nacionais e internacionais e 87 capítulos de livros temáticos em Dendrometria, Inventário e Manejo Florestal, além de vários outros com conotação multidisciplinar; 385 trabalhos em congresso, 58 textos em jornais e entrevistas, 51 softwares registrados no INPI, e 12 não registrados. Orientou e coorientou, durante sua carreira, 418 discentes, sendo 73 no Mestrado e 20 no Doutorado, 9 Pós-doutorados, 316 em Iniciação científica, trabalhos de conclusão de curso e especialização. Participou de mais de 218 eventos técnico científicos. É autor de 18 livros e ganhador de mais de 60 prêmios em nível estadual, nacional e internacional.

Lucas Rezende Gomide, Department of Forest Sciences, Federal University of Lavras

Engenheiro florestal - UFLA (2002) e mestrado na mesma instituição (2004). Durante o mestrado, desenvolveu um modelo fitogeográfico para um plano de revitalização das áreas de preservação permanente da bacia do rio São Francisco, algo inovador naquela época. Utilizando as relações entre variáveis ambientais e um algoritmo de árvore de decisão. Na UFPR, conclui o doutorado em 2009, sendo um dos estudos pioneiros envolvendo o uso do algoritmo genético, simulated annealing e restrições espaciais no planejamento florestal. A partir de 2010, inicia a carreira como professor, ministrando disciplinas de graduação (estatística aplicada, manejo florestal, planejamento e analise de decisões florestais) e na pós-graduação (pesquisa operacional, planejamento florestal, programação computacional e tópicos especiais). No ano de 2012-2015 foi sub chefe do DCF, sendo convidado em 2013 a coordenar o núcleo de estudos em manejo florestal (NEMAF). O núcleo desenvolve uma série de ações sociais, estudos e eventos científicos contando com mais de 90 alunos que já passaram pelo grupo. Em meados de 2014, tornou-se Editor Chefe da Revista Cerne, ajudando a reformular a revista na melhoria de todos os seus indicadores. O JCR teve uma aumento expressivo e a revista passou a ser internacional, contando com uma média de 15-20 de autores internacionais. Auxiliou na coordenado do projeto CEMIG GT-456 que forneceu inúmeros produtos, como teses, dissertações, resumos de congresso e artigos. A linha de pesquisa adotada envolve o uso de modelos de programação linear/inteira e inteligência computacional na resolução de problemas florestais. Desenvolve modelos determinísticos e estocásticos via simulação de Monte Carlo para auxilio a tomada de decisão em operações florestais (colheita, transporte e silvicultura). Recentemente, vem aplicando o uso de algoritmos genéticos na seleção de variáveis para modelos não lineares otimizando sua performance. Um dos pioneiros no uso da programação genética dentro da engenharia florestal, contribuíndo para o avanço na modelagem preditiva de atributos.

Downloads

Publicado

27-08-2024

Como Citar

Haddad, H. M. D., de Oliveira, C. D. C., e Silva, C. S. J., Scolforo, J. R. S., & Gomide, L. R. (2024). The Chinese Postman Problem and Simulated Annealing applied to urban forest inventory. FLORESTA, 54(1). https://doi.org/10.5380/rf.v54i1.93565

Edição

v. 54 n. 1 (2024)

Seção

Artigos

Licença

Direitos Autorais para artigos publicados nesta revista são do autor, com direitos de primeira publicação para a revista. Em virtude da aparecerem nesta revista de acesso público, os artigos são de uso gratuito, com atribuições próprias, em aplicações educacionais e não-comerciais.A revista, seguindo a recomendações do movimento Acesso Aberto, proporciona acesso publico a todo o seu conteudo, seguindo o principio de que tornar gratuito o acesso a pesquisas gera um maior intrcambio global de conhecimento. 

Conteúdos do periódico licenciados sob uma Licença Creative Commons 4.0 Internacional (CC BY 4.0)