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

Authors

  • 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

Abstract

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

Download data is not yet available.

Author Biographies

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

Published

2011-11-04

How to Cite

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

Issue

Vol. 19 No. 3 (2011)

Section

Articles

License

Authors who submit papers for publication by TRANSPORTES agree to the following terms:

  1. The authors retain the copyright and grant Transportes the right of first publication of the manuscript, without any financial charge, and waive any other remuneration for its publication by ANPET.
  2. Upon publication by Transportes, the manuscript is automatically licensed under the Creative Commons License CC BY 4.0 license. This license permits the work to be shared with proper attribution to the authors and its original publication in this journal, and to be adapted for non-commercial purposes, provided appropriate credit is given and any derivative works are distributed under the same terms.
  3. Authors are authorized to enter into additional separate contracts for the non-exclusive distribution of the version of the manuscript published in this journal (e.g., publishing in an institutional repository or as a book chapter), with recognition of the initial publication in this journal, provided that such a contract does not imply an endorsement of the content of the manuscript or the new medium by ANPET.
  4. Authors are permitted and encouraged to publish and distribute their work online (e.g., in institutional repositories or on their personal websites) after the editorial process is complete. As Transportes provides open access to all published issues, authors are encouraged to use links to the DOI of their article in these cases.
  5. Authors guarantee that they have obtained the necessary authorization from their employers for the transfer of rights under this agreement, if these employers hold any copyright over the manuscript. Additionally, authors assume all responsibility for any copyright infringements by these employers, releasing ANPET and Transportes from any responsibility in this regard.
  6. Authors assume full responsibility for the content of the manuscript, including the necessary and appropriate authorizations for the disclosure of collected data and obtained results, releasing ANPET and Transportes from any responsibility in this regard.