Uma proposta de um algoritmo do tipo Grey Wolf Optimizer para o problema de transporte com designação e carregamento

Abstract

Resumo: O problema de transporte com designação e carregamento (ALTP, do inglês Assignment and Loading Transportation Problem) foi recentemente introduzido na literatura inspirado por um problema envolvendo operações militares. O ALTP possui potenciais aplicações em logística de emergência e, como tal, requer algoritmos que constroem soluções aceitáveis em curtos intervalos de tempo. No presente trabalho, um novo algoritmo metaheurístico é proposto para o ALTP. O algoritmo proposto tem por base uma variação da metaheurística Grey Wolf Optimizer, que é inspirada na hierarquia social e comportamento de caça de alcateias de lobos cinzas na natureza. O algoritmo apresentado é avaliado em 80 instâncias, compreendendo tanto instâncias reais como artificiais, e comparado com o algoritmo heurístico disponível na literatura para a construção de soluções rápidas para o problema. O desempenho de ambos os algoritmos é avaliado em diferentes limites de tempo para execução. Os resultados experimentais indicam que o algoritmo desenvolvido no presente trabalho é bastante competitivo e pode ser aplicado com sucesso ao novo problema introduzido na literatura. Particularmente, instâncias realísticas são resolvidas com maior eficácia pelo algoritmo desenvolvido, dentro de limites de tempo distintos, quando comparado à heurística disponível na literatura. Palavras-chave: Problema de transporte com designação e carregamento. Grey Wolf Optimizer. Meta-heurísticas. Otimização. Programação linear inteira mista. Logística de emergência.

Abstract: The Assignment and Loading Transportation Problem (ALTP) was recently introduced in the literature inspired by a problem emerging in military operations. The ALTP has potential applications in emergency logistics and, as such, requires algorithms that provide reasonable solutions in acceptable time limits. In the present work, a new metaheuristic algorithm is proposed for the ALTP. The algorithm developed is based on a recent version of the Grey Wolf Optimizer (GWO), which is inspired in the hierarchical structure and hunting behavior of grey wolves in nature. The algorithm is evaluated in 80 benchmark instances, comprising both realistic and artificial datasets, and compared to the state-of-the-art meta-heuristic in the literature. The performance of both meta-heuristics is studied in different time limits for the execution of the algorithms. Experimental results indicate that the algorithm developed in the present study is quite competitive and can be successfully applied to the newly introduced problem in the literature. Particularly, realistic instances are solved with greater efficacy by the GWO, within distinct time limits, when compared to the algorithm available in the literature. Keywords: Assignment and loading transportation problem. Grey Wolf Optimizer. Metaheuristics. Optimization. Mixed Integer Linear Programming