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

Authors

  • 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

Abstract

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

Download data is not yet available.

Author Biography

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

Additional Files

Published

2016-11-29

How to Cite

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: 11 sep. 2025.

Issue

Vol. 5 No. 1 (2016)

Section

Artigos completos / Full papers

License

I  (we) submit the present work, an original and unpublished manuscript, from my (our) authorship, to Abakós - Magazine of Interdisciplinary Studies on Science and Informatics, and  I (we) agree that the copyright related to this work will become property of  PUC Minas Publisher. No partial or full reproduction is allowed, by any means (printed or electronic), dissociated from Abakós. Any reproduction requires prior written authorization granted by the Editor.

I (we) declare there is no type of interest conflict among the subject theme, author(s), organization(s), institution(s) and person(s).

I (we) recognize that Abakós is licensed under CREATIVE COMMONS:

Licença Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported (CC BY-NC-ND 3.0).