自动化集装箱码头混合式任务分配算法研究

    Hybrid task allocation algorithm for automated container terminal

    • 摘要: 随着全球贸易和航运规模持续扩大,码头集装箱吞吐量呈指数级增长,对港口物流效率,特别是自动导引车(AGV)的协同作业效率提出了更高的要求。现有的集中式算法和分布式算法在平衡计算复杂度和优化质量上存在不足,难以有效解决自动化集装箱码头对于缩短完工时间、提高作业效率的需求。针对上述问题,提出一种结合集中式算法和分布式竞价的混合式任务分配算法(HAA)。首先,从调度系统、AGV群和任务集角度着手,构建以最小化完工时间、AGV总行驶距离及任务执行延迟时间为目标的多目标优化模型;其次,利用遗传算法对该问题进行求解,将任务集划分为与AGV数量相等的有序任务子集;最后,各AGV分布式计算对任务子集的竞价值,并结合匈牙利算法求解由竞价值构建的开销矩阵。通过仿真试验,在多种不同任务规模、任务密度的场景下对所提HAA方法进行验证,并与传统的集中式算法和分布式算法对比分析。结果表明,该方法在获得接近集中式算法的求解质量的同时,计算时间平均降低39.09%,展现出较好且稳定的优化性能,且能够适用于周期性调度场景。

       

      Abstract: With the continuous expansion of global trade and shipping,container throughput at terminals increases exponentially. Higher requirements are posed on port logistics efficiency,particularly the collaborative operation efficiency of automated guided vehicles(AGVs). Existing centralized algorithms and distributed algorithms exhibit limitations in balancing computational complexity and optimization quality. The demands of automated container terminals for shortening makespan and improving efficiency cannot be effectively accommodated by existing algorithms. To address these problems,a Hybrid task Allocation Algorithm(HAA) combining centralized algorithms and distributed bid was proposed. First,a multi-objective optimization model was constructed from the perspectives of the scheduling system,AGV fleet,and task set to minimize makespan,total AGV travel distance,and task execution delay. Second,a genetic algorithm was utilized to solve this problem. The task set was divided into ordered task subsets equal to the number of AGVs. Finally,bid values for the task subsets were distributively computed by each AGV. The cost matrix constructed from the bid values was solved using the Hungarian algorithm. Through simulation experiments,the proposed HAA method was validated under scenarios with various task scales and task densities. Comparative analyses with traditional centralized algorithm and distributed algorithms were performed. The results demonstrate that a solution quality close to that of centralized algorithms is achieved by the proposed method. Meanwhile, the computation time is reduced by 39.09% on average. Good and stable optimization performance is exhibited. Furthermore,the method can be effectively applied to periodic scheduling scenarios.

       

    /

    返回文章
    返回