Problema de orientação de equipas (TOP) aplicado às linhas de engarrafamento móveis

Abstract

Os custos com transportes nas empresas estão constantemente a aumentar devido à realidade económica nacional e à dependência de energias fósseis. É, portanto essencial que seja feita uma otimização constante com vista a minimizar estes custos. Esta dissertação propõe estudar a aplicação do modelo de problemas de orientação de equipas com janelas temporais às linhas de engarrafamento móvel de uma empresa Portuguesa. Recorre-se para isso a coordenadas geográficas geradas aleatoriamente (clientes aleatórios) e à utilização de distâncias reais entre essas localizações através do serviço disponibilizado pelo Google Maps. Inicialmente apresentam-se conceitos importantes sobre a cadeia de abastecimento seguido do estado da arte no âmbito de problemas de otimização de rotas. Apresenta-se o caso de estudo, com a descrição do problema real, recursos disponíveis e assunções na modelação do problema real e a ainda o modelo matemático submetido ao NEOS Server para a obtenção de soluções ótimas. Recorre-se a utilitários da linha de comandos em conjunto com expressões regulares para filtrar e formatar a resposta fornecida pelo NEOS Server. Apresenta-se ainda a aplicação web, desenvolvida em Nodejs, para gerir os clientes e para a conceção das diferentes instâncias submetidas aos testes, para a consolidação do estudo. Apresenta-se uma análise dos resultados obtidos da aplicação do TOPTW, bem como estratégias alternativas para melhorar as soluções obtidas e para tentar obter resultados em instâncias de maior dimensão. Os resultados dos diferentes testes são apresentados numa folha de Excel, juntamente com informação pertinente extraída da análise dos resultados, nomeadamente através de tabelas comparativas gráficos e diagramas de Gantt. Por fim, apresentam-se as conclusões do trabalho desenvolvido ao longo da dissertação e perspetivas para trabalho futuro.

The costs with transports in organizations are constantly increasing due to the national economic reality and to the highly dependency of fossil energies. It’s crucial to do a constant optimization to minimize that costs. This dissertation proposes a study of the team orienteering problems with time windows applied to a mobile bottling line of a Portuguese organization. To do that, we use random generated geographic coordinates and we use the actual distances between them through the use of a Google Maps service. Initially, we present important concepts of the chain supply and the state of the art in route optimization problems. Then we present the case of study with the description of the real problem, available resources and the assumptions of the real problem and also the mathematic model submitted to NEOS Server in order to obtain the optimal solutions. After that, we present a web application developed in Nodejs and mongoDB for random client generation, instance generation and client management. We show the analysis of results and alternative strategies to improve the obtained solutions. The results are displayed with resource of Excel tables and comparative charts. Finally we present the conclusions and perspectives for the future work.