关键词: 自动化码头, 自动导引车, 任务分配, 分支定价算法

Abstract: In automated container terminals, the horizontal transportation system plays a crucial role, connecting the berth and yard, two complex subsystems, and is considered one of the key factors affecting the efficiency of the entire container terminal. The horizontal transportation system is responsible for scheduling a limited number of Automated Guided Vehicles (AGV), which transport import and export containers repeatedly between the berth and yard, completing vessel loading and unloading tasks. With the continuous enlargement of container ship sizes, the number of containers to be loaded and unloaded upon vessel berthing also significantly increases. However, due to the confined operational area, the simultaneous operation of a large number of AGV can lead to considerable conflicts and congestion, and simply increasing the number of AGV operations cannot alleviate the operational pressure on the horizontal transportation system. Failure to allocate tasks to AGV reasonably and generate operational sequences will result in decreased efficiency, increased operational costs, and may even affect the overall operational efficiency of the automated terminal. On the other hand, currently, all AGV in large-scale automated container terminals are powered solely by electricity. However, constrained by existing battery technology, their battery capacity is limited, restricting their maximum travel distance after a single full charge. Therefore, this study aims to allocate operational tasks to AGV while selecting appropriate charging times, effectively reducing the operational costs of the horizontal transportation system, improving operational reliability, and ensuring the operational efficiency of automated container terminals.
   To address these issues, this study constructs a spatio-temporal network graph based on the operational process and charging characteristics of AGV, depicting both transportation tasks and charging processes. By combining the traditional AGV task allocation problem with the charging problem and transforming them into graph problems, this study effectively reduces the complexity of the model. Based on the constructed network graph, we aim to minimize the transportation costs of AGV fixed, transportation, and charging systems, and build a model for task allocation optimization and charging time selection to decide AGV task allocation, operational sequences, and charging times. We employ the Dantzig-Wolfe principle to decompose the model into a main problem of path-based set partitioning and a shortest path sub-problem with constraints such as battery capacity, placing different nature constraints in the main problem and sub-problem separately to reduce the complexity of model solving. For the decomposed main problem and sub-problem, we design a solution framework based on the branch-and-price algorithm. This framework generates initial solutions using a greedy algorithm, continuously solves the main problem using commercial solvers, and designs a label correction algorithm to solve the sub-problem to obtain fractional solutions of the model. Finally, based on the arc branching strategy, we obtain integer solutions, construct the AGV task operation sequence with the lowest cost, and select charging times for each AGV.
   Finally, this study generates experimental data based on the fully automated Phase IV terminal of Shanghai Yangshan Port Area in China, and conducts simulation experiments on cases of different scales to test the performance of the proposed model algorithm. The results of small-scale experiments demonstrate that the proposed model and algorithm can obtain accurate solutions in a short time, consistent with the results of directly solving the original model after linearization, obtaining AGV task sequences including charging tasks, greatly improving solution efficiency. Large-scale experiment results indicate that the proposed model and algorithm can effectively apply to practical scheduling operations of terminal AGV, optimize AGV task allocation and operational sequences, select reasonable charging times, and effectively reduce the operational costs of the horizontal transportation system. Sensitivity analysis of scheduling schemes reveals that the more tasks and complex terminal layouts, the more AGV are required to complete loading and unloading tasks, leading to higher operational costs. An sensitivity analysis of battery capacity shows that with the decrease in battery capacity, the method proposed in this study will prioritize increasing the number of charging times for AGV to reuse them. When the maximum distance decreases to a certain extent, relying solely on increasing charging times cannot complete the operational tasks, and further increasing the number of AGV operations will be necessary to ensure the completion of container loading and unloading tasks.

Key words: automated terminal, automatic guided vehicle, task allocation, branch and price algorithm