1.目的及意义

1.1研究背景

随着全球一体化的快速发展，集装箱运输己成为国际贸易的主要运输形式。自2000年以来，中国港口集装箱运输发展速度极快，年均复合增长率保持在15%以上。在集装箱码头吞吐量快速增长的同时，由集疏港作业给码头带来的问题日益凸显。目前，大型集装箱堆场的翻箱率己经高达67%一100%，而进口箱翻箱率远高于出口箱。

对于进口箱，客户分散且提箱时间具有很强的随机性。由于场外集卡到港时间不确定，导致提箱顺序与目标箱在堆场的堆存位置顺序不一致，从而产生大量翻箱。翻箱问题是直接影响堆场作业效率的关键因素之一。这不仅增加集卡在码头的周转时间，而且降低堆场提箱作业效率。堆场翻箱以及集卡拥堵问题己经成为制约集装箱码头发展的瓶颈。集装箱码头不确定型集卡提箱与堆场翻箱协同优化势在必行。

集卡提箱顺序与堆场协同优化问题，是以在满足场外集卡最大提箱时间要求条件下使堆场翻箱量最少为优化目标。集装箱翻箱问题（the container relocation problem，CRP）已经被证明是具有NP特性的组合优化问题（NP-hard问题）。当CRP问题规模不大的时候仍然可以通过精确算法得到最优解，但是在实际生产中由于不确定因素和约束条件的增加，主流的解决方案是通过启发式算法进行求解。启发式算法可以解决较大规模的组合优化问题，节约算法的时间成本和存储空间成本，在可以容忍的时间范围内获得问题的近优解。

1.2国内外发展现状

KIM^[1]按照顺序提箱，利用分支定界法和启发式算法计算翻箱量。其次Zhao和Anne V ^[2]等人将场外集卡预约提箱时间的信息根据不同信息质量做了详细分类，基于有效内预约提箱时间研究集卡到达时刻信息质量和堆场贝位堆存情况对进口箱翻箱效率的影响。Guang^[3]利用M/Ek/c排队模型计算集卡排队的平均队长，构建了基于集卡预约信息的优化模型，使非稳态排队论逐渐得到应用。

在翻箱问题上，国外学者研究比较早。Kim和Hong^[4]等在假设已知提箱顺序的基础上利用分支定界算法探讨了提取进口箱时阻碍箱落箱位置的优选问题。当贝规模逐渐增大时，又开发了OH启发式算法。Lee和hsu^[5]以预翻箱过程中翻箱量最小为目标，建立基于多商品流问题和边际约束的整数规划模型，利用启发式算法对落箱位置进行优化模型，开发快速求解算法。Jin Bo^[6]等针对一个贝位内的翻箱问题，提出了贪婪算法和前瞻算法混合的两阶段启发式算法。Raka Jovanovic和 Stefan Vo#223;^[7]考虑如果一个块被移动到堆垛时堆垛是否会达到最大层次，通过改进BRP的Min-Max启发式，设计了一个新的启发式算法来解决翻箱问题。Dusan Ku和Tiru S. Arthanari^[8]考虑了CRP的出发时间窗，制定了一个SDP模型，并使用基于搜索的算法（DFS），并且引入抽象启发式来最优解决模型。

国内大连理工大学的李丕安，周鹏飞等^[9]分析了影响客户提箱顺序的因素，针对提箱时间动态不确定性，建立基于一定概率保证的广义提箱顺序模型，开发了快速求解算法。姚诗^[10]、李厚源^[11]等以确定性集卡到达信息的进口箱翻箱问题为基础,基于部分集卡信息的进口箱提箱与翻箱问题提出了各自的启发式算法。曾庆成等^[12]基于部分集卡到达信息进行码头进口箱的翻箱优化，提出了最小化二次翻箱的启发式算法。冯媛君等^[13]对于堆场翻箱和外集卡提箱顺序同步优化，建立了基于动态规划的启发式算法。赵金秋^[14]等基于虚拟路径对进口箱进行了翻箱落位的启发式算法。邵乾虔等^[15]对不确定环境下的进口箱提箱作业进行了动态优化。基于统计分布规律模拟外部集卡到港的随机性，提出了动态优先提箱的概率的概念和计算方法，并以此设计了分支定界 启发式算法的双层算法。

1.3 研究现状总结