Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/SLSS-85BJG5
Type: | Dissertação de Mestrado |
Title: | Heurísticas e algoritmo exato para o problema de roteamento de veículos com coleta e entrega simultâneas |
Authors: | Dilson Lucas Pereira |
First Advisor: | Geraldo Robson Mateus |
First Referee: | Sergio Ricardo de Souza |
Second Referee: | Alexandre Salles da Cunha |
Third Referee: | Alysson Machado Costa |
Abstract: | Este trabalho trata do Problema de Roteamento de Veículos com Coleta e Entrega Simultâneas, para o qual devem ser desenvolvidas rotas para atender as demandas de coleta e entrega de um conjunto de consumidores. Cada consumidor deve ser atendido por uma única rota, a carga recebida é trazida de um depósito central, para onde tambémé levada toda a carga coletada. A capacidade dos veículos utilizados não deve ser violada em nenhum ponto das rotas. O problema é abordado de maneira heurística e exata. Inicialmente, são desenvolvidas heurísticas híbridas baseadas em idéias de diversas metaheurísticas, em especial ILS, GRASP e VND. Essas heurísticas são testadasem diversas instâncias e comparadas aos melhores resultados da literatura, obtendo resultados competitivos com os melhores algoritmos existentes. É desenvolvido um método exato Branch-and-price e, nesse contexto, são propostas novas estratégias para a resolução do subproblema, um Problema de Caminho Elementar Mínimo com Restrição de Recursos. Em experimentos computacionais, essas estratégias demonstram redução significativa no tempo computacional da resolução da Geração de Colunas. É apresentada também uma estratégia em que limites inferiores obtidos a partir da geração de colunas são utilizados no processo de decisão do branching. O algoritmo Branch-and-price é testado e comparado a um algoritmo Branch-and-cut-and-price da literatura. |
Abstract: | This work adresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery, where routes must be devised to fulfil the pickup and delivery requests of a set of customers. Each customer must be served by only one route, the load it receives isbrought from a central depot, to where the picked-up load is also taken. The capacity of the used vehicles must not be violated at any point of the routes. Heuristics and anexact algorithm are proposed to solve the problem. Initially, we devise some heuristics based on ideas of many metaheuristics, specially ILS, GRASP, and VND. These heuristics are tested in many instances and are compared to the best results of the literature, obtaining results comparable to the best existing algorithms. Afterwards, aBranch-and-price method is developed, and in this context, we propose new strategies to the resolution of the subproblem, an Elementary Resource Constrained Shortest Path Problem. Based on computational experiments, these strategies show considerable reduction on the computational time of the Column Generation resolution. Wepresent a strategy in which lower bounds obtained from the column generation are used in the branching process. The Branch-and-price algorithm is tested and compared to a Branch-and-cut-and-price algorithm from the literature. |
Subject: | Algorimos de computador Otimização matemática Computação Transporte rodoviário Processamento de dados |
language: | Português |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/SLSS-85BJG5 |
Issue Date: | 25-Feb-2010 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
dilson.pdf | 3.99 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.