论文部分内容阅读
摘要：为提高煤炭出口码头作业效率和服务水平，对装船作业调度进行优化。在考虑装船机联机作业的前提下，以最小化煤炭出口码头作业线运行能耗成本和船舶在港时间成本为目标，综合考虑作业流程约束和泊位、垛位和作业线的作业唯一性约束，建立混合整数规划模型，并设计基于仿真解码方案的遗传算法求解。用实例验证模型的可行性和算法的有效性。结果表明，研究成果可为具有工艺流程复杂、装船机联机作业等特点的煤炭出口码头装船作业调度问题提供较好的解决方案。
关键词：
煤炭出口码头; 装船作业; 作业线调度; 联机作业; 遗传算法
中图分类号： U691+.3
文献标志码： A
收稿日期： 2020-08-04
修回日期： 2021-01-06
基金项目：
国家重点研发计划（2020YFE0201200）
作者简介：
冯鹏（1996—），男，山西晋城人，硕士研究生，研究方向为港口规划与港口物流，（E-mail）[email protected];
郭子坚（1965—），男，辽宁沈阳人，教授，博士，研究方向为港口规划与港口物流，（E-mail）[email protected]
Scheduling optimization of loading operation in coal export
terminals considering union operation of ship loaders
FENG Peng， GUO Zijian， JIANG Ying， CAO Zhen， XU Xinglu
（
State Key Laboratory of Coastal and Offshore Engineering， Dalian University of Technology， Dalian 116024， Liaoning， China）
Abstract：
In order to improve the efficiency and service level of coal export terminals， the loading operation scheduling is optimized. A mixed integer programming model is established with considering union operation of ship loaders. The model objective is to minimize the energy consumption cost of the operation lines of coal export terminals and the time cost of ships berthing at terminals. The model constraints are the operation process constraint and the uniqueness constraints of berths， stock positions and operation lines. A genetic algorithm based on the simulation decoding scheme is designed to solve the model. The feasibility of the model and the validity of the algorithm are verified by a case. The results indicate that the research results can provide a better solution to the scheduling problem of loading operation in coal export terminals with the features of complex technological process and union operation of ship loaders.
Key words：
coal export terminal; loading operation; operation line scheduling; union operation; genetic algorithm
0 引 言
煤炭在我國的能源结构中占有重要地位。由于煤炭供需关系在地域分布上的差异，我国煤炭存在大规模的“西煤东调”“北煤南运”现象。港口作为煤炭运输链的枢纽，其服务水平的提升是保障我国煤炭运输体系高效、流畅的关键。随着煤炭运输需求逐年攀升，煤炭出口码头的通过能力和服务水平亟待提高。然而，由于城市的不断发展和扩张，港口的发展空间大大减小，促使港口由新建、扩建码头的粗放式发展模式，向发展“智慧港口”的方向转变。
煤炭出口码头装船工艺流程具有较强的专业性和特殊性，主要包括利用取料线上的取料机将煤炭从相应垛位取出，经前端横向连接线运往相应装船线，并由与之相连的装船机完成装船。为提高作业效率，码头配置移动式装船机，在条件允许的情况下可为相邻泊位装船，既可单机作业，也可联机作业[1]。因此，在制订装船线调度方案时，不仅要考虑联机作业的高效性和灵活性，而且要尽可能降低装船机移泊作业对其原本对应泊位装船作业的影响。由于船舶需求量与码头垛位堆存量的差异，一艘船往往需要从多个垛位取煤。另外，为满足配煤需求，取料线和取料机配置形式一般为“一线双机”，布置在同一取料线上的两台取料机可在堆存不同煤种的两个垛位按比例取煤，并在取料线上混合后进行装船。 在堆场作业调度方面：钱国栋[2]通过建立煤炭码头堆场作业优化模型，提出堆场管理优化措施;王翼展等[3]以极小化作业完成时间为目标，在堆取料机可在工作區任意位置结束工作的条件下，给出多项式时间最优算法;VAN VIANEN等[4]以减少列车等待时间、提升码头作业效率为目标，对堆取料机调度进行了仿真研究;HU等[5]针对堆取料机调度问题，以完成时间最短为目标，建立混合整数规划模型，并设计了遗传算法进行求解;KALINOWSKI等[6]将取料机调度问题表示为混合整数规划问题，并设计了常数因子近似算法和分支定界精确算法进行求解。在装船、卸车作业调度方面：宓为建等[7]针对煤炭码头装船调度问题，建立泊位与机械联合调度模型，并设计了多目标遗传算法进行求解;邰世文等[8]针对煤炭码头卸车调度问题，以卸车效率最大和列车在港时间最短为目标，提出多目标优化模型，并设计了遗传算法进行求解;DE PAULA等[9]针对煤炭出口码头综合调度问题提出并行遗传算法，以提高码头通过能力;MENEZES等[10]针对散货出口码头调度问题，考虑皮带机路径限制，提出使用分支定价算法求解的数学规划模型;BURDETT等[11]将煤炭出口码头综合调度问题转化为柔性车间调度问题，并使用元启发式算法求解;UNSAL等[12]考虑了散货出口码头的泊位、取料机和堆场调度问题，提出改进的Benders分解算法求解规划模型;PRATAP等[13]针对散货进口码头堆场作业和列车调度优化问题，通过建立混合整数线性规划模型，采用两种启发式算法进行求解。已有研究对煤炭码头工艺流程的约束不够充分，导致与实际生产作业情况存在偏差，特别是对配置移动式装船机，可在相邻泊位联机作业的多泊位连续布置煤炭码头，仍缺少优化调度的解决方案。
本文结合煤炭出口码头装船作业实际情况，在考虑装船机联机作业的前提下，通过建立以最小化煤炭出口码头作业线运行能耗成本和船舶在港时间成本为目标的混合整数规划模型，设计基于仿真解码方案的遗传算法，对该调度问题进行优化研究。模型和求解方法可为具有工艺流程复杂、装船机联机作业等特点的煤炭出口码头制订合理、高效的装船作业调度方案提供决策依据。
1 模型构建
1.1 问题描述
煤炭出口码头是专业化程度极高的大宗散货码头。由于码头单船作业量较大，而堆场垛位容量有限，通常需从多个垛位取料才能满足船舶需求。同时，码头还需保证煤炭种类或发热量等主要性质符合船舶需求。由于堆场堆存煤种通常难以完全满足船舶的多样需求，所以许多大型煤炭出口码头发展配煤工艺来实现煤炭供求的灵活匹配。配煤是指装船过程中，将从同一取料线两侧按一定比例取两种煤在取料线上混合，达到需求后将煤经连接线和装船线装入船舱的过程。若某垛位的堆存煤种与船舶需求煤种相同或性质相近，则无需配煤就可取料装船，这种作业模式称为单装。在现代大型煤炭出口码头的装船作业中，配煤和单装作业均占相当大的比重，但无论何种作业模式，均占用一组作业线（取料线、连接线、装船线各一条）连续完成。为便于描述和建模，定义从一个垛位取料（配煤时两个垛位），经一组作业线连续装载至一艘船的过程，为该船的一项装船任务。
船舶到港后，依据其靠泊优先级在相应泊位依次靠泊，完成辅助作业后针对各项装船任务依据作业优先级在指定作业线上依次进行取料装船作业，待船舶完成其全部装船任务后，解缆离泊。受码头工艺流程限制，各作业线在任意时刻仅能服务一项装船任务，各项装船任务需按照一定次序先后作业，且不同装船任务切换时还需考虑装船机移泊时间和不可跨越等约束，调度难度较大。因此，本文为规划期内的到港船舶指定靠泊优先级和靠离泊时刻，并为其装船任务指定作业线、作业优先级和开始时刻，使得煤炭出口码头作业线运行能耗成本和船舶在港时间成本最低。
为方便建模和求解，假设：①船舶到港时刻（到达港池而非锚地的时刻）和靠泊泊位均已知;②船舶在港时间从船舶到港算起，到解缆离泊为止;③装船任务的取料垛位、取料量和作业时间均已知;④同一装船任务的作业过程不可中断;⑤不考虑码头设备故障等因素。
1.2 符号说明
（1）集合和下标。
I和J分别表示到港船舶和装船任务集合，i∈I，j∈J;T为时刻集合，t∈T;K和P分别表示泊位和垛位集合，k∈K，p∈P;取料线、连接线、装船线集合分别用U、V、W表示，u∈U，v∈V，w∈W。
（2）参数。Au、Av、Aw分别为取料线u、连接线v、装船线w的单次启动能耗成本;Eu、Ev、Ew分别为取料线u、连接线v、装船线w运输煤炭的单位能耗成本;Ei为船i在港时间单位成本;tarri为船i到港时刻;τtri、τauxi、τuni分别为船i回旋、辅助作业和解缆时间;dj、τtaj分别为任务j装船量和作业时间;πk，k′为装船机从泊位k移动到泊位k′的时间;M为充分大的正实数。βi，k、θi，j、δj，k、γj，p、αw，k、αu，v，w、αp，p′，u均为0-1变量：若船i在泊位k靠泊，则βi，k=1，否则βi，k=0;若任务j属于船i，则θi，j=1，否则θi，j=0;若任务j属于泊位k，则δj，k=1，否则δj，k=0;若任务j从垛位p取料，则γj，p=1，否则γj，p=0;若装船线w可达泊位k，则αw，k=1，否则αw，k=0;若连接线v可达取料线u和装船线w，则αu，v，w=1，否则αu，v，w=0;若取料线u可达垛位p和p′，则αp，p′，u=1，否则αp，p′，u=0。
（3）变量。决策变量包括zi，i′、zj，j′、yj，u、yj，v、yj，w，均为0-1变量。若船i与i′属于同一个泊位，且前者靠泊优先级高于后者，则zi，i′=1，否则zi，i′=0。若任务j与j′占用同一垛位或作业线，且前者作业优先级高于后者，则zj，j′=1，否则zj，j′=0。若任务j分别占用取料线u、连接线v和装船线w，则yj，u，yj，v，yj，w=1，否则yj，u，yj，v，yj，w=0。其他变量中：au、av、aw分别表示取料线u、连接线v、装船线w的启动次数;tmooi、tdepi分别为船i靠、离泊时刻;tsj为任务j开始时刻;xj，t为0-1变量，若t时刻任务j正在进行，则xj，t=1，否则xj，t=0。 1.3 目标函数及其约束条件
以最小化煤炭出口码头作业线运行能耗成本（包括启动能耗成本和运输能耗成本）和船舶在港时間成本为目标，构建优化模型如下：
min F|F=
uAuau+vAvav+wAwaw+
juEuyj，u+vEvyj，v+
wEwyj，wdj+i（tdepi-tarri）Ei
（1）
s.t.
zi，i′+zi′，i=kβi，kβi′，k， i≠i′
（2）
tmooi′≥max（tarri′+τtri′，tdepi-M（1-zi，i′）），
i≠i′
（3）
tdepi=maxj（（tsj+τtaj）θi，j）+τuni
（4）
tsj+M（1-θi，j）≥tmooi+τauxi
（5）
zj，j′+zj′，j=maxp，u，v，w（（γj，pγj′，p），（yj，uyj′，u），
（yj，vyj′，v），（yj，wyj′，w））， j≠j′
（6）
tsj′≥tsj+τtaj-M（1-zj，j′）+wyj，wyj′，w·
kk′δj，kδj′，k′πk，k′， j≠j′
（7）
t+M（1-xj，t）≥tsj
（8）
t-M（1-xj，t）<tsj+τtaj
（9）
txj，t=τtaj
（10）
uyj，uvyj，vwyj，w=1
（11）
yj，u≤pp′<pγj，pγj，p′αp，p′，u
（12）
yj，v≤uwyj，uyj，wαu，v，w
（13）
yj，w≤kδj，kαw，k
（14）
jkxj，tyj，wδj，kk≤j
kxj，tyj，w′δj，kk+
M1-
jxj，tyj，w′， w<w′
（15）
w-w′≤1-jxj，tyj，wθi，j·
jxj，tyj，w′θi，jM+1， w≠w′
（16）
式（1）为目标函数，其中：启动能耗成本由各作业线启动次数和单次启动能耗成本计算，表达式为
uAuau+vAvav+wAwaw;运输能耗成本由各作业线煤炭运输量和单位能耗成本计算，表达式为juEuyj，u+vEvyj，v+wEwyj，wdj;船舶在港时间成本由其在港时间和单位时间成本计算，表达式为itdepi-tarriEi。
约束条件中：式（2）对同一泊位船舶的靠泊优先级进行约束;式（3）表示船舶在到港并回旋，且相应泊位的前船离泊后才可靠泊;式（4）表示船舶在完成其所有装船任务后方可解缆离泊;式（5）表示在船舶靠泊并完成辅助作业前，不可开始装船作业;式（6）对占用同一资源的两项任务进行作业优先级约束;式（7）表示若两项任务占用同一资源，则优先级较低者应在优先级较高者完成作业后开始作业，且若二者占用同一装船线，则还需考虑装船机移泊时间;式（8）～（10）保证同一装船任务作业过程不可中断;式（11）表示一项装船任务需且仅需占用取
料线、连接线和装船线各一条;式（12）～（14）对任务占用资源的可达性关系进行约束;式（15）保证装船机不进行交叉作业;式（16）表示仅相邻两台装船机可联机作业。
2 遗传算法设计
煤炭出口码头装船调度问题具有复杂、随机、多约束等特点，是典型的NP难问题。遗传算法具有全局搜索的特征，且搜索速度较快[14]，在求解此类问题上具有独特的优势。当前遗传算法已广泛应用于调度问题的求解，且取得了较好的实际效果。
2.1 染色体编码
本研究的决策变量包括到港船舶靠泊优先级，装船任务作业优先级，以及占用作业线等。染色体由5个序列构成，见表1。
表1中：MoorOrder为船舶靠泊优先级序列，bi表示船i在相应泊位上的靠泊优先级（bi值越小，船i的靠泊优先级越高）;TaskOrder为装船任务作业优先级序列，cj表示任务j的作业优先级（cj值越小，任务j在相应作业线上的优先级越高）;BeltBQ、BeltBC、BeltBM分别表示装船任务占用的取料线、连接线、装船线序列，ej、fj、gj分别表示任务j占用的取料线、连接线、装船线。
2.2 初始化种群及染色体解码
初始种群的生成规则如下：
（1）MoorOrder序列。依据船舶靠泊泊位随机生成。
（2）TaskOrder序列。对同一泊位，靠泊优先级较高的船舶，其装船任务作业优先级也较高。据此原则，生成装船任务作业优先级序列的步骤如下：① 随机生成作业优先级;②对靠泊同一泊位的两艘船，若靠泊优先级较高者的装船任务作业优先级编号最大值，大于靠泊优先级较低者的装船任务作业优先级编号最小值，则交换两项任务的作业优先级编号;③重复步骤②，直至满足原则为止。
（3）BeltBQ、BeltBM序列：在可达该装船任务所占垛位和泊位的取料线和装船线中随机选择。
（4）BeltBC序列：在可达所选取料线和装船线的连接线中随机选择。
本文使用遗传算法生成调度方案，仿真得到码头在各调度方案下的运行结果，统计各作业线启动次数、作业量和各船舶在港时间等指标，求得目标函数值，并将其倒数作为适应度函数。 2.3 遗传算子
使用轮盘赌和保优策略进行选择。针对染色体序列特点，设计以下3种交叉策略。
（1） 整体单点交叉，见图1。
此策略可能导致以下3种新染色体序列不满足约束条件的情况，需修正：
①若在MoorOrder序列中同一泊位的两艘船靠泊优先级相等，则交叉部分保留，未交叉部分以缺失的优先级编号替换。
②若在TaskOrder序列中两项装船任务作业优先级相等，则交叉部分保留，未交叉部分以缺失的优先级编号替换。
③若TaskOrder序列与MoorOrder序列矛盾，则修正原则同生成初始种群时对TaskOrder序列的修正原则。
（2）TaskOrder序列多点交叉，见图2。图2中，r1～r4为交叉点位置。此策略可能导致TaskOrder序列中两项装船任务作业优先级相等，或TaskOrder序列与MoorOrder序列矛盾的情况，修正原则同上。
（3）BeltBQ、BeltBC、BeltBM序列多点交叉，见图3。图3中，r1～r4為交叉点位置。
同时，设计3种变异策略：针对MoorOrder序列，在同一泊位中随机选择两艘船，交换其靠泊优先级;针对BeltBM序列，在可达任务相应泊位的其他装船线中随机选择一条不同的装船线;针对TaskOrder序列，随机选择两项任务，交换其作业优先级，修正原则同上。
计算时，以一定概率随机选择一种策略进行交叉或变异。
3 实例分析
以我国某煤炭出口码头为例，将利用本文提出的优化模型得到的调度方案（优化方案）与调研得到的码头实际调度方案（现行方案）进行对比分析，验证模型和算法有效性。该码头包括3个泊位、40个垛位、3条取料线、2条连接线、3条装船线，见图4。
规划期内码头到港13艘船，到港时刻见表2，现行方案见图5。以⑥号船为例：该船在第1天2：06到港，2：40靠泊于2#泊位;在完成辅助作业后，其4项装船任务（编号24、25、26、27）分别于 4：20、6：40、15：10、4：20开始作业，并分别于6：40、13：50、17：00、15：10完成;在最后一项任务（编号26）完成后，该船解缆，并于17：10离泊。
码头调度优化方案见图6。现行方案和优化方案的作业线分配情况见表3。在⑥号船作业过程中，其26、27号任务占用本泊位的装船线BM2进行装船，24、25号任务占用1#泊位的装船线BM1，因此，27与24、25号任务可同时进行，实现了装船机的联机作业，提高了码头作业效率。由于码头工艺流程限制，26和27号任务均需占用取料线BQ2，无法同时作业，优化方案为二者分配了相同的装船线，待27号任务完成后26号任务紧接着占用装船线BM2作业。与现行方案相比，优化方案中装船线BM1的启动次数减少了一次。
通过优化，码头作业线总启动次数从102次减为81次（减少20.6 %，见表4），大大简化了人员操作，改善了装船作业连续性，从而使作业效率得以提高。同时，作业线启动次数的减少也为码头节省了2 300 kW·h的电能。不过，作业线运行能耗主要与装船量有关，在装船量不变且码头设备保持现状的情况下，能耗优化空间有限。能耗优化目标可通过使用清洁能源或更新节能设备等措施实现。
另外，与现行方案相比，优化方案中船舶平均在港时间减少11.6%（3.04 h，见图7），最后一艘船离港时刻提前7 h。以作业时间相对重合的①、⑦号船为例进行分析：两船分别靠泊于1#、2#泊位，在优化方案中①号船的装船机联机作业集中在⑦号船完成辅助作业前，在⑦号船完成辅助作业后，BM2（SL2）即返回2#泊位，与BM3（SL3）联机为⑦号船作业，停靠在1#泊位的①号船则继续由BM1（SL1）单机作业。与现行方案相比，①号船联机作业时间从7.33 h减少至3.50 h，而⑦号船单机作业时间从0增加至4.17 h。这样的调度方式，使得⑦号船提前12 h离泊，从而使其后的⑧号船得以提前靠泊装船，而①号船虽延后4 h离泊，但由于其后的②号船到港较晚，所以并未对1#泊位后续船舶的装船作业造成影响。由此可以看出，通过合理的资源调配和作业优先级调整，优先保障较繁忙泊位的装船作业，能在总体上有效减少船舶在港时间，提高煤炭出口码头的服务水平。
4 结 论
通过深入分析煤炭出口码头装船作业的复杂流程和现实约束，在考虑装船机联机作业的前提下，以最小化煤炭出口码头作业线运行能耗成本和船舶在港时间成本为目标，综合考虑作业流程约束，泊位、垛位和作业线的作业唯一性约束等，建立混合整数规划模型，设计基于仿真解码方案的遗传算法，对其调度问题进行优化研究。最后，利用本文提出的调度优化模型对实例进行计算，优化方案下规划期内码头作业线总启动次数减少20.6%，船舶平均在港时间减少11.6%，最后一艘船提前7 h离港，优化效果良好。本文研究成果可为具有工艺流程复杂、装船机联机作业等特点的煤炭出口码头制订合理、高效的装船作业调度方案提供决策依据，从而进一步提升煤炭出口码头服务水平，为我国煤炭运输链的高效和流畅运行提供保障。
参考文献：
[1]岳金灿， 周运文， 郭建睿. 关于煤炭装船码头移动式装船机联机作业的探讨[J]. 港工技术， 2013， 50（1）： 13-15. DOI： 10.16403/j.cnki.ggjs2013.01.008.
[2]钱国栋. 曹妃甸港煤码头堆场作业管理及优化设计研究[D]. 秦皇岛： 燕山大学， 2015.
[3]王翼展， 张安， 陈永， 等. 煤炭码头堆取料机的调度问题[J]. 杭州电子科技大学学报（自然科学版）， 2019， 39（6）： 88-93. DOI： 10.13954/j.cnki.hdu.2019.06.016. [4]VAN VIANEN T， OTTJES J， LODEWIJKS G. Simulation-based rescheduling of the stacker-reclaimer operation[J]. Journal of Computational Science， 2015， 10： 149-154. DOI： 10.1016/j.jocs.2014.06.004.
[5]HU Dayong， YAO Zhenqiang. Stacker-reclaimer scheduling in a dry bulk terminal[J]. International Journal of Computer Integrated Manufacturing， 2012， 25（11）： 1047-1058. DOI： 10.1080/0951192X.2012.684707.
[6]KALINOWSKI T， KAPOOR R， SAVELSBERGH M W P. Scheduling reclaimers serving a stock pad at a coal terminal[J]. Journal of Scheduling， 2017， 20： 85-101. DOI： 10.1007/s10 951-016-0495-8.
[7]宓為建， 王郡娴， 张晓华， 等. 基于多目标遗传算法的煤码头泊位与机械联合调度[J]. 上海海事大学学报， 2016， 37（2）： 46-52. DOI： 10.13340/j.jsmu.2016.02.009.
[8]邰世文， 商剑平. 煤炭码头卸车调度问题多目标优化模型及算法[J]. 运筹与管理， 2018， 27（6）： 91-99. DOI： 10.12005/orms.2018.0138.
[9]DE PAULA M R， BOLAND N， ERNST A T， et al. Throughput optimisation in a coal export system with multiple terminals and shared resources[J/OL]. Computers and Industrial Engineering， 2019， 134： 37-51. DOI： 10.1016/j.cie.2019.05.021.
[10]MENEZES G C， MATEUS G R， RAVETTI M G. A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports[J]. European Journal of Operational Research， 2017， 258： 926-937. DOI： 10.1016/j.ejor.2016.08.073.
[11]BURDETT R L， CORRY P， YARLAGADDA P K D V， et al. A flexible job shop scheduling approach with operators for coal export terminals[J]. Computers and Operations Research， 2019， 104： 15-36. DOI： 10.1016/j.cor.2018.11.019.
[12]UNSAL O， OGUZ C. An exact algorithm for integrated planning of operations in dry bulk terminals[J]. Transportation Research Part E， 2019， 126： 103-121. DOI： 10.1016/j.tre.2019.03.018.
[13]PRATAP S， KUMAR B M， SAXENA D， et al. Integrated scheduling of rake and stockyard management with ship berthing： a block based evolutionary algorithm[J]. International Journal of Production Research， 2016， 54（14）： 4182-4204. DOI： 10.1080/00207543.2015.1111535.
[14]艾立红， 韩晓龙. 考虑能耗的自动化码头装卸设备协调调度[J]. 上海海事大学学报， 2018， 39（4）： 26-31. DOI： 10.13340/j.jsmu.2018.04.005.
（编辑 贾裙平）
关键词：
煤炭出口码头; 装船作业; 作业线调度; 联机作业; 遗传算法
中图分类号： U691+.3
文献标志码： A
收稿日期： 2020-08-04
修回日期： 2021-01-06
基金项目：
国家重点研发计划（2020YFE0201200）
作者简介：
冯鹏（1996—），男，山西晋城人，硕士研究生，研究方向为港口规划与港口物流，（E-mail）[email protected];
郭子坚（1965—），男，辽宁沈阳人，教授，博士，研究方向为港口规划与港口物流，（E-mail）[email protected]
Scheduling optimization of loading operation in coal export
terminals considering union operation of ship loaders
FENG Peng， GUO Zijian， JIANG Ying， CAO Zhen， XU Xinglu
（
State Key Laboratory of Coastal and Offshore Engineering， Dalian University of Technology， Dalian 116024， Liaoning， China）
Abstract：
In order to improve the efficiency and service level of coal export terminals， the loading operation scheduling is optimized. A mixed integer programming model is established with considering union operation of ship loaders. The model objective is to minimize the energy consumption cost of the operation lines of coal export terminals and the time cost of ships berthing at terminals. The model constraints are the operation process constraint and the uniqueness constraints of berths， stock positions and operation lines. A genetic algorithm based on the simulation decoding scheme is designed to solve the model. The feasibility of the model and the validity of the algorithm are verified by a case. The results indicate that the research results can provide a better solution to the scheduling problem of loading operation in coal export terminals with the features of complex technological process and union operation of ship loaders.
Key words：
coal export terminal; loading operation; operation line scheduling; union operation; genetic algorithm
0 引 言
煤炭在我國的能源结构中占有重要地位。由于煤炭供需关系在地域分布上的差异，我国煤炭存在大规模的“西煤东调”“北煤南运”现象。港口作为煤炭运输链的枢纽，其服务水平的提升是保障我国煤炭运输体系高效、流畅的关键。随着煤炭运输需求逐年攀升，煤炭出口码头的通过能力和服务水平亟待提高。然而，由于城市的不断发展和扩张，港口的发展空间大大减小，促使港口由新建、扩建码头的粗放式发展模式，向发展“智慧港口”的方向转变。
煤炭出口码头装船工艺流程具有较强的专业性和特殊性，主要包括利用取料线上的取料机将煤炭从相应垛位取出，经前端横向连接线运往相应装船线，并由与之相连的装船机完成装船。为提高作业效率，码头配置移动式装船机，在条件允许的情况下可为相邻泊位装船，既可单机作业，也可联机作业[1]。因此，在制订装船线调度方案时，不仅要考虑联机作业的高效性和灵活性，而且要尽可能降低装船机移泊作业对其原本对应泊位装船作业的影响。由于船舶需求量与码头垛位堆存量的差异，一艘船往往需要从多个垛位取煤。另外，为满足配煤需求，取料线和取料机配置形式一般为“一线双机”，布置在同一取料线上的两台取料机可在堆存不同煤种的两个垛位按比例取煤，并在取料线上混合后进行装船。 在堆场作业调度方面：钱国栋[2]通过建立煤炭码头堆场作业优化模型，提出堆场管理优化措施;王翼展等[3]以极小化作业完成时间为目标，在堆取料机可在工作區任意位置结束工作的条件下，给出多项式时间最优算法;VAN VIANEN等[4]以减少列车等待时间、提升码头作业效率为目标，对堆取料机调度进行了仿真研究;HU等[5]针对堆取料机调度问题，以完成时间最短为目标，建立混合整数规划模型，并设计了遗传算法进行求解;KALINOWSKI等[6]将取料机调度问题表示为混合整数规划问题，并设计了常数因子近似算法和分支定界精确算法进行求解。在装船、卸车作业调度方面：宓为建等[7]针对煤炭码头装船调度问题，建立泊位与机械联合调度模型，并设计了多目标遗传算法进行求解;邰世文等[8]针对煤炭码头卸车调度问题，以卸车效率最大和列车在港时间最短为目标，提出多目标优化模型，并设计了遗传算法进行求解;DE PAULA等[9]针对煤炭出口码头综合调度问题提出并行遗传算法，以提高码头通过能力;MENEZES等[10]针对散货出口码头调度问题，考虑皮带机路径限制，提出使用分支定价算法求解的数学规划模型;BURDETT等[11]将煤炭出口码头综合调度问题转化为柔性车间调度问题，并使用元启发式算法求解;UNSAL等[12]考虑了散货出口码头的泊位、取料机和堆场调度问题，提出改进的Benders分解算法求解规划模型;PRATAP等[13]针对散货进口码头堆场作业和列车调度优化问题，通过建立混合整数线性规划模型，采用两种启发式算法进行求解。已有研究对煤炭码头工艺流程的约束不够充分，导致与实际生产作业情况存在偏差，特别是对配置移动式装船机，可在相邻泊位联机作业的多泊位连续布置煤炭码头，仍缺少优化调度的解决方案。
本文结合煤炭出口码头装船作业实际情况，在考虑装船机联机作业的前提下，通过建立以最小化煤炭出口码头作业线运行能耗成本和船舶在港时间成本为目标的混合整数规划模型，设计基于仿真解码方案的遗传算法，对该调度问题进行优化研究。模型和求解方法可为具有工艺流程复杂、装船机联机作业等特点的煤炭出口码头制订合理、高效的装船作业调度方案提供决策依据。
1 模型构建
1.1 问题描述
煤炭出口码头是专业化程度极高的大宗散货码头。由于码头单船作业量较大，而堆场垛位容量有限，通常需从多个垛位取料才能满足船舶需求。同时，码头还需保证煤炭种类或发热量等主要性质符合船舶需求。由于堆场堆存煤种通常难以完全满足船舶的多样需求，所以许多大型煤炭出口码头发展配煤工艺来实现煤炭供求的灵活匹配。配煤是指装船过程中，将从同一取料线两侧按一定比例取两种煤在取料线上混合，达到需求后将煤经连接线和装船线装入船舱的过程。若某垛位的堆存煤种与船舶需求煤种相同或性质相近，则无需配煤就可取料装船，这种作业模式称为单装。在现代大型煤炭出口码头的装船作业中，配煤和单装作业均占相当大的比重，但无论何种作业模式，均占用一组作业线（取料线、连接线、装船线各一条）连续完成。为便于描述和建模，定义从一个垛位取料（配煤时两个垛位），经一组作业线连续装载至一艘船的过程，为该船的一项装船任务。
船舶到港后，依据其靠泊优先级在相应泊位依次靠泊，完成辅助作业后针对各项装船任务依据作业优先级在指定作业线上依次进行取料装船作业，待船舶完成其全部装船任务后，解缆离泊。受码头工艺流程限制，各作业线在任意时刻仅能服务一项装船任务，各项装船任务需按照一定次序先后作业，且不同装船任务切换时还需考虑装船机移泊时间和不可跨越等约束，调度难度较大。因此，本文为规划期内的到港船舶指定靠泊优先级和靠离泊时刻，并为其装船任务指定作业线、作业优先级和开始时刻，使得煤炭出口码头作业线运行能耗成本和船舶在港时间成本最低。
为方便建模和求解，假设：①船舶到港时刻（到达港池而非锚地的时刻）和靠泊泊位均已知;②船舶在港时间从船舶到港算起，到解缆离泊为止;③装船任务的取料垛位、取料量和作业时间均已知;④同一装船任务的作业过程不可中断;⑤不考虑码头设备故障等因素。
1.2 符号说明
（1）集合和下标。
I和J分别表示到港船舶和装船任务集合，i∈I，j∈J;T为时刻集合，t∈T;K和P分别表示泊位和垛位集合，k∈K，p∈P;取料线、连接线、装船线集合分别用U、V、W表示，u∈U，v∈V，w∈W。
（2）参数。Au、Av、Aw分别为取料线u、连接线v、装船线w的单次启动能耗成本;Eu、Ev、Ew分别为取料线u、连接线v、装船线w运输煤炭的单位能耗成本;Ei为船i在港时间单位成本;tarri为船i到港时刻;τtri、τauxi、τuni分别为船i回旋、辅助作业和解缆时间;dj、τtaj分别为任务j装船量和作业时间;πk，k′为装船机从泊位k移动到泊位k′的时间;M为充分大的正实数。βi，k、θi，j、δj，k、γj，p、αw，k、αu，v，w、αp，p′，u均为0-1变量：若船i在泊位k靠泊，则βi，k=1，否则βi，k=0;若任务j属于船i，则θi，j=1，否则θi，j=0;若任务j属于泊位k，则δj，k=1，否则δj，k=0;若任务j从垛位p取料，则γj，p=1，否则γj，p=0;若装船线w可达泊位k，则αw，k=1，否则αw，k=0;若连接线v可达取料线u和装船线w，则αu，v，w=1，否则αu，v，w=0;若取料线u可达垛位p和p′，则αp，p′，u=1，否则αp，p′，u=0。
（3）变量。决策变量包括zi，i′、zj，j′、yj，u、yj，v、yj，w，均为0-1变量。若船i与i′属于同一个泊位，且前者靠泊优先级高于后者，则zi，i′=1，否则zi，i′=0。若任务j与j′占用同一垛位或作业线，且前者作业优先级高于后者，则zj，j′=1，否则zj，j′=0。若任务j分别占用取料线u、连接线v和装船线w，则yj，u，yj，v，yj，w=1，否则yj，u，yj，v，yj，w=0。其他变量中：au、av、aw分别表示取料线u、连接线v、装船线w的启动次数;tmooi、tdepi分别为船i靠、离泊时刻;tsj为任务j开始时刻;xj，t为0-1变量，若t时刻任务j正在进行，则xj，t=1，否则xj，t=0。 1.3 目标函数及其约束条件
以最小化煤炭出口码头作业线运行能耗成本（包括启动能耗成本和运输能耗成本）和船舶在港时間成本为目标，构建优化模型如下：
min F|F=
uAuau+vAvav+wAwaw+
juEuyj，u+vEvyj，v+
wEwyj，wdj+i（tdepi-tarri）Ei
（1）
s.t.
zi，i′+zi′，i=kβi，kβi′，k， i≠i′
（2）
tmooi′≥max（tarri′+τtri′，tdepi-M（1-zi，i′）），
i≠i′
（3）
tdepi=maxj（（tsj+τtaj）θi，j）+τuni
（4）
tsj+M（1-θi，j）≥tmooi+τauxi
（5）
zj，j′+zj′，j=maxp，u，v，w（（γj，pγj′，p），（yj，uyj′，u），
（yj，vyj′，v），（yj，wyj′，w））， j≠j′
（6）
tsj′≥tsj+τtaj-M（1-zj，j′）+wyj，wyj′，w·
kk′δj，kδj′，k′πk，k′， j≠j′
（7）
t+M（1-xj，t）≥tsj
（8）
t-M（1-xj，t）<tsj+τtaj
（9）
txj，t=τtaj
（10）
uyj，uvyj，vwyj，w=1
（11）
yj，u≤pp′<pγj，pγj，p′αp，p′，u
（12）
yj，v≤uwyj，uyj，wαu，v，w
（13）
yj，w≤kδj，kαw，k
（14）
jkxj，tyj，wδj，kk≤j
kxj，tyj，w′δj，kk+
M1-
jxj，tyj，w′， w<w′
（15）
w-w′≤1-jxj，tyj，wθi，j·
jxj，tyj，w′θi，jM+1， w≠w′
（16）
式（1）为目标函数，其中：启动能耗成本由各作业线启动次数和单次启动能耗成本计算，表达式为
uAuau+vAvav+wAwaw;运输能耗成本由各作业线煤炭运输量和单位能耗成本计算，表达式为juEuyj，u+vEvyj，v+wEwyj，wdj;船舶在港时间成本由其在港时间和单位时间成本计算，表达式为itdepi-tarriEi。
约束条件中：式（2）对同一泊位船舶的靠泊优先级进行约束;式（3）表示船舶在到港并回旋，且相应泊位的前船离泊后才可靠泊;式（4）表示船舶在完成其所有装船任务后方可解缆离泊;式（5）表示在船舶靠泊并完成辅助作业前，不可开始装船作业;式（6）对占用同一资源的两项任务进行作业优先级约束;式（7）表示若两项任务占用同一资源，则优先级较低者应在优先级较高者完成作业后开始作业，且若二者占用同一装船线，则还需考虑装船机移泊时间;式（8）～（10）保证同一装船任务作业过程不可中断;式（11）表示一项装船任务需且仅需占用取
料线、连接线和装船线各一条;式（12）～（14）对任务占用资源的可达性关系进行约束;式（15）保证装船机不进行交叉作业;式（16）表示仅相邻两台装船机可联机作业。
2 遗传算法设计
煤炭出口码头装船调度问题具有复杂、随机、多约束等特点，是典型的NP难问题。遗传算法具有全局搜索的特征，且搜索速度较快[14]，在求解此类问题上具有独特的优势。当前遗传算法已广泛应用于调度问题的求解，且取得了较好的实际效果。
2.1 染色体编码
本研究的决策变量包括到港船舶靠泊优先级，装船任务作业优先级，以及占用作业线等。染色体由5个序列构成，见表1。
表1中：MoorOrder为船舶靠泊优先级序列，bi表示船i在相应泊位上的靠泊优先级（bi值越小，船i的靠泊优先级越高）;TaskOrder为装船任务作业优先级序列，cj表示任务j的作业优先级（cj值越小，任务j在相应作业线上的优先级越高）;BeltBQ、BeltBC、BeltBM分别表示装船任务占用的取料线、连接线、装船线序列，ej、fj、gj分别表示任务j占用的取料线、连接线、装船线。
2.2 初始化种群及染色体解码
初始种群的生成规则如下：
（1）MoorOrder序列。依据船舶靠泊泊位随机生成。
（2）TaskOrder序列。对同一泊位，靠泊优先级较高的船舶，其装船任务作业优先级也较高。据此原则，生成装船任务作业优先级序列的步骤如下：① 随机生成作业优先级;②对靠泊同一泊位的两艘船，若靠泊优先级较高者的装船任务作业优先级编号最大值，大于靠泊优先级较低者的装船任务作业优先级编号最小值，则交换两项任务的作业优先级编号;③重复步骤②，直至满足原则为止。
（3）BeltBQ、BeltBM序列：在可达该装船任务所占垛位和泊位的取料线和装船线中随机选择。
（4）BeltBC序列：在可达所选取料线和装船线的连接线中随机选择。
本文使用遗传算法生成调度方案，仿真得到码头在各调度方案下的运行结果，统计各作业线启动次数、作业量和各船舶在港时间等指标，求得目标函数值，并将其倒数作为适应度函数。 2.3 遗传算子
使用轮盘赌和保优策略进行选择。针对染色体序列特点，设计以下3种交叉策略。
（1） 整体单点交叉，见图1。
此策略可能导致以下3种新染色体序列不满足约束条件的情况，需修正：
①若在MoorOrder序列中同一泊位的两艘船靠泊优先级相等，则交叉部分保留，未交叉部分以缺失的优先级编号替换。
②若在TaskOrder序列中两项装船任务作业优先级相等，则交叉部分保留，未交叉部分以缺失的优先级编号替换。
③若TaskOrder序列与MoorOrder序列矛盾，则修正原则同生成初始种群时对TaskOrder序列的修正原则。
（2）TaskOrder序列多点交叉，见图2。图2中，r1～r4为交叉点位置。此策略可能导致TaskOrder序列中两项装船任务作业优先级相等，或TaskOrder序列与MoorOrder序列矛盾的情况，修正原则同上。
（3）BeltBQ、BeltBC、BeltBM序列多点交叉，见图3。图3中，r1～r4為交叉点位置。
同时，设计3种变异策略：针对MoorOrder序列，在同一泊位中随机选择两艘船，交换其靠泊优先级;针对BeltBM序列，在可达任务相应泊位的其他装船线中随机选择一条不同的装船线;针对TaskOrder序列，随机选择两项任务，交换其作业优先级，修正原则同上。
计算时，以一定概率随机选择一种策略进行交叉或变异。
3 实例分析
以我国某煤炭出口码头为例，将利用本文提出的优化模型得到的调度方案（优化方案）与调研得到的码头实际调度方案（现行方案）进行对比分析，验证模型和算法有效性。该码头包括3个泊位、40个垛位、3条取料线、2条连接线、3条装船线，见图4。
规划期内码头到港13艘船，到港时刻见表2，现行方案见图5。以⑥号船为例：该船在第1天2：06到港，2：40靠泊于2#泊位;在完成辅助作业后，其4项装船任务（编号24、25、26、27）分别于 4：20、6：40、15：10、4：20开始作业，并分别于6：40、13：50、17：00、15：10完成;在最后一项任务（编号26）完成后，该船解缆，并于17：10离泊。
码头调度优化方案见图6。现行方案和优化方案的作业线分配情况见表3。在⑥号船作业过程中，其26、27号任务占用本泊位的装船线BM2进行装船，24、25号任务占用1#泊位的装船线BM1，因此，27与24、25号任务可同时进行，实现了装船机的联机作业，提高了码头作业效率。由于码头工艺流程限制，26和27号任务均需占用取料线BQ2，无法同时作业，优化方案为二者分配了相同的装船线，待27号任务完成后26号任务紧接着占用装船线BM2作业。与现行方案相比，优化方案中装船线BM1的启动次数减少了一次。
通过优化，码头作业线总启动次数从102次减为81次（减少20.6 %，见表4），大大简化了人员操作，改善了装船作业连续性，从而使作业效率得以提高。同时，作业线启动次数的减少也为码头节省了2 300 kW·h的电能。不过，作业线运行能耗主要与装船量有关，在装船量不变且码头设备保持现状的情况下，能耗优化空间有限。能耗优化目标可通过使用清洁能源或更新节能设备等措施实现。
另外，与现行方案相比，优化方案中船舶平均在港时间减少11.6%（3.04 h，见图7），最后一艘船离港时刻提前7 h。以作业时间相对重合的①、⑦号船为例进行分析：两船分别靠泊于1#、2#泊位，在优化方案中①号船的装船机联机作业集中在⑦号船完成辅助作业前，在⑦号船完成辅助作业后，BM2（SL2）即返回2#泊位，与BM3（SL3）联机为⑦号船作业，停靠在1#泊位的①号船则继续由BM1（SL1）单机作业。与现行方案相比，①号船联机作业时间从7.33 h减少至3.50 h，而⑦号船单机作业时间从0增加至4.17 h。这样的调度方式，使得⑦号船提前12 h离泊，从而使其后的⑧号船得以提前靠泊装船，而①号船虽延后4 h离泊，但由于其后的②号船到港较晚，所以并未对1#泊位后续船舶的装船作业造成影响。由此可以看出，通过合理的资源调配和作业优先级调整，优先保障较繁忙泊位的装船作业，能在总体上有效减少船舶在港时间，提高煤炭出口码头的服务水平。
4 结 论
通过深入分析煤炭出口码头装船作业的复杂流程和现实约束，在考虑装船机联机作业的前提下，以最小化煤炭出口码头作业线运行能耗成本和船舶在港时间成本为目标，综合考虑作业流程约束，泊位、垛位和作业线的作业唯一性约束等，建立混合整数规划模型，设计基于仿真解码方案的遗传算法，对其调度问题进行优化研究。最后，利用本文提出的调度优化模型对实例进行计算，优化方案下规划期内码头作业线总启动次数减少20.6%，船舶平均在港时间减少11.6%，最后一艘船提前7 h离港，优化效果良好。本文研究成果可为具有工艺流程复杂、装船机联机作业等特点的煤炭出口码头制订合理、高效的装船作业调度方案提供决策依据，从而进一步提升煤炭出口码头服务水平，为我国煤炭运输链的高效和流畅运行提供保障。
参考文献：
[1]岳金灿， 周运文， 郭建睿. 关于煤炭装船码头移动式装船机联机作业的探讨[J]. 港工技术， 2013， 50（1）： 13-15. DOI： 10.16403/j.cnki.ggjs2013.01.008.
[2]钱国栋. 曹妃甸港煤码头堆场作业管理及优化设计研究[D]. 秦皇岛： 燕山大学， 2015.
[3]王翼展， 张安， 陈永， 等. 煤炭码头堆取料机的调度问题[J]. 杭州电子科技大学学报（自然科学版）， 2019， 39（6）： 88-93. DOI： 10.13954/j.cnki.hdu.2019.06.016. [4]VAN VIANEN T， OTTJES J， LODEWIJKS G. Simulation-based rescheduling of the stacker-reclaimer operation[J]. Journal of Computational Science， 2015， 10： 149-154. DOI： 10.1016/j.jocs.2014.06.004.
[5]HU Dayong， YAO Zhenqiang. Stacker-reclaimer scheduling in a dry bulk terminal[J]. International Journal of Computer Integrated Manufacturing， 2012， 25（11）： 1047-1058. DOI： 10.1080/0951192X.2012.684707.
[6]KALINOWSKI T， KAPOOR R， SAVELSBERGH M W P. Scheduling reclaimers serving a stock pad at a coal terminal[J]. Journal of Scheduling， 2017， 20： 85-101. DOI： 10.1007/s10 951-016-0495-8.
[7]宓為建， 王郡娴， 张晓华， 等. 基于多目标遗传算法的煤码头泊位与机械联合调度[J]. 上海海事大学学报， 2016， 37（2）： 46-52. DOI： 10.13340/j.jsmu.2016.02.009.
[8]邰世文， 商剑平. 煤炭码头卸车调度问题多目标优化模型及算法[J]. 运筹与管理， 2018， 27（6）： 91-99. DOI： 10.12005/orms.2018.0138.
[9]DE PAULA M R， BOLAND N， ERNST A T， et al. Throughput optimisation in a coal export system with multiple terminals and shared resources[J/OL]. Computers and Industrial Engineering， 2019， 134： 37-51. DOI： 10.1016/j.cie.2019.05.021.
[10]MENEZES G C， MATEUS G R， RAVETTI M G. A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports[J]. European Journal of Operational Research， 2017， 258： 926-937. DOI： 10.1016/j.ejor.2016.08.073.
[11]BURDETT R L， CORRY P， YARLAGADDA P K D V， et al. A flexible job shop scheduling approach with operators for coal export terminals[J]. Computers and Operations Research， 2019， 104： 15-36. DOI： 10.1016/j.cor.2018.11.019.
[12]UNSAL O， OGUZ C. An exact algorithm for integrated planning of operations in dry bulk terminals[J]. Transportation Research Part E， 2019， 126： 103-121. DOI： 10.1016/j.tre.2019.03.018.
[13]PRATAP S， KUMAR B M， SAXENA D， et al. Integrated scheduling of rake and stockyard management with ship berthing： a block based evolutionary algorithm[J]. International Journal of Production Research， 2016， 54（14）： 4182-4204. DOI： 10.1080/00207543.2015.1111535.
[14]艾立红， 韩晓龙. 考虑能耗的自动化码头装卸设备协调调度[J]. 上海海事大学学报， 2018， 39（4）： 26-31. DOI： 10.13340/j.jsmu.2018.04.005.
（编辑 贾裙平）