1.基于遗传算法的船舶分段堆场调度研究2

上海交通大学学报

ＪＯＵＲＮＡＬＯＦＳＨＡＮＧＨＡＩＪＩＡＯＴＯＮＧ　ＵＮＩＶＥＲＳＩＴＹ　　　　

Ｖｏｌ．４７Ｎｏ．７　

Ｊｕｌ．２０１３　

（）１００６２４６７２０１３０７１０３６０７　　文章编号：－－－基于遗传算法的船舶分段堆场调度研究

张志英，　徐建祥，　计　峰

（）同济大学机械与能源工程学院，上海２０１８０４

摘　要：针对船舶分段移动计划主要依靠经验以及缺乏有效调度的现状，研究建立以分段移动度最小为目标的优化模型，综合考虑了分段在堆场中的停放位置及进、出场路径．通过遗传算法选择分段在堆场中停放位置的最优方案，并构建启发式规则确定分段在堆场中的最优进、出场路径，从最后以某船厂实际数据为例，对模型在堆场调度问题中的应用进行了实例验而实现对模型的求解．

证，结果表明，所研究方法可求解得出较优的堆场作业计划，并实现堆场资源的高效利用．关键词：遗传算法；启发式规则；船舶堆场；调度中图分类号：ＴＰ３９１；Ｕ６７３　　　文献标志码：Ａ　　

ＳｈｉｂｕｉｌｄｉｎＹａｒｄＳｃｈｅｄｕｌｉｎＡｒｏａｃｈＢａｓｅｄｏｎＧｅｎｅｔｉｃＡｌｏｒｉｔｈｍ　　　　　ｐｇｇｐｐｇ　　

ｉｎｉａｎ－ｅｎＺＨＡＮＧ　ｚｈｉｘｉａｎＩ－　ＸＵ　　Ｊ　ｙｇ，ｊｆｇｇ，

（，，）ＳｃｈｏｏｌｏｆＭｅｃｈａｎｉｃａｌＥｎｉｎｅｅｒｉｎＴｏｎｉＵｎｉｖｅｒｓｉｔＳｈａｎｈａｉ２０１８０４，Ｃｈｉｎａ　　　　　ｇｇｇｊｙｇ

：ＡｂｓｔｒａｃｔＴｈｉｓａｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｄｅｆｉｎｅｄａｓｔｈｅａｓｓｉｎｍｅｎｔａｎｄｏｆｔｈｅｉｎｂｏｕｎｄａｅｒｒｅｓｅｎｔｅｄａｔｈｓ　　　　　　　　　　　　　　ｇｐｐｐｐａｎｄｏｕｔｂｏｕｎｄｏｂｅｃｔｓｔｏｔｈｅｓｈｉｉｎａｒｄｗｉｔｈｔｈｅａｉｍｏｆｍｉｎｉｍｉｚｉｎｔｈｅｄｅｒｅｅｏｆｍｏｖｅｍｅｎｔｏｆｔｈｅ　　　　　　　　　　　　　　　ｊｐｐｇｙｇｇ　　ｂｌｏｃｋｓ．Ａｅｎｅｔｉｃａｌｏｒｉｔｈｍ　ｗａｓｆｏｒｍｕｌａｔｅｄｔｏｓｅｌｅｃｔｔｈｅｏｔｉｍａｌａｒｋｉｎｏｓｉｔｉｏｎｓｆｏｒｔｈｅｉｎｂｏｕｎｄｂｌｏｃｋｓ．　　　　　　　　　　　　ｇｇｐｐｇｐ　ｈｅｕｒｉｓｔｉｃｒｕｌｅｗａｓｅｍｂｅｄｄｅｄｉｎｔｈｅａｌｏｒｉｔｈｍｔｏｓｅｌｅｃｔｔｈｅｏｔｉｍａｌｍｏｖｉｎａｔｈｓｆｏｒｔｈｅｂｌｏｃｋｓ．ＡｌｉｃａＡ　　　　　　　　　　　　　　　－ｇｐｇｐｐｐ　

，ｔｉｏｎｄａｔａｗｅｒｅｏｂｔａｉｎｅｄｆｒｏｍａｓｈｉａｒｄｔｏｖａｌｉｄａｔｅｔｈｅｍｏｄｅｌａｎｄｔｈｅｒｅｓｕｌｔｓｈｏｗｅｄｔｈａｔｔｈｅｒｏｏｓｅｄａｌ　　　　　　　　　　　　　　　　　－ｐｙｐｐｏｒｉｔｈｍ　ｗａｓｅｆｆｅｃｔｉｖｅｔｏｓｏｌｖｅｔｈｅｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｉｎｓｈｉｂｕｉｌｄｉｎａｒｄｓ．　　　　　　　ｇｇｐｐｇｙ　　

：；；ｅｎｅｔｉｃａｒｄｓＫｅｗｏｒｄｓａｌｏｒｉｔｈｍ；ｈｅｕｒｉｓｔｉｃｒｕｌｅｓｈｉｂｕｉｌｄｉｎｓｃｈｅｄｕｌｉｎ　　ｇｙｇｇｐｇｙ　　

是　　船舶分段堆场是船企不可或缺的重要资源，

由于受分段脱胎后进行后处理的堆放或暂存场所．生产和管理等因素影响，分段脱胎后与后续工序之间的周转流动并非“即时无缝”连接，导致脱胎的分段不能及时送往船坞搭载，从而增加对堆场资源的需求．堆场负荷严重已成为船厂物流系统正常运转的瓶颈．同时，不合理的调度机制和缺乏有效的管理信息系统使分段处于无序堆放状态，也给生产管理带来很多问题．因此，研究船舶分段堆场调度问题并制定合理的堆场调度计划成为重要问题．

面向船舶制造的分段堆场调度属于二维空间平

收稿日期：２０１２０８２７－－面调度问题，目前国内外专门针对这类问题的研究但其与集装箱堆场调度问题等类似．针对集装较少，

箱的翻箱量问题，有人通过建立最小生成树模型，并运用动态规划方法和启发式算法求解模型确定最小

］１３－翻箱量［文献［中考虑集装箱码放顺序的全序．４］

关系，设计单箱码放算法求解动态码放模型．集装箱堆场调度中箱位分配和翻箱量类似于船舶堆场中的分段停放位置和临时移动分段数量，但两者的堆放规则不同，前者属于分层堆放，后者是平面堆放．分段堆场调度问题属于Ｎ近几年各种智Ｐｈａｒｄ问题．－遗传算法作为一种能算法逐渐被引入调度问题中，

），）基金项目：国家自然科学基金资助项目（上海科技创新行动计划项目（７０８７２０７６１１ｄｚ１１２１８０３

，：作者简介：张志英（男，内蒙古人，副教授，博士，研究方向为生产计划控制，工业工程．１９７１Ｅ－ｍａｉｌｚｚｈａｎ０８＠ｔｏｎｉ．ｅｄｕ．ｃｎ．－）ｙｇｇｊ

　第７期

张志英，等：基于遗传算法的船舶分段堆场调度研究　　

１０３７

非确定性的拟生态随机优化算法，在调度问题中得到了广泛应用．有些研究以最小完工时间为目标，利

］５６－用改进遗传算法求解计划与调度的集成模型［针．

然后规划其在堆场中的移动路径．对于出场分段，则只需根据其在堆场中的停放位置规划出场路径即可．确定分段的移动路径需经过２个步骤：①根据启发式规则求出具有最少临时分段数的路径（可能不唯一）具有．②利用临时场地比较这些可行路径，临时场地主要用于最小分段移动度的为最优路径．

暂时存放临时分段，可以减少分段移动度；降低道路降低运输工具的空间压力及道路被堵塞的可能性；

负荷；缩短移动距离，同时减轻分段在移动过程中的降低潜在质量风险．损伤程度，

对Ｊ文献［中提出新的自适应ｏｂＳｈｏ７］　ｐ调度问题，遗传算法进行求解．

本文以分段移动度最小为优化目标，运用遗传算法和启发式规则对分段在堆场中的调度问题进行合理安排分段进出堆场顺序，确定分段在堆场建模．

中的最优停放位置，规划其进、出堆场的移动路径，优化堆场资源的利用率，提高堆场周转率．并结合某船厂实际数据对模型进行了实例验证．

１　问题描述与解决方法

１．１　问题描述

出场　　分段按其在堆场中的作业类型分为进场、进场分段是脱胎后要移进堆场进行后续处理分段．

或暂存的分段；出场分段是在堆场中完成了后续处理或暂存运往船坞搭载等后续工位的分段．临时分段是对分段进出堆场过程造成阻碍的分段．在调度过程中需要先将临时分段移至道路或临时场地上，等计划分段到达目的位置后，再将其移回原处．分段出场分段到目的移动度指平板车在堆场中搬运进、

地整个过程的移动难度．搬运过程中，若平板车遇到则移动度增加α．为区别相同临时移１个临时分段，

动分段数的路径而定义系数β，β指平板车经过１个空场地的移动难度．分段的搬运是造成成本的主要原因，包括设备维修费、油耗、质量风险等，从而必须先保证临时分段移动量最少，再考虑平板车的移动路径问题，因此，本文取α＝１，α应远大于β，β＝０．分段进出堆场的移动路径不唯一，不同的移０００１．　动路径具有不等的分段移动度．

考虑到分段堆场的实际情况及便于堆场调度问题的研究，假设：出堆场，不①分段按计划时间进、存在提前、延期和占先；②分段进出堆场的道路确定且唯一；③堆场由若干大小相等的正方形场地组成；④分段用最小包络矩形近似；⑤一个作业场地只能放一个分段；⑥临时分段只能移动到道路或与其相邻的４个临时场地上，且必须移回原处．本文要解决的问题：①确定进场分段在堆场中合适的停放位置；②确定分段进出堆场的最佳移动路径．１．２　解决方法

对于调　　本文以分段移动度最小建立目标函数．首先结合优化目标，利用遗传度周期内的进场分段，

算法（为其安排停放位置，ＧｅｎｅｔｉｃＡｌｏｒｉｔｈｍ，ＧＡ）　ｇ

２　堆场调度模型的建立与求解

２．１　建立堆场状态矩阵

　　为了表示分段在堆场中的停放位置及堆场场地

的状态，建立图１所示堆场状态矩阵．它是一个０－１矩阵，１表示场地上仅停放１个分段，０表示场地上无分段．图１表示一个５行９列的堆场，将位于第，第ｎ列的作业场地命名为（ｍ行、ｍ，ｎ，ｈ）ｈ为状态值，若该场地放有分段，则ｈ为１，否则为０．

图１　堆场状态矩阵Ｆｉ．１　Ｙａｒｄｓｔａｔｅｍａｔｒｉｘ　　ｇ

２．２　堆场节点状态模型

将堆　　为了求得分段移动路径上的临时分段数，场中的作业场地和道路用节点表示，建立分段堆场节点状态模型．堆场中作业场地（表示对ｍ，ｎ，ｈ）应的节点．道路用一个名为Ｖ０的节点表示，其状态始终为０．每个节点有上下左右４个方向，路径必然经过节点的其中２个方向．若节点状态为１，则其４个方向的路权为０．否则为０．因此，在分段进出堆５，场路径上，每经过一个状态为１的节点，分段起始位置节点与目标位置节点间的距离就增加１．据此定）义，节点间的距离如图２（所示．图２（表示相连ａｂ）节点的状态模型，即将相邻节点之间的路权相加．其中将２个状态为０的节点之间的距离定为０．００１是为了区别不同的０节点．根据以上规则，可以将任意堆场转换为节点状态模型．由此，分段进、出堆场时，依照某路径从起始位置到达目标位置过程中需经过的临时分段数，可通过计算节点状态模型中对应路

１０３８

上　海　交　通　大　学　学　报

１，Ｏ２无分段烄，ＹｇＯ＝ｒ烅ｉｋ２ｊ０，Ｏ２有分段烆则目标函数为ｉｎ∑ｍｉｎ　　　ｍ

ｉ＝１

ｒｉｋｊ第４７卷　

径上分段起始位置节点与目标位置节点间的距离，并将其数值取整后得到．

（）（１－θａ＋｛［∑（２ｈβ）Ｘ｝＋α＋ｄβ］θ）

ｋ＝１

ｉｊｉｊ，Ｏ２

ｎｚ（）１

…，…，式中：ｉ＝１，２，ｎ；２，ｍ　　ｊ＝１，…，（，，２，ｚ；ａｘＹｇＹｇｋ＝１，　θ＝ｍＯｒ１ｒｉｋｊ）（）２（）３（）４（）５（）６（）７（）８

ｉｋｊ图２　节点间的距离图Ｆｉ．２　Ｄｉｓｔａｎｃｅｂｅｔｗｅｅｎｎｏｄｅｓ　　ｇ

约束条件：

０≤ｔ０≤ｔｉ≤ｔＴ０≤ｔ０≤ｔｉ≤ｔｉｋｊ０＜ＬＷｉ≤Ｓｉ０

（ｘｘｘｙｙｙｉ，ｉ）ｖ，ｖ）≠（≠（ｊ，ｊ）（ｘｘｙｙｉ，ｉ）ｉａ，ｉａ）＋＋≠（（ｘｘｙｙｂ，ａ）＋＋≠（ｊ，ｊ）ｊｊ（ｘｘｙｙｖ，ｖ）ｖｄ，ｖｄ）＋＋≠（

２．３　场地更新机制

若　　作业场地的状态随分段进出堆场发生变化．

安排一个进场分段，则对应的停放场地状态由０变若是出场分段从堆场中出来，则放置该分段的为１，

场地状态由１变为０．临时移动的分段因为其移出堆场后又需重新放回原位置，故其状态不变．２．４　分段堆场调度模型

　　堆场作业计划以分段移动度最小为优化目标，对于出场分段，可以将道路看作起始点（即当作已确，定位置的进场分段处理）从道路处开始寻最优路径来简化模型．参数设定如下：

…，…，为Ｔ周期内待调度Ａ＝（Ａ１，Ａ２，ＡＡｎ）ｉ，…，（计划分段集，为分段Ａｉ＝１，２，ｎ；ＬＷｉ）ｉ，ｉ的…，…，为分段Ａ投影参数；Ｒｒｒｒｒｉ＝（ｉ１，ｉ２，ｉｉｍ）ｉ的ｊ，…，具有最少临时分段数的路径集，２，ｍ；ｄｊ＝１，ｉｊ为，ｒ，…，，路径ｒＧ＝（ｇｇｉｒｒｒｊ经过的场地数量；ｉｉ１ｇｉ２ｉｋｊｊｊｊ…，）…，为ｒｋ＝１，２，ｇｒｉｊ对应的临时移动分段集，ｉｚｊ为临时分段ｇ需经过的场地数；ｚ；ｈｔｒｒ０为Ｔ周期ｉｋｉｋｊｊ的开始时间；ｔｔＴ为Ｔ周期的结束时间；ｉ为Ａｉ出场时间；的在场时Ｓｔ０为单个作业场地面积；ｉｋ为ｇｒｊｉｋｊ间，其中临时分段的在场时间指该分段停留在堆场临时分段ｇ本有４个相连场地（上，下，中的时间；ｒｉｋｊ，左，右）定义另外２个场地ｒｉｊ经过了其中２个场地，，为（称为临时场地．其中，位于堆场边上的Ｏ１，Ｏ２）分段的临时场地集为ＯＷｉ为分段Ａｉ开始１或空集；（调度时，堆场状态矩阵中“的个数；为Ｔ０”ｘｙｖ，ｖ）周期内在场分段Ｓｖ在堆场中的停放位置（ｘｙｖ，ｖ分别为堆场的行与列）．

定义决策变量如下：

１，分段Ａｉ选择路径ｒｉｊ烄Ｘ＝ｉｊ烅０，Ａｉ选择其他路径烆１，Ｏ１无分段烄，ＹｇＯ＝ｒ烅ｉｋ１ｊ０，Ｏ１有分段烆（）９｜Ｗｉ＝１１－Ｗｉ｜＋

根据启发式规则求出　　在堆场节点状态模型中，

的分段可行路径并不唯一．通过引入临时场地用于）本文根据目标函数（逐个计算并确停放临时分段，１定每个分段的可行路径，集中具有最小分段移动度的路径，并得出该方案产生的最小总移动难度．然后，运用遗传操作在所有方案中选出总移动度最小）的方案来安排堆场计划；约束条件（分段的出２场时间在Ｔ周期内；约束条件（保证分段Ａ３）ｉ出场时，需移动的临时分段的在场时间要晚于分段的计）划开始时间；约束条件（表示作业场地能容下放置４的分段；约束条件（限定一个作业场地只能５）８）～（）放一个分段；约束条件（说明相邻的调度分段之间９的堆场状态必定不同．２．５　模型求解

　　船舶堆场调度模型的遗传算法设计如下：

（）初始化．以当前堆场状态为调度的初始状１态建立堆场状态矩阵．

（）产生初始种群．将进场分段在堆场中可能放２

置的作业场地位置组合形成一种调度方案（染色体）．

（）编码．染色体的第ｎ位基因是Ｔ周期内需ｉ

调度的第ｎ个分段．进场分段的基因特征值是当前堆场状态矩阵中“的序号（按从左到右，从上到下０”依次给零标号，随机数到第ｍ个零，则ｍ就是该基因的特征值）出场分段的基因值是其所在场地的序．号．根据编码机制，以图１为例，生成图３所示的染色体．第４、特征值５、９、１０、１１位基因是出场分段，而第１１８、２６、１１、４４是出场分段停放场地的序号，１

　第７期

张志英，等：基于遗传算法的船舶分段堆场调度研究　　

１０３９

位基因的值为－２，其表示第３位基因（原先是进场分段）在此时要出场．第１位基因的值４表示选择场）地（作为停放位置．３，７，０

序号代替（若是出场分段则不变）但随机产生的序．号必须在１～ｎ中产生，ｎ是进场分段当前堆场状态矩阵中０的个数上限．如可从１～５中选取３代替图

５中Ｘ染色体的第２个基因值２，５为当前堆场中空场地的个数．染色体变异如图５所示．

图３　染色体Ｆｉ．３　Ｃｈｒｏｍｏｓｏｍｅｇ

）解码．计算每个分段的堆场计划产生的分ｉｉ　　（

段移动度并汇总．具体过程如下：

①根据堆场状态矩阵建立堆场节点状态模型．

逐步向外探寻最短路径．与每个②从Ｖ０出发，

，点对应记录一个数（称为这个点的标号）它表示从，称为Ｐ标号）或者是最短Ｖ０到该点的最短路权（

称为Ｈ标号）将直接与Ｖ０相连的点路权的上界（．的Ｈ标号定义为它们之间的距离；否则，为无穷大．将Ｈ标号小于无穷大的点放入最前沿点集合Ｓ．在集合Ｓ中每次把其中数值最小的一个Ｈ标号点修即已确定最短路径的点，记改为具有Ｐ标号的点（

，为Ｖｎ）考虑各个与Ｖｎ直接相连的点Ｖｃ的Ｈ标号是否更新．若Ｖ０到点Ｖｎ之间距离Ｌ０ｎ加上Ｖｎ到Ｖｃ之间的距离Ｌ则将点Ｖｃ的ｎｃ小于点Ｖｃ的Ｈ标号，　否则，不变．直到Ｈ标号值修改为Ｌ０ｎ与Ｌｎｃ的和；进、出场分段停放位置节点的Ｈ标号被修改为Ｐ标号，算法终止．

确定具有最小分段移动度的路１）③根据式（

并记录路径．径，

每安排一个分段，④依次安排分段堆场计划．

则相应更新堆场状态矩阵以及堆场节点状态模型．

）计算方案产生的分段移动度．１⑤根据式（

（）选择．本文采用比例选择算子，使个体按照３

与适应度倒数成正比的概率向下一代群体繁殖．（）交叉．随机产生染色体Ｏ（基因值为０或４），将双亲的基因，在染色体Ｏ的基因值为１对应１

如图４所示．的位置处互换，

图６　堆场的初始状态ａｒｄＦｉ．６　Ｉｎｉｔｉａｌｓｔａｔｅｏｆ　　　ｙｇ

图５　染色体变异图

Ｆｉ．５　Ｍｕｔａｔｉｏｎｏｆｃｈｒｏｍｏｓｏｍｅｓ　　ｇ

３　实例验证与结果分析

３．１　实例验证

以上海某　　为验证模型及算法的可行与正确性，

大型船厂一周计划期内的船舶分段堆场计划调度为利用Ｖ例，ｉｓｕａｌＳｔｕｄｉｏ２０１０软件，在处理器为１．２　

输入参ＧＨｚ，内存为２ＧＢ的计算机上进行求解．数如下：①堆场初始状态；②周期Ｔ内进出场分段

的数量、顺序及计划时间；种群规模为③算法参数：染色体长度为５交叉概率为０．变异概率为１００，５，９，

算法终止代数为１某堆场的初始状态如图６０．１，００．所示，图中有８其中５１个作业场地，８个场地被占用，Ｂｎ为放置在场地上的分段名．

　　按时间顺序排列的一周内堆场计划如表１所示．表有３从Ｂ８７个进场分段（２依次命名到，若在一周内某进场分段进场Ｂ１１８个出场分段，１８）

后又要从堆场中出来，则其作为出场分段时所在位置表示为未定的Ｖ０通过算法程序确定进场分段０．在堆场中的停放位置以及进出场分段从停放位置到

图４　染色体交叉图

Ｆｉ．４　Ｃｒｏｓｓｏｖｅｒｏｆｃｈｒｏｍｏｓｏｍｅｓ　　ｇ

得到一种较优的堆场调度方案如道路Ｖ０的路径，

表２所示．表中，每条移动路径的第一个位置节点，为进出场Ｖｉｉｊ分别是堆场状态矩阵的行与列）ｊ（

分段的停放位置．随着程序的运行，个体的多样性在

）变异．随机生成一个染色体０，在基因值为５　　（

将个体的基因用另一随机产生的１对应的位置上，

１０４０

上　海　交　通　大　学　学　报

表１　一周内堆场计划

Ｔａｂ．１　Ｙａｒｄｓｃｈｅｄｕｌｉｎｉｎｏｎｅｗｅｅｋ　　　ｇ　

第４７卷　

序号１　２　３　４　５　６　７　８　９　１０　１１　１２　１３　１４　

分段属性进进出进进进进进出进出进出进

分段停放位置　

序号１５　１６　１７　１８　１９　２０　２１　２２　

分段属性出进进进进出出进进出出进进进

分段停放位置

序号２９　３０　３１　３２　３３　

分段属性进进出出出进进进出出进进进进

分段停放位置

序号４３　４４　

分段属性进出出进进进进出出进进进进

分段停放位置

Ｂ８２Ｂ８３Ｂ８Ｂ８４Ｂ８５Ｂ８６Ｂ８７Ｂ８８Ｂ１６Ｂ８９Ｂ８４Ｂ９０Ｂ４１Ｂ９１

Ｂ４４Ｂ９２Ｂ９３Ｂ９４Ｂ９５Ｂ３７Ｂ５６Ｂ９６Ｂ９７Ｂ８６Ｂ５７Ｂ９８Ｂ９９Ｂ１００

Ｖ５８Ｂ１０１Ｂ１０２Ｂ８５Ｂ８８Ｂ７７Ｂ１０３Ｂ１０４Ｂ１０５Ｂ１１Ｂ２０Ｂ１０６Ｂ１０７Ｂ１０８Ｂ１０９

Ｂ１１０Ｂ３９Ｂ８３Ｂ１１１Ｂ１１２Ｂ１１３Ｂ１１４Ｂ１３Ｂ８９Ｂ１１５Ｂ１１６Ｂ１１７Ｂ１１８

Ｖ５３Ｖ００

Ｖ１８Ｖ００Ｖ００Ｖ９５

４５　４６　４７　４８　４９　５０　

Ｖ５１Ｖ７２

３４　３５　３６　３７　

Ｖ２４Ｖ００

Ｖ２７Ｖ００Ｖ５５

２３　２４　２５　２６　２７　２８　

Ｖ２２Ｖ３２

５１　５２　５３　５４　５５　

Ｖ００Ｖ７３

３８　３９　４０　４１　４２　

表２　调度方案Ｔａｂ．２　Ｓｃｈｅｄｕｌｉｎｓｃｈｅｍｅｇ　

序号１　

分段

属性进

分段的移动路径

序号

分段

属性进

分段的移动路径

序号

分段

属性出

分段的移动路径

Ｂ８２Ｖ８８Ｖ７８Ｖ７９Ｖ６９Ｖ５９Ｖ４９Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

１８　Ｂ９４Ｖ６７Ｖ５７Ｖ５８Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

３３　Ｂ７７Ｖ９５Ｖ８５Ｖ７５Ｖ６５Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

２　３　４　５　６　７　

Ｂ８３Ｂ８Ｂ８４Ｂ８５Ｂ８６Ｂ８７

进出进进进进

Ｖ３１Ｖ２１Ｖ１１Ｖ０Ｖ１８Ｖ０

Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ３３Ｖ２３Ｖ１３Ｖ０

Ｖ４９Ｖ３９Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ９６Ｖ８６Ｖ７６Ｖ７７Ｖ６７Ｖ５７Ｖ４７Ｖ３７Ｖ３８Ｖ２８Ｖ１８Ｖ０

１９　Ｂ９５进Ｖ７９Ｖ６９Ｖ５９Ｖ５８Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

３４　Ｂ１０３进Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

２０３７　Ｂ２１　Ｂ５６

出出

Ｖ５１Ｖ４１Ｖ３１Ｖ２１Ｖ１１Ｖ０Ｖ７２Ｖ６２Ｖ６３Ｖ５３Ｖ５４Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

３５　Ｂ１０４进Ｖ５５Ｖ４５Ｖ４６Ｖ３６Ｖ３７Ｖ３８Ｖ２８Ｖ１８Ｖ０

３６１０５　Ｂ３７　Ｂ１１３８２０　Ｂ３９　Ｂ１０６４０１０７　Ｂ４１１０８　Ｂ４２　Ｂ１０９４３１１０　Ｂ４４　Ｂ３９４５８２　Ｂ４６１１１　Ｂ４７　Ｂ１１２４８１１３　Ｂ４９　Ｂ１１４５０１３　Ｂ５１９０　Ｂ５２　Ｂ１１５５３１１６　Ｂ５４　Ｂ１１７５５１１８　Ｂ进出出进进进进进出出进进进进出出进进进进

Ｖ５８Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ２２Ｖ１２Ｖ０Ｖ３２Ｖ２２Ｖ１２Ｖ０Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

Ｖ５１Ｖ４１Ｖ３１Ｖ３２Ｖ２２Ｖ１２Ｖ０Ｖ４６Ｖ３６Ｖ３７Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ３４Ｖ３３Ｖ３２Ｖ２２Ｖ１２Ｖ０Ｖ３７Ｖ３８Ｖ２８Ｖ１８Ｖ０

Ｖ５３Ｖ４３Ｖ３３Ｖ３２Ｖ２２Ｖ１２Ｖ０Ｖ３１Ｖ３２Ｖ２２Ｖ１２Ｖ０Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ３１Ｖ３２Ｖ２２Ｖ１２Ｖ０Ｖ３３Ｖ３２Ｖ２２Ｖ１２Ｖ０Ｖ３２Ｖ２２Ｖ１２Ｖ０Ｖ２４Ｖ１４Ｖ０Ｖ２７Ｖ１７Ｖ０Ｖ１８Ｖ０Ｖ２２Ｖ１２Ｖ０Ｖ２４Ｖ１４Ｖ０Ｖ２７Ｖ１７Ｖ０

２２　Ｂ９６进Ｖ８２Ｖ７２Ｖ６２Ｖ６３Ｖ６４Ｖ５４Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

８　９　

Ｂ８８Ｂ１６

进出进出进

Ｖ３７Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ２７Ｖ１７Ｖ０Ｖ２７Ｖ１７Ｖ０

Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

Ｖ７６Ｖ７７Ｖ６７Ｖ５７Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

２３　Ｂ９７２４８６　Ｂ２５　Ｂ５７

进出出

１０８９　Ｂ１１　Ｂ８４１２　Ｂ９０

Ｖ５９Ｖ５８Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ４９Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ７３Ｖ６３Ｖ５３Ｖ５４Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

１３　Ｂ４１出Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

２６　Ｂ９８进Ｖ９２Ｖ８２Ｖ７２Ｖ７３Ｖ６３Ｖ５３Ｖ５４Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

１４　Ｂ９１进Ｖ９４Ｖ８４Ｖ８３Ｖ７３Ｖ６３Ｖ５３Ｖ５４Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

２７　Ｂ９９

进

Ｖ６３Ｖ５３Ｖ５４Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

１５４４　Ｂ１６　Ｂ９２

出进

Ｖ５８Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ８３Ｖ７３Ｖ６３Ｖ５３Ｖ５４Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

２８　Ｂ１００进Ｖ５４Ｖ５５Ｖ４５Ｖ４６Ｖ４７Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

２９１０１　Ｂ３０　Ｂ１０２３１８３　Ｂ３２　Ｂ８８

进进出出

Ｖ６１Ｖ５１Ｖ４１Ｖ３１Ｖ２１Ｖ１１Ｖ０Ｖ４９Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０Ｖ３３Ｖ２３Ｖ１３Ｖ０Ｖ３７Ｖ３８Ｖ２８Ｖ１８Ｖ０

１７　Ｂ９３进Ｖ７７Ｖ６７Ｖ５７Ｖ５８Ｖ４８Ｖ３８Ｖ２８Ｖ１８Ｖ０

第５解开始收敛，收敛时间为３３代后逐渐消失，８３利用本文方法，可安排１周及以上的计划，并且运ｓ．

行算法程序可得到较优的调度方案，充分利用堆场资源，提高作业效率．

　第７期

张志英，等：基于遗传算法的船舶分段堆场调度研究　　

１０４１

３．２　数值试验分析

３．２．１　算法比较分析　堆场调度问题的复杂性主要是由于进场分段不同放置位置的组合造成的．对于由不同方案组成的解空间可以通过分支定界法（）简称“求出最优方案，但Ｂ＆Ｂ实际上是一Ｂ＆Ｂ”

８］

遍历特性使其不能求解大规模问题［种枚举算法，．

时略低于ＧＡ，当分段数大于９，则前者的耗时明显高于后者，２种算法的时间差随分段数增加逐步扩大．随着分段数的增加，可行方案数以几何级数增加，问题规模越来越大，ＧＡ的优越性较Ｂ＆Ｂ就越突出．

在输入分段数为１２）对于９行９列的堆场，３　　（

时，以初始利用率Ｐｂ分别为９０％、８５％、８０％、结果如图８所示．７５％、７０％进行数值试验，Ｂ＆Ｂ的耗时随着堆场Ｐｂ的降低而急剧增大．当Ｐｂ＝８５％时，Ｂ＆Ｂ运行时间需要４４ｍｉｎ，Ｐｂ＜７５％时则不可解．而ＧＡ的耗时呈增长趋势，但相对稳定，且在不同Ｐｂ中均能得出较优解．Ｂ＆Ｂ和ＧＡ在前３次试验中得到相同解，但后者耗时明显低于前者．随着堆场的Ｐｂ逐渐降低，空场地个数则不断增加，可行方案数呈几何级数增长，问题规模越来越大，远远超出了Ｂ＆Ｂ的可求解范围．

现将ＧＡ与Ｂ＆Ｂ从以下两方面进行对比：）在堆场初始状态（（堆场尺寸为９×９，空场１

地数为２相同时，输入不同的分段数进行数值试３）运算结果如图７所示．图中，验，ｎ为分段个数．Ｂ＆Ｂ的耗时随着分段数增加而急剧增加，在分段数为１２，时算法耗时需要４当分段数为１８ｍｉｎ３及以上的试验中则不可解．ＧＡ的时间曲线总体上呈小幅度增加趋势，但相对稳定，而且在不同分段数的试验中总能得出较优解．在分段数为６～１０时２种算法的在分段数为６～９时，分段移动度是一致的；Ｂ＆Ｂ耗

增加分段３．２．２　模型可解性分析　增大堆场尺寸、数量或降低堆场初始利用率，都会提高问题难度．其中堆场尺寸影响算法求解分段的进出场路径，而后当问２个因素增加了进场分段的可选停放方案数．题规模扩大到一定程度时，ＧＡ运行时间也会增大，但可通过适当减小种群规模来满足时间要求．对于１５行１５列及初始状态有６０个空场地的超大规模

当分段数超过１算法收敛时间为调度问题，００个时，

但通过修改算法的内部参数，如将种群规１６８ｍｉｎ．

，模减到６程序收敛时间相应减少到８如０个，１ｍｉｎ表３所示．随着种群规模逐渐减小，算法运行时间随着降低，但分段移动度却不断增加．原因是种群多样性的减少使得算法容易陷入局部最优解．

１０４２

表３　不同参数的结果比较

上　海　交　通　大　学　学　报

第４７卷　

ｒｅｆｏｒａｒｓｈａｌｌｉｎｅｘｏｒｔｃｏｎｔａｉｎｅｒｓ［Ｊ］．Ｅｕｒｏｅａｎ　－ｍ　ｐｇｐｐ　，：ｏｆＯｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ２００９，１９６（２）４６８Ｊｏｕｒｎａｌ　　　－ｐ４７５．

［］钱迈，渠洪涛，等．集装箱堆场作业计划模型及４　江南，

］（）：算法［铁道学报，Ｊ．２００９，３１５８１６．－，，，ＩＡＮＧ　ＮａｎＱＩＡＮ　ＭａｉＱＵ　Ｈｏｎｔａｏｅｔａｌ．Ｍｏｄｅｌ　　Ｊ－　ｇ

ａｒｄｌａｎｓ［ａｌｏｒｉｔｈｍｏｆｃｏｎｔａｉｎｅｒｏｅｒａｔｉｏｎＪ］．ａｎｄ　　　　　　ｙｐｇｐ，（）：ＪｏｕｒｎａｌｏｆｔｈｅＣｈｉｎａＲａｉｌｗａＳｏｃｉｅｔ２００９，３１５８１６．　　　　－ｙｙ　［］５ｈａｏＸＹ，ＬｉＸＹ，ＧａｏＬ，ｅｔａｌ．Ｉｎｔｅｒａｔｉｏｎｏｆ　Ｓ　　　　　　　ｇ

ｒｏｃｅｓｓｌａｎｎｉｎｅｎｅｔｉｃａｎｄｓｃｈｅｄｕｌｉｎａｍｏｄｉｆｉｅｄａｌ　　－　　　－ｐｐｇｇｇ　ｏｒｉｔｈｍ－ｂａｓｅｄａｒｏａｃｈ［Ｊ］．Ｃｏｍｕｔｅｒｓ＆Ｏｅｒａｔｉｏｎｓ　　ｇｐｐｐｐ，（）：Ｒｅｓｅａｒｃｈ２００９，３６３２０８２２０９６．－［］６ｉａｏＬ　Ｈ，ＬｖＳＰ．Ａｎｉｍｒｏｖｅｄｅｎｅｔｉｃａｌｏｒｉｔｈｍｆｏｒ　Ｑ　　　　　　　ｐｇｇ

］ｒｏｃｅｓｓｌａｎｎｉｎａｎｄｓｃｈｅｄｕｌｉｎＪ．ＩｎｔＪｉｎｔｅｒａｔｅｄ　　　　ｐｐｇｇ［ｇ　，（）：ＡｄｖＭａｎｕｆＴｅｃｈｎｏｌ２０１２，５８２７２７７４０．　　－［周莹君，王家海．基于自适应遗传算法的Ｊ７］ｏｂ　沈斌，

］：Ｊ．计算机应用，２００９，２９（４）Ｓｈｏｐ调度问题研究［１６１１６７．－，Ｚ，ＷＡＮＧＨＥＮｉｎＨＯＵ　Ｙｉｎｕｎｉａｈａｉ．　　Ｓ　Ｂ－　Ｊ－ｇｊ

Ｒｅｓｅａｒｃｈｏｆｓｈｏｓｃｈｅｄｕｌｉｎｂａｓｅｄｏｎｓｅｌｆｏｂｒｏｂｌｅｍ　　　　　　－ｐｇｊｐ　　ｅｎｅｔｉｃａｄａｔｉｖｅａｌｏｒｉｔｈｍ［Ｊ］．ＪｏｕｒｎａｌｏｆＣｏｍｕｔｅｒ　　　　ｐｇｇｐ，（）：Ａｌｉｃａｔｉｏｎｓ２００９，２９４１６１１６７．－ｐｐ

［］，８ｈｕｎＣＳ，ＦｌｎｎＪＫｉｒｃａＯ．Ａｂｒａｎｃｈａｎｄｂｏｕｎｄａｌ　Ｃ　　　　　　　－ｇｙ　

ｏｒｉｔｈｍｔｏｍｉｎｉｍｉｚｅｔｈｅｔｏｔａｌｔａｒｄｉｎｅｓｓｆｏｒｍ－ｍａｃｈｉｎｅ　　　　　　　ｇ

］ｒｏｂｌｅｍｓ［ｆｌｏｗｓｈｏＪ．ＥｕｒｏｅａｎＪｏｕｒｎａｌｅｒｍｕｔａｔｉｏｎ　　　ｐｐｐｐ　，（）：ｏｆＯｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ２００６，１７４４１１０．　　－ｐ

Ｔａｂ．３　Ｃｏｍａｒｉｓｏｎｏｆｄｉｆｆｅｒｅｎｔａｒａｍｅｔｅｒｓ　　　ｐｐ

堆场大小

分段数

空场地数

种群规模１００　

１５×１５　

１００　

６０　

６０　３０　

收敛时间／临时分段

ｍｉｎ１６８　８１　２８　

移动次数２６６２７１２８４

４　结　语

综合　　本文通过研究船舶分段堆场的调度过程，

计划分段个数、堆场尺寸等因素，考虑初始利用率、

通过建模并采用遗传算法及启发式算法对其进行求解．仿真结果验证了本文方法的有效性和实用性．参考文献：

［］１ｉｒｎＫ　Ｈ，ＰａｒｋＹ　Ｍ，ＲｌｌＫ　Ｒ．Ｄｅｒｉｖｉｎｄｅｃｉｓｉｏｎ　Ｋ　　　ｙｇ　

ｒｕｌｅｓｔｏｌｏｃａｔｅｅｘｏｒｔｃｏｎｔａｉｎｅｒｓｉｎｃｏｎｔａｉｎｅｒａｒｄｓ　　　　　　　ｐｙ［］，Ｊ．ＥｕｒｏｅａｎＪｏｕｒｎａｌｏｆＯｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ２０００，　　　　ｐｐ（）：１２４１８９１０１．－［］２ｈａｎＣＲ，Ｃｈｅｎ　Ｗ　Ｗ，ＳｈｉＬＹ，ｅｔａｌ．Ａｎｏｔｅｏｎｄｅ　Ｚ　　　　　　　－ｇ　

ｒｉｖｉｎｄｅｃｉｓｉｏｎｒｕｌｅｓｔｏｌｏｃａｔｅｅｘｏｒｔｃｏｎｔａｉｎｅｒｓｉｎｃｏｎ　　　　　　　－ｇｐ　］ａｒｄｓ［ｔａｉｎｅｒＪ．ＥｕｒｏｅａｎＪｏｕｒｎａｌｏｆＯｅｒａｔｉｏｎａｌＲｅ　　　　　－ｙｐｐ，（）：ｓｅａｒｃｈ２０１０，２０５４４８３４８５．－［］３ｅｅＹＳ，ＣｈａｏＳＬ．Ａｎｅｉｈｂｏｒｈｏｏｄｓｅａｒｃｈｈｅｕｒｉｓｔｉｃ　Ｌ　　　　　　　ｇ

上接第１０３５页）　　（

［［５］ａｏＹ　Ｙ．ＤｅｃｉｓｉｏｎｔｈｅｏｒｅｔｉｃｒｏｕｈｓｅｔｍｏｄｅｌｓＣ］　Ｙ　－　　　∥ｇ

Ｐｒｏｃｅｅｄｉｎｓｏｆｔｈｅ２ｎｄＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎ　　　　　　ｇ，ＬＲｏｕｈＳｅｔｓａｎｄＫｎｏｗｌｅｄｅＴｅｃｈｎｏｌｏＮＡＩ．Ｈｅｉ　　　　－ｇｇｇｙ：，ｄｅｌｂｅｒＳｒｉｎｅｒ２００７：１１２．－ｇｐｇ

［６］ａｏＹ　Ｙ，ＺｈａｏＹ．Ａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎｉｎｄｅｃｉｓｉｏｎ　Ｙ　　　　　－［］，ｔｈｅｏｒｅｔｉｃｒｏｕｈｓｅｔｍｏｄｅｌｓＪ．ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅｓ　　　　ｇ２００８，１７８：３３５６３３７３．－［７］ｕＱ　Ｈ，ＺｈａｎＬ，ＣｈｅｎＤＧ，ｅｔａｌ．Ｇａｕｓｓｉａｎｋｅｒ　Ｈ　　　　　－ｇ　

：Ｍ，ｎｅｌｂａｓｅｄｆｕｚｚｒｏｕｈｓｅｔｓｏｄｅｌｕｎｃｅｒｔａｉｎｔｍｅａｓ　　　－ｙｇｙ　　ｕｒｅｓａｎｄａｌｉｃａｔｉｏｎｓ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆ　　　　ｐｐ

，ＡｒｏｘｉｍａｔｅＲｅａｓｏｎｉｎ２０１０，５１：４５３４７１．　－ｐｐｇ

［８］ｕＱ　Ｈ，ＹｕＤＲ，ＰｅｄｒｃｚＷ，ｅｔａｌ．Ｋｅｒｎｅｌｉｚｅｄ　Ｈ　　　　　ｙ

ｆｕｚｚｒｏｕｈｓｅｔｓａｎｄｔｈｅｉｒａｌｉｃａｔｉｏｎｓ［Ｊ］．ＩＥＥＥ　　　　ｙｇｐｐ　

，Ｔｒａｎｓａｃｔｉｏｎｏｎｎｏｗｌｅｄｅｎｄａｔａｎｉｎｅｅｒｉｎ　　Ｋ　ａ　Ｄ　Ｅｇｇｇ（）：２０１１，２３１１１６４９１６６７．－［９］　李华雄，周献中，李天瑞，等．决策粗糙集理论及其

研究进展［Ｍ］．北京：科学出版社，２０１１．

［］１０ｉＨ　Ｘ，ＺｈｏｕＸＺ，ＺｈａｏＪＢ，ｅｔａｌ．Ａｔｔｒｉｂｕｔｅｒｅｄｕｃ　Ｌ　　　　　　　－：ｔｉｏｎｉｎｄｅｃｉｓｉｏｎｔｈｅｏｒｅｔｉｃｒｏｕｈｓｅｔｓｍｏｄｅｌａｆｕｒｔｈｅｒ　　－　　　　ｇｉｎｖｅｓｔｉａｔｉｏｎ［Ｃ］ｏｕｈＳｅｔｓａｎｄＫｎｏｗｌｅｄｅＴｅｃｈ∥Ｒ　　　　－ｇｇｇ，Ｌ：Ｓ，２ｎｏｌｏＮＣＳ．ＢｅｒｌｉｎｒｉｎｅｒＰｕｂｌｉｓｈｅｒ０１１，　ｐｇｇｙ６９５４：４６６４７５．－［］１１ｌａｋｅＣＬ，ＭｅｒｚＣＪ．ＵＣＩｒｅｏｓｉｔｏｒｏｆｍａｃｈｉｎｅ　Ｂ　　　　　　ｐｙ　

／（［ｌｅａｒｎｉｎｄａｔａｂａｓｅｓ［ＥＢＯＬ］．２０１００３０１）２０１２０６－－－－ｇ　］：／／／ＭＬ０４．Ｈｔｔｗｗｗ．ｉｃｓ．ｕｃｉ．ｅｄｕ／～ｍｌｅａｒｎＲｅ－ｐｏｓｉｔｏｒ．ｈｔｍｌ．ｐｙ