Uma abordagem à resolução do Capacitated Vehicle Routing Problem utilizando uma meta-heurística baseada em recozimento quântico

Abstract

A presente dissertação foi desenvolvida no âmbito da obtenção do grau de Mestre em Engenharia de Sistemas. Devido à sua atualidade e relevância prática, decidiu-se estudar o Problema de Encaminhamento de Veículos (Vehicle Routing Problem - VRP) e desenvolver e implementar uma meta heurística baseada em recozimento quântico para a obtenção de soluções para o VRP. A revisão de literatura incidiu, fundamentalmente, nas variantes e nos métodos de resolução do VRP, permitindo obter conhecimento do estado da arte a ser incluído no algoritmo a desenvolver. Também da literatura, selecionaram-se aleatoriamente 40 instâncias públicas, com o cuidado de representarem uma grande amplitude dimensional, incluindo desde instâncias fáceis até instâncias de muito difícil solução. Previamente à implementação da meta-heurística baseada em recozimento quântico implementou-se em Python 3 o Algoritmo de Poupanças de Clarke and Wright. Esta implementação permitiu ter uma base de comparação para o algoritmo seguinte e permitiu um primeiro contacto com a implementação de algoritmos para a resolução de problemas de Otimização Combinatória. Relativamente aos resultados computacionais, obteve-se, em média, um desvio percentual face à solução ótima de 672.35%, e que foi alcançado em 7 horas de processamento. Apesar do algoritmo ter encontrado uma solução viável para todas as instâncias, destacam-se a fragilidade da eficácia do método e a maior velocidade do algoritmo. O algoritmo baseado em recozimento quântico, implementado também em Python 3, é baseado nos conceitos de mecânica quântica e não necessita de qualquer hardware quântico para a sua resolução. O principal conceito utilizado é o tunelamento quântico. Foram realizados vários processamentos com diferentes combinações de valores para os parâmetros relativos ao recozimento quântico, sendo que o algoritmo apenas foi capaz de solucionar, em tempos computacionais razoáveis, 26 das 40 instâncias escolhidas. Analisaram-se os resultados do algoritmo comparando-os com a solução ótima e com o Algoritmo de Poupanças de Clarke and Wright. Obteve-se, no melhor dos processamentos, um desvio percentual face à solução ótima de 166.90% e um desvio percentual face ao Algoritmo de Poupanças de Clarke and Wright de -19.93% ao fim de 35 horas de processamento.

This dissertation was developed to achieve a master’s degree in Systems Engineering. Due to its actuality and practical relevance, it was decided to study the Vehicle Routing Problem (VRP) and to develop and implement a quantum-annealing-based meta-heuristic for obtaining solutions for the VRP. The bibliographical review addressed essentially the VRP’s variants and solution methods, and it provided knowledge about the state of the art about the topic to be included in the algorithm to be developed. Additionally, 40 public instances were selected, with the caution that they represent a big dimensional amplitude, including easy-solving instances and very hard-solving ones. Previously to the implementation of the quantum-annealing-based meta-heuristic, Clarke & Wright’s Savings Algorithm was implemented. This first implementation gave a comparative base for the following algorithm and allowed a first contact with the implementation of Combinatorial Optimization solving algorithms. On the computational results, it was obtained a mean percentual deviation facing the optimal solution of 672.35% by the end of 7 hours of processing runs. Although the algorithm found a viable solution to all 40 selected instances, the weakness of the method stands out, and also the faster velocity of the algorithm which was implemented using Python 3. The quantum-annealing-based algorithm is based on quantum mechanical concepts and doesn’t need any quantum hardware for its resolution. The main concept used was quantum-tunnelling. The implementation of the algorithm was made using the language Python 3. Various processing runs were made, using different values to the quantum-annealing parameters. The algorithm could only solve 26 of the 40 instances in reasonable computing times. The results of the algorithm were analysed in confront with the optimal solution and Clarke & Wright’s Savings Algorithm results. In the best processing run a percentual deviation facing the optimal solution of 166.90% was obtained, and a percentual deviation facing Clarke & Wright’s Savings Algorithm of -19.93%, being needed 35 hours to process all instances.