Para uma empresa cuja operação envolva o transporte de cargas, é fundamental que se recorra a processos de planeamento de rotas com bons desempenhos. A qualidade inerente a estes processos é determinante para que a utilização de recursos, em particular a frota de veículos disponíveis, permita alcançar as metas definidas. Neste trabalho é realizada uma análise comparativa da aplicação de diferentes métodos heurísticos ao planeamento de rotas. É considerado um cenário em que existe um conjunto de pedidos que deverão ser servidos por uma frota de veículos. Os pedidos são colocados progressivamente ao longo do tempo, provocando a necessidade de se aplicarem alterações a rotas de forma a permitir que esses pedidos possam ficar afetados a alguma das viaturas. Para cada pedido é conhecida uma quantidade, um local de carga, e um local de descarga, e a cada local estão associados intervalos temporais que impõe limites para os instantes em que se pode iniciar a respetiva carga ou descarga. Os cenários considerados foram obtidos através de um gerador de instâncias, concebido para o efeito, e que permite a definição de diferentes parametrizações para as instâncias a gerar. Os algoritmos implementados podem ser divididos em três conjuntos. Num primeiro conjunto, são consideradas heurísticas de inserção que se pretende que sirvam como enquadramento para decisões humanas, tomadas de uma forma intuitiva. Num segundo conjunto, é usado um Algoritmo Genético, sendo pretendido obter conjuntos de rotas com maior qualidade do que as obtidas com as heurísticas de inserção. Num terceiro conjunto, em que também se recorre ao Algoritmo Genético, é adicionado um método de seleção de rotas que recorre a cenários previsionais obtidos a partir de pedidos conhecidos, com o qual se pretende alcançar benefícios num prazo mais alargado. Os resultados obtidos apontam para um melhor desempenho por parte do Algoritmo Genético, face às heurísticas de inserção. Verificou-se que o desempenho dos algoritmos em que se introduz a componente previsional é fortemente afetado pela parametrização das instâncias, na medida em que essa parametrização restringe a qualidade das previsões. São também propostos desenvolvimentos e alterações ao trabalho realizado, que se considera poderem conduzir a melhores desempenhos por parte dos algoritmos considerados, bem como permitir a obtenção de resultados mais conclusivos.

For companies where transportation is a significant part of the business process, high performance route planning methods are mandatory. The quality of these methods is crucial in achieving the best use of the available resources, in particular the fleet of vehicles. This thesis work involves a comparative analysis of different heuristic methods for route planning problems. Several requests are considered, which should be fulfilled by a fleet of vehicles. These requests are progressively known over time, thus requiring the need for route modifications in order to allow those requests to be fulfilled. Each request is characterized by a load, a pickup location, a delivery location, and time-windows which limit the instants when each pickup or delivery may begin. The used scenarios were obtained by an instance generator, which was designed for that purpose, which allows the previous definition of different parametrizations for the generated instances. Three groups of algorithms were considered. The first group includes three insertion heuristics, which are thought of as a framework for the outcome of human decisions. In the second group a Genetic Algorithm is used, with the purpose of obtaining better results in comparison to the first group. A third group of algorithms, also using the Genetic Algorithm, incorporate a method for route selection based on sets of predicted requests using previously known requests, with the purpose of achieving longer term benefits. Overall, the results which were achieved using the Genetic Algorithm were better than those obtained using the insertion heuristic. The performance gain of incorporating the scenario generation is highly influenced by the parametrization defined for each instance, which affects the quality of the predicted requests. Modifications regarding several aspects of the current thesis work are proposed, hoping these might lead to a performance increase for the Genetic Algorithm, and also allowing more relevant results.

Trabalho de projecto de mestrado, Matemática Aplicada à Economia e à Gestão, Universidade de Lisboa, Faculdade de Ciências, 2016