本发明涉及航运技术领域，特别涉及一种船体分段堆场的调度方法及装置。
背景技术：
现代造船模式中船体建造以中间产品即分段作为生产的基本作业单元进行船体建造。分段在建造车间建造成型后，经过涂装、舾装等工艺再上船台合拢为整船，再对整船进行一些涂装、舾装工作，最后才能下水。分段的体积和重量大大超过一般车间生产的工件，而且分段无论是建造还是存放的时候都不能够堆积，因此分段在成型后、合拢前需要占用船厂内大量的空间用于存放。这类专门划分出来用于分段存放的区域称之为“分段堆场”。分段堆场主要用于临时存放分段，并且承担一部分分段建造后期工作，如分段建造后期的报验、修补、打磨、预舾装等。近年来，随着造船工艺水平和调度效率的不断提高，分段堆场的空间资源紧缺、调度管理落后已成为影响船厂物流系统正常运转的制约因素。对分段堆场资源的合理计划，提高分段堆场的利用率、降低堆场的运作成本是提高现代造船水平的重要因素。
分段堆场空间调度不同于分段建造车间的空间调度。现有的研究分段建造车间的空间调度问题不需要考虑分段在移动路径上的空间需求，然而分段堆场空间调度除了要考虑分段的时间和所需空间的约束，还需要考虑分段在运输过程中对路径上空间的需求。目前，关于分段堆场上资源调度问题的研究主要是针对分段堆位的分配研究。我国当前造船厂中，堆场作业计划基本是依赖有一定经验的工作人员进行人工编排，因计划不当导致临时移动过多的情况常有发生。在理论和应用上有必要开展面向船厂分段堆场堆位资源调度问题的研究及应用，一方面可以提高分段堆场的调度效率，节约成本，提高利用率，另一方面实现与现代造船模式的接轨。
技术实现要素：
本发明实施方式的目的在于提供一种分段堆场的调度方法，通过研究分段堆场堆位分配的策略、分段临时调度的策略，并结合以上两个调度策略对分段堆场的分段调度任务进行优化，提高了分段堆场的调度效率，降低了分段堆场的运行成本。
为解决上述技术问题，本发明的实施方式提供了一种船体分段堆场的调度方法，包括：为进入分段堆场的分段分配堆位，建立第一分段临时移动率模型；求解第一分段临时移动率模型；其中，所述第一分段临时移动率模型的目标函数为计划期内的所有分段进场和出场操作时的在场分段临时移动次数。
本发明实施方式相对于现有技术而言，主要区别及其效果在于：通过研究分段堆场堆位分配的策略、分段临时调度的策略，并结合以上两个调度策略对分段堆场的分段调度任务进行优化，提高了分段堆场的调度效率，降低了分段堆场的运行成本。
另外，为进入分段堆场的分段分配堆位时，选择堆位自由度最小的堆位。
另外，为进入分段堆场的分段分配堆位时，选择堆位自由度变化值最小的堆位。
另外，进入分段堆场的分段分配堆位时，选择堆位影响度值最小的堆位。
另外，船体分段堆场的调度方法还包括：对第一分段临时移动率模型进行分段临时移动调度；对第一分段临时移动率模型进行优化，得到第二分段临时移动率模型；求解第二分段临时移动率模型；其中，分段临时移动调度是针对进场和出场分段的运输路径上的阻挡分段的堆位调整。
另外，所述对第一分段临时移动率模型进行分段临时移动的步骤中，采用阻挡分段最少的路径选择原则确定分段在堆场内的运输路径。
另外，所述对进场分段的运输路径上的阻挡分段的堆位调整包括：将阻挡分段向里移动，而进场分段则放置在原阻挡分段所在的堆位；先将阻挡分段移出，待进场分段放置对应堆位后，再将阻挡分段放回原来的堆位；在堆场上存在其他空堆位时，将阻挡分段移至其他堆位，所选的新堆位不得在进场分段的移动路径上。
另外，所述对出场分段的运输路径上的阻挡分段的堆位调整包括：先将阻挡分段移出，待出场分段离开后，再将阻挡分段放回原来的堆位；先将阻挡分段移出，待出场分段离开后，将阻挡分段填补到出场分段的堆位；在堆场上存在其他空堆位时，将阻挡分段移至其他堆位，所选的新堆位不得在出场分段的移动路径上。
另外，所述求解第二分段临时移动率模型具体为，利用禁忌搜索算法求解第二分段临时移动率模型。
附图说明
图1是根据本发明实施方式提供的分段堆场的示意图；
图2是根据本发明实施方式提供的分段堆场第五天调度任务执行示意图；
图3是根据本发明实施方式提供的船体分段堆场的调度方法流程图；
图4是根据本发明实施方式提供的堆场布局为分段i进场前的分段堆场堆存状态示意图；
图5是根据本发明实施方式提供的另一堆场布局为分段i进场前的分段堆场堆存状态示意图；
图6是根据本发明实施方式提供的进场分段的堆位选择示意图；
图7是根据本发明实施方式提供的分段出场时的三种临时移动策略示意图；
图8是根据本发明实施方式提供的分段任务序列示意图；
图9是根据本发明实施方式提供的邻域搜索过程示意图。
具体实施方式
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合附图对本发明的各实施方式进行详细的阐述。然而，本领域的普通技术人员可以理解，在本发明各实施方式中，为了使读者更好地理解本申请而提出了许多技术细节。但是，即使没有这些技术细节和基于以下各实施方式的种种变化和修改，也可以实现本申请所要求保护的技术方案。
本发明实施方式涉及一种船体分段堆场的调度方法，本实施方式的调度方法可以应用在终端侧设备，如手机，平板电脑等终端设备，也可以应用在网络侧的服务器。
分段堆场(planarstorageyard,psy)用于分段的临时存放，以及分段的报验、修补、打磨以及预舾装等。在船体设计阶段，船体被划分为若干个个分段。船体建造过程即以分段为单位，首先由若干块钢铁板组合焊接分段，然后各个分段经过涂装、舾装等流程，直到最后在船坞搭载合拢成整船。为了协调各车间的工作节拍，船厂划分了若干的区域用于生产流通过程中分段的临时存放。例如，若一分段焊接成型后的下一道工序在涂装车间，实际生产中，该分段从建造车间完工运出后并不是直接运往涂装部，而是先到分段堆场。在分段堆场上完成对分段建造工艺的检验以及修补、打磨等工作，有的分段还会安排部分预舾装工作。而后，根据涂装车间的生产计划确定的各分段时间需求从分段堆场提取该分段。
图1是根据本发明实施方式提供的分段堆场的示意图，如图所示，该分段堆场上划分出4×5个分段堆位，每个分段堆位可存放一个分段，图1(a)为分段堆场的立体示意图，图1(b)为分段堆场的平面示意图。分段建造完成后的体积一般是长10～20米，宽10～15米，高5米左右，而重量一般在100～300吨左右。如此的体积和重量比一般制造业的中间产品大非常多，一般的运输工具根本无法使用。船厂有专门为运输分段设计的平板车(flattransporter，ft)，平板车的轮胎可以自行改变方向，并且自带千斤顶用于抬放分段，其车身是一个大的平台用于放置分段，如图1所示。当平板车在分段堆场内放置分段时，首先需要在堆场内寻找到一块适当大小的空地，并且有足够的空间让平板车载着分段移动到该空地。而后在空地上放置四个2米高的支撑杆，平板车到达空地后将分段放置在这四根支撑杆上，然后自己从分段下面移出。调查显示，平板车提取分段和放置分段通常需要10至30分钟，如果分段的线型较为复杂，可能需要更多的时间来确定分段的着力点，运输过程中对速度也有严格的限制，时间更久。由此可见，每一次的平板车操作都需要耗费不少时间和成本。
分段在堆场内的运输由平板车完成，属于平面运输，在运输过程中，分段的运输路径若要经过其他分段堆位，则相关的分段堆位上不能存放分段，对于已经存放分段的分段堆位则必须将分段暂时移开，即需要进行临时移动操作。根据分段堆场的布局，若平板车在堆场内斜线行驶，干涉到的分段堆位相对比较多。在堆场比较空的情况下矛盾不明显，但是一旦堆场上存放了一定数量的分段，斜线行驶就不可行了。此外，虽然平板车的车轮可以定点转方向，但是在装载了分段时该操作的成本还是很高的。因此，本章对平板车在分段堆场内的行驶路径进行了限制——只能够沿平行或垂直于分段堆位的方向行驶，即平板车一旦进入分段堆场范围内，其行驶方向只能够是直上、直下、直左和直右。而在调度过程中，分段在分段堆场内的运输路径也是调度的内容之一。
分段在堆场内的运输由平板车完成，属于平面运输，在运输过程中，分段的运输路径若要经过其他分段堆位，则相关的分段堆位上不能存放分段，对于已经存放分段的分段堆位则必须将分段暂时移开，即需要进行临时移动操作。根据分段堆场的布局，若平板车在堆场内斜线行驶，干涉到的分段堆位相对比较多。在堆场比较空的情况下矛盾不明显，但是一旦堆场上存放了一定数量的分段，斜线行驶就不可行了。此外，虽然平板车的车轮可以定点转方向，但是在装载了分段时该操作的成本还是很高的。因此，本章对平板车在分段堆场内的行驶路径进行了限制——只能够沿平行或垂直于分段堆位的方向行驶，即平板车一旦进入分段堆场范围内，其行驶方向只能够是直上、直下、直左和直右。而在调度过程中，分段在分段堆场内的运输路径也是调度的内容之一。
在分段堆场上，针对分段的运输操作可以分为以下三类：
将要进场的分段移入堆场的某个堆位；
将要出场的分段移出堆场；
对已经放置在堆场上的分段进行临时移动。
如图2所示的一个4×3的分段堆场。每个位置上的分段都标示了其到达和离开堆场的时间，如63表示该分段第3天进场，第6天离场。假设在第五天，该分段堆场存在两个调度任务：存放75和提取53。为了方便说明，该运输过程中将分段分为：固定位置分段、进场分段、出场分段和临时移动分段这几种类型。为了完成图2左侧的分段堆场调度任务，一个可行的操作方案可以是首先将进场分段75放置到堆场位置(2,2)上；第二步，将分段72从(3,4)转移到(4,4)；最后一步是将分段53从堆场右侧移出堆位(3,3)。
存放进场分段和提取出场分段是由于前后道工序的生产需求产生的运输任务，可以看作是分段堆场的必要操作。对于存放分段的操作，我们需要确定它在堆场上的位置即终点和到达该位置的移动路径。而对于提取分段的操作，我们需要确定其运输的路径。在执行前两种运输任务时，如果有分段挡住了目标分段的运输路径，我们称之为阻挡分段，则首先要将阻挡分段移开。对阻挡分段的移动操作也是由平板车来完成的，而这类型的移动不属于分段堆场固有的任务，本文称之为临时移动(unproductivemove，um)。临时移动是由于堆场内的空间安排与生产需求不一致，导致堆在里面的分段要先出场，从而阻挡其移动的分段需要重新安排堆位。根据调查表明，在分段堆场的进出场任务执行过程中，由于厂区的平面布局、平板车资源、分段任务等是固定的，而且一次分段移动需耗费很大的时间成本，临时移动次数的多少将是影响分段堆场进出场任务执行时间的决定性因素。临时移动次数的多少直接影响分段堆场的任务执行效率，进而影响计划的准确度。因此问题优化的目标为调度周期内的分段临时移动率——rum。如式(1)所示，rum表示调度过程中的场上分段临时移动次数和总的分段进出场调度任务的比率。
生产实际的分段堆场情况要比图2的问题复杂很多，由于调度缺乏很好的优化算法，过多的临时移动占用了大量的时间、增加了运输的总成本。从描述中我们也可以看到，这类操作是应该尽量避免的，以减少操作的成本和时间。但是另一方面，对于大的场地，空间约束复杂，分段进出场的时间各不相同，临时移动操作又是不可避免的。尤其是在当前，调度计划完全凭计划员的经验，临时移动操作过多已成为分段堆场的一个负担，是当前亟需解决的问题。
总而言之，分段堆场调度问题是指已知分段堆场信息和一组进场和出场分段调度任务的前提下，确定平板车在分段堆场内的操作序列，以及每一次平板车操作的分段对应的起点、终点位置和行走路径。对于存放分段的操作，其起点可以是在上一个工作车间的出口，那么我们需要确定其终点即它在分段堆场上的堆位，和到达该堆位的平板车行驶路径。而对于提取分段的操作，其起点在分段在堆场内占用的堆位，终点可以是下一个工作车间的入口，我们也需要确定其运输的路径。此外，对于临时移动的分段，我们首先要确定哪些分段需要临时移动，其次需要确定临时移动的策略。
图3是根据本发明实施方式提供的船体分段堆场的调度方法流程图，该方法包括：
s301、为进入分段堆场的分段分配堆位，建立第一分段临时移动率模型。
已知一个大小为r×c的分段堆场和一组已知进场时间ati和出场时间rti的分段i，分段堆位分配问题是指为进入分段堆场的分段选择堆位，使得在调度周期t内分段堆场的临时移动率最小。
该问题基于以下假设：
(1)分段的进出场时间是确定的；
(2)分段堆场的尺寸是确定的，是一块矩形场地。堆场划分成虚拟的矩阵型单元格，即分段堆位；
(3)每个分段堆位一次只能存放一个分段，堆场上的分段在放置时不能堆积或重叠；
(4)平板车用于在分段堆场内运输分段，平板车在堆场内走直线，并且与堆场边界垂直或水平；
(5)分段堆场调度的时间单位为天，在同一时间单位内，先执行分段出场任务，再执行分段进场任务；
(6)同一时间单位内的分段任务，不作为阻挡分段计入；
(7)对阻挡分段的临时移动操作只发生在执行提取出场分段或存放进场分段的过程中，其他时间不会执行该操作。
本发明实施方式定义以下参数：
r分段堆场堆位的行数
c分段堆场堆位的列数
m分段堆场堆位数，m＝r×c
j分段堆场堆位编号，j∈{1,2,…,m}
t分段堆场调度周期
t时间单位，本章中时间单位为天
n分段总数
i分段编号，i∈{1,2,…,n}
ati分段i的进场时间
rti分段i的出场时间，在该问题中分段的出场时间记为实际出场的前一天，也就是说，对于分段出场的阻挡分段计算不考虑当天同样出场的分段
pti分段i的分段堆场上存放的时间
本发明实施方式定义以下决策变量：
xi分段i的堆位所在的行
yi分段i的堆位所在的列
osi分段i进场时遇到的阻挡分段个数
ori分段i出场时遇到的阻挡分段个数
基于上述定义的参数和决策变量，分段堆位分配问题的优化目标为最小化分段堆场的分段临时移动率。计算计划期内的所有分段者进场和出场操作时的在场分段临时移动次数。由于在该问题中不考虑在场分段的临时移动策略，即假设阻挡分段先运到一个临时堆放区域，待目标任务完成后再移回原堆位，因此分段临时移动的次数恰好为阻挡分段个数的两倍。将获得的分段临时移动次数除以总的分段调度任务数，即为分段临时移动率，如式(2)所示。
公式(2)即为建立的第一分段临时移动率模型的目标函数。
建立的第一分段临时移动率模型的约束包括：
(1)所有分段的堆位必须在分段堆场内
(2)确定两个分段的堆位之间的位置关系：若分段i'所在堆位在分段i所在堆位的左侧，则lii'＝1，如式(5)；若分段i'所在堆位在分段i所在堆位的右侧，则rii'＝1，如式(6)；若分段i'所在堆位在分段i所在堆位的上方，则uii'＝1，如式(7)；若分段i'所在堆位在分段i所在堆位的下方，则dii'＝1，如式(8)；
(3)获得两个分段i和i'在时间轴上的关系
(4)对于任意两个分段i和i'，只要它们在计划期内都曾存放在分段堆场上，则要么分段i和i'在时间轴上没有交叉，要么分段i和i'在空间上没有重叠。即对于式(5)至式(9)中的变量，必须满足以下约束
(5)若分段i'在分段i进场时已经存放在分段堆场内，则apij等于1，否则为0
(6)若分段i'在分段i出场时已经存放在分段堆场内，则rpij等于1，否则为0
(7)平板车可以从分段堆场的上下左右四面的过道到达或离开堆位。则分段i在进场时，平板车的运输路径为目标堆位对应的四个方向上阻挡分段最少的路径，且该路径上对应的阻挡分段个数即为该分段i进场时的阻挡分段个数osi，如式(4-13)所示，式中每一行表示一个方向上的阻挡分段个数。
(8)同上，分段i在出场时，平板车的运输路径为分段i所在堆位对应的四个方向上阻挡分段最少的路径，且该路径上对应的阻挡分段个数即为该分段i出场时的阻挡分段个数ori，，如式(14)所示，式中每一行表示一个方向上的阻挡分段个数。
s302、求解第一分段临时移动率模型；
算法中涉及的符号定义如下：
sjempi分段i进场前分段堆场上的空堆位集
sjocpi分段i进场前分段堆场上的已被其他分段占用的堆位集
cli分段i的候选堆位集
dj平板车到达堆位j的可选移动方向集，
d平板车移动方向索引，d∈dj
cjd平板车存放分段到堆位j或从堆位j提取分段时，其移动方向d上的堆场堆位集
fdij分段i进场前，堆位j的自由度
vfdij分段i进场前，堆位j的自由度变化值
vobsij如果分段i进场后放置在堆位j上，对分段堆场上已占用堆位的影响度
分段堆场上进场分段堆位分配方法是用于解决调度期内的进场分段如何选择堆位的问题。分段堆场的堆位分配问题是一类np-hard问题。本节基于模型中的目标函数和约束条件，设计了一套启发式算法。假设当前的进场分段为分段i，其选择堆位的算法实施步骤如下。
(1)搜索候选堆位集
所谓候选堆位集，即在分段i进场前，分段堆场上所有的空堆位中，所需临时移动次数最少的堆位的集合。
首先需要获取分段i进场前的分段堆场上所有堆位的堆存状态；而后获得当前所有的空堆位sjempi，对于所有的堆位j∈sjempi，计算平板车到达该堆位所需的最少分段临时移动次数
(2)堆位评价规则
分段堆场的堆位状况复杂多变，为了从cli中选择一个好的堆位，需要给选择堆位制定一个评价指标，本节提出以下几条规则：
规则1：
选择堆位自由度最小的堆位。所谓堆位自由度，是指在当前的分段堆场堆存状态下，可以通过多少条路径到达该堆位。基于本文的假设，平板车在堆场内直线行驶，即堆位的自由度在初始状态下为4。
应用该规则的目的是，优先选择自由度小的堆位给当前的分段，把自由度大的堆位留给后面的分段。
假设图4所示的堆场布局为分段i进场前的分段堆场堆存状态，其中灰色堆位为已占用堆位，白色虚线标识的堆位为空堆位。则可以获得各空堆位的自由度值，如以下矩阵所示。
可以看到堆位(2,3)的自由度为1，是全场空堆位中自由度最小的，因此根据规则1，，我们选择堆位(2,3)放置当前分段。
规则2：
选择堆位自由度变化值最小的堆位。在规则1的基础上，考虑要选择的堆位对堆场上所有空堆位的影响。在分段i进场前堆场上所有空堆位的自由度的和为
同样以图4为例，假设选择了堆位(2,3)，则分段堆场上的布局变为图5所示。
而在分段进场后的堆场布局下，各空堆位的自由度值为如下矩阵。
对比前后两个矩阵，可以看到，除了堆位(2,3)自身的自由度的变化，场上其他空堆位的自由度没有受到影响，则堆位(2,3)的自由度变化值为堆位(2,3)原来的自由度，即为1。对于其他堆位的自由度变化值如以下矩阵所示。
一般情况下，自由度小的堆位对其他堆位的影响也小，即自由度变化值也小。应用该规则的目的是，在规则1的基础上，让当前分段尽量堆放着靠近已有的分段的堆位上。
规则3：
选择堆位影响度值最小的堆位。该规则中堆位的影响度值包括了两个部分：一是该堆位对分段堆场上已占用堆位集sjocpi的影响；一是对分段堆场上其他空堆位集sjempi的影响。前部分不仅考虑到在场分段的堆位布局，还引入在场分段的出场时间，以此作为当前堆位选择的依据之；而后一部分，是考虑到当前的堆位选择结果对后来的进场分段的影响。
首先，获得候选堆位j对分段堆场上已占用堆位的影响度，设定为参数vobsij。新进场的分段i改变了分段堆场的布局，新分段有可能会成为堆场上已有分段在出场时的阻挡分段。则如果分段i放置在候选堆位j，那么分段i成为阻挡分段的次数记为vobsij的值。
其次，对于候选堆位j对分段堆场上其他空堆位的影响，我们采用规则2中描述的堆位自由度变化值vfdij。
由于规则3是基于两个子规则的组合，我们需要将这两个子规则的值进行归一化。
vobsij的归一化如下：
wherevobsijmin＝0,vobsijmax＝max{r-2,c-2,r c-6}
vfdij的归一化如下：
wherevfdijmin＝0,vfdijmax＝r c-2
基于式(16)和式(17)，规则3的堆位选择指标函数值可以表达为：
v＝α·u_vobsij β·u_vfdijwhereα β＝1(18)
堆位选择指标最小的堆位为最优堆位。接下来使用一个例子来说明规则3的堆位选择过程。如图6所示的4×5的分段堆场，r＝4，c＝5，场上已经放置了若干个分段，被占用的堆位上的数字标识，如63表示该分段是第3天进场的，将于第6天出场。假设当前时间为第5天，且有一个分段进场任务95。首先根据分段堆场的布局和在场分段的信息，我们可以获取两个矩阵：空堆位的自由度矩阵和已在场分段的阻挡分段数矩阵，以此来描述堆场空堆位的自由度和分段放置后可能造成的阻挡次数。我们选择其中的三个候选堆位来说明整个流程，见图6中case1-3。以case2为例，假设选择堆位(3,3)，vfdi(3,4)值包括堆位自身的减少值(从2到0)以及堆位(3,4)的自由度减少值(从2到1)。由此可得出vfdi(3,4)＝(2-0) (2-1)＝3。同时，选择堆位(3,3)会导致已堆放在堆位(2,3)的分段在出场时产生一个阻挡分段，则vobsi(3,4)＝1。依据式(16)，vobsijmax＝max{r-2,c-2,r c-6}＝max{2,3,3}＝3，则
以上三种规则，将在算例分析中进行分析比较。基于这三种规则的分段堆位分配算法的详细操作流程的总体描述如下：
step1:初始化各参数，t＝1
step2:获取第t天所有的出场分段任务，依次执行以下步骤
step2.1:计算从各个方向移动目标分段所需的临时移动次数
step2.2:选择step2.1中值最小的那条路径
step2.3:如果没有阻挡分段，则直接提取目标分段，否则先将阻挡分段移出，提取出目标分段，再将阻挡分段运回。
step2.4:更新分段堆场的布局，继续执行step2.1直到当天出场分段运输完毕，转到step3
step3:获取第t天所有的进场分段任务，对每个进场分段i执行以下步骤
step3.1:获取当前堆场上的空堆位，标为cli
step3.2:选择规则1至规则3中的一条规则，对cli中所有候选堆位进行评价，记录各候选堆位的指标值
step3.3:将分段存放在step3.2中评价值最优的堆位
step3.4:更新分段堆场的布局，继续执行step3.1直到当天进场分段运输完毕，转到step4
step5:t＝t 1，返回step2直到所有任务执行完毕
s303、对第一分段临时移动率模型进行分段临时移动调度；
分段临时移动调度是针对进场和出场分段的运输路径上的阻挡分段的堆位调整。因为分段在分段堆场内的运输是通过平板车实现的，只可以进行平面移动，所以存在以下情况：在分段出场时，存在分段所在的堆位的运输路径上堆放了其他的分段，导致目标分段无法移出，此时需要移动其中一条运输路径上的阻挡分段，使得目标分段有足够的空间移出；在分段进场时，存在所选择的堆位的运输路径上被堆场上其他的分段堵住了，导致平板车无法到达目标堆位，此时也需要调整目标堆位某一条路径上的阻挡分段，保证目标分段能够运至选择的堆位。
分段临时移动调度问题即指在执行进场分段存放或出场分段提取的任务时，对分段堆场内阻碍其运输的阻挡分段，如何执行对阻挡分段的操作策略。分段临时移动调度，不仅是为了执行目标任务——存放或提取分段，也可以借助临时移动改变分段堆场的布局，使得分段堆场的堆放更加有序，从而减少以后的临时移动次数。
考虑到本章所有问题的优化目标，我们希望尽量减少分段临时移动的次数。因此，设定只有在执行进场分段存放或出场分段提取的任务的时候，我们才会考虑对在场的分段进行临时移动。
分段临时移动调度问题包括选择要移动的分段和确定分段的临时移动策略以及新堆位这两大步骤。以下是详细的求解步骤描述。
选择临时移动的分段
在目标任务执行之前，搜索分段堆场上已存放的分段。依据当前的分段堆场布局，通过式(19)，即采用阻挡分段最少的路径选择原则确定分段在堆场内的运输路径。而所选路径上存在的分段即为本节的临时移动分段。
临时移动调度策略
在进场分段堆位进行分配的过程中，没有考虑在场分段的临时移动策略，即假定分段一旦进入堆场，其堆位就确定不变了。对于调度人员，改变在场分段的堆位是希望避免的情况。但是存在一种可能，即通过改变在场分段的堆位会减少整个调度周期内的临时移动的次数，从而从全局的角度得到更好的解。因此，我们在分段堆场的调度问题中引入分段的临时移动策略。
对分段进场时的阻挡分段的处理方法有如下三种：
(1)将阻挡分段向里移动，而进场分段则放置在原阻挡分段所在的堆位；
(2)先将阻挡分段移出，待进场分段放置对应堆位后，再将阻挡分段放回原来的堆位；
(3)在堆场上存在其他空堆位时，将阻挡分段移至其他堆位，所选的新堆位不得在进场分段的移动路径上。
对分段出场时的阻挡分段的处理方法有如下三种：
(1)先将阻挡分段移出，待出场分段离开后，再将阻挡分段放回原来的堆位；
(2)先将阻挡分段移出，待出场分段离开后，将阻挡分段填补到出场分段的堆位；
(3)在堆场上存在其他空堆位时，将阻挡分段移至其他堆位，所选的新堆位不得在出场分段的移动路径上。
图7描述了分段出场时的三种临时移动策略。图中标出的分段62表示该分段是第2天进场，第6天出场。假设现在是计划的第6天，该分段出场时，左边的路径上有分段115和83，右边的路径上有分段72和71，上边的路径上有分段104，下边的路径上有分段95。则最少需要移动一个堆场上的其他分段，如选择下边的路径，则位于堆位(3,3)的分段95被选作临时移动的分段。图中依次显示了三种移动策略，左边两种都需要三次移动：移出阻挡分段，提取目标分段和移入阻挡分段；而右边的策略将阻挡分段运输到一个新的堆位，然后提取目标分段，需要两步。通常情况下，我们会优先选择第三种策略，但是也不排除前两种策略的存在，特别是当堆场上分段比较多的时候，就会用到前两种策略。
分段临时移动调度算法同时包括了分段堆位的选择过程，其详细步骤描述如下：
step1:计算目标堆位每个方向的阻挡分段集，保留阻挡分段个数最少的的分段集，其对于的分段运输路径为目标分段的候选运输路径
step2:对于step1获得的每个分段集，将集合中分段从外向内进行排序，依次重复如下步骤：
step2.1:除了阻挡分段所在路径上的所有堆位，获取分段堆场上的其他空堆位
step2.2:基于临时移动策略3，调用4.3.3中的堆位选择算法，若该阻挡分段的移动需要进行额外的临时移动，在跳转到step2.3；否则从step2.1中的空堆位中选择分段的新堆位，转到step2.4
step2.3:基于临时移动策略1和2，将阻挡分段先移至缓冲区域，然后运输目标分段，更新分段堆场的布局。基于新的堆场布局，调用4.3.3中的堆位选择算法，从原阻挡分段所在路径上的堆位上选择新的堆位，转到step2.4
step2.4:更新分段堆场的布局
step3:对于多个候选运输路径的情况，选择总的临时移动距离最少的路径
s304、对第一分段临时移动率模型进行优化，得到第二分段临时移动率模型。
已知分段堆场信息和一组进场和出场分段调度任务，求平板车在分段堆场内运输分段的操作序列，以及每一次平板车操作的分段对应的起点、终点位置和行驶路径。对于进场分段，需要确定其在分段堆场上的堆位，和到达该堆位的平板车行驶路径。而对于出场分段，需要确定其运输的路径。对于在分段进场和出场时的阻挡分段，要确定临时移动策略和阻挡分段的新堆位。
问题优化的目标为调度周期内的分段临时移动率(rum)。分段在堆场内临时移动次数的多少直接影响分段堆场的任务执行效率，一般认为，分段堆场任务执行效率是分段堆场的重要指标，降低临时移动率是分段堆场的重要目标。
对该问题的研究基于如下的假设：
(1)分段的进出场时间是确定的，分段必须经过堆场再进入下一道工序，即分段在堆场上的停留时间至少为一天；
(2)分段堆场调度的时间单位为天；
(3)分段堆场的尺寸是确定的，是一块矩形场地，可以将其看作一个放大的棋盘，堆场划分成虚拟的矩阵型单元格，即分段堆位；
(4)每个分段堆位一次存放一个分段，堆场上的分段在放置时不能堆积或重叠；
(5)分段堆场的四周都有过道，平板车可以从分段堆场的上、下、左、右四个边进入堆场；
(6)平板车用于在分段堆场内运输分段，平板车在堆场内走直线，并且与堆场边界垂直或水平；
(7)对阻挡分段的临时移动操作只发生在执行提取出场分段或存放进场分段的过程中，其他时间不会执行该操作；
(8)分段堆场的调度任务不能同时执行，必须给出分段移动的次序，当前一个移动操作完成后，才能进入下一个移动操作。
本发明实施方式定义以下参数：
m分段堆场堆位数
t分段堆场调度周期
n分段总数
i分段编号，i∈{1,2,…,n}
j分段堆场堆位编号，j∈{1,2,…,m}
t时间单位，本章中时间单位为天。t∈{0,1,2,…,t}，t＝0表示初始时间
ht时间t内，分段进场和出场任务数
h时间t内的任务索引，h∈{1,2,…,ht}
ati分段i的进场时间
rti分段i的离场时间
pti分段i的分段堆场上存放的时间
dj平板车到达堆位j的可选移动方向集，
d平板车移动方向索引，d∈dj
cjd平板车存放分段到堆位j或从堆位j提取分段时，其移动方向d上的堆场堆位集
fdj分段堆位j的堆位自由度，即平板车在无阻挡的情况下到达该堆位的可选路径数
rum分段堆场的分段临时移动率
本发明实施方式定义以下决策变量：
osi分段i进场时遇到的阻挡分段个数
ori分段i出场时遇到的阻挡分段个数
asi分段i是否安排到该场地，是为1，否则为0
优化目标
minimizerum(20)
约束条件
问题的优化目标为最小化分段运输中的分段临时移动率。平板车在堆场内沿直线移动，可以从分段堆场的上下左右四面的过道到达或离开堆位。因此对于计划期内的分段进场和出场的操作，分别计算四个方向上阻挡分段的个数，选择阻挡数最少的路径。具体的目标表达如式(20)所示，目标函数前半部分表示所有分段进场任务从选择的路径到达选定堆位时的临时移动次数，目标函数后半部分表示所有分段出场任务从选择的路径离开分段堆场时的临时移动次数。
式(21)保证每次任务只能对一个分段进行了一次操作，包括进场或出场操作。
每个分段只能进场和出场各一次，且分别在其进场和出场的时间内执行。式(22)表示分段在其进场时间内被存放到堆场，式(23)表示分段在其离场时间内被提取出堆场。
式(24)和式(25)建立了平板车操作和堆场上堆位的映射关系。确保每个分段在进场后到其离场前，必须占用分段堆场上的一个堆位，并且在提取操作后释放其在分段堆场上占用的分段堆位。
式(26)跟踪分段和堆位的关系，确保在堆场上的分段在离场前保持堆位不变。除非该分段发生进场和离场的事件，否则，其状态和前一步的状态保持一致。
式(27)确保分段堆场上的每一个堆位在同一时刻最多只能存放一个分段。
s305、利用禁忌搜索算法求解第二分段临时移动率模型。
分段堆场调度是根据给定的任务获得堆场上的分段运输计划。本节提出一种基于禁忌搜索的启发式算法，用于解决大型组合优化问题。
算法首先提供一个初始解π和空的禁忌表tl。计数器iter和niter分别用于记录算法总的迭代次数和无改善的迭代次数。当无改善的迭代次数到达nonimpiter或者总的迭代次数到达maxiter，则取当前获得的最好的解为最终的解。基于以上的说明，算法的总体流程描述如下：
step1:获取初始解，
step1.1:生成初始任务序列seq
step1.2:基于seq，获取初始方案π
step1.3:计算初始方案π的目标函数值，标记为f(seq)，setf*＝f(seq)
step2:重复以下步骤直到iter≥maxiterorniter≥nonimpiter
step2.1:设定iter:＝iter 1,niter:＝niter 1
step2.2:生成seq的邻域i.e.,n(seq)
step2.3:对于邻域中的每一组序列seq'，seq'∈n(seq)，重复如下步骤：
step2.3.1:基于序列seq'，获取解就方案π'
step2.3.2:计算初始方案π'的目标函数值，标记为f(seq')
step2.3.3:如果f(seq')<f*，则f*＝f(seq'),niter＝0
step2.4:记录seq到seq'邻域搜索的过程，更新禁忌表tl
基于以上的算法总流程，以下几节详细描述了初始序列的生成方法、邻域搜索方法以及禁忌表的设计。
初始解
根据分段的进场和出场时间，可以获得在调度周期内每一天的分段的进场/出场任务，分段任务序列的优化必须满足分段进出场的时间约束。而对于每个时间单元内的所有分段进出场任务，则将其分为出场分段任务集和进场分段任务集。在调度时，首先执行所有的出场分段任务，把堆场上的相关堆位腾空，再执行进场分段任务。那么，我们还需要确定同时间内出场分段任务集和进场分段任务集内的分段任务序列。
首先，对于单位时间内的进场分段任务，根据它们在堆场上停留时间pti从大到小排序，实验说明该策略优于随机获得的序列。所以这里以此来确定同时间内进场分段任务集内的任务运输序列。
对于单位时间内出场分段任务集中的分段运输任务序列的确定，需要基于当天分段堆场的布局。在每一天的任务执行之前，搜索分段堆场上当天出场的所有分段，分别计算它们出场时最少的阻挡分段个数，并进行从小到大的排序，以此来确定分段出场任务的执行序列。此规则可以确保，每一次选择的出场任务都是在当前堆场布局下，尚未执行的出场分段任务中，需要分段临时移动次数少。
解的表示
本问题研究的分段运输任务中，存在两种基本任务(tk)：存放进场分段(tk＝s)和提取出场分段(tk＝r)。每一个任务可以表示为(t,i,tk)，其中t指任务发生的时间，i是任务中的分段编号，tk指任务的种类。图8是一个分段任务序列中的一段，其中每一列包含了任务的三个要素(t,i,tk)，如第一列表示该任务是在第4天存放编号为5的分段。
评价函数
算法的评价函数即为本章的优化目标函数——分段临时移动率rum，函数值越小，调度方案越优。首先对于给定的任务序列，需要获得分段堆场内的分段运输计划，基于该运输计划来计算对应的分段临时移动率。问题结合了分段任务序列优化、分段堆位选择以及分段临时移动这三个部分，详细流程描述如下：
step1:获取调度周期内所有进出场任务，并按照任务发生时间排序。令k＝1
step2:获取任务k的相关信息(t,i,tk)
step3:如果tk＝r，
step3.1:选择分段i出场路径
step3.2:调用4.4.2节描述的分段临时移动算法，确定阻挡分段的移动策略
step3.3:记录执行任务k发生的临时移动次数，更新分段堆场的布局，转到step5
step4:如果tk＝s，
step4.1:调用4.3.3节描述的分段堆位选择算法，确定进场分段i的堆位以及进场的运输路径
step4.2:若存在阻挡分段，则调用4.2.2节描述的分段临时移动算法，确定阻挡分段的移动策略
step4.3:记录执行任务k发生的临时移动次数，更新分段堆场的布局，转到step5
step5:k＝k 1，返回step2直到所有任务执行完毕
通过以上流程获得分段进出场任务的调度计划，计算总的临时移动次数，调用式(1)，获得评价函数的值。
邻域搜索
算法是基于分段任务序列的求解，则解的邻域空间可通过如下步骤获得：(1)随机选择一个时间区域；(2)在满足时间约束的条件下，随机选择一个分段任务和一个新的位置，将任务插入新位置；(3)检测新的任务序列的可行性。如图9所示，ins(t,x1,x2)表示将任务x2插入到任务x1前的操作。
为了确保解的可行性，需要保证堆场上的分段总数不能超过堆场的负荷能力，所以要对每一个邻域进行可行性分析和修正。对于该问题，计算每一次分段任务执行后堆场上的分段数量，如式(29)所示，我们可以确定方案的可行性。
如果存在nstok>n×m，则表示该方案是不可行的。对于这种情况，我们将导致分段任务溢出的分段任务，在满足实际约束的条件下，移至序列的最后。
在搜索过程中，采用最佳匹配策略。对于一个已知的解决方案π，其邻域的搜索通过随机访问其邻居直到访问数到达预定的数值。其邻域n(π)的访问空间随着问题的规模增加而增大。因此，为了提高效率，减少邻域的搜索空间，把ins(t,x1,x2)限定在n(π)的子空间。本文中，考虑了计算时间和求解精度两者的权衡，我们选择每一步邻域搜索时的最大数量，为每次堆场调度的周期t。
禁忌表
禁忌表用于记录最近几次邻域变换的操作，用于跟踪邻域的搜索过程以避免重复操作。该算法中，每进行一次邻域搜索ins(t,x1,x2)，将元素(t,x1,x2)记录下来，并在设定的迭代次数中保留着禁忌表中，从而避免重复搜索操作。
禁忌表tl＝(e1,e2,…,emaxl)中，maxl表示禁忌长度，代表在迭代过程中被禁对象不允许被选择的步数。el＝(t,x1,x2)是禁忌表中的一个元素，记录邻域搜索的操作。每一次邻域搜索后，禁忌表通过以下步骤进行更新：将最前的一个禁忌元素释放，将剩余的元素依次向前移动一位，即el-1＝el,l＝2,…,maxl，将新的禁忌元素加入到最后的位置emaxl。
本领域的普通技术人员可以理解，上述各实施方式是实现本发明的具体实施例，而在实际应用中，可以在形式上和细节上对其作各种改变，而不偏离本发明的精神和范围。
1.一种船体分段堆场的调度方法，其特征在于，包括：
为进入分段堆场的分段分配堆位，建立第一分段临时移动率模型；
求解第一分段临时移动率模型；
其中，所述第一分段临时移动率模型的目标函数为计划期内的所有分段进场和出场操作时的在场分段临时移动次数。
2.根据权利要求1所述的方法，其特征在于，为进入分段堆场的分段分配堆位时，选择堆位自由度最小的堆位。
3.根据权利要求1所述的方法，其特征在于，为进入分段堆场的分段分配堆位时，选择堆位自由度变化值最小的堆位。
4.根据权利要求1所述的方法，其特征在于，为进入分段堆场的分段分配堆位时，选择堆位影响度值最小的堆位。
5.根据权利要求1所述的方法，其特征在于，还包括：
对第一分段临时移动率模型进行分段临时移动调度；
对第一分段临时移动率模型进行优化，得到第二分段临时移动率模型；
求解第二分段临时移动率模型；
其中，分段临时移动调度是针对进场和出场分段的运输路径上的阻挡分段的堆位调整。
6.根据权利要求5所述的方法，其特征在于，所述对第一分段临时移动率模型进行分段临时移动的步骤中，采用阻挡分段最少的路径选择原则确定分段在堆场内的运输路径。
7.根据权利要求6所述的方法，其特征在于，所述对进场分段的运输路径上的阻挡分段的堆位调整包括：
将阻挡分段向里移动，而进场分段则放置在原阻挡分段所在的堆位；
先将阻挡分段移出，待进场分段放置对应堆位后，再将阻挡分段放回原来的堆位；
在堆场上存在其他空堆位时，将阻挡分段移至其他堆位，所选的新堆位不得在进场分段的移动路径上。
8.根据权利要求6所述的方法，其特征在于，所述对出场分段的运输路径上的阻挡分段的堆位调整包括：
先将阻挡分段移出，待出场分段离开后，再将阻挡分段放回原来的堆位；
先将阻挡分段移出，待出场分段离开后，将阻挡分段填补到出场分段的堆位；
在堆场上存在其他空堆位时，将阻挡分段移至其他堆位，所选的新堆位不得在出场分段的移动路径上。
9.根据权利要求6所述的方法，其特征在于，所述求解第二分段临时移动率模型具体为，
利用禁忌搜索算法求解第二分段临时移动率模型。
技术总结