Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/86453
Title: | Um problema de otimização de rotas com janelas temporais | Other Titles: | A route optimization problem with time windows | Authors: | Mesquita, Micael Mateus | Orientador: | Pascoal, Marta Margarida Braz | Keywords: | Programação linear inteira mista; Problema de recolha de produtos; Heurísticas; Mixed integer linear programming; Product collection problem; Heuristics | Issue Date: | 20-Feb-2018 | Serial title, monograph or event: | Um problema de otimização de rotas com janelas temporais | Place of publication or event: | Departamento de Matemática da FCTUC | 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. |
Description: | Dissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia | URI: | https://hdl.handle.net/10316/86453 | Rights: | openAccess |
Appears in Collections: | UC - Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
thesis.pdf | 1.32 MB | Adobe PDF | View/Open |
Page view(s) 50
442
checked on Aug 14, 2024
Download(s) 50
909
checked on Aug 14, 2024
Google ScholarTM
Check
This item is licensed under a Creative Commons License