Um problema de otimização de rotas com janelas temporais

Abstract

O problema de recolha de produtos (PRP) é um problema de otimização cujo objetivo é determinar a ordem pela qual visitar todos os vértices de um grafo, utilizando um conjunto limitado de veículos, minimizando a distância total a percorrer. Além disso, a visita a cada cliente deve realizar-se durante um intervalo de tempo definido a priori e a duração total de cada viagem não deve exceder um determinado limite. Este problema é uma extensão do problema do caixeiro viajante (PCV) onde a diferença entre eles reside na criação de mais do que uma rota. Este problema é então chamado de problema do caixeiro viajante múltiplo (PCVM) ou problema de estabelecimento de rotas (PRV). Neste caso, o problema de recolha de produtos será um problema do caixeiro viajante múltiplo pois não usufrui das restrições de capacidade. Neste trabalho o PRP é formulado como um programa linear inteiro misto. Essa formulação é exemplificada e, em seguida, são descritos alguns métodos heurísticos clássicos para este problema com alterações de forma a ser aplicado ao problema em questão. Por fim, estuda-se o comportamento do problema de recolha de produtos quando resolvido através da utilização de software para programação matemática e recorrendo a métodos heurísticos implementados, em problemas gerados de forma aleatória com várias dimensões, comparando a qualidade das soluções aproximadas com as soluções exatas. Posteriormente, foram feitos testes para problemas de maiores dimensões de forma a identificar o método heurístico mais eficiente, tanto em termos da qualidade das soluções como em termos de tempos de execução.

The product collection problem (PRP) is an optimization problem whose purpose is to determine the order in which to visit all the vertices of a graph, using a limited set of vehicles, minimizing the total distance to go. In addiction, the visit to each client must take place during a defined time interval a priori and the total duration of each trip must not exceed a certain limit. This problem is an extension of the traveling salesman problem (TSP) where the difference between them lies in creating more than one route. This problem is then called the multiple traveling salesman problem (M-TSP) or vehicle routing problem (VRP). In this case, the product collection problem will be a multiple traveling salesman problem because it does not enjoy capacity restrictions. In this work the product collection problem is formulated as a mixed integer linear program. This formulation is exemplified and then some classic heuristic methods for this problem with changes are described in order to be applied to the problem in question. Finally, we study the behavior of the product collection problem when solved through the use of software for mathematical programming and using heuristic methods implemented in randomly generated problems with several dimensions, comparing the quality of the approximate solutions with the exact solutions. Subsequently, tests were performed for larger problems in order to identify the most efficient heuristic method, both in terms of the quality of the solutions and in terms of execution times.