Uma proposta de heurística para o single picker routing problem considerando restrições de empilhamento máximo

Abstract

Resumo: Neste trabalho apresenta-se uma nova heurística para o Problema de Roteirização para um Único Operador ("Single Picker Routing Problem"), abordando características complexas de problemas reais. Este problema consiste em determinar a menor rota a ser realizada, dentro de um armazém, de forma a coletar - manualmente, todas as caixas (ou itens) de um pedido. Os trabalhos na literatura que tratam sobre o tema, o abordam considerando somente a distância percorrida em uma rota. Na revisão da literatura realizada, não foi encontrado nenhum trabalho que apresente uma abordagem heurística que considere restrições de empilhamento máximo no carregamento em uma rota, integrado ao roteamento e a política LIFO na sequência de coleta. Deste modo, as heurísticas propostas abordam características e restrições reais, como o posicionamento das caixas nos paletes, o sequenciamento de coleta e a distância percorrida, as restrições de empilhamento máximo foram tratadas com uma abordagem recursiva e divisão e conquista do problema, junto a uma estrutura em árvore. As heurísticas desenvolvidas foram aplicadas ao problema de carregamento e ao problema de carregamento e roteamento integrado. Foram testadas em um variado conjuntos de dados, considerando diversos cenários e estratégias. As heurísticas de carregamento obtiveram um desempenho aceitável, pois foram processadas de forma rápida (menos de 1 segundo) e eficiente em relação ao volume total ocupado, com média de 85% de ocupação, considerando somente as restrições de carregamento simples, e a 64% de ocupação com todas as restrições práticas. Todas as soluções encontradas nas instâncias de carregamento e roteamento foram melhoradas por uma heurística de melhoria, também proposta neste trabalho.

Abstract: In this work, a heuristic approach for the single picker routing problem is proposed, along with more complex and practical constraints. This is the problem of determining the least cost tour for a warehouse worker, so that he can collect all item in a request. Literature on the theme shows that the problem is mostly considered only regarding the routes. The proposed heuristic deals with much more realistic considerations, such as pallet volume capacity, boxe's positions inside of it and maximum stacking, considered here as box maximum weight, so far, it is unknown of a work that takes into account routing and stacking of the cargo, along with an LIFO policy. Both loading and routing heuristics were extensively tested in a variety of scenario and strategy. The loading heuristic have performed well, achieving the results in a small period (less than one second) and effective regarding the total volume on those that considered all restrictions. For the routing and loading heuristic instances, all of them were optimized regarding their initial solution by a proposed improvement heuristic. Up to now, there is no knowledge of heuristic that perform the routing and also takes into account maximum stacking in their restrictions.