A branch-and-price algorithm for task allocation and global path planning of multiple AGVs in intelligent warehouses

Automated guided vehicles (AGVs) are essential components of modern intelligent warehouse logistics systems, serving as the cornerstone of efficient material handling. Their growing importance highlights their vital role in enhancing the functionality and effectiveness of intelligent warehouses in today’s industries. These material handling systems encompass three key aspects of decision-making: task-to-AGV assignment, AGV path planning, and the scheduling of arrival and departure times for each AGV at various stations. While extensive research has focused on these elements independently, integrated studies addressing the problem comprehensively remain relatively rare. This study proposes a co-optimization problem for task allocation and global path planning for multiple AGVs in intelligent warehouse systems. It effectively integrates dispatching, conflict-free routing, and scheduling of these AGVs. We formulate the problem as a mixed-integer linear programming (MILP) model to minimize the delay time for all tasks and the operational time for all AGVs. Given that this problem is NP-hard, solving the MILP model efficiently for realistic-scale instances is challenging. To tackle the complexities involved, we developed a tailored branch-and-price (BP) algorithm specifically designed for small- to medium-scale problems, complemented by an efficient heuristic algorithm tailored for larger-scale challenges. Enhancements to the BP algorithm’s performance were achieved by incorporating several acceleration techniques that cater to the specific characteristics of our problem. Our experimental results reveal three key findings: (i) the BP algorithm effectively addresses the problem, (ii) the heuristic serves as a viable standalone solution for large-scale scenarios, while also providing high-quality initial solutions for the BP algorithm promptly, and (iii) the introduced acceleration methods significantly reduce the computational time required by the BP algorithm. Overall, our paper presents a robust and tailored approach to AGV material handling systems, providing valuable insights for warehouse operators and supporting their decision-making processes.