Proposta de um Algoritmo Híbrido baseado em Colônia de Formigas para o Problema de Roteamento de Veículos com Restrições de Cobertura

Autores

  • Vitor A A Souza Universidade Federal de Minas Gerais
  • Ramon Lopes Universidade Federal do Recôncavo da Bahia
  • Tiago Januario Universidade Federal da Bahia http://orcid.org/0000-0003-0237-1596

DOI:

https://doi.org/10.5752/P.2316-9451.2016v5n1p3

Resumo

O Problema de Roteamento de Veículos (PRV) é um problema clássico de Otimização Combinatória, e a principal motivação para o seu estudo e de suas variações é o alto gasto com o transporte de cargas, impactando nos preços da matéria prima e do produto final. Neste trabalho, estuda-se uma variação do PRV denominada Problema de Cobertura Multi- Veículo (PCMV) que, diferentemente das demais variações existentes na literatura, possui restrições de cobertura e natureza seletiva, além das restrições de carga nos veículos. Este trabalho propõe um algoritmo híbrido baseado em Colônia de Formigas (CF) para o PCMV que utiliza um algoritmo Variable Neighborhood Search (VNS) e fundamenta-se na trans- formação do PCMV em um Problema de Roteamento de Veículos Capacitado (PRVC), para o qual o método apresentado foi projetado. O algoritmo proposto obteve 16 novos limites primais para as 30 Instâncias consideradas em um tempo computacional inferior a 21 segundos, enquanto os resultados apresentados na literatura foram encontrados em até quatro horas de execução. 

Downloads

Não há dados estatísticos.

Biografia do Autor

Tiago Januario, Universidade Federal da Bahia

É Professor Adjunto no Departamento de Ciência da Computação, Instituto de Matemática, Universidade Federal da Bahia. Possui graduação em Ciência da Computação pela Universidade Federal de Viçosa, mestrado em Ciência da Computação pela Universidade Federal de Minas Gerais com período sanduíche na Università degli Studi di Udine, Tem experiência em Teoria dos Grafos e Otimização Combinatória.

Downloads

Publicado

2016-11-29

Como Citar

SOUZA, Vitor A A; LOPES, Ramon; JANUARIO, Tiago. Proposta de um Algoritmo Híbrido baseado em Colônia de Formigas para o Problema de Roteamento de Veículos com Restrições de Cobertura. Abakós, Belo Horizonte, v. 5, n. 1, p. 3–17, 2016. DOI: 10.5752/P.2316-9451.2016v5n1p3. Disponível em: https://periodicos.pucminas.br/abakos/article/view/P.2316-9451.2016v5n1p3. Acesso em: 23 jun. 2025.

Edição

Seção

Artigos completos / Full papers