Integração de aprendizado de máquina e otimização no roteamento de veículos

Abstract

Resumo: O problema de roteamento de veículos capacitado é um problema fundamental de otimização combinatória e de grande interesse para as áreas de logística e de sistemas de transporte. Tradicionalmente, algoritmos exatos, heurísticas e metaheurísticas são utilizados para resolver o problema. Os métodos exatos, como o empregado pelo resolvedor SCIP, garantem soluções ótimas, porém são inviáveis para grandes instâncias do problema, devido à complexidade exponencial deste. Heurísticas e metaheurísticas obtêm soluções aproximadas em tempo razoável ao explorar o espaço de soluções de maneira eficiente. Entretanto, esses métodos necessitam, geralmente, de conhecimentos específicos acerca do problema em questão, não sendo facilmente generalizáveis. Avanços recentes em aprendizado de máquina oferecem caminhos promissores para superar essas limitações, embora ainda não tenham sido extensivamente explorados. Nesta dissertação, nós enfrentamos o problema de roteamento de veículos capacitado sob duas perspectivas: a do método exato e a do aprendizado profundo, a fim de comparar os seus resultados. O método exato utiliza um modelo em programação inteira elaborado na interface Python do resolvedor SCIP. Já a abordagem de aprendizado de máquina é baseada em uma Rede de Atenção em Grafos treinada sob o paradigma do aprendizado por reforço. Especificamente, analisamos três estratégias de treinamento para estes modelos: REINFORCE baseada em Greedy Rollout, o estimador de Monte Carlo Diferenciável (DiCE) e uma versão aprimorada da arquitetura utilizando a função de ativação Mish para tornar o DiCE mais eficiente (DiCEMish). Experimentos demonstram que, embora o modelo SCIP forneça soluções ótimas, ele é computacionalmente intensivo e inviável para grandes instâncias. Por outro lado, os modelos de redes neurais obtêm soluções quase-ótimas com um custo computacional reduzido. O modelo DiCEMish, em particular, aprimora o treinamento e a qualidade da solução ao empregar modificações na arquitetura da rede para permitir um maior fluxo dos gradientes. Esses resultados indicam que as redes de atenção em grafos treinadas sob técnicas de aprendizado por reforço oferecem uma alternativa viável e eficiente aos métodos tradicionais (exatos, heurísticos e metaheurísticos) para resolver o problema do roteamento de veículos capacitado com um menor custo computacional e com maior capacidade de generalização

Abstract: The Capacitated Vehicle Routinf Problem (CVRP) is a essential problema in combinatorial optimization and of great interest to the logistic and transportantion systems fields. Traditionally, exact algorithms, heuristics and metaheuristics have been used to solve it. Exact methods, like the one employed by SCIP, guarantee optimal solutions but are impratical for larger instances due to its exponential time complexity. Heuristics and metaheuristics provide aproximate solutions in a reasonable time by exploring the solution space efficiently. However, they often require problem-specific tuning, limiting their generalization capacities. Recent developments in machine learning offer promising avenues to overcome this limitations, while not being exaustively explored. In this dissertation, we tackle the CVRP by using two distinct approaches to compare their results: one will use the exact method by implementing a model using the SCIP framework in python; the other will use deep learning in the form of a Graph Attention Network (GAT) trained under the reinforcement learning paradigm. Specifically, we implement and evaluate three training strategies for the GAT models: REINFORCE with a greedy rollout baseline, the differentiable Monte Carlo estimator (DiCE), and an enhanced architecture incorporating the Mish activation function to make DiCE more efficient (DiCEMish). Our experiments show that while the SCIP model delivers optimal solutions, it is computationally intensive and impratical for larger instances. In contrast, the GAT models achieve near optimal solutions with reduced computational cost and in less time. The DiCEMish, in particular, improves training and solution quality through architectural modifications that enhance gradient flow. These results indicate that GATs trained with reinforcement learning techniques offer a viable and efficient alternative to the traditional exact, heuristic and metaheuristic methods for solving the CVRP with a reduced computational cost and improved generalization capacities