现代造船中的船体以分段为单位分区域堆置加工，为了实现体积重量都很大的分段在各个生产车间和堆场之间的运输，一般使用大型动力平板运输车(以下简称平板车)^[1-2]。据统计，船厂每个分段从成型到最后在船坞搭载成整船的过程中，需要由平板车在厂区内不同的车间或堆场间转运10次甚至更多, 而每艘船一般被分割成上百个分段。实际生产中，由于在厂区内的分段运输量大，运输效率低，不少船厂不得不在夜间也进行分段运输的工作。造成该局面的主要原因之一是对分段运输缺乏良好的调度计划。因此制定合理的平板车调度计划迫在眉睫。

在平板车的实际运输过程中，车辆要沿着堆场道路或空堆位行驶，需结合分段任务间的约束关系安排顺序和车次。Lee等^[3-4]定义了分段的空间调度问题，将平板车作为重要的资源约束。Park等^[5]对韩国一造船厂的分段位置分配进行研究，提出以减少分段无效移动目标，来降低平板车运输成本。Roh等^[6]研究了船厂内多平板车的场外干涉，并用蚁群算法得到初始解。Byung等^[7]研究了多规格平板车下的分段运输问题，以实现平板车延迟、拖期时间最小。Woo等^[8]对于分段在整个造船厂内的运输过程流程优化进行了研究。张志英等^[9]构建了基于最短路径算法的分段堆场调度，用迪杰斯特拉算法计算了平板车的路径。陶宁蓉等^[10]研究了平板车并车运输问题。但这些研究和算法都是考虑了场外的平板车运输过程，并没有涉及平板车场内部分的调度及平板车的分配问题。

本文以平板车最小空载时间为优化目标，考虑了堆场内部分段的位置约束，运用遗传算法对平板车在船厂中的多堆场场内运输调度问题进行建模。在考虑平板车数量、运输能力、分段运输任务之间先后约束关系等因素的条件下确定平板车任务执行顺序，从而减少无效物流时间提高平板车运输分段的效率。结合某船厂的实际数据对模型进行了实例验证。

1 平板车调度问题描述与假设

当前调度期内有n个待执行的分段运输任务和若干辆不同运载能力的运输平板车。运输任务之间存在先后约束关系。平板车有多种型号，一个分段运输任务必须由满足承重需求的一台平板车运输至目的地。将所有分段任务分派给各个平板车，并确定各任务在所分配平板车上的运输顺序和执行时间。任务需要在释放后执行，进涂装、冲砂的移动任务需要尽快执行，调度的要求是使物流时间最小化，更为具体的说是在保证准时性与任务执行路径最优的前提下，减少无效物流时间，故以最小化平板车空载时间为主要优化目标。

在平板车运输中应遵循如下规则及假设：1)分段运输任务存在释放时间，所有任务只能在其释放后才可执行；2)平板车运输分段的过程一旦开始执行，不可被其他任务打断；3)平板车在同一时刻最多只能运输一个分段；4)部分任务间存在先后关系，存在先后关系的任务对，在后任务至少需要等到在先任务的分段装载完成后才可以开始执行；5)平板车在运输分段时，提取和放置的要求很严格，其准备时间和分段自身的体积、重量以及结构相关，是不可忽略的；6)平板车空载和运输分段时的运行速度是一定的；7)分段运输的调度周期为一个工作日；8)平板车只能运输自身承载能力内的分段；9)在同一地点进行任务交接是调度目标之一，因此在平板车任务调度时，对于此种情况，不计算空载行驶距离。

根据以上规则及假设，本文拟确定平板车堆场内部干涉条件及任务拓扑关系；确定各个任务的运输顺序和执行时间；对平板车的调度方案进行优化。

2 建立平板车调度模型 2.1 平板车任务分类及堆位状态

对于一个给定串行任务序列，序列的具体构成是分段运输申请所展开的衍生任务与目标移动任务。分段运输申请对应一个目标移动任务，但是移动过程中会需要某些分段的临时移动以配合目标移动任务的进行，而这些临时移动对应若干衍生任务，这些衍生任务便成为了该目标移动任务的前置任务。分段运输申请对应的目标移动任务与其相应的衍生移动任务构成了一个分段运输申请所对应的指令族，分段运输申请的执行顺序即构成了指令族的执行顺序，如图 1所示。

在指令族内只有在衍生任务按次序执行完毕后，目标移动任务才可执行，这构成了分段移动任务之间的先后约束，而该先后约束的本质是多个任务不能对堆位这一资源同时占用。任务之间先后约束的来源是多个运输任务的执行需要占用相同的资源。在分配平板车的情况下，还需要执行堆位、道路任务。调度方案必须完全满足分段任务之间的约束关系，才能保证获得的解决方案是可行的。

2.2 调度任务拓扑关系

对图 1的指令进行分析，3个指令族共11个任务都是某堆场区域的移动指令，如图 2所示，左侧指令为衍生任务指令，右侧指令为移动申请对应的目标移动指令。目前仅有一个序列约束，即目标任务必须在衍生任务执行完成后才可执行。若移动指令3、移动指令5、移动指令9在堆场内的移动路径有重合干涉，以中间连接线示意。分段移动为将分段从原始堆位运送至目标堆位，在堆场内的移动路径为空堆位的组合。

2.3 平板车调度模型 2.3.1 数据预处理

时间t_i^l是一个比较固定的量，不同分段间差异不是很大，所以计算时只需要确定分段提取基本时间t_basic^l加上时间冗余量c₁

$ t_{\rm{i}}^l = t_{{\rm{basic}}}^l + {c_1} $

(1)

式中：i为平板车运输任务编码，某个运输任务的编号为i，i=1, 2, …, n；t_i^l为任务i的分段提取时间；t_basic^l为分段提取基本时c₁为分段提取时间冗余量。

共包含两部分：1)堆场内的移动时间；2)在道路上的移动时间。根据出堆场与入堆场的移动距离，任务两堆场之间的最短移动距离，结合平板车负载情况下的移动速度，加上一定的冗余量c₂，即求得平板车负载移动时间。因船厂内部进行车速管控，车辆均能达到此速度，因此在限制速度下取v^l作为平板车负载下的移动速度。负载移动时间t_i^y为

$ \begin{array}{*{20}{c}} {t_i^y = \left[ {d\left( {{j_{1,i}},{j_{2,i}}} \right) + d\left( {{j_{2,i}},{j_{3,i}}} \right) + } \right.}\\ {\left. {d\left( {{j_{3,i}},{j_{4,i}}} \right)} \right] \div {v^l} + {c_2}} \end{array} $

(2)

式中：t_i^y为任务i平板车负载移动时间；j_{1, i}为任务i移动的分段所在的原始堆位编号，j_{1, i}=1, 2, …, m；j_{2, i}为任务i出堆场的边界堆位编号，j_{2, i}=1, 2, …, m；j_{3, i}为任务i进堆场的边界堆位编号，j_{3, i}=1, 2, …, m；j_{4, i}为任务i所要移动至的目标堆位编号，j_{4, i}=1, 2, …, m；d(j₁, j₂)为两堆位j₁与j₂之间的移动距离，j₁=1, 2, …, m; j₂=1, 2, …, m；v^l为平板车载有分段时的速度，单位为m/min；c₂为分段负载移动时间冗余量。

时间t_i^u如表达式(3)所示，与分段长度、分段形状有一定关系，不同分段间有较大差异，计算时不同分段以一定系数α乘以分段放置基本时间t_basic^u加上冗余量c₃得到分段放置时间。

$ t_i^u = \alpha t_{{\rm{basic}}}^u + {c_3} $

(3)

式中：t_i^u为任务i分段放置时间；α为任务i分段放置时间系数；t_basic^u为分段放置基本时间；c₃为分段放置时间冗余。

短平直分段α=1，短平直分段α=2，曲面分段α=4。任务i与任务h之间的堆场外空载移动时间t_ih^p包含两部分：1)堆场内的移动时间；2)在道路上的移动时间。根据堆位分配模块得到平板车在堆场内的移动距离，根据最优路径子模块得到两任务之间的最短移动距离。因船厂内部进行车速管控，车辆均能达到此速度，因此在限制速度下取v^e作为平板车空载下的移动速度。结合平板车空载情况下的移动速度，加上一定的冗余量c₄，即求得平板车空载移动时间为

$ \begin{array}{*{20}{c}} {p{t_{ih}} = \left[ {d\left( {{j_{4,h}},{j_{3,h}}} \right) + d\left( {{j_{3,h}},{j_{2,h}}} \right) + } \right.}\\ {\left. {d\left( {{j_{{2_h}}},{j_{1,h}}} \right)} \right] \div {v^e} + {c_4}} \end{array} $

(4)

式中：c₄为分段空载时间冗余量；v^e为平板车空载时的速度，单位为m/min；t_ih^p为先执行任务i再执行任务i₁之间的平板车空载时间，h=1, 2, …, n。

2.3.2 优化目标及约束条件

平板车车每次执行任务与空载时所行驶的路径均为当前最优路径的前提下，保证准时性，且使平板车任务与任务间空驶时间最短优化目标为

$ \begin{array}{*{20}{c}} {T = a\sum\limits_{l = 0}^{{m_1}} {\sum\limits_{h = 0,h \ne i}^n {\sum\limits_{i = 0}^n {{z_{ihl}} \cdot p{t_{ih}}} } } + }\\ {b\sum\limits_{i = 0}^n {\left( {{x_i} - r{t_i}} \right)} } \end{array} $

(5)

式中：a，b分别为空载时间，拖期时间的系数，且a+b=1。x_i为任务i的开始执行时间；rt_i为任务i的释放时间；z_ihl=1，平板车l在执行任务i后执行任务h，否则执行其他任务。

约束条件：

$ {x_i} \ge r{t_i} $

(6)

$ \sum\limits_{l = 1}^{{m_1}} {{y_{il}}} = 1 $

(7)

$ {x_i} + l{t_i} \le {x_h} $

(8)

$ {x_j} \ge {x_i} + t{a_i}\sum\limits_{h = 1}^n {{z_{ihl}} \cdot p{t_{ih}}} $

(9)

$ {y_{il}} = 1,C{C_l} \ge C{N_i} $

(10)

当y_il=1，任务i由平板车l执行，否则由其他平板车执行；CN_i为第i个运输任务的运输能力需求；j为某个堆位的编号，j=1, 2, …, m；l为某辆平板车的编号，l=1, 2, …, m₁；C_l^C为第l辆平板车运输能力；t_i^a为任务i所需执行时间。

约束式(6)保证了任务必须在释放后方可执行；每一个任务被执行且仅被执行一次；约束式(7)保证了每一个任务被执行且仅被执行一次；约束式(8)保证了任务i若与任务h存在先后约束，任务h需要在先任务i提取结束后开始执行；约束式(9)平板车l执行完任务i后紧接着执行任务h；约束式(10)保证了平板车的运输能力大于等于任务需求运输能力。

3 构建遗传算法求解 3.1 算法描述

不考虑平板车在道路上的干涉，那么可以采用经典的遗传算法进行求解，遗传算法在车辆调度的优化研究中应用很广。但对于复杂约束优化问题，遗传算法需要根据具体问题采取相应的约束处理方法来保持算法的适用性和结果的可行性，其中最为常用的约束处理方法是罚函数法和染色体修正法。罚函数的缺点是很难使算法产生满足复杂约束的可行解，而染色体修正法是通过对不可行解的修正使其满足约束条件，适用于复杂约束问题。算法以遗传算法为框架，构建算法的流程如图 3。

3.2 产生初始种群

该问题的包括任务的分配和调度顺序两个部分，调度任务采用双编码，每个基因可表示为(任务，平板车)。

通常，初始种群的个体是随机产生的。但由于随机产生的个体很难满足优化问题的约束条件，特别是工序约束要求，因此，对不可行个体的染色体进行修正也是十分必要的。

3.3 选择与变异

根据平板车调度任务拓扑关系解法，依次确定各任务的开工时间。任务拓扑关系的解法如图 4所示，其解法步骤如下：

1) 读取所有分段移动任务i与其相应的堆场内移动路径。

2) 读取所有堆场内移动路径含有堆位j的分段移动任务，按序排列并重新编号构成任务j的干涉任务序列{干涉任务1, 干涉任务2, …, 干涉任务f}，f₁=f₂=0。

3) 若堆位j是干涉任务f的目标堆位，则记录f₁=f，同时干涉任务f₂+1, …, f₁-1是干涉任务f₁的前置任务，干涉任务f₂是干涉任务f₂+1, …, f₁-1的前置任务。

4) 若堆位j是干涉任务f的起始堆位，则记录f₂=f，同时干涉任务f₁是干涉任务f₂的前置任务。

5) 返回3)，直到所有干涉任务都判定完毕。

6) 干涉任务f₂是干涉任务f₂+1, …, f₁-1的前置任务。返回2)，直到所有堆位都循环完毕。

确定开工时间的详细步骤如下：

1) 从基因中提取分段运输任务的序列和平板车分配，平板车的初始位置以及可调用时间。

2) 确定任务的开工时间x_i。

① 获取该任务的所有先任务完成时间；

② 获取平板车上一任务完成时间，加上达到该任务执行地的空载时间(2.5×pt_ih)，相加得平板车可调用时间；

③ 取两时间的较大值作为任务开工时间；

3) 更新平板车的位置与任务完成时刻(x_i+2.5×ta_i)。

4) 所有任务调度完成后，程序结束。

数学模型中的目标函数可以用来对个体的表现进行评价。目标函数的值越小，适应度函数的值也越小，表示个体的适应度越高。

选择操作采用轮盘赌的方法。随机从种群中选择两个个体，保留适应度高的个体。重复上述过程直到获取产生后代所需的个体数。这里采用调度问题常用的部分匹配交叉(partially matched crossover，PMX)策略。变异操作采用单点变异法。采用单点变异时，变异点处的父个体基因进行变化，而其他位置的基因保持不变。部分匹配交叉策略表示如下:

1) 随机选择父代两个个体基因上的两个交叉点。

2) 交换父代个体两交叉点之间的基因，交叉点之外的基因保持不变。

3) 确定两个交叉父代中基因的映射关系。即理清并标记出交叉段基因的关联关系。

4) 根据3)确定的基因映射关系，修复子代中由于交叉导致的重复基因。

调度序列的变异操作即对一个父代染色体中随机选择两个位置，其中一个插到另一个位置的前面。同样，交叉变异后得到的后代先要进行可行性检验以及基因修复。

3.4 个体可行性判断及修复

遗传算法在无约束和简单约束的优化问题中表现很好，但在处理复杂约束优化问题时，需要采取一定的措施来保持遗传算法的适用性和算法结果的可行性。在初始种群产生时，以及个体进行交叉、变异后，可能会存在个体是不可行解，则需要采用染色体修复。

经过几代进化后，种群中出现不可行解的几率增加，主要原因是，遗传算法的交叉和变异都是随机操作。对于遗传算法产生的个体的可行性的判断主要基于数学模型所描述的约束关系。如果个体是可行的，则不需要对其进行任何处理；否则，对个体中的不可行染色体进行修复。可行性的判断包括：是否满足承重约束、任务序列是否满足任务前后置关系、对于由于平板车承重约束导致的个体不可行的基因，修复方式是将任务分配给符合承重约束的平板车。

4 平板车调度实例

为验证所建模型的可行性和正确性，以上海某大型船厂一周内的船舶分段堆场计划调度为例，使用c#软件模拟以上算法并求解。

根据分段的具体信息，平板车的载重量，将任务序列重新排序，为每组任务分配相应的平板车，给出调度时间。输入的参数包括：当前堆场占用信息、分段基本信息、平板车基本信息、任务序列及其调运路线。在分段基本信息中包含分段号、重量长宽等几何要素、进出场时间、堆放的位置信息。平板车基本信息如表 1所示，平板车只能运输重量小于额定载重的船体分段。

任务序列如表 2所示，分段编号由小到大排列，并给出了任务的初始及终止位置，例如分段编号为1的任务是由曲面车间出发，要运输到预舾装车间，进行舾装的预处理等工艺操作；如分段编号为10的任务是由初始堆场堆位T1112，运送到临时堆置分段的堆场中临时放置；载入分段编号为12的任务是将堆置在堆位T1114中的分段运送到总组平台进行总组。

表 3输出结果为平板车共有3辆，有30个分段任务，通过程序确定任务的执行顺序以、平板车的选取方式以及平板车任务的起止时间。

由表 3可以计算出1号平板车空载时间为528 min，2号平板车空载时间为820 min，3号平板车空载时间为537 min。可以算出其空载率为0.535，相比传统0.6以上的空载率，减少了平板车空载时间。由表 4可得出随着平板车数量的增多，其空载率逐渐下降，相比调度员凭经验这种方式更加方便快捷，避免了场内调度的运输任务冲突和道路重复占用。

如图 5给出了迭代次数与适应度函数之间的关系。在迭代200次时，计算机运行时间较为合适，且能得到较优的运算结果。

随着平板车数量的增加分别计算其空载率，当平板车数量为3时，空载率为0.535；平板车数量为4时，空载率为0.527；平板车数量为6时空载率为0.518，空载率在平板车数量较少时会随着其数量的增多而降低，而在传统的依靠调度员经验调度时空载率会明显提高。

实际生产中，平板车的分配，任务序列的排程主要由调度员凭经验完成，且只能排数量较少的任务计划。利用本文所研究的方法，可安排数量较多的任务分段及更多数量的平板车，并且能使平板车充分利用，空载时间较少，提高堆场中分段调运效率、降低成本。程序结果表明用遗传算法来解决平板车的分配问题是有可行解的，鉴于运行程序的时间限制，采用迭代200次左右的较优解生成问题的解决方案，系统输出任务的执行顺序、平板车与分段间的对应关系和执行终止任务的时间。相比传统分配方法有较大优势。

5 结论

1) 考虑了平板车相互干涉的条件及拓扑关系，避免了调度过程中任务数量较大，平板车数量较多时任务及平板车之间的冲突和堆位的重复占用。

2) 以空载率为研究对象，并据此结合遗传算法对平板车调度序列进行求解，其空载率相比传统按照调度员经验的分配方式有明显优势，能够解决分段任务数量较大的调度状况。

3) 结合遗传算法的平板车调度方式，计算速度较快能够大幅改善依靠人工即时分配平板车造成的资源浪费和杂乱无章的现状，使堆场的平板车资源得到充分的利用，从而减少空载时间降低运输成本。