Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/ESBF-BA8NBU| Tipo: | Dissertação de Mestrado |
| Título: | Gamma Deployment Problem in Grids: Complexity and a new Integer Linear Programming Formulation |
| Autor(es): | Marcelo Fonseca Faraj |
| primer Tutor: | Sebastián Alberto Urrutia |
| primer Co-tutor: | João Fernando Machry Sarubbi |
| primer miembro del tribunal : | Cristiano Maciel da Silva |
| Segundo miembro del tribunal: | Geraldo Robson Mateus |
| Tercer miembro del tribunal: | João Fernando Machry Sarubbi |
| Resumen: | Redes veiculares constituem um dos componentes mais essenciais dos sistemas inteligentes de transporte. Elas possuem um potencial para facilitar a gestão de tráfego, reduzir taxas de acidente de trânsito e proporcionar outras soluções para a construção de cidades inteligentes. Um dos principais desafios associados a redes veiculares é a escolha das melhores localizações para instalação das infraestruturas de comunicação, as quais são conhecidas como roadside units ou RSUs. Esta dissertação lida com o Problema da Deposição Gamma, o qual consiste em depositar o mínimo número de roadside units em uma rede rodoviária de modo a cumprir a métrica Deposição Gamma. De acordo com esta métrica, uma porcentagem mínima dos veículos transitando pela rede rodoviária devem estar cobertos, sendo que um veículo é considerado coberto caso encontre ao menos uma roadside unit a cada intervalo pré-determinado de sua viagem. Nesta dissertação, propõe-se um tratamento formal baseado em teoria dos grafos e apresenta-se uma prova de que a versão de decisão do Problema da Deposição Gamma em Grades pertence à classe de complexidade NP-completo. Em seguida, expõe-se um problema associado ao modelo multifluxo de programação linear inteira presente na literatura e propõe-se uma pequena correção. Também se introduz um novo modelo de programação linear inteira baseado em cobertura de conjuntos e demonstra-se que o politopo associado a sua relaxação linear está contido no politopo associado à relaxação linear do modelo multifluxo. Por fim, experimentos computacionais com um otimizador comercial mostram que a formulação cobertura de conjuntos se comporta de modo muito superior à formulação multifluxo em termos de gap de relaxação linear e tempo de execução. |
| Abstract: | Vehicular ad hoc networks are one of the most significant components of intelligent transportation systems. They have the potential to ease traffic management, lower accident rates and provide other solutions to smart cities. One of the main challenges on vehicular ad hoc networks is to choose the best places to deploy roadside units. This thesis deals with the Gamma Deployment Problem, which consists of deploying the minimum number of roadside units on a road network meeting the Gamma Deployment metric. Within this metric, at least a given fraction of vehicles passing in the road network must be covered, i.e they should meet at least one roadside unit each predetermined time interval. In this thesis, I propose a formal treatment based on graph theoretical concepts and provide a proof that the decision version of the Gamma Deployment Problem in Grids is NP-complete. In addition, I expose an issue with the multi-flow integer linear programming formulation present in literature and propose a slight correction for it. I also introduce a new integer linear programming formulation based on set covering and provide a proof that the polytope associated with its linear programming relaxation is contained in the polytope associated with the linear programming relaxation of the multi-flow formulation. Finally, computational experiments with a commercial optimizer show that the set covering formulation widely outperforms the multi-flow formulation regarding linear programming relaxation gap and running time. |
| Asunto: | Complexidade computacional Problemas da deposição gamma Redes veiculares Computação Programação linear inteira Heurística |
| Idioma: | Inglês |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Institución: | UFMG |
| Tipo de acceso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/ESBF-BA8NBU |
| Fecha del documento: | 15-feb-2019 |
| Aparece en las colecciones: | Dissertações de Mestrado |
archivos asociados a este elemento:
| archivo | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| marcelofaraj.pdf | 1.4 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.