张艳伟，蔡梦蝶

（武汉理工大学交通与物流工程学院，湖北武汉 430063）

集装箱码头堆场装船发箱和翻箱效率直接影响岸边装船作业和船舶靠泊时间，是提升集装箱港口竞争力的重要突破口之一。受船舶配载等不确定信息的影响，堆场装船前预翻箱整理往往不能完全满足发箱要求，装船时翻箱作业不可避免。由于装船时翻箱不产生价值［1］，单次发箱的翻箱次数过多会影响装船作业连贯性，优化装船时堆场翻箱方案，实现智能高效决策，是提高堆场装船发箱和翻箱效率、保障岸边装船作业的有效手段。集装箱码头堆场通常划分为不同箱区，每个箱区由多个贝位组成。一个贝位的长度为一个标准集装箱长，贝位内通常可堆垛6列4层及以上，即包含24个集装箱箱位及以上。由于多层直接堆垛、贝位内集装箱多且每个集装箱具有唯一属性、一个集装箱可能存在多次翻箱等，堆场翻箱问题解空间大，当堆存状态不佳时，甚至无法在有效时间内得到可行方案，具有NP难属性［2］。因此，装船时翻箱问题（container relocation problem，CRP）一直是研究热点之一。关于CRP的研究，主要包括数学模型研究、精确求解方法研究和智能算法等方面。

Caserta等［3］提出二元线性规划模型CRP-Ⅱ，Expósito-Izquierdo等［4］指出CRP-Ⅱ会产生不可行解，难以保证解最优，将其改进为CRP-Ⅱ*。Zehendner等［5］也对CRP-Ⅱ进行了修正。Petering等［6］提出混合整数线性规划模型CRP-Ⅲ，整数决策变量比CRP-Ⅱ少。Galle等［7］改进二进制整数编码方式，提出二元整数规划模型CRP-Ⅰ。Jin［8］指出CRP-Ⅰ中后进先出约束存在缺陷，设计整数变量将其变为线性约束。……