A reinforcement learning-based hyper-heuristic for AGV task assignment and route planning in parts-to-picker warehouses.
In: Transportation Research Part E: Logistics & Transportation Review, Jg. 185 (2024-05-01), S. N.PAG
academicJournal
Zugriff:
• This paper formulates the task assignment and route planning of multiple AGVs in an intelligent warehouse as a fixed-destination Multiple Depot Traveling Salesman Problem (MDTSP). Considering the layout of the automated warehouse and the driving characteristics of the AGVs, a MILP model is developed to minimize the total completion time. A series of valid inequalities are presented to strengthen the model by analyzing the characteristics of the problem. • We develop a hyper-heuristic that uses a novel selection strategy based on the improved Multi-Armed Bandits algorithm called Co-SLMAB. It applies the Exponential Monte Carlo with counters (EMCQ) as the acceptance criterion. To our knowledge, ours is the first study to investigate the suitability of a reinforcement learning-based hyper-heuristic (RLHH) method for solving the multi-AGVs task assignment and scheduling problem. • We introduce a novel scheduling approach that optimizes racks' allocation between AGVs and the handling sequence in the RMFS. Then, an efficient method for conflict-free AGV path planning is proposed, which takes different collision avoidance measures depending on the situation. Practicality is achieved by integrating task scheduling and path planning for multi-AGV systems. • We demonstrate the superior performance of the RLHH on various problem instances through a comparative analysis with other algorithms. Furthermore, we analyze the efficiency of the proposed algorithm based on real-life warehouse layouts and perform a sensitivity analysis on AGV configurations. Numerical investigations reveal that the proposed approach greatly enhances the productivity of RMFS and the coordination of AGVs in an actual intelligent warehouse scenario. Globally, e-commerce warehouses have begun implementing robotic mobile fulfillment systems (RMFS), which can improve order-picking efficiency by using automated guided vehicles (AGVs) to realize operations from parts to pickers. AGVs depart from their initial points, move to a target rack position, and subsequently transport racks to picking stations. The AGVs return the racks to their original positions after the workers pick them up. When all tasks are completed, the AGVs return to their starting point. In this context, the main challenge is the task assignment and route planning of multiple AGVs to minimize travel times. We formulate a mixed-integer linear programming (MILP) model with valid inequalities to solve small problem instances optimally. We introduce a reinforcement learning (RL)-based hyper-heuristic (HH) framework to solve large instances to near-optimality. A typical HH framework comprises two levels: high-level heuristics (HLH) and low-level heuristics (LLH). The framework starts from an initial solution and improves iteratively through LLHs, while the HLH invokes a selection strategy and an acceptance criterion to generate a new solution. We propose a novel selection strategy based on the improved Multi-Armed Bandits algorithm called Co-SLMAB and Exponential Monte Carlo with counters (EMCQ) as the acceptance criterion. The corresponding collision avoidance rules are then formulated for different conflicts to construct a conflict-free traveling route for AGVs. Besides testing the proposed framework's effectiveness in real-life warehouse layouts, we perform extensive computational experiments and a thorough sensitivity analysis. The results show that (i) the proposed valid inequalities aid in obtaining better lower bounds and significantly speed up the solution process; (ii) the Co-SLMAB-HH framework is quite competitive compared to CPLEX, outperforming the other tested hyper-heuristics and the problem-specific heuristic regarding convergence and computation time; and (iii) a pool of LLHs consisting of a wide range of different operators is advantageous over a limited set of simple operators while solving problems using hyper-heuristics. [ABSTRACT FROM AUTHOR]
Titel: |
A reinforcement learning-based hyper-heuristic for AGV task assignment and route planning in parts-to-picker warehouses.
|
---|---|
Autor/in / Beteiligte Person: | Li, Kunpeng ; Liu, Tengbo ; Ram Kumar, P.N. ; Han, Xuefang |
Link: | |
Zeitschrift: | Transportation Research Part E: Logistics & Transportation Review, Jg. 185 (2024-05-01), S. N.PAG |
Veröffentlichung: | 2024 |
Medientyp: | academicJournal |
ISSN: | 1366-5545 (print) |
DOI: | 10.1016/j.tre.2024.103518 |
Schlagwort: |
|
Sonstiges: |
|