基于岸桥共享策略的集装箱码头协同调度优化_宋云婷.pdf

第 28 卷 第 2 期2023 年 4 月工业工程与管理Industrial Engineering and ManagementVol.28 No.2Apr.2023基于岸桥共享策略的集装箱码头协同调度优化宋云婷（大连理工大学 经济管理学院，辽宁 大连 116024）摘要:在保证船舶按计划完成装卸作业的前提下，为了达到尽量降低港口作业成本的目的，利用集装箱岸桥可在相邻船舶之间移位作业的特点，以港口方总成本最低为目标，以船舶靠泊位置、开启岸桥与核算岸桥数量等为决策变量，构建了基于岸桥共享策略的泊位与岸桥协同调度优化模型。针对模型的特点，设计了以遗传算法为框架，在其内部嵌套靠泊位置优化模块和岸桥共享优化模块的算法进行求解。最后，以大连港集装箱码头实际作业的优化调度为案例，验证了模型和算法的有效性，表明该方法能够减少岸桥启动数量，节省港口作业成本。经与不同算法对比，显示本文设计的靠泊位置优化和岸桥共享优化模块能够提高算法的稳定性，并能够取得更好的优化结果。关键词:集装箱码头；泊位；岸桥；优化中图分类号:U 169.6 文献标识码:AContainer Terminal Collaborative Scheduling Optimization Based on Quay Sharing StrategySONG Yunting（School of Management and Economics，Dalian University of Technology，Dalian，Liaoning 116024，China）Abstract:In order to reduce the cost of port operation as much as possible under the premise of ensuring the ships to complete the loading and unloading operation as planned，an optimization model of berth and quay crane cooperative scheduling based on quay crane sharing strategy was constructed with a goal of the minimum total cost of the port side，and decision variables were berthing position of ships，numbers of opened quayside and calculated numbers of quay cranes.This model took advantages of the feature that the container quayside bridge could move between adjacent ships.According to the characteristics of the model，an algorithm based on the genetic algorithm was designed，in which the position optimization module and quay sharing optimization module were nested.Finally，the method was used to optimize the scheduling of container terminal operations in Dalian port，which verified the effectiveness of the model and algorithm.The results show that the method can reduce the number of quay crane start-up and save the port operation cost.Through the algorithm comparison，the designed algorithm has better optimization results and stability.Key words:container terminal;berth;quay;optimization文章编号：1007-5429（2023）02-0167-08DOI：10.19495/ki.1007-5429.2023.02.018收稿日期：2021-04-18基金项目：国家自然科学基金重点项目（42030409）作者简介：宋云婷（1993），黑龙江哈尔滨人，博士后，研究方向为港口生产调度优化。E-mail：。-167第 28 卷 宋云婷，等：基于岸桥共享策略的集装箱码头协同调度优化1 引言 所谓岸桥共享，是指在条件允许的情况下，将正在作业的岸桥调转至其相邻船舶继续作业，以实现岸桥共享使用的一种调度策略。岸桥是集装箱码头装卸作业最主要的装卸设备，其作业消耗是港口成本的主要构成部分。与作业繁忙的枢纽港不同，对于数量更多的一般支线港而言，集装箱作业量不饱和基本上属于常态。因此，在保证集装箱班轮在船期表规定的时间内离港的前提下如何合理调配泊位和岸桥资源以降低港口的作业成本，是港口调度组织优化的重要内容。利用作业过程中岸桥可在相邻船舶间移动的特点，将其与集装箱班轮靠泊位置进行协同调度1，寻找最大限度地降低港口作业成本的优化方法，对于港口生产的科学管理具有重要的现实意义。集装箱港口的生产调度优化一直是学者关注的重要问题，现有的研究多以船舶在港时间最短2-3、码头生产成本最低4、港口和船方的综合成本最低5为优化目标，将泊位、岸桥和场桥等装卸作业设施进行综合考虑，建立集成调度优化模型6。在涉及港口特定环境方面，通常考虑港区碳排放总量7、泊位疏浚8、潮汐影响9等因素，以港口平均等待时长及船舶离港延误最小为目标，建立优化模型。分析发现，上述研究多以船舶在港口作业时间最短或港口成本最低为目标，缺乏对船舶按计划离港的需求进行综合考量。实际上，对于集装箱港口而言，保证船舶按照其与船公司的约定时间完成装卸作业是基本要求，在此前提基础上寻找岸桥调度新策略、优化岸桥开工数量，并综合协调靠泊位置进行协同调度优化，才能反映港口的根本需求。在求解方法方面，已有研究采用线性优化软件8进行求解，当考虑到泊位及岸桥的协同调度或其他复杂因素时，需要采用如粒子群算法9、蚁群算法10及遗传算法11等优化算法进行求解。其中，遗传算法的应用较为广泛，但是当模型中加入岸桥共享策略时，已有算法并不能实现模型的求解，需要在现有方法基础上进行改进。综上，本文提出了新的优化思路，其主要的创新点及贡献是：（1）考虑集装箱港口常态化运行下装卸作业基本需求、船舶柔性靠泊特点及作业过程中岸桥可在相邻船舶间移动的特性，在保证船舶规定时间内离港的前提下，以港口作业成本最低为目标，建立了基于岸桥共享策略的集装箱码头协同调度优化模型。（2）针对模型中柔性泊位划分与共享岸桥间协同调度问题的复杂性，在遗传算法内嵌套靠泊位置优化模块和岸桥共享优化模块实现算法的优化设计。2 模型构建 2.1问题描述在制定生产作业方案时，确定启动作业岸桥的数量是其主要内容。不论来港作业的集装箱船舶载箱量多少，如果都采取将泊位上配备的所有岸桥全部启动，虽然可以很快完成装卸作业，但按班轮方式运行的集装箱船舶并不需要立即离港。这样，对于大多数载箱量较少的船舶而言，短时间内快速完成装卸实际意义并不大，而只要求在计划离港前完成装卸即可。因此，如何既保证集装箱船舶按时离港，又尽量减少岸桥启动数量，降低港口作业成本，是港口关心的问题。为简化优化模型而又符合现场作业实际情况，可进行如下假设：（1）岸桥间不能跨越移动；（2）岸桥的移动时间可忽略不计；（3）码头的水深条件均能满足船舶靠泊的安全需求。2.2参数及变量（1）参数V：到港船舶的总数量v：到港船舶编号LB：泊位岸线长度（米）Lv：船舶v的船长（米）Nqua：港口可使用的岸桥总数Nquav：为船舶 v提供装卸作业服务的岸桥最大数量Cqua：每组装卸设备的单位运行成本（元），其中每组装卸设备包含一个岸桥以及相匹配的场桥与集卡Chan：每组装卸设备的启动成本（元）-168第 2期工 业 工 程 与 管 理LS：两艘停靠在泊位岸线上的紧邻船舶之间最小安全距离的一半（米）Qv：船舶v在港装卸集装箱数量q：每组装卸设备的装卸效率（TEU/h）twaiv：船舶v到港后由于无合适的空闲泊位而产生的待泊时间，如果没有等待直接靠泊则twaiv=0tarrv：船舶v的靠泊时刻tserv：船舶v的在港停留总时间（h）tmaxv：船舶v的最长在港停留时间限制tendv：船舶v的作业完成时刻，tendv=tarrv+tserv（2）决策变量xhvt：0-1变量，若岸桥h在时刻t分配至船舶v，xhvt=1，否则xhvt=0 x*hv：为0-1变量，若xhvtarrv=1且岸桥h为新启动的岸桥，x*hv=1，否则x*hv=0nv：船舶v在港接受装卸服务时配备的核算岸桥数量。当不存在为船舶v提供装卸服务的岸桥在作业过程中移至其他船舶时，nv=h=1Hxhvt，t tarrv，tendv；反之，nv需要根据作业岸桥数量与时间的变化重新核算yv：船舶v的船头在岸线的位置（米）zuv：0-1 变量，若船舶 u 停靠在船舶 v 的左侧，zuv=1，否则zuv=0zuv：0-1 变量，若船舶 u 的离泊时间早于船舶 v的靠泊时间（tendutarrv），zuv=1，否则zuv=02.3模型建立本文在保证船舶按时离港的前提下，以港方总成本最低为目标，建立基于岸桥共享策略的集装箱码头协同调度优化模型如下：minC=v=1Vh=1HChanx*hv+v=1VCquanvtserv（1）s.t.v=1Vh=1HxhvtNqua，t 0，T（2）v=1Vxhvt1，t 0，T，h1，H（3）1h=1HxhvtNquav，t tarrv，tendv，v1，V（4）h=1Hxhvt-h=1Hxhvt*1，t，t*tarrv，tendv，tNqua0，其他（16）适应度函数值越大表明该个体的适应性越好。因此在目标函数的基础上，考虑对最大作业岸桥数量限制的违背程度，以式（17）作为个体的适应度函数，该值越大表明该个体的适应度值越大，也就越容易被选择成为父代染色体。minZ=C+Ccon（17）遗传操作中采用轮盘赌选择算子优选个体。结合染色体划分的特点，交叉操作采用选择父代对应染色体直接交换的方式，即在两个父代的G条染色体中随机产生一个交叉点，将两个父代个体中交叉点处的染色体进行交换，其他染色体保持不变。交叉操作如图2所示。变异操作分为两个步骤分别进行。第一个步骤是针对第一段基因的变异，在满足变异概率的情况下，从G条染色体中随机选择一条，并从该条染图1个体编码示意图-170第 2期工 业 工 程 与 管 理色体的第一段基因中随机选择两个位置进行交换，第二段基因中对应位置也进行交换，如图 3所示。第二个步骤是针对第二段基因的变异，在满足变异概率的情况下，从G条染色体中随机选择一条，并从该条染色体的第二段基因中随机选择一个位置，在满足约束式（4）与式（8）的情况下随机改变其值，如图4所示。3.3算法设计为降低船舶的待泊时间与港口的运行成本，根据集装箱船舶靠离泊过程，设计了靠泊位置优化模块以及岸桥共享优化模块。（1）靠泊位置优化模块（position optimization module，PO）对于组内的靠泊船舶，若按照集中分布或均匀分布的方式在岸线上安排靠泊，可能存在船舶到港后待泊时间较长的情况。对此本文设计了靠泊位置优化模块，首先将船舶均匀分布于岸线，通过判断船舶的等待时间和可能调整的位置区间，对船舶的停靠位置进行依次调整，其具体求解步骤如下。Step 1.1 输入第(g-1)组船舶占用岸线情况，包括船头所在位置yv，g-1(v1，Vg-1)以及离泊时间tendv，g-1(v1，Vg-1)，输入当前g组船舶的信息，包括船舶数量Vg、靠泊序列Xg、船长Lvg、到港时间tarrvg等。Step 1.2 依据当前g组船舶的靠泊序列，按照均匀分布的方式将靠泊船舶安排在岸线上，每条船前后均保留安全距离LS。第一艘船的船头从岸线起始位置开始停靠，即y1g=LS，最后一艘船刚好停靠在岸线结束位置，即yVgg=LB-LS-LVgg。相邻两船之间的距离除2LS外，另外增加 LB-v=1Vg(Lvg+2LS)/(Vg-1)的距离，以保证g组船舶均匀分布在岸线上，且满足约束式（10）式（12），记录当前g组船舶的靠泊位置yvg。Step 1.3 根据(g-1)组船舶占用岸线情况以及g组船舶靠泊位置yvg，计算g组船舶的靠泊时间tarrvg与待泊时间twaivg，令v1。Step 1.4 判断twaivg0，若是，转Step 1.5；否则转Step 1.9。Step 1.5 计算船舶 v允许沿岸线调整的范围y*vg yv-1，g+Lv-1，g+2LS，yv+1，g-Lvg-2LS。当v=1时，y*1g LS，y2g-L1g-2LS；当v=Vg时，y*Vgg yVg-1，g+LVg-1，g+2LS，LB-LVgg-LS。调整方法为以yvg为中心在该范围内以单位距离依次移动船舶，令y*vgyvg+1(-1)。Step 1.6 计算船舶v靠泊位置为y*vg时的待泊时间twai*vg。若twai*vgVg，转Step 1.10；否则转Step 1.4。Step 1.10 输出g组船舶靠泊位置yvg、靠泊时间tarrvg与待泊时间twaivg，结束。上述求解流程能够保证优化结果满足约束式（10）式（13）。（2）岸桥共享优化模块（quay optimization module，QO）为了实现岸桥共享调配，本文设计了岸桥共享优化模块，根据染色体生成的初始岸桥调配方案和调整后的靠泊位置，分析满足约束的可调整岸桥方图2个体交叉操作示意图图3个体第一段基因变异操作示意图图4个体第二段基因变异操作示意图-171第 28 卷 宋云婷，等：基于岸桥共享策略的集装箱码头协同调度优化案，并反馈至靠泊位置优化模块，其具体求解步骤如下。Step 2.1 输入全部船舶占用岸线情况，包括船舶的靠泊时间tarru、离泊时间tendu、靠泊位置yu、船长Lu、预分配岸桥数量N*u Ng|g=1，2，G、新开岸桥数nnewu、核算岸桥数量nu（令nnewuN*u，nuN*u），其中，u1，V，标记的船舶记为空。Step 2.2 判断是否存在可将为当前船舶作业的岸桥移动至其他船舶u*(u*u)的情况。对于任意船舶u，遍历所有船舶，若船舶u*(u*u)在船舶u的紧邻上方且满足tarrutarru*tendu，令AUuu*=1，否则AUuu*=0；若船舶u*(u*u)在船舶u的紧邻下方且满足tarrutarru*0，转 Step 2.3；若否，则转Step 2.9。Step 2.9 输出tarru、tendu、yu、nnewu、nu，结束。上述求解流程中，Step 2.6保证优化结果满足约束式（8）和式（9），Step 2.2保证优化结果满足约束式（5）。3.4算法流程综合以上染色体构成、遗传操作、靠泊位置优化模块和岸桥共享优化模块的设计思想，其模型的求解流程如图5所示。4 算例分析 4.1背景及数据由大连港集装箱码头的现场作业记录，得到两天内共有20艘班轮先后到港，各班轮的船长、到港时间、装卸箱量等信息见表1。该码头岸线总长LB为1 000 m，配备岸桥数量Nqua为10台，为每艘船舶作业的岸桥数量不超过3台。根据集装箱码头的装卸工艺，装卸设备是以岸桥为核心，与场桥、集卡等编组运行，其各项作业相关的数据见表2。表1到港船舶信息序号12345678910船长(m)2619815697198110104233180162到港时间(Y-M-D hh:mm)2019-5-4 04:102019-5-4 08:202019-5-4 08:402019-5-4 11:502019-5-4 14:402019-5-4 17:002019-5-4 19:002019-5-4 19:202019-5-4 20:202019-5-5 03:00装卸箱量(TEU)761136451184695388211370548651序号11121314151617181920船长(m)1203041561361008714594114122到港时间(Y-M-D hh:mm)2019-5-5 06:502019-5-5 08:202019-5-5 11:102019-5-5 13:502019-5-5 17:202019-5-5 21:102019-5-5 21:202019-5-5 21:502019-5-5 22:102019-5-5 22:20装卸箱量(TEU)210695514394296205615225351554-172第 2期工 业 工 程 与 管 理4.2计算结果设置种群大小为50，迭代次数为100，交叉概率为0.8，变异概率为0.2，罚系数取100。通过计算机编程，得到嵌入靠泊位置优化模块和岸桥共享优化模块的遗传算法（GAPOQO算法）求解的优化结果见图6。图6表达的泊位分配及岸桥调度方案显示了各岸桥对船舶装卸作业的关系。以5#岸桥为例，其作业过程为：当船舶1靠泊时，5#岸桥作为新开岸桥调度至船舶1进行装卸作业，当船舶4靠泊时移动至船舶4继续进行装卸作业，直至作业完成；当船舶10靠泊时，5#岸桥重新作为新开岸桥调度至船舶10进行装卸作业；当船舶13靠泊时，5#岸桥移动至船舶13继续进行装卸作业；当船舶14靠泊时，5#岸桥移动至船舶14继续进行装卸作业，直至作业完成。上述过程中5#岸桥在为船舶1作业过程中移动至船舶4的调度过程即为QO模块，可以看出这一调度过程减少了为船舶4的新开岸桥数量，虽然在一定程度上适当延长了船舶1的作业时长，但并没有影响后续船舶9与船舶10的顺利靠泊。从图6所示的整个调度方案看，在20艘船舶装卸作业的岸桥调度过程中，自始至终只开动了10台岸桥中的8台作业，保留2台处于待命状态，减少了岸桥启动费用，实现了降低作业成本的目的。4.3算法对比为了说明GAPOQO的有效性以及嵌入的靠泊位置优化模块（PO模块）与岸桥共享优化模块（QO模块）的合理性，在相同遗传算法（GA算法）的基础上，通过设置是否采用以上两种模块，分4种情况进行优化计算。其中：GAPO表示在GA算法的基础上增加PO模块，而不采用QO模块；GAQO表示在GA算法的基础上增加QO模块；GA表示不采用任何模块。采用以上4种求解方法分别进行30次独立运算，其优化结果的最小值、平均值以及标准差的对比情况见表3。图5模型求解流程表2码头作业相关数据参数qtmaxvLSCquaChan单位TEU/hhm元/h元/次取值3516101 4282 000图6泊位分配及岸桥共享调度优化后方案表3四种求解方法优化结果对比求解方法最优值（万元）平均值（万元）标准差（万元）GAPOQO38.692 339.005 70.143 1GAPO40.292 340.452 30.149 7GAQO38.892 339.179 00.152 2GA40.292 340.492 30.154 9-173第 28 卷 宋云婷，等：基于岸桥共享策略的集装箱码头协同调度优化从表3中可以看出：在最小值方面，GAPOQO方法同时采用PO与QO模块求得优化解的最小值更小，其次是 GAQO方法，GAPO与 GA方法求得的最小值相同且最大；在平均值方面，GAPOQO方法求得的平均值最低，其次是GAQO与GAPO，最大的是GA。最小值与平均值的对比结果表明，QO模块通过在作业过程中移动岸桥能够在一定程度上降低成本，PO模块通过调整船舶在岸线上的位置能够降低船舶的待泊时间，对降低成本的作用不明显。在标准差方面，GAPOQO方法的标准差最小，且4种求解方法的标准差基本上处于合理且相近的层次。标准差对比结果表明GAPOQO方法具有较好的稳定性。5 结论 为解决在港口实际生产中如何在尽量降低港口作业成本的同时，又能够保证船舶按计划完成装卸作业的问题，本文利用集装箱岸桥在相邻船舶之间移位作业的特点，采取岸桥共享策略达到这一目标，构建了泊位与岸桥协同调度优化模型。针对模型的特点，设置了靠泊位置优化模块，即通过判断船舶的等待时间和可能调整的位置区间，对船舶的停靠位置进行优化调整。同时利用设置的岸桥共享优化模块，在满足约束条件下，实现各岸桥共享的调度方案，通过两个模块的数据不断交互，可得到较为优化的结果。由大连港集装箱码头实际作业调度案例的计算，验证了所提模型和算法的有效性。经不同算法对比，也显示出其算法具有更好的优化结果及稳定性。说明本文提出的优化模型及算法可为科学管理港口提供技术支撑。综上，本文设计的优化模型及算法能够有效降低港口经营成本，对港口解决实际运营问题具有重要的应用价值。但是本文在研究中假设船舶能够在确定时间到港，但实际中还会出现船舶延迟到港等情况，如何在更为复杂的情况下开展协同调度优化是下一步需要深入研究的内容。参考文献：1 TIAN Y，ZHOU Q，ZHU B F.A genetic algorithm based on spatiotemporal conflict between continuous berth-allocation and time-varying specific crane assignment J.Engineering Optimization，2019，51（3）：390-411.2 范丽先，王行苑，尹静波.基于公平原则的泊位-岸桥联合调度研究 J.工业工程与管理，2017，22（2）：60-68.3 张思，吕梦晴，代剑环，等.基于不确定性操作时间的岸桥调度优化研究 J.工业工程与管理，2020，25（5）：50-58.4 郑红星，张敬涛，刘保利.考虑潮汐影响的连续泊位和岸桥集成调度 J.计算机集成制造系统，2018，24（10）：2599-2611.5 CORRECHER J F，ALVAREZ-VALDES R.A biased random-key genetic algorithm for the time-invariant Berth allocation and quay crane assignment problemJ.Expert Systems with Applications，2017，89：112-128.6 KASM O，DIABAT A，CHENG T.The integrated berth allocation，quay crane assignment and scheduling problem：Mathematical formulations and a case studyJ.Annals of Operations Research，2020，291：435-461.7 WANG T，LI M，HU H.Berth allocation and quay crane-yard truck assignment considering carbon emissions in port area J.International Journal of Shipping and Transport Logistics，2019，11（2）：216-242.8 焦小刚，郑斐峰，徐寅峰，等.考虑泊位疏浚的连续型泊位和动态岸桥联合调度 J.运筹与管理，2020，29（2）：47-57.9 MALEKAHMADI A，ALINAGHIAN M，HEJAZI S R，et al.Integrated continuous berth allocation and quay crane assignment and scheduling problem with time-dependent physical constraints in container terminals J.Computers&Industrial Engineering，2020，147：106672.10 敖丹，杨勇生.基于作业链的泊位与岸桥协同调度研究 J.计算机工程与应用，2022，58（7）：286-294.11 杨劼，高红，刘巍.离散泊位布局下的泊位岸桥动态协调调度 J.计算机工程与应用，2018，54（3）：265-270.12 宋云婷，王诺.基于时间不确定的集装箱码头靠泊计划优化 J.交通运输系统工程与信息，2020，20（4）：224-230.-174