摘要：针对集装箱港口提箱过程中的翻箱问题，以最小化翻箱次数为指标，构建基于状态结点的网络图模型，将翻箱问题转化为最短门路问题，并采纳最短门路算法进行求解，最初给出一组计算样例。
1.集装箱堆场翻箱问题
在集装箱码头作业过程中，因为船舶抵港工夫具备不确定性，可能呈现集装箱提箱程序与初始堆放地位不齐全相符的状况，导致须要较早离场集装箱被压在后续离场集装箱上层景象。所以提箱过程中不可避免须要进行翻箱，甚至当被翻箱落箱地位选取不当，会造成后续提箱的二次翻箱；翻箱过程存在如下定义：
（1）指标箱：某一堆存状态下，预最先发箱的集装箱为该堆存状态下的指标箱;
（2）必翻箱：若某集装箱下方存在比其优先取箱的箱子，则该集装箱为相应堆存状态下的必翻箱；
（3）阻塞箱：间断堆存在某集装箱上方的必翻箱，为相应堆存状态下该集装箱的阻塞箱；
如图1所示为某一贝位内的堆存状态（6*6的贝位，且均为20FT集装箱，底部横轴为栈编号，左侧纵轴为层编号）；当提箱程序为C21->C15->C12时，可知以后堆存状态的指标箱位C21，C12处于栈顶，不存在阻塞箱，可间接收回；而C15作为后续堆存状态的指标箱，其上方还有其余集装箱；此时，定义C12,C13,C14为指标箱C15的阻塞箱，同时C12,C13,C14称为以后堆存状态的必翻箱；
图1 堆存状态
2. 基于状态结点的网络图模型
（1）堆存状态：指某堆存范畴内集装箱的堆存状况，如图1所示，即为栈6-11的一组堆存状态；翻箱过程中可行的堆存状态应具备如下特点：
a）：集装箱不能悬空搁置；
b）：不思考轻压重等分量准则；
c）：不容许超过堆存区域既定的最大堆高；
d）：集装箱地位不能超过作业机械所能达到的最大堆高；
（2）状态结点：每一个可行的堆存状态即可作为一个状态结点；
（3）结点可达：针对某一指标箱，若状态结点A中的某一集装箱通过翻箱操作后失去的堆存状态与状态结点B统一，则称结点A可达结点B；
（4）权重取值: 且若结点A可达结点B，那么结点A、B间存在方向A->B,且可计算A->B的翻箱次数，并将其作为连贯权重；
（5）网络图构建原理：以初始堆存状态作为根节点，将指标箱作为层级划分的标识。同时，将提箱过程中各层可能的堆存状态作为该层的叶子节点，实现提箱操作的堆存状态作为完结节点；结构形如图2所示的树状网络图构造，并减少虚构完结节点：
图2状态结点树状网络图
（4）网络图性质：剖析可知，上述结构的堆存状态树状网络图具备以下特色：
特色0：完结状态层中，不存在待提集装箱，此时堆存状态可能为空，也可能包含非待提箱；
特色1：图中入度为0的点和出度为0的点有且仅有一个（别离为根节点和虚构完结节点）；其余节点的出度、入度均大于等于1；
特色2：虚构节点作为后续节点与所有完结节点相连，且权重均等于0；
特色3：上一层的指标箱在以后堆存状态肯定处于栈顶或已被提箱离场；
特色4：因为提箱程序有优先级要求，联合特色3，因而不存在跨层节点连贯；
特色5：因为不波及预翻箱作业，则中间层每层至多存在一个状态叶子节点，且两两状态之间不可达；
特色6：联合特色4和特色5可知，网络图为有向无环图；
至此，通过构建具备上述特色的树状网络图，可将翻箱问题转化为寻找从根节点到虚构完结节点的最短门路问题，并采纳最短门路问题算法进行准确求解。
3. 计算样例
（1）初始堆存状态Node0；
（2）结构树型网络图构造
结点信息如下：
（3）最短门路问题求解
以后最短门路反对Dijkstra's 算法（正权有向图）、Floyd算法、0-1整数布局等形式求解；此外，进一步联合特色6可知，上述构建的最短门路问题为有向无环图，因而可采纳更为高效的基于拓扑排序的疾速求解算法求解；最终失去翻箱计划如下，翻箱次数为1次；
参考文档
- da Silva Firmino A, de Abreu Silva R M, Times V C. An exact approach for the container retrieval problem to reduce crane's trajectory[C]//2016 IEEE 19th international conference on intelligent transportation systems (ITSC). IEEE, 2016: 933-938.
- https://bbs.huaweicloud.com/blogs/211445-有向无环图最短门路问题及其变种问题的疾速求解算法.
本文分享自华为云社区《集装箱港口翻箱问题的最短门路求解算法》，原文作者：CKW@10270 。
点击关注，第一工夫理解华为云陈腐技术~