2.1 问题定义

本节对钢材存储跨内的行车调度问题进行了低层次的定义，该定义将由算法来解决。该定义概述了问题的输入、算法的输出、目标函数以及约束条件。

2.1.1 输入与输出

该问题的主要输入参数为：1）钢材参数信息清单；2）成品跨信息清单；3）堆垛信息清单；4）各跨之间辊道信息清单；5）行车信息清单；6）装载指令信息清单（一份装车指令会明确指出哪些钢材需要装载到特定的车辆上）。

该算法的输出内容包括每台行车所执行的动作，并按照动作类型进行分类：1）钢材装载作业；2）组织钢材移送作业；3）从轧机接收钢材的作业；4）将钢材送往超声波探伤处的作业。

每个动作组都由一个列表来表示，该列表存储了行车必须执行的动作。这些动作按照应执行的顺序进行排列。每个动作都由成品跨指定，包括起始和结束坐标以及要移动的钢材。对于装车动作，还会提供与之对应的装车顺序以及接收钢材的车辆的相关信息。调度动作还包括其目的的指示，例如是否与为未来的运输做准备或将钢材组批有关。

2.1.2 目标函数

该函数的目标是将装载所有订单中的钢材所需的移动次数降至最低。此外，在执行其他类型的移动操作时，还需尽量减少未来所需的装载车移送次数。

2.1.3 硬件限制条件

在本小节中，将介绍该问题的主要硬件限制条件。在解决方案中必须严格遵循这些限制条件。这些限制条件主要与行车的操作规则、成品跨、堆垛以及设备可用性有关。

成品跨限制：每个成品跨都有一个明确的可用区域，该区域标明了钢材堆垛的位置；堆垛的钢材必须遵守最高高度限制；在跨内的某些区域，对于可存放于这些位置的钢材尺寸有限制要求。

行车限制条件：每台行车每次只能搬运有限数量的钢材，这取决于钢材的尺寸和重量；行车只能到达跨内的特定区域。跨内某些区域可以由多台行车共同进入，但它们之间必须保持一定的安全距离。

堆垛约束：在一个钢材堆垛中，只有最上面的钢材可以在任何时刻都可以移动；钢材必须始终放置在堆垛的最上面；堆垛中的钢材长度和宽度必须加以限制；在轨道车和卡车上的钢材堆垛必须遵循半金字塔结构，即最上面的钢材在长度或宽度上不能超过下面的钢材。

设备限制条件：行车无法投入使用；过跨辊道无法使用；正在维护中的场地行车不允许进入；若超探设备无法使用，则不得将钢材送至超探区域。

2.2 软约束条件

在本小节中，将介绍该问题的主要软性约束条件。软性约束并非强制性要求，但它们对于实现更符合客户期望的解决方案是很有益的。这些约束主要与堆垛内钢材的炉号组批有关。理想的情况下，具有相似特性的钢材应放置在相同的堆垛中，以保持成品跨的组织调度有序，并便于准备和装载作业。

此问题的软性限制条件为：将具有相同炉号的钢材归类放置在同一堆垛中；将来自相同装车顺序的钢材组批归入同一堆垛；避免将新的钢材堆放在已为发货准备好的堆垛上；销售发货日期较早的钢材应置于堆垛的顶部；来自轧钢厂的钢材应分配到便于未来发货的堆垛中。

2.3 主要算法

为解决该问题而设计的算法包含四个主要部分，此外还有用于吊运钢材发货订单的预处理阶段。该算法的流程图如图2所示。

这些组成部分分为生成分配来自轧机的钢材的吊运、发送钢材进行超探检查、装载车辆以及组织调度成品跨等几项内容。在执行这些步骤后，会生成一个包含每个阶段移送路径的对象。需要特别注意的是，每个组成部分都独立生成一组移送路径，这意味着跨内每个步骤的初始状态都是作为输入的。该流程中最为关键的阶段是装车作业和组织协调作业工作，因为这些环节往往需要进行最多的行车操作。接下来的段落将对每个步骤进行更详细的说明。

2.3.1 装车订单的预处理

在开始算法的其他阶段之前，有必要对装车订单进行预处理。首先，这些装车订单会按照其出发的预定日期进行排序。如果车辆已经在堆场等待装载，那么这个装车订单将在移动生成阶段用于装载处理。如果车辆尚未进入堆场，那么这个装车订单将被列出，以便在成品跨组织移动时进行装车准备。

在对这些钢材进行内部分类之后，属于该装货订单的钢材也会进行分类，目的是减少装货所需的吊运次数。为了实现这种分类，会考虑钢材在堆垛中的出现顺序。同时，还需考虑目标堆垛限制或车辆中钢材堆叠限制来进行这些板材的分类。

2.3.2 生成板材入库作业

此阶段的任务主要是将来自轧制过程的钢材引导至合适的堆垛区域。在轧制过程中，钢材会被放置在辊道上，并被引导输送至其中一个成品跨。当到达目的地成品跨后，该钢材必须被运至相应的堆垛处。所选的堆垛区域应与刚刚轧制完成的钢材具有最佳的兼容性，并且不会违反任何高度或尺寸要求。

2.3.3 产生超探作业

有些钢材在发往客户之前需要通过超声波探伤检查。这些钢材通常在跨内里成堆堆放。在某个时候，它们必须由行车吊运到过跨辊道上，然后将钢材运送到超声波探伤设备处。超探结束离开设备后，钢材再次由行车收集吊运，并被导向合适的堆垛。就像处理辊道上钢材的阶段一样，为从超探设备中出来的钢材选择合适的堆垛位置对于保持成品跨的组织有序性非常重要；因此，应选择与之最匹配的堆垛。

2.3.4 产生发货装车作业

钢材装车作业可能比之前介绍的要更为复杂，这是因为完成装车过程需要进行更多的动作。此外，这些动作的顺序和目的地对于保持组织有序以及确保装车操作正确进行至关重要。

当针对某一装车订单的钢材已经整齐堆垛好，准备进行装车时，装车吊运过程就会变得简单。在这种情况下，行车移动到堆垛上方，尽可能多地吊起钢材，并将其运送到车辆上，如有必要，还需重复这些动作。然而，如果钢材散落在整个跨内中或者被其他钢材压在堆垛下方，装货任务就会变得更加复杂。在这种情况下，行车需要访问多个堆垛或取出若干钢材，才能到达需要装车的特定钢材处。

图3展示了生成作业流程的图表。

该算法生成装车作业的第一步是确定放置钢材的位置。在本例中，该位置即为车辆在堆场中的停放位置。接下来，必须确定装车订单中首批板材所在的堆垛。在确定了堆垛之后，需要分析即将装车的钢材是否处于堆垛下方被其他批次钢材压住；也就是说，即将发货的钢材在该堆垛中是否上面覆盖着其他的钢材。在这种情况下，必须移除阻碍装车的上层钢材到另一个堆垛中，直到要发货装车的钢材位于最上面。既然钢材已经位于最上面，那么接下来就需要计算行车能够吊运的钢材数量，同时考虑到行车能够起吊移动重量的限制。然后才可以将钢材吊运到其目的地。这个过程会一直重复，直到装货订单中的所有钢材都到达目的地位置。

2.3.5 产生调度作业

调度作业可分为三种类型：装车准备、装卸移送钢材、按组批钢材作业。这些操作在输出中通过一个参数加以区分，该参数能够识别列表中每项作业的组织作业类型。

当有装车交货指令但车辆尚未停靠在成品跨指定位置时，会生成装车的准备作业。在车辆就位后，可为该订单的钢材进行吊运准备，以便于装车。这种组织过程遵循图3中的流程图，但目的地不再是车辆，而是跨中的一个堆垛。这样一来，来自装车指令的钢材会被组合成一个单独的堆垛，同时保持它们将被装载到车辆上的堆垛上下的顺序。

当一个钢材需要被装车，但其却被其他钢材堆垛在一起被压在下面时，就会出现移除上层钢材和再返回到这个堆垛的作业操作。在这种情况下，最上面的板材会被移动到其他堆垛区域，直到要装车的钢材位于最上面。在装车完成指定的钢材后，该堆垛之前被移除的钢材必须被放回其原来的堆垛上。

钢材分组作业操作旨在将具有相似特性的板材进行分类，以保持成品跨的有序调度。如果某块钢材所在的堆垛与要求不匹配，而相邻的可匹配堆垛中有空位，则应将该钢材移至更合适的堆垛位置。

2.3.6 选择最佳作业移送

在某些类型的移送作业操作中，尤其是按照订单组批的移送作业操作中，将一个或多个钢材从堆垛区移动到其他位置存在多种可能性。在这种情况下，会列出所有有效的移动选项，并根据一系列用于确定最佳选择的标准来选定一个最佳选项。

选择移送作业的标准包括：1）按销售订单对钢材进行组批；2）将准备装车钢材进行组批；3）按客户要求对钢材进行分类组批；4）按卡车路径进行组批；5）清空堆垛；6）减少翻垛次数；7）缩短行车的移动距离。一旦选定作业操作，行车就会被引导至指定的堆垛处，从那里收集指定的钢材，然后将它们放置到目标堆垛处组批。