基于多目标遗传算法的煤码头泊位与机械联合调度

宓为建+王郡娴+张晓华+梁枭+夏孟珏

摘要：

针对煤码头泊位分配问题，考虑泊位与机械的联合调度.综合考虑煤种类对船舶靠泊位置的影响、航道开放时间和如开设机械双线作业等特殊原则，以最大化岸线利用率和机械利用率以及最小化船舶在港时间为目标，建立泊位与机械的联合调度模型.设计具有自适应性的多目标遗传算法进行求解.利用天津港煤码头实际案例分析验证模型的可行性和算法的有效性.该方法可为大多数散货码头的生产运营管理提供借鉴.

关键词：

煤码头；泊位分配；机械调度；多目标遗传算法

中图分类号：U691.31

文献标志码：A 收稿日期：20150414 修回日期：20150609

0引言

随着我国煤炭需求量的激增，煤炭码头发展规划水平不断提升.作为煤炭运输的中转站，码头泊位作业系统的高效化愈发重要.[1]然而，目前鲜有针对散货码头泊位分配问题的科学合理的优化调度方案.散货码头泊位分配问题与集装箱码头的十分相似，而集装箱码头泊位分配问题和岸桥分配问题一直是港口研究热点.[2]

BIERWIRTH等[2]依据岸线布局将泊位分配问题分为离散型和连续型.针对前者，通常以最小化所有到港船舶总在港时间为目标，建立混合整数规划模型，并利用启发式算法、模拟退火算法、遗传算法进行求解；韩笑乐等[3]基于先到先服务（FirstComeFirstService，FCFS）修改后的规则生产初始解，结合禁忌搜索和模拟退火法求解.针对连续型泊位问题，IMAI等[4]建立整数规划模型，指出连续泊位调度计划的高效性；ZHEN等[5]考虑船舶到达与作业时间的不确定性，提出两阶段模型，利用亚启发式算法求解；DU等[6]考虑船舶燃油消耗，提出混合整数二阶锥规划模型；HENDRIKS等[7]同步考虑泊位分配和堆场计划.

实际上，泊位分配与机械调度相互影响[8]，船舶靠泊作业时间很大程度上由所分配的机械数量决定，因此在泊位分配问题中必须同时考虑机械调度.针对集装箱码头泊位与岸桥这两个港口关键资源约束，ZHANG等[9]考虑了岸桥覆盖范围，并用梯度优化技术求解；CHANG等[10]依据滚动水平方法编出程序模型，利用混合并行遗传算法求解；RAA等[11]考虑船舶的优先权，提出混合整数线性规划模型.

散货码头的泊位和岸边机械分配问题虽然与集装箱码头的相似，但其仍然具有自身的特殊性[12]，例如：散货种类影响装卸机械的选型、船舶停靠的岸线位置、航道开放时间等.因此，有必要针对散货码头的特殊性，在决策船舶靠泊方案时考虑岸边机械资源，建立船舶与岸边机械的联合调度模型，以使调度方案更加合理.

1问题描述

煤码头在散货码头中占据重要地位，出口型煤码头布局见图1，其中泊位系统主要包括码头岸线、装卸机械设备（移动式装船机、皮带输送装置等）以及到港服务的船舶，其调度计划的两项基本工作是了解船舶动态和编制昼夜作业计划，而码头现存人工调度计划由于工作人员个人工作能力的差别使得制订出的泊位计划不尽合理.

煤码头所运输的煤可分为末煤和块煤两种，末煤由装船机作业，块煤由门机作业，而装船机在左侧，门机在码头右侧，即末煤船舶靠泊在左，块煤船舶靠泊在右.船舶作业时间与岸边装卸机械的分配有关，岸边机械可在合适情况下开设双线作业.一般情况下载质量≥3.0万t，船舱数≥4个的船舶比较适合采用双线作业方式装船.例如，当某台装船机处于空闲状态时，可以动态安排到邻近船舶进行辅助装船作业，以缩短船舶在港时间.航道每隔两小时变换一次航道开放状态，见表1.

此外，为便于计算，假设：码头岸线泊位为连续直线型泊位，以10m为一个岸壁线单元，以1h为一个时间单位；待排船均已到达港口锚地（静态调度）；任意时刻，某一岸壁线单元仅能被一艘船占用；每艘船所需机械数量有上限和下限，由该船配载舱数决定；内外贸船舶进出港手续办理时间不一样；航道深度满足所有船的需求；停靠在码头上的船舶，船身占有的泊位长度可以从该船映射的缆绳桩头尾之间的距离来确定，并将此长度反映为均匀的缆绳桩之间距离的整数倍，一个桩位只可用于一艘船.抵港船舶的靠泊作业流程见图2.

因此，与已有的研究[13]相比，进一步考虑在散货煤码头分开靠泊块煤、末煤船舶，航道开放时间，允许适当开设双线协同作业等实际特点，同时考虑岸线、机械利用率最大和船舶总在港时间最短等多个目标.

2模型建立

2.1参数及变量

参数定义：i代表待安排靠泊计划的船舶，I为锚地待排船舶总数，1≤i≤I；j为岸线被分割的岸壁线单元，J为分割的岸壁线单元总数，1≤j≤J；t表示某一时刻；L为岸线总长度；li为船i的长度（包括水平安全距离）；Ci为船i装载量；Hi为船i办理进出港手续时间；ta和tb分别为内、外贸船舶办理进离港手续时间；ri为01变量，ri为0时是内贸船，否则是外贸船；Pi为01变量，Pi为1时指船上货物种类为块煤，否则为末煤；ti为船i从锚地到靠泊位置所需时间；v为机械（装船机或门机）作业速率；v1和v2分别代表装船机和门机作业速率；ni为预配船舱数量，其中nit代表任意时刻需要装舱的船舱数量，超过某数量级别才能开设双线作业；A为装船机台数；G为门机台数；B为岸壁线单元的长度.

自变量：Qit为t时刻为船i服务的机械数量；Si为船i停靠的起始岸壁线单元；bi为船i靠泊时刻.

因变量：Xjit为01变量，t时刻若船i占用泊位j则Xjit为1，否则为0；Ei为船i停靠的结束岸壁线单元；Ti为船i作业总时间；di为船i离港时刻；F1，F2和F3为3个目标函数.

2.2约束条件

泊位与机械联合调度模型的约束条件如下：

li/B代表岸壁线单元在船i所停靠的起止岸线内；bi≤t≤bi+Ti指船i的停靠时间；若满足岸壁线单元与时间的约束范围，则泊位j被占用，Xjit为1，否则为0.式（2）保证船i结束位置在最后一个岸壁线单元内.式（3）满足船i在作业总时间Ti内的装载作业量必须大于船i的计划装载量，即在规定时间内完成作业任务.式（4）表示岸边机械作业速率.式（5）和（6）分别表示某时刻所有船舶所分配的装船机和门机的总数量不超过实际数量.式（7）表示若船i需要装舱的数量小于nit，则船上机械不多于1台，若船i需要装舱的数量大于等于nit，则船上机械不多于2台.式（8）是船i办理进离港手续时间公式.式（9）保证船i在离港前完成作业，并办完离港手续.式（10）和（11）分别表示船i进港与离港时刻必须在规定的进离港时间段内，否则必须等待.式（12）表示岸壁线单元的连续性约束.式（13）保证任意两艘船在位置和空间上的互不交叉，如图3所示，i1和i2代表任意两艘船，Si与Ei分别指船i停靠起始和结束岸壁线单元，两矩形框分别表示两艘船在空间和时间上的位置，而这两艘船的互不碰撞表现为两个矩形无重叠区域，即同一时刻同一位置只有一艘船被服务.

2.3模型目标

式（14）的目标是岸线利用率最大.根据《海港总平面设计规范》，岸线利用率=（在泊船长×在泊时间）/（码头岸线总长度×船舶在港时间）.式（14）中：Ei-Si+1代表在泊船长；di-bi代表船舶的在泊时间；η=maxdi-maxbi，即用所有船的最晚离港时间减去最早靠泊时间，得到所有船的在泊时间.式（15）的目标是机械利用率最大，即尽量使分配给所有船的岸边装船机和门机处于忙期，提高工作效率.机械利用率=（所有机械实际工作时间）/（总机械数量×所有船的在港时间）.式（16）的目标是船舶总在港时间最短.实际上码头方希望船舶的在港时间最短，不仅要尽量减少船舶作业时间，而且要减少船舶等待时间.

3算法设计

最优化处理是寻找目标的最优解，若优化目标超过一个并需同时进行优化处理，则称为多目标优化.用遗传算法解决该问题时产生了一类新的研究和应用，称为遗传多目标优化.由于各目标之间无法比较，一个解可能对某个目标函数是最好的，但对其他目标函数是最差的，这一系列解称作非支配解（nondominatedsolutions）.判据空间有一个特殊的点，叫做正理想解（positiveidealsolution），用z*k=（z*1，z*2，…，z*q）表示，其中z*k=sum{fk（x）/x∈S}，k=1，2，…，q.对每个目标来说，寻找z*k是可能的，但是寻找一个能够同时最大化每个fk（x）（k=1，2，…，q）的点z*通常是非常复杂的.通过给定偏好，将非支配解集中可选的解进行排序，然后获得最终决策结果，此最终解称作最优妥协解（bestcompromisedsolution）.权重和方法（weightedsumapproach）是一种有效的适应值分配机制.在多目标优化中，用该方法来获得最优妥协解.权重和方法被应用到遗传算法中时，其缺点可以被遗传算法基于种群搜索和进化搜索的力量削弱.权重和方法包括固定权重方法、随机权重方法和适应性权重方法.采用适应性权重方法，可以更全面地利用遗传算法的搜索能力，利用当前种群中一些有用的信息来重新调整权重，从而获得朝向正理想解的搜索压力.

3.1遗传算法编码

泊位与机械分配问题的目的是找到最合适的船舶靠泊顺序、靠泊位置以及确定船舶动态作业的机械数量.染色体编码中需包含船舶靠泊顺序和靠泊位置信息，因此采用自然数编码方式.子染色体1表示船舶的靠泊顺序（VO），子染色体2表示船舶停靠的起始位置（VL）.表2为8艘船的染色体编码.例如，根据得出的编码，船6（长度100m）首先进行靠泊，并停靠在起始岸壁线单元（长度10m）为从31～40的10个岸壁线单元上.针对Xjit，利用编码中的船舶进港顺序依次安排进港，岸线位置排满后，后续船舶必须等前面的船舶作业完成并离港后，在进港时间段内进港，其计算以岸线上船舶的最早离港时间为基准，得出每艘船的靠泊时间.船i是否占用泊位单元j由船长决定.子染色体2表示j的起始值，根据船长计算出所有被占用的j的值.

3.2适应度函数

在适应性权重法中，首先对目标函数进行转化，将各子目标函数化归为[0，1]之间的实数.令Z1=F1和Z2=F2，这两个利用率的值在[0，1]之间.F3则是所有船舶的在港时间，是较大的实数.令Z3=Ii=1dimaxdiI，由于目标Z3是求最小值，将其转化为求最大值，即令

因为转化后的目标函数满足适应度函数设计要求，所以可令适应度函数为Z（x），目标函数即为令其最大化，其理论最大值为3.利用适应性确定多目标权重的方法，同时结合了生产式求解思路和启发式决策思路的优点，在进化过程中，每代Zmaxk和Zmink变化时，也相应动态调整权重，即在进化过程中，根据当前有用信息对目标偏好进行持续调整，获得向正理想解搜索的压力，不同于传统的固定权重多目标优化.

3.3选择、交叉与变异操作

采用轮盘赌的方法选出下一代.对染色体1采用次序杂交（ordercrossover），以避免交叉后染色体产生不可行解，见图4.适用于自然数编码的变异算子有反转变异、插入变异和交换变异，该算法中采用交换变异，具体见图5.

3.4染色体初始化及修复

染色体1的初始值是船舶编号的一个随机顺序，染色体2的初始值是根据染色体1的初始顺序和船舶长度依次生成的随机整数ξ，

即该随机起始位置在未被占用的岸壁线单元数内.由于岸线为连续泊位，编码形式采取的是自然数编码.在交叉和变异后，由于受船舶靠泊位置的约束，会产生大量不可行解，因此对染色体2编码段进行修复，使之较快找到较优停泊位置.重新计算连续的空闲岸壁线单元，如果该空闲段的长度能够满足停下一艘最小的船舶，则在该岸壁线单元内随机生成起始基因位，如果生成的解不满足任何一个约束条件，则对该解设置惩罚系数以淘汰该解，以此方法修复染色体.

4.1算例数据

根据天津港煤码头实际船舶昼夜装卸计划及配

载数据，整理出20艘船的装卸数据，见表3.全岸线长1100m，0～550m靠泊末煤船，550～1100m靠泊块煤船，则共有110个岸壁线单元（岸壁线单元长度是10m）；单台装船机额定能力为6700t/h，门机额定能力1600t/h；货类中“1”代表块煤，“2”代表末煤；需要装货的船的船舱数代表船的级别.

4.2算例结果及分析

对于大量的在港船舶，人工无法快速制订靠泊方案，而智能算法能够迅速找到较优的船舶靠泊方案.通过编写的算法程序，将试验在Itel（R）Core（TM）i5CPU@2.53GHz和4GB内存的个人电脑上，应用eMplant软件运行求解.遗传算法的初始种群规模为40，迭代次数为450，交叉概率为0.85，变异概率为0.01，多次运行算法程序，每次计算时间为2～5min，靠泊方案计算结果见表4.例如，船舶编号为20的“百盛”首先进行靠泊，靠泊起始位置在10m处，其开始作业时间为17：00，经过144min装卸作业完成.

联合调度方案见图6.由图6可直观观察到港

船舶的靠泊位置、靠泊时间以及等待和机械分配情

况.例如船16为运输块煤的船舶，其停靠所占用的

岸线位置为930～1090m；为方便机械较快地对靠泊船舶进行作业，允许船舶提前靠泊等待.

船1，3，6均开设了双线作业，即当1台可移动装船机处于工作空闲期时，可把它调度到邻近的较大船舶处协助作业.

原则上，船舶靠泊后会有已经安排好的机械对其进行作业，如果没有，则需等待机械空闲时动态调度邻近的空闲机械对其进行作业.例如船1和19，当船19作业完成且后续船舶还未进港时，可动态调度船19上的作业机械对船1进行作业.双线作业的开设即为某时刻动态调整机械的作业.

其次，对程序算法的鲁棒性和适应度函数进行评价.算例规模分别为10艘船和20艘船，遗传算法的初始种群规模为40，迭代次数为450，交叉概率为0.85，变异概率为0.01，分别运行程序5次.算例每代最优个体适应度函数值的收敛曲线见图7.由于三个目标函数经过归一化处理，因而适应度函数值无量纲.图中结果显示，不同参数和算例规模下的模型运算结果的收敛曲线均能收敛到3，证明算法在深度和广度上具有良好的收敛性，模型系统具有较好鲁棒性.综上可得，所设计的适应性权重的多目标遗传算法适用于解决散货码头连续泊位岸线上的船舶与机械联合调度问题.

5结束语

综合考虑不同货类对船舶停靠位置的影响、航道开放时间和如开设机械双线作业等原则，根据模

型的复杂性和多目标的特点，设计多目标遗传算法.利用实数编码、次序交叉、交换变异算子，采用适应性权重方法，迫使算法向正方向收敛.利用天津港煤码头数据验证模型和算法的可行性及有效性.采用图形化的信息显示方式，结合手动调整进一步确定优化方案，得到较好的人机结合效果.本文的研究不仅对散货码头的运营具有借鉴意义，而且对同类不确定性多项式问题的解决具有指导意义.

参考文献：

[1]王煜，郑惠强，李强.基于知识工程的煤炭码头堆场分配策略[J].上海海事大学学报，2012，33（3）：2630.

[2]BIERWIRTHC，MEISELF.Asurveyofberthallocationandquaycraneschedulingproblemsincontainerterminal[J].EuropeanJournalofOperationalResearch，2010，202（3）：615627.

[3]韩笑乐，陆志强，奚立峰.具有服务优先级别的动态离散泊位调度优化[J].上海交通大学学报，2009，43（6）：902905.

[4]IMAIA，SUNX，NISHIMURAE，etal.Berthallocationinacontainerport：usingacontinuouslocationspaceapproach[J].TransportationResearchPartB：Methodological，2005，39（3），199221.

[5]ZHENL，LEELH，CHEWEP.Adecisionmodelforberthallocationunderuncertainty[J].EuropeanJournalofOperationalResearch，2011，212（1）：5468.

[6]DUY，CHENQ，QUANX，etal.Berthallocationconsideringfuelconsumptionandvesselemissions[J].TransportationResearchPartE：LogisticsandTransportationReview，2011，47（6）：10211037.

[7]HENDRIKSMPM，LEFEBERE，UDDINGJT.Simultaneousberthallocationandyardplanningattacticallevel[J].ORSpectrum，2013，35（2）：441456.

[8]邱波.集装箱码头泊位系统资源配置与调度优化研究[D].大连：大连海事大学，2014.

[9]ZHANGC，ZHENGL，ZHANGZ，etal.Theallocationofberthsandquaycranesbyasubgradientoptimizationtechnique[J].Computers&IndustrialEngineering，2010，58（1）：4050.

[10]CHANGD，JIANGZ，YANW，etal.Integratingberthallocationandquaycraneassignments[J].TransportationResearchPartE：LogisticsandTransportationReview，2010，46（6）：975990.

[11]RAAB，DULLAERTW，SCHAERENRV.Anenrichedmodelfortheintegratedberthallocationandquaycraneassignmentproblem[J].ExpertSystemswithApplications，2011，38（11）：1413614147.

[12]李强，宓超，赵宁，等.自动化散货装船机物位检测技术[J].上海海事大学学报，2013，34（3）：1316，89.

[13]唐晨.天津港煤码头泊位作业系统生产组织优化研究[D].大连：大连海事大学，2013.