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

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.