Roteamento de veículos sem e com janelas temporais

• Author(s): Semedo, Arlindo Tavares
• Date: 2013
• Persistent ID: http://hdl.handle.net/10773/12035
• Origin: RIA - Repositório Institucional da Universidade de Aveiro
• Subject(s): Matemática aplicada - Teses de mestrado; Problema do caixeiro viajante; Optimização combinatória; Programação linear
• Document Type: Master Thesis
• Language: Portuguese
• Advisor(s): Agra, Maria Cristina Saraiva Requejo

Description

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. Mestrado em Matemática e Aplicações