A branch-and-bound approach for AGV dispatching and routing problems in automated container terminals. (April 2022)

• Record Type: Journal Article
• Authors: Wang, Zehao; Zeng, Qingcheng
• Is Part Of: Computers & industrial engineering. Volume 166(2022)
• Publication Date: 2022-04
• Subjects: Automated container terminals -- AGV dispatching -- Path planning -- Bidirectional path -- Branch-and-bound; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.107968
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The AGV dispatching and routing problem considering conflict is addressed. A layout with multiple bidirectional paths is investigated. A MIP model is developed to avoid congestion and conflict. A tailored branch-and-bound algorithm is proposed. The results verify the effectiveness of the proposed algorithm. Abstract: The efficiency of automated container terminals primarily depends on the automated guided vehicle (AGV) scheduling scheme. This paper investigates the AGV dispatching and routing problem with multiple bidirectional paths to generate conflict-free routes. A mixed-integer programming (MIP) model is formulated to minimize the completion time of all jobs (i.e., minimize the makespan). A tailored branch-and-bound (B&B) algorithm is developed to solve the problem within a reasonable amount of time, where the B&B process is used to obtain job assignments and job sequences, and a heuristic algorithm is proposed to generate conflict-free routes. To expedite the proposed algorithm, some accelerating techniques are designed in view of the characteristics of the problem. Computational experiments indicate that the proposed algorithm can obtain near-optimal solutions in small-scale instances, and in large-scale instances, the B&B algorithm significantly outperforms the port scheduling strategies. The proposed algorithm can be applied to real-world cases and dynamic cases, and a two-stage greedy heuristic algorithm is also developed to obtain a satisfactory solution in a short amount of time. Some managerial insights into AGV scheduling are offered to guide terminal operations in this study.