Aplicação de metaheurísticas na abordagem do problema de roteamento de veículos capacitado com janelas de tempo
| Orientador(a) (dc.contributor.advisor) | Gómez, Arthur Tórgo | |
| Coorientador(a) (dc.contributor.advisor-co1) | Costa, Cristiano André da | |
| Lattes Coorientador(a) (dc.contributor.advisor-co1Lattes) | http://lattes.cnpq.br/9637121030877187 | pt_BR |
| Lattes Orientador(a) (dc.contributor.advisorLattes) | http://lattes.cnpq.br/3090969413342098 | pt_BR |
| Autor(a) (dc.contributor.author) | Galafassi, Cristiano | |
| Autor(a) Lattes (dc.contributor.authorLattes) | http://lattes.cnpq.br/7555705724716780 | pt_BR |
| Data de Disponibilização (dc.date.accessioned) | 2015-04-01T18:43:13Z | |
| dc.date.available (dc.date.available) | 2015-04-01T18:43:13Z | |
| Data da defesa / Data do evento (dc.date.issued) | 2011-10-31 | |
| Abstract (dc.description.abstract) | This paper approaches the Capacitated Vehicle Routing Problem with Time Windows, which must obey the restrictions on vehicle capacity and time windows for customer service. To solve this problem will be used two metaheuristics, Tabu Search and Genetic Algorithms, and are developed an hybrid algorithm based on this two metaheuristics. The aim is to contribute with the development of a Hybrid Algorithm focused on Vehicle Routing Problem that uses the Tabu Search intensification power and the Genetic Algorithms diversification power, in order to obtain good quality solutions without compromising the computational time. In the experiments, with respect to Tabu Search, we analyze the search process by varying the size of the Tabu List and the maximum number of iterations without improvement in objective function value, such as stopping criterion, applied to an intensification policy. For the genetic algorithm are analyzed the influence and the search behavior on the basis of three crossover operators, applied to two elitism policies. Still, for the hybrid algorithm, we analyze the impact of the Tabu List size and rates of mutation and crossover. Finally, the results are compared with the best heuristics in the literature and with exact methods, where the Hybrid Algorithm shows robust, getting several optimal solutions. | en |
| Resumo (dc.description.resumo) | Este trabalho aborda o Problema de Roteamento de Veículos Capacitado com Janelas de Tempo, onde devem ser atendidas as restrições de capacidade do veículo e as janelas de tempo de atendimento do cliente. Para resolver tal problema serão utilizadas as metaheurísticas Busca Tabu e Algoritmos Genéticos, além do desenvolvimento de um Algoritmo Híbrido baseado nas duas metaheurísticas. Busca-se contribuir com o desenvolvimento de um Algoritmo Híbrido focado no Problema de Roteamento de Veículos que utilize o poder de intensificação da Busca Tabu e o poder de diversificação do Algoritmo Genético, objetivando a obtenção de soluções de boa qualidade sem comprometer o tempo computacional. Nos experimentos, no que tange a Busca Tabu, analisa-se o processo de busca da através da variação do tamanho da Lista Tabu e do número máximo de iterações sem melhora do valor da função objetivo, como critério de parada, aplicados a uma política de intensificação. Para o Algoritmo Genético, é analisada a influência e o comportamento da busca com base em três operadores de cruzamento aplicados a duas políticas de elitismo. Ainda assim, para o Algoritmo Híbrido, analisa-se o impacto do tamanho da Lista Tabu e das taxas de Mutação e Cruzamento. Por fim, os resultados obtidos são comparados com os melhores métodos heurísticos encontrados na literatura e com métodos exatos, onde o Algoritmo Híbrido mostra-se robusto, obtendo soluções ótimas para diversas instancias de problemas. | pt_BR |
| Agência de fomento (dc.description.sponsorship) | CNPQ – Conselho Nacional de Desenvolvimento Científico e Tecnológico | pt_BR |
| URI (dc.identifier.uri) | http://www.repositorio.jesuita.org.br/handle/UNISINOS/3229 | |
| Idioma (dc.language) | pt_BR | pt_BR |
| Nome da instituição (dc.publisher) | Universidade do Vale do Rio dos Sinos | pt_BR |
| País da Instituição (dc.publisher.country) | Brasil | pt_BR |
| Departamento (dc.publisher.department) | Escola Politécnica | pt_BR |
| Sigla da Instituição (dc.publisher.initials) | Unisinos | pt_BR |
| Programa (dc.publisher.program) | Programa de Pós-Graduação em Computação Aplicada | pt_BR |
| Direitos de acesso ao documento (dc.rights) | openAccess | pt_BR |
| Assunto (dc.subject) | Metaheurísticas | pt_BR |
| Assunto (dc.subject) | Busca tabu | pt_BR |
| Assunto (dc.subject) | Algoritmos genéticos | pt_BR |
| Assunto (dc.subject) | Algoritmo híbrido | pt_BR |
| Assunto (dc.subject) | Problema de roteamento de veículos | pt_BR |
| Assunto (dc.subject) | Hibridização | pt_BR |
| Assunto (dc.subject) | Metaheuristics | en |
| Assunto (dc.subject) | Tabu search | en |
| Assunto (dc.subject) | Genetic algorithm | en |
| Assunto (dc.subject) | Hybrid algorithm | en |
| Assunto (dc.subject) | Vehicle routing problem | en |
| Assunto (dc.subject) | Hybridization | en |
| Tema (CNPq) (dc.subject.cnpq) | ACCNPQ::Ciências Exatas e da Terra::Ciência da Computação | pt_BR |
| Título (dc.title) | Aplicação de metaheurísticas na abordagem do problema de roteamento de veículos capacitado com janelas de tempo | pt_BR |
| Tipo de arquivo (dc.type) | Dissertação | pt_BR |
Arquivos
Pacote original
1 - 1 de 1
Carregando...
- Nome:
- CristianoGalafassi.pdf
- Tamanho:
- 2.84 MB
- Formato:
- Adobe Portable Document Format
- Descrição:
- Aplicacao_metaheuristicas
Licença do pacote
1 - 1 de 1
Carregando...
- Nome:
- license.txt
- Tamanho:
- 2.12 KB
- Formato:
- Item-specific license agreed upon to submission
- Descrição: