Uma nova heurística baseada na meta-heurística VNS para o problema de agrupamento de entregas em veículos de uma frota heterogênea

Autores

  • Jorge Von Atzingen dos Reis Universidade Federal de Uberlândia
  • Claudio Barbieri da Cunha Universidade de São Paulo

DOI:

https://doi.org/10.14295/transportes.v19i3.213

Resumo

Resumo: Este artigo trata do problema de distribuição física que envolve o agrupamento e a alocação de entregas a uma frota de veículos visando minimizar o frete total. Este problema surge em diferentes situações práticas em que os pontos a serem atendidos estão suficientemente próximos entre si de tal modo que as distâncias percorridas entre paradas consecutivas podem ser consideradas irrele-vantes para o custo total de entregas da frota e, portanto, podem ser desconsideradas para o cálculo dos fretes pagos a terceiros que rea-lizam esse serviço. O problema pode ser modelado como um problema de bin-packing unidimensional com bins de tamanho variável (do inglês Variable Sized Bin-Packing Problem, VSBPP), uma generalização do tradicional problema de bin-packing no qual bins (veículos) de diferentes capacidades e custos estão disponíveis para a alocação de um conjunto de objetos (cargas) de modo que o custo total dos bins (veículos) utilizados seja mínimo. Neste trabalho é proposta uma nova heurística baseada na Busca em Vizinhança Variável (do inglês Variable Neighborhood Search ou VNS) para a resolução desse problema. Experimentos computacionais com instâncias derivadas de problemas benchmarking da literatura evidenciam que essa nova heurística produz resultados melhores em tempos de processamento bastante reduzidos.

Palavras-chave: busca em vizinhança variável, problema de agrupamento e alocação de entregas, meta-heurística

Abstract: In this paper we deal with the physical distribution problem which comprises grouping and assigning deliveries to a hetero-geneous fleet of vehicles aiming to minimize the total freight cost. This problem arises in several practical situations in which the customers to be served are geographically close enough to each other such that distances traveled between consecutive stops can be regarded as irrelevant when compared to the overall vehicle costs, and thus not considered when establishing the freight rate to be paid to third-party carriers. The problem can be modeled as one-dimensional Variable Sized Bin-Packing Problem (VSBPP), a generalization of the traditional bin-packing problem, in which bins (vehicles) with different sizes and costs are available for the assignment of the objects (deliveries) such that the total cost of the used bins (vehicles) is minimized. A new heuristic based on VNS (Variable Neighborhood Search) is proposed to solve this problem. Computational experiments conducted using instances derived from benchmark problems from the literature evidence that our heuristic produces improved results in very short times.

Keywords: variable neighborhood search, variable sized bin-packing problem, metaheuristic.

Downloads

Não há dados estatísticos.

Biografia do Autor

Jorge Von Atzingen dos Reis, Universidade Federal de Uberlândia

Departamento de Engenharia de Produção

Faculdade de Ciências Integradas do Pontal

Claudio Barbieri da Cunha, Universidade de São Paulo

Programa de Pós-Graduação em Engenharia de Transportes

Escola Politécnica da Universidade de São Paulo

Volume 19, Número 3, Dezembro de 2011

Downloads

Publicado

04-11-2011

Como Citar

Reis, J. V. A. dos, & Cunha, C. B. da. (2011). Uma nova heurística baseada na meta-heurística VNS para o problema de agrupamento de entregas em veículos de uma frota heterogênea. TRANSPORTES, 19(3), 75–84. https://doi.org/10.14295/transportes.v19i3.213

Edição

v. 19 n. 3 (2011)

Seção

Artigos

Licença

Ao submeter um manuscrito para publicação neste periódico, todos os seus autores concordam, antecipada e irrestritamente, com os seguintes termos:

  1. Os autores mantém os direitos autorais e concedem à Revista TRANSPORTES o direito de primeira publicação do manuscrito, sem nenhum ônus financeiro, e abrem mão de qualquer outra remuneração pela sua publicação pela ANPET.
  2. Ao ser submetido à Revista TRANSPORTES, o manuscrito fica automaticamente licenciado sob a Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e da publicação inicial neste periódico.
  3. Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento da publicação inicial nesta revista, desde que tal contrato não implique num endosso do conteúdo do manuscrito ou do novo veículo pela ANPET.
  4. Os autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) depois de concluído o processo editorial. Como a Revista TRANSPORTES é de acesso livre, os autores são estimulados a usar links para o site da Revista TRANSPORTES nesses casos.
  5. Os autores garantem ter obtido a devida autorização dos seus empregadores para a transferência dos direitos nos termos deste acordo, caso esses empregadores possuam algum direito autoral sobre o manuscrito. Além disso, os autores assumem toda e qualquer responsabilidade sobre possíveis infrações ao direito autoral desses empregadores, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
  6. Os autores assumem toda responsabilidade sobre o conteúdo do trabalho, incluindo as devidas e necessárias autorizações para divulgação de dados coletados e resultados obtidos, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.