Scheduling Twin Yard Cranes in a Container Block

（集装箱码头双起重机调度问题）

每年，数百万个集装箱进入和离开码头的堆放区。如果堆叠操作效率不高，则会导致较长的轮船、火车和卡车延误，这将影响整个流程的运作效率。为了改善堆垛操作，新的集装箱码头（尤其是在欧洲）通过部署双自动堆垛起重机来解除陆地和海边的连接。每对自动堆垛起重机负责一个块（Block），如图3所示，每个块由多个行（Rows），层（Tiers）和托架（Bays）组成，自动起重机可以同时沿该块的托架和行移动，但不能彼此通过，必须分开安全距离。

图3. 集装箱堆场布局的示意图

本中心研究如何安排双自动起重机在堆场的一个块中执行一组集装箱存取请求。根据不同运输方式的重要性和可接受的等待时间，请求具有不同的优先级。该问题被建模为具有优先约束的多重非对称广义旅行商问题（NP难问题）。该研究开发了一种自适应大邻域搜索启发式算法，可以快速计算出接近最优的解决方案。本研究进行了广泛的计算实验，以评估启发式算法的性能，包括在真实终端上进行验证。它为小规模实例获得了接近最优的解决方案。对于大规模实例，本中心提出的算法在数秒内得出的结果可优于CPLEX 四小时找出的结果6.77%以上，并且从实践上讲，它比其他启发式方法在实践中的表现要高出24％以上。该研究的启发式方法和最佳解决方案之间的平均差距小于3％。

表3. ALGT与mAGTSP和AGTSP的精确解值之间的差值

本研究发表于交通运输领域顶尖期刊Transportation Science (2015,49(3),686-705)。