Collaborative human-robot order picking system : algorithms for task allocation and routing in complex environments
Authors:   , Yu Shitao 
Published: October 2023

[EMBARGOED UNTIL 8/1/2024] Order picking, which involves retrieving items from storage locations for an internal or external customer, is a core function in warehouses and accounts for up to 65 percent of the total operating cost. It is considered as a crucial driver for supply chain performance as improper planning of picking operations leads to inefficient asset utilization and delayed deliveries, which, in turn, adversely affects customer satisfaction, operating cost, and competitiveness. A majority of warehouses adopt a picker-to-parts system (workers travel through a warehouse to retrieve and transport items from storage to packing station), and the fulfillment speed of such order picking system (OPS) depends on the following key decisions - (i) set of orders to be picked in a tour (order batching decision), (ii) assignment of a batch to a picker and order in which their a processed (batch assignment and sequencing decisions), and (iii) route followed x by the picker to collect the orders in each batch (picker routing decision). However, with the growing customer demand and global labor shortage, warehouses are seeking efficient and less labor-intensive order picking systems. Autonomous mobile robots (AMRs) or collaborative robots (cobots) have the potential to alleviate the strain on human workers and expedite order picking operations. However, there are several key operational challenges to address for ensuring an effective collaborative human-robot order-picking system (CHR-OPS), where humans perform item retrieval tasks, and AMRs handle item transportation to the depot. This research aims to improve the fulfillment efficiency of a picker-to-parts CHROPS by optimizing key decisions associated with two warehouse picking strategies, namely, static picking and dynamic picking. In the case of static picking, the items to be retrieved from storage for a given day are known as apriority. On the other hand, the dynamic picking strategy allows for orders to arrive over time (e.g., e-commerce warehouses), and the pick cycle (or picking plan) can be updated in real time. First, we address the problem of optimizing the following key subproblems of a CHR-OPS with a static picking strategy: (i) order batching (how many items should be collected in each AMR tour?), (ii) batch assignment and sequencing (how to assign batches to AMRs, and in what order should they be processed?), and (iii) picker-robot routing (how should the AMR and picker be routed to coordinate the picking process?). Existing literature has not dealt with the three subproblems, and this work is the first to address them for a picker-to-parts CHR-OPS system employing multiple pickers and AMRs. A mixed integer linear programming model is developed to jointly optimize the three subproblems with the objective of minimizing the total tardiness of all orders. The MILP model is validated and solved to optimality for small instances. However, since the problem under consideration is NP-hard, it is computationally intractable for larger instances. To efficiently handle large instances, we proposed deterministic and stochastic local search algorithms, namely variable neighborhood descent and a new variant of simulated annealing. The numerical experiments demonstrate the superior performance of the proposed solution approach compared to existing methods. Besides, our results also show that the picking efficiency is impacted by human{robot team composition, AMR speed, AMR capacity and warehouse layout. Subsequently, we address the CHR-OPS with dynamic picking and developing interventionist picking algorithms for a multi-robot multi-human setting. Specifically, we propose two interventionist policies for dynamic collaborative order picking, namely, the collaborative human-robot interventionist picking algorithm (CHRIPA) and the collaborative human-robot rule-based interventionist picking algorithm (CHR-RIPA). The evaluation of the policies demonstrates that the proposed rules can improve the overall performance of the system compared to benchmark approaches (human-only dynamic picking and collaborative picking with no intervention). In addition, results indicate CHR-IPA outperforms CHR-RIPA in terms of average tar diness and order completion time, albeit with a slightly higher travel distance for human workers. The results have led to several managerial implications for a collaborative order picking system. Further, the proposed models and algorithms are modular and can be adapted to any warehouse setting by accounting for the relevant parameters such as warehouse layout, AMR capacity and human-robot composition. Finally, the directions for future research have been identified and summarized.