Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/ESBF-935ND6
Tipo: | Dissertação de Mestrado |
Título: | Algoritmos exatos e heurísticos para problemas seletivos de roteamento de veículos com restrições de cobertura |
Autor(es): | Ramon Pereira Lopes |
primer Tutor: | Alexandre Salles da Cunha |
primer miembro del tribunal : | Geraldo Robson Mateus |
Segundo miembro del tribunal: | Ricardo Saraiva de Camargo |
Tercer miembro del tribunal: | Edna Ayako Hoshino |
Resumen: | Esta dissertação dedica-se ao estudo de dois problemas de Otimização Combinatória: o Problema de Roteamento de Veículos Seletivo Min-Max (PRVSMM) e o Problema de Cobertura Multi-Veículo (PCMV). Este trabalho propõe um algoritmo de Geração de Colunas e duas heurísticas para o PRVSMM. Com base nos experimentos computacionais realizados, os métodos propostos não se mostraram competitivos em relação àqueles existentes na literatura. No contexto do PCMV, este trabalho propõe um Branch-and-Price e uma heurística. Nos experimentos computacionais realizados para avaliar os algoritmos propostos, nove dentre as trinta instâncias consideradas foram resolvidas na otimalidade. Apesar de as técnicas empregadas para os dois problemas terem o mesmo fundamento, nota-se que o método de Geração de Colunas quando aplicado ao segundo problema obteve um desempenho melhor em comparação ao primeiro |
Abstract: | In this work, we investigate two Combinatorial Optimization problems: the Min-Max Selective Vehicle Routing Problem and the Multi-vehicle Covering Tour Problem. The former models the design of energy-efficient sensor networks; the latter models the delivery of mobile health-care facilities. We propose a Column Generation algorithm and two heuristics for the Min-Max Selective Vehicle Routing Problem. Computationalexperiments were performed to assess the quality of the solutions obtained by these heuristics in comparison to those given by the methods found in the literature. The experiments indicate that the methods proposed here for the Min-Max Selective Vehicle Routing Problem are not as efficient and effective as those found in the literature for the majority of considered instances. For example, one of the proposed heuristics provided new best upper-bounds for seven out of seventy instances considered, though this heuristic required much more time than that required by the other methods. In the context of the Multi-vehicle Covering Tour Problem, we propose a Branch-and- Price algorithm and a heuristic. The Branch-and-Price algorithm solved to proven optimality nine out of thirty instances considered in the computational experiments. In conclusion, one can observe that the algorithm proposed for the second problem had superior performance when compared to the algorithm proposed for the first one, although the same set of techniques were applied for solving both problems |
Asunto: | Otimização matemática Computação |
Idioma: | Português |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Institución: | UFMG |
Tipo de acceso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-935ND6 |
Fecha del documento: | 17-dic-2012 |
Aparece en las colecciones: | Dissertações de Mestrado |
archivos asociados a este elemento:
archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
ramonlopes.pdf | 1.24 MB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.