不确定环境下集装箱码头泊位与岸桥联合调度梁承姬;吴宇【摘要】在集装箱码头操作系统中,有效的泊位岸桥调度计划有助于提高码头的运营效率和客户满意度.针对船舶到港时间和装卸作业时间随机的泊位岸桥联合调度问题,综合考虑了连续泊位下船舶偏离偏好泊位产生的惩罚时间,并通过添加延缓时间的方法来吸收不确定性因素带来的影响.为了体现调度计划的鲁棒性,将延缓时间添加在目标函数中,建立了以船舶在港总时间、偏离偏好泊位的惩罚时间、客户满意度和延缓时间之和最小化为目标的混合整数规划模型,提出一种自改变遗传算法和启发式靠泊相结合的改进遗传算法对模型进行求解;通过算例分析,证明了提出的改进遗传算法在计算不确定环境下的泊位岸桥联合调度问题的有效性.%In the container terminal operating systems, effectively berth quay scheduling is helpful to improve operational efficiency and customer satisfaction. For the simultaneous berth and quay crane scheduling problem with stochastic ves-sels arrival and working time, it considers the penalty time caused by the ship departure from the berth, and puts forward a method by adding a delay time to absorb the impact of uncertainty factors. In order to reflect the robustness of scheduling plan, this paper adds delay time in the objective function, and sets up a mixed integer programming model with the goal of minimizing the sum of the total time of vessels in port, the penalty time caused by the ship departure from the berth, cus-tomer satisfaction and delay time, and puts forward a improved Genetic Algorithm(GA)combined with since change GA and heuristic berthing to solve the model. By the analysis of examples, it is proved that theimproved GA is effective in calculating the simultaneous berth and quay crane scheduling problem under stochastic environment.【期刊名称】《计算机工程与应用》【年(卷),期】2017(053)007【总页数】8页(P212-219)【关键词】连续泊位;随机;延缓时间;启发式靠泊;改进遗传算法【作者】梁承姬;吴宇【作者单位】上海海事大学科学研究院物流研究中心,上海 201306;上海海事大学科学研究院物流研究中心,上海 201306【正文语种】中文【中图分类】TP301.6泊位和岸桥是集装箱码头岸边两类重要资源，随着经济的快速发展，港口物流也迅猛发展起来，港口的吞吐量越来越大，从而使得港口的岸边资源也越来越紧张。

因此合理安排两类资源，有效的泊位以及岸桥调度计划能够提高港口的作业效率和服务水平，增加客户的满意度，降低港口的运营成本，提高竞争力。

对于泊位、岸桥联合调度问题的研究主要是在确定性条件下展开的。

针对动态连续泊位岸桥集成调度问题，Mesisel等建立了以最小化船舶总服务成本为目标的模型，采用启发式算法进行求解，同时考虑了岸桥边际生产率逐渐减少和操作时间变化等因素[1]。

Mohammad针对泊位分配和岸桥配置问题，提出了集成的启发式算法来求解[2]。

杨春霞等建立了船舶在港时间和码头生产成本最小化为目标函数的泊位-岸桥分配问题的优化模型，应用一种多目标遗传算法和启发式算法来求解该模型，并将计算结果与单目标优化相比，得出提出的优化方法能够获得使码头综合效益较大的满意解[3]。

姬晓涛，等针对泊位岸桥集成调度问题，建立了以码头运营成本和客户满意度指标为目标的多目标混合整数非线性模型，采用多目标遗传算法进行求解[4]。

杜卫华等在考虑岸桥移动约束限制的基础上，建立了泊位岸桥集成调度的混合整数规划模型，以船舶的延误成本和岸桥的移动成本最小为求解目标，通过Cplex软件对模型进行求解[5]。

房鹏针对泊位岸桥协调调度问题，采用遗传算法对模型进行求解，并通过预测船舶到港数计算出码头应配置的岸桥数[6]。

乐美龙等针对泊位偏好和岸桥干扰的泊位和岸桥分配问题，建立了混合整数线性规划模型，通过Gurobi软件和两阶段启发式算法对模型进行求解[7]。

韩笑乐等针对拥有不同服务优先级的动态到港船舶的离散泊位调度问题，采用了启发式算法，禁忌深度搜索和模拟退火算法相结合的混合算法对问题进行了求解[8]。

郑红星等针对单船岸桥分配和调度问题，考虑了岸桥间干扰等待时间和作业量均衡，建立了最小化船舶在泊作业时间为目标的数学模型，设计了改进蚁群算法对模型进行求解[9]。

针对不确定条件下的泊位、岸桥相关问题的研究，Han等考虑船舶到港时间的不确定性，建立了离散型的泊位岸桥集成调度模型，运用遗传算法和抽样仿真的方法得到鲁棒性的泊位岸桥调度计划[10]。

Zhen等针对动态的、连续的不确定性条件下的泊位调度问题，建立了双层模型，以及前摄调度方案和反馈调度方案，采用启发式算法进行求解[11]。

桂小娅在考虑船舶到港时间不确定性的情况下，研究了动态、连续的泊位岸桥集成调度问题，建立了在确定性条件下的初始调度计划模型和在不确定性条件下的基础调度模型，设计了双层循环迭代算法进行求解，最后通过仿真实验证明了算法的有效性[12]。

孙彬等针对不确定性因素的情况，设计了一种基于鲁棒式的泊位岸桥联合调度方法，主要研究在不确定性的条件下怎样通过联合实时调度提高系统的鲁棒性[13]。

谢鑫等考虑船舶的抵港时间和装卸时间的不确定研究了离散泊位的分配问题，采用Cplex软件对问题进行求解[14]。

王冬越等考虑船舶到港时间的不确定性，建立了最小化在港总时间和港口装卸成本的泊位-岸桥分配多目标数学模型，采用优化技术处理该问题[15]。

综上所述，确定性条件下的泊位、岸桥联合调度问题研究得比较多，但在连续泊位下大多数只考虑了船舶偏离偏好泊位增加的成本，而忽略了偏离偏好泊位而增加的时间。

不确定性条件下的泊位岸桥联合调度的研究大多数都只考虑了船舶到港时间的不确定性，而忽略了船舶装卸时间的不确定性。

在泊位、岸桥联合调度问题的求解方法上，大多数采用的是Gurobi、Cplex或者是传统的启发式算法、遗传算法等来进行求解，这些求解方法不仅计算时间比较长，而且容易陷入局部最优解，使得求解的结果不理想。

对于一些比较复杂的问题，单纯的使用求解器或者传统的智能算法可能得不到满意的求解结果。

为了更加符合港口的实际运营，本文同时考虑船舶到港时间和装卸作业时间的不确定性对泊位、岸桥联合调度问题进行了研究，不仅考虑了船舶在港总时间还考虑了客户满意度和船舶偏离偏好泊位而产生的惩罚时间，同时为了避免在计算过程中早熟现象的发生，缩小算法的搜索区域，减少算法的计算时间，使计算结果更加精确，得到全局最优解；本文设计自改变遗传算法和启发式靠泊相结合的改进遗传算法对模型进行求解，并和标准遗传算法相比，得出本文的改进遗传算法得到的结果将更优。

泊位岸桥联合调度问题，研究中主要分离散泊位和连续泊位，而在实际的码头中，泊位都是连续的，码头岸线没有明确泊位界限，在满足物理约束条件下，船舶可以在任意泊位靠泊。

在船舶靠泊后，码头会安排相应的岸桥对船舶进行装卸作业，同时也会安排对应的集卡进行运输作业，因为堆场箱区有分类，为了使集卡的作业路径最短，所以每艘船都会有一个偏好停泊的位置，而当该船偏离了自己的偏好泊位后，不仅会使作业成本增加，而且还会延迟作业时间。

对于每艘船都会有一个期望离港时间，如果码头安排的作业不是很合理，则会导致船舶无法在期望离港时间内离港，那么就会影响船公司对码头的满意程度，从而影响码头的未来发展。

在岸桥分配上，由于船公司的相关要求和码头的实际作业安排，每艘船都有一个最多和最少所需岸桥数目，船舶在作业过程中分配的岸桥数不能改变，且船舶只有等到所有的岸桥都作业完毕之后才能离港，下一艘船舶只能等到上一艘船舶离开后才能停靠该泊位。

在泊位岸桥联合调度问题中，主要的不确定性因素是船舶到港时间的不确定和装卸作业时间的不确定，两个不确定性因素的发生都会对船舶的调度计划产生很大的影响。

在实际港口运行中，不确定性因素是经常存在的，因此不确定条件下的调度计划更符合码头实际。

这里考虑的泊位是连续泊位，相比于离散泊位能够能有效的利用泊位资源，更贴近实际。

每艘船舶都有一个偏好泊位，引入单位距离时间惩罚因子，如果偏离偏好泊位则会产生相应的惩罚时间。

同时以船舶的期望离港时间和实际离港时间差来表示客户的满意度，差值越大表示船越早离港，客户满意度越高。

在不确定性因素上，假设船舶的实际到港时间是一个服从以计划到港时间为均值的均匀分布，即ΔBi 为船舶到港时间的变动范围。

同时船舶的装卸时间Ci也是一个服从岸桥平均作业时间为均值的均匀分布。

为了使调度计划的鲁棒性更强，减少不确定性因素发生时对调度计划的影响，提出了一种添加延缓时间的方法来吸收不确定性因素带来的影响，规定在延缓时间内该泊位和岸桥等相关资源仍然假设被该船占用。

延缓时间的最大值根据船舶到港时间的变动范围来确定，即δmax=2μ，μ为船舶到港时间的标准差，可由船舶到港的变动范围ΔBi求得。

δ分正负两种情况，δ＞0表示船舶延迟到港，即船舶的实际到港时间在范围内，则给船舶添加的延缓时间为正数；δ＜0表示船舶提前到港，即船舶的实际到港时间在范围内，则添加的延缓时间为负数。

如果延缓时间添加的足够大，那么能够吸收的不确定性也就比较大，计划的鲁棒性就更强。

调度计划的鲁棒性可以用延缓时间的大小来体现，因此在目标函数中加入了最大化延缓时间这一目标，并引入目标函数权重系数来平衡目标函数值中的权重大小。