A branch-and-price heuristic algorithm for the ART and external truck scheduling problem in an automated container terminal with a parallel layout

The scheduling of horizontal transportation equipment in automated container terminals is a focal area of concern in the port industry. In an automated container terminal with a parallel layout, artificial intelligence robots of transportation (ARTs) and external trucks (ETs) are critical vehicles that connect the quayside, yard side, and hinterland. The operational management of ARTs and ETs is complex because of various factors affecting their operational performance, such as vehicle congestion, limited handover point capacity, limited crane operation capacity, and intersection of ARTs and ETs. This study considers the ART and ET scheduling problem, which involves the task assignment of ARTs and the sequencing of all operations for ARTs and ETs. We formulate the problem as a mixed-integer linear programming (MILP) model to minimize the delay time for all ART and ET tasks. However, since the problem is NP-hard, the MILP model cannot be efficiently solved for realistic-scale instances. Therefore, we reformulate the original model into a route-based model and propose a tailored branch-and-price heuristic algorithm to solve the new formulation. In addition, several acceleration methods adapted to the problem characteristics are introduced to enhance the performance of the algorithm. Computational experiments validate the effectiveness of the proposed algorithm and provide managerial insights to support operational decision-making for terminal operators.