Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/12035
Title: Roteamento de veículos sem e com janelas temporais
Author: Semedo, Arlindo Tavares
Advisor: Agra, Maria Cristina Saraiva Requejo
Keywords: Matemática aplicada - Teses de mestrado
Problema do caixeiro viajante
Optimização combinatória
Programação linear
Defense Date: 2013
Publisher: Universidade de Aveiro
Abstract: Neste trabalho abordamos o Problema de Roteamento de Veículos (PRV) e o Problema de Roteamento de Veículos com Janelas Temporais (PRVJT). O PRV, bem como a sua extensão PRVJT, são problemas combinatórios pertencentes à classe de problemas NP-Difíceis. Para ambos os problemas, apresentamos dois grupos de formulações em Programação Linear Inteira Mista: um grupo de formulações em que cada rota é associada a um veículo específico e outro grupo de formulações em que são determinadas as rotas sem as associar aos veículos. Usamos as formulações apresentadas para obter resultados computacionais para vários exemplos. Os exemplos que usamos têm 4, 7, 13 , 20, 25, 40, 50, 75 e 100 clientes, 1 depósito e até 27 veículos. Os resultados computacionais permitem-nos comparar, para estes exemplos, os valores da relaxação linear e os valores da melhor solução admissível encontrada. Esses resultados computacionais foram obtidos com as formulações usando o software Xpress.
We consider the Vehicle Routing Problem (VRP) and the Vehicle Routing Problem with Time Windows (VRPTW). The VRP and its extension VRPTW are combinatorial problems belonging to the class of NP-Hard problems. For both problems we present two groups of mixed integer linear programming formulations, a group of formulations where each route is associated with a particular vehicle and another group of formulations where the route is determined without being associated with the vehicles. We use the formulations presented to obtain computational results for several examples. The examples have 4, 7, 13, 20, 25, 40, 50, 75 and 100 clients, 1 depot and at maximum 27 vehicles. The computational results allow us to compare the linear relaxation values and the values of the best feasible solution obtained. The computational results were obtained using the formulations with the software Xpress.
Description: Mestrado em Matemática e Aplicações
URI: http://hdl.handle.net/10773/12035
Appears in Collections:DMat - Dissertações de mestrado
UA - Dissertações de mestrado

Files in This Item:
File Description SizeFormat 
Tese.pdftese719.57 kBAdobe PDFView/Open


FacebookTwitterLinkedIn
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.