Abordagens exata e meta-heurísticas para o problema do carteiro rural ao vento com dependência de tempo

Abstract

Resumo: Este trabalho aborda o Problema do Carteiro Rural ao Vento Dependente do Tempo (PCRV-DT), um problema desafiador de otimização combinatória que surge em cenários logísticos do mundo real. O PCRV-DT visa encontrar um caminho fechado de custo mínimo, que inclua todas as arestas que demandam atendimento, tendo em vista que o custo de travessia de uma aresta depende do sentido de atendimento e varia ao longo do horizonte de planejamento, refletindo a flutuação nas condições de tráfego. Esse aspecto permite que o problema modele de forma mais realista a dinâmica do tráfego. Além das questões associadas à redução do impacto econômico, indiretamente ele também possibilita reduzir os impactos sociais e ambientais causados durante a execução da rota. Para resolver o problema, este estudo apresenta uma formulação matemática de programação inteira mista para o PCRV-DT, além de duas variações de uma abordagem meta-heurística baseada em Algoritmos Genéticos Adaptativos com Chaves Aleatórias Viciadas (A-BRKGA). Essas variações, propostas para resolver o problema de forma eficiente, diferem entre si pelo número de execuções, pela forma de seleção dos indivíduos e pela intensidade com que a Busca Local ocorre. Múltiplos testes preliminares foram realizados para ajustar os parâmetros envolvidos nas abordagens meta-heurísticas. Além disso, uma heurística capaz de gerar soluções iniciais de qualidade foi incorporada às abordagens de resolução exata e meta-heurísticas, visando melhorar a sua eficiência. As abordagens propostas foram avaliadas e comparadas em um conjunto de instâncias com até 139 clientes e 15 intervalos de tempo, com base em dados concebidos para refletir padrões de tráfego realistas. Resultados de extensivos testes computacionais mostram que o modelo matemático é computacionalmente eficiente para tratar instâncias menores. Por outro lado, as variações da meta-heurística alcançam soluções de alta qualidade para todo conjunto de instâncias, usando uma fração de tempo, quando comparadas com o modelo exato, nas instâncias de grande porte. O efeito da inclusão da solução inicial na qualidade da solução também foi avaliado para as abordagens propostas. Nas variações da meta-heurística, essa inclusão mostrou-se eficiente tanto para aumentar a qualidade da solução como para reduzir o esforço computacional. Para o modelo matemático, e em instâncias de grande porte, a inserção da solução inicial foi fundamental para a geração de novas soluções incumbentes, dada a limitação no tempo de processamento imposta. Esses aspectos reforçam a importância da integração entre diferentes abordagens para tratar problemas complexos, como o apresentado neste trabalho

Abstract: This study addresses the Time-Dependent Windy Rural Postman Problem (TD WRPP),achallenging combinatorial optimization problem that arises in real-world logistics scenarios. The TD-WRCPP aims to find a minimum cost closed path that includes all the required edges, considering that the cost of crossing an edge depends on the service direction and varies throughout the planning horizon, reflecting the fluctuation in traffic conditions. This aspect allows the problem to model traffic dynamics more realistically. Beyond the issues related to economic impact reduction, it also indirectly enables the reduction of social and environmental impacts caused during route execution. To solve the problem, this study presents a mixed integer linear programming formulation for the TD-WRCPP, as well as two variations of a meta-heuristic approach based on Adaptive Biased Random-Key Genetic Algorithms (A-BRKGA). These variations, proposed to efficiently solve the problem, differ in the number of runs, the individual selection method, and the intensity of Local Search. Multiple preliminary tests were performed to tune the parameters involved in the meta-heuristic approaches. Furthermore, a heuristic capable of generating high-quality initial solutions was incorporated into both the exact and meta-heuristic solution approaches, aiming to improve their efficiency. The proposed approaches were evaluated and compared on a set of instances with up to 139 customers and 15 time intervals, based on data designed to reflect realistic traffic patterns. Results from extensive computational tests show that the mathematical model is computationally efficient for handling smaller instances. On the other hand, the meta-heuristic variations achieve high-quality solutions for the entire instance set, using a fraction of the time, when compared to the exact model, in large-scale instances. The effect of including the initial solution on solution quality was also evaluated for the proposed approaches. In the meta-heuristic variations, this inclusion proved to be efficient both in increasing solution quality and in reducing computational effort. For the mathematical model, and in large-scale instances, the insertion of the initial solution was fundamental for generating new incumbent solutions, given the imposed processing time limit. These aspects reinforce the importance of integrating different approaches to address complex problems, such as the one presented in this work