基于资源调度视角的港口预翻箱问题建模方法

1.集装箱堆场预翻箱问题
　　预翻箱与翻箱场景类似，不同之处在于，翻箱动作发生在出箱作业时，而预翻箱发生在出箱作业前，依据计划出箱顺序，对指定堆存区的集装箱堆垛状态进行调整，以保证出箱作业时，堆存状态与出箱顺序的一致性，从而减少出箱时的翻箱作业；且由于不存在出箱操作，预翻箱作业不会增加堆垛空间；当前堆场涉及预翻箱的典型场景包括：贝位预翻箱、区段内预翻箱整理、出口箱整体转堆三类；
　　（1）贝位预翻箱：翻箱空间仅在一个贝位内的预翻箱场景；
　　　　　　　　　　　　　　
　　（2）区段内预翻箱整理：相较与贝位预翻箱，区段内预翻箱将空间扩大到了指定的区块范围内，集装箱的重堆放就可能发生在不同贝位间；区段内预翻箱适用于某船舶相应出口箱堆存较零散，堆存位内集装箱较少，堆存密度不高的场景。
　　　　　　　　　　　　　
　　（3）出口箱整体转堆：出口箱整体转堆主要适用于预堆存策略下集港的出口箱。具体为，在装船前按转堆计划将相关出口箱从各区块整体转堆到距船舶预停靠泊位较近的区块，以达到有效减少甚至完全避免装船时翻箱的可能，减少装船时水平运输距离，提高装船效率。
　　　　　　　　　　　　
2. 建模方法-以贝位内翻箱为例
　　针对贝位内翻箱场景，以最小化翻箱次数为目标，引入堆存序列，堆存路径等概念，进行模型的构建；
2.1 集装箱移动move
　　定义二元组<c,t>表示集装箱c在时刻t进行了一次移动（move），即在时刻t集装箱c进行了从某栈顶出栈的操作，或者入栈到了某栈顶端。（注：时刻t并非严格指代具体的时刻，其主要用于区分翻箱操作的次序）；
2.2.可行堆存序列的定义
　　一条包含move、出入栈信息的作业序列；例如对任意栈s，栈高为3层, 初始状态假设为空栈；定义如下三条堆存序列：
　　L1：[(集装箱1,时刻0),入栈]-> [(集装箱2,时刻3),入栈] -> [(集装箱3,时刻4),入栈] -> [(集装箱1,时刻5),出栈]；
　　L 2：[(集装箱1,时刻0),入栈]-> [(集装箱2,时刻3),入栈] -> [(集装箱3,时刻4),入栈] -> [(集装箱4,时刻5),入栈] -> [(集装箱4，时刻7),出栈]；
　　L 3：[(集装箱1,时刻0),入栈]-> [(集装箱2,时刻3),入栈] -> [(集装箱2,时刻4),出栈] -> [(集装箱3,时刻5),入栈]；
　　可知，由于集装箱出栈操作只能对栈顶集装箱进行，则L1为不可行序列（第4步，时刻5集装箱1出栈时不在栈顶）；而对L2虽然满足了栈顶出栈规则，但在第4步时，栈高超过了3，因此，同样不可行；只有L3为可行堆存序列，最终栈s的堆存状态为集装箱1在一层，集装箱3在二层；此外，对于贝位内翻箱场景，可行的堆存序列需要满足如下条件：
　　（a）在任意时刻t，最多仅有一个出/入栈move；
　　（b）对任意入栈move，要求集装箱c在插入栈顶后不超过栈的堆高要求以及时刻t集装箱c位于栈顶；
　　（c）每个栈的最终堆垛状态满足不压箱要求；
2.3可行堆存路径
　　每个栈对应的堆存序列包含至少一个集装箱的进出栈操作，因此，每个集装箱在各个栈的出/入栈操作按时刻升序组成的操作路径为该集装箱在堆场的一组堆存路径，堆存路径即为该集装箱在堆场的翻箱步骤；如下例所示，表示集装箱1在时刻1从箱位1放置到箱位2，在时刻3由箱位2放置到箱位3
　　eg: 集装箱1：”箱位1 “–(时刻1)–>“箱位2”–(时刻3)–>“箱位3”;
2.4 数学模型
　　结合上述定义，可得如下形式的MIP模型；
　　目标：最小化各栈执行堆存序列中出栈move数之和（翻箱次数） （1）
　　约束：
　　　　任意时刻，集装箱的入栈move数一定大于等于出栈move数 （2）
　　　　任意时刻，最多只有一个集装箱入栈 （3）
　　　　每个栈最多执行一条堆存序列 （4）
2.5 计算样例
　　（1）贝位内翻箱场景初始堆存状态
　　　　　　　　　　　　
　　（2）采用枚举法或其他启发式方法定义如下堆存序列：
　　　　　　　　　　　　
　　（3）构建MIP模型并调用求解器求解得翻箱方案如下：
　　翻箱次数为7次；栈s0执行序列L1, 栈s1执行序列L2, 栈s3执行序列L3；
3. 结论
　　（1）T的设定甚至决定了模型是否存在可行解；例如对于初始堆存包含3个压箱状态的堆垛（即至少需要翻箱3次），若T设定为2，易知，无论堆存序列是否为全局，该模型无可行解；
　　（2）上述建模方法中，当T足够大，且执行序列为全集时，可获取到最优解，令T = 5，枚举所有堆存序列，可得最优翻箱次数为4次，各集装箱的堆存路径为：
　　C0：”A0-7-1-3 “–(时刻1)–>“A0-7-2-3”–(时刻3)–>“A0-7-3-2”;
　　C1: “A0-7-1-2”–(时刻2) –>“A0-7-3-1”;
　　C2: 不移动
　　C3：“A0-7-2-2”–(时刻4) –> “A0-7-3-3”；
　　C4: 不移动
　　（3）当问题规模较大时，采用枚举法/启发式方法短时间内无法获取到堆存序列的全集，因此，为了获取精确解，可结合列生成技术进行建模求解；

参考文献
【1】 van Brink M, van der Zwaan R. A branch and price procedure for the container premarshalling problem[C]//European Symposium on Algorithms. Springer, Berlin, Heidelberg, 2014: 798-809.