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

摘要： 自动化集装箱码头中,AGV(自动引导车)负责衔接岸桥和场桥两个装卸作业设备,被认为是影响整体效率的关键环节之一。为刻画AGV充电特征,降低作业成本,提高自动化集装箱码头系统作业可靠性,本文通过时空网络图刻画AGV运输任务和充电过程,以运输成本最小为目标,构建任务分配优化与充电时机选择模型。为求解模型,基于分支定价算法框架设计求解方法,首先通过Dantzing-Wolfe原理将模型分解为基于路径的集合划分主问题和一个存在电量等资源约束的最短路径子问题,其次设计标号修正算法求解。实验结果表明,本文模型算法能够提高模型的求解质量,有效优化AGV作业顺序并选择合适的充电时机,提升AGV任务分配方案的可靠性,并进一步分析了最大电池容量、行驶距离的变化对AGV使用数量、充电次数以及码头作业效率的影响。

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