The joint order batching and picking routing problem : algorithms and new formulation

Abstract

Efficiently managing large deposits and warehouses is not an easy task. The amount of variables and processes involved from the moment a consumer purchases a single product until its receipt is quite considerable. There are two major problems involving warehouses processes: the order picking problem (OPP) and the order batching problem (OBP). The OPP aims to minimize the distance traveled by a picker while collecting a set of products (orders). The OBP seeks to assign orders to batches with a capacity limit to minimize the sum of distances traveled during the retrieving of products from all batches. When these two problems are approached together, they become the Joint Order Batching and Picking Routing Problem (JOBPRP). This work proposes a novel formulation for JOBPRP and develops a dynamic programming based heuristic, and a grouping genetic algorithm with controlled gene transmission to JOBPRP. To assess our proposals, we executed compu tational experiments over literature datasets. The mathematical model was used within a mixed-integer programming solver (Gurobi) and tested on the smaller instances to evalu ate the quality of the solutions of our metaheuristic approach. Our computational results evidence high stability for all tested instances and much lower objective value than the previously reported in the literature while maintaining a reasonable computational time.

Administrar grandes depósitos e armazéns de forma eficiente não é uma tarefa fácil. A quantia de variáveis e processos envolvidos desde o momento em que o consumidor realiza a compra de um único produto, até o seu recebimento, é bastante considerável. Dentro deste contexto, existem dois principais problemas envolvendo processos em armazéns: o problema de coleta de pedidos (OPP) e o problema de loteamento de pedidos (OBP). O OPP tem por objetivo minimizar a distância viajada por um funcionário enquanto ele faz a coleta de uma lista de produtos (pedidos). O OBP busca agrupar pedidos em lotes, que possuem um determinado limite de capacidade, de forma que a soma das distâncias via jadas durante a coleta dos produtos de todos os lotes seja minimizada. Quando estes dois problemas são abordados de forma conjunta, a estratégia é conhecida como problema de loteamento e coleta simultânea de pedidos (JOBPRP). Este trabalho propõe uma nova formulação matemática para o JOBPRP e apresenta novas soluções algorítmicas para tal problema: uma heurística baseada em dois níveis de programação dinâmica e um algo ritmo genético de agrupamento com controle de transmissão de genes. Para avaliar nossas propostas, executamos experimentos computacionais com conjuntos de dados fornecidos pela literatura. O modelo matemático foi utilizado em um software solucionador de pro gramas inteiros-mistos (Gurobi), onde se realizaram testes com pequenas instâncias para aferir a qualidade das soluções da nossa abordagem metaheurística. Nossos resultados computacionais evidenciaram alta estabilidade para todas as instâncias testadas e meno res valores objetivo que os reportados previamente na literatura, mantendo um tempo de execução razoável.