贾树晋，李维刚，杜 斌

(宝钢集团中央研究院自动化研究所，上海，201900)

热轧轧制计划的多目标优化模型及算法

贾树晋，李维刚，杜 斌

(宝钢集团中央研究院自动化研究所，上海，201900)

针对热轧轧制计划优化问题，建立基于奖金收集车辆路径问题(PCVRP)的多目标优化模型，其中包含两个目标：目标1为最小化相邻板坯的宽度、厚度与硬度的跳跃惩罚；目标2为最大化收集的奖金，即使得尽可能多的板坯编入轧制计划。在此基础上，提出一种基于Pareto最优的多目标蚁群系统算法(MOACS)，避免了传统加权法需要确定目标权重系数的缺点，一次运行可产生多个Pareto最优解，给决策者带来了更大的决策自由度。现场数据测试表明该算法具有良好的优化性能和实用性。

热轧轧制计划；多目标优化；Pareto最优；蚁群算法

热轧是现代钢铁生产中的一个重要工序。当前，用户对钢铁产品的需求日趋小批量、多品种，这对钢铁企业的生产组织提出了更高的要求。热轧生产组织的关键和核心是热轧轧制计划的制订，即根据生产条件、用户需求及轧制规程，合理安排待生产板坯的加工顺序。执行一个合理有效的热轧轧制计划，能提高产品质量与生产效率，降低能耗和生产成本，提升钢铁企业的竞争力。然而，由于生产中涉及大量复杂的约束，热轧轧制计划被认为是钢铁生产计划与调度中最复杂和难解的问题之一。

鉴于热轧轧制计划优化问题的重要性，国内外学者进行了大量的研究。根据建立的模型类型，这些研究可分为旅行商问题(Travelling Salesman Problem, TSP)模型、车辆路径问题(Vehicle Routing Problem,VRP)模型及其变种。Lopez等[1]提出了一种奖金收集旅行商模型(PCTSP)，并利用基于禁忌搜索和“Cannibalization”概念的启发式算法来求解，得到了较好的结果。但这个模型是针对轧制单元计划提出的，每次只考虑一个轧制单元的编制，本质上说是一种串行策略。鉴于这种情况，随后发表的文献将研究重点放在并行策略的研究上。Tang等[2]提出了著名的多旅行商模型(MTSP)，采用并行策略同时生成多个轧制单元，并通过改进的遗传算法进行了求解，然而这个模型未能包含轧制单元的能力约束。黄可为等[3]建立了MTSP模型，从实际应用的角度描述了基于模型的热轧计划排程系统的建立和开发实现技术。李耀华等[4]建立了不确定轧制计划数的VRP模型，该模型考虑了轧制单元中烫辊材和主体材的合理安排，并构造出一种基于单亲遗传算子的免疫算法求解此模型。贾佳等[5]建立了单一、混合轧制计划类型的主体材计划VRP模型，提出了轧制计划类型最小区间编制规则，并采用专家经验实现了计划协调，经测试表明该方法提高了批量计划的组批数量、轧制效率和组批质量。Liu[6]将热轧批量计划优化问题归结为多目标奖金收集车辆路径问题(Prize Collecting Vehicle Routing Problem, PCVRP)模型，并通过加权法将多目标优化模型转化为单目标优化模型，使用基于分解-协调的蚁群算法进行了优化求解。笔者等考虑了板坯表面等级约束、热装热送等约束,建立了一种带双时间窗的车辆路径问题(VRPDTW)模型，并根据优化目标的优先级，提出了一种基于分解的分层递阶优化算法[7]。除TSP模型和VRP模型外，也有部分学者尝试建立不同的模型。Pan等[8]建立了一种多目标多路径问题模型，并提出了一种改进的列生成算法来编制大规模的热轧批量计划。郭冬芬等[9]建立了热轧轧制计划问题的约束满足模型，并设计了基于约束满足和启发式的混合求解算法。

热轧轧制计划优化问题属于多目标优化问题，目前的主流求解方法是通过加权的方式将其转化为单目标优化问题，然后使用单目标优化算法进行求解。此类方法存在的问题是目标权重系数一般不易确定，尤其是在目标数量级不一致的情形下。为此，文献[10]中将热轧轧制计划问题归结为一种带能力约束的双目标TSP问题模型，并首次采用基于Pareto最优的多目标优化算法进行求解，该方法将所有候选板坯编入轧制计划，适用于候选板坯数较少的情形，当候选板坯数较多时，需要较长优化时间。因此，本文考虑将部分候选板坯编入轧制计划的情形，建立基于奖金收集车辆路径问题(PCVRP)的多目标优化模型，并根据模型特点提出一种多目标蚁群算法进行优化。

1 热轧轧制计划的数学模型

1.1 问题描述

如图1所示，一个轧制计划由若干个轧制单元构成，一个轧制单元由烫辊材与主体材两部分组成，在宽度上呈“乌龟壳”结构。烫辊材按照由窄到宽的顺序排列，主要用于预热轧辊，其数量一般较少，容易确定，因此本文不对其讨论。主体材是轧制单元的主要组成部分，按照由宽到窄的顺序排列，以防止在带钢表面留下印迹，影响产品质量，另外，在板坯排序时还要兼顾相邻板坯间的厚度、硬度跳跃，使其尽量平滑。

在热轧过程中，为避免由于轧辊磨损引起产品质量问题，工作辊在轧完一个轧制单元后必须更换。由于更换轧辊会导致热轧生产中断，且耗时较长，会影响生产效率，因此从产品质量与生产效率角度综合考虑，轧制单元的轧制长度应限定在一定范围内。另外，为了避免连续轧制同一宽度的板坯引起轧辊凹痕，必须对连续同宽轧制公里数作一限制。

综上分析，编制轧制单元时主体材需要满足以下轧制规程：①宽度须呈非增变化，且要求变化平滑，跳跃幅度有限制；②硬度变化要平稳，递增或递减均可，但不能反复跳跃；③厚度变化要平稳，不能反复跳跃，最好是朝非减方向变化；④连续同宽轧制公里数应限定在一定范围内；⑤总轧制长度要有一定限制。

因此，热轧轧制计划编制可定义为：从候选板坯集中挑选部分板坯，对这些板坯进行合理分组(每个分组对应一个轧制单元)，然后根据轧制规程对轧制单元中的板坯进行排序，使得相邻板坯间的宽度、厚度与硬度的跳跃惩罚最小，同时使尽可能多的板坯被编入轧制计划。

(a)轧制计划的结构 (b)轧制单元宽度截面

图1 轧制计划结构及其轧制单元形状

Fig.1 Structure of rolling plan and shape of a rolling unit

1.2 数学模型

PCVRP可定义为：配送中心有m辆车，每辆车的最大载重量为U，需要为n个客户配送货物，客户i的需求量为qi，与客户j之间的距离为dij，每个客户最多被一辆车服务，如果客户i被服务，获得pi的奖金，否则，得到pi的惩罚。每辆车的起点和终点均为配送中心，要求合理安排每辆车的行车路径，使得总行驶距离尽可能短，收集到的奖金尽可能多。

在轧制计划中，令每块板坯对应一个客户，每个轧制单元对应一辆车，客户的需求对应板坯的轧制长度，相邻板坯间的宽度、厚度与硬度跳跃惩罚对应客户之间的距离，如板坯被编入轧制计划，得到pi的奖金，否则，得到pi的惩罚。另外，引入编号为0的虚拟板坯，对应配送中心，其轧制长度为0，与其他板坯间的跳跃惩罚为0，虚拟板坯必须被编入轧制计划。这样，就可将热轧轧制计划优化问题与PCVRP对应起来。

数学模型的决策变量定义如下：

wi：板坯i后连续同宽轧制的累积轧制长度

则热轧轧制计划优化问题可描述为以下的多目标PCVRP模型：

(1)

(2)

s.t.

(3)

(4)

(5)

y0k=1 (k∈M)

(6)

(7)

wj+T(1-sijxijk)≥wi+qj

(i,j∈N{0},k∈M)

(8)

qi≤wi≤R(i∈N{0})

(9)

(10)

(11)

xijk∈{0,1} (i,j∈N,k∈M)

(12)

yik∈{0,1} (i∈N,k∈M)

(13)

其中，目标函数A代表板坯宽度、厚度、硬度与加热时间跳跃惩罚最小；目标函数B代表未被编入轧批的板坯总惩罚最小(即收集的奖金最多)；约束条件(3)表示在第k个轧制单元内，板坯j前至多有一块板坯；约束条件(4)表示在第k个轧制单元内，板坯i后至多有一块板坯；约束条件(5)避免轧制单元内出现子回路；约束条件(6)表示虚拟板坯0必须被编入轧制计划；约束条件(7)表示每块实物板坯至多被安排到一个轧制单元内；约束条件(8)和(9)限制了每个轧制单元内最大连续同宽轧制长度，其中T为一个很大的数；约束条件(10)和(11)为每个轧制单元的能力约束，限制了最大最小轧制长度；约束条件(12)和(13)表示决策变量 为0-1变量。

2 热轧轧制计划的多目标优化算法

由于PCVRP属于组合优化问题，因此，轧制计划的PCVRP模型中，当板坯数量较大时，会带来“组合爆炸”的问题，对其精确求解非常困难。一般对这类问题，可通过启发式算法或智能优化算法进行优化求解。另外，对于多目标优化问题，一般采用加权法进行处理，但轧制计划模型中的两个目标的量纲不一致，也不在同一数量级，因此，其目标权重系数难以合理确定。本文利用基于Pareto最优的多目标优化蚁群算法进行求解，以避开确定目标权重系数这一难题。

在众多蚁群算法中，蚁群系统(Ant Colony System, ACS)[11]算法是一种最为成功的蚁群算法，但其原始算法只能解决单目标优化问题，因此，本文在ACS算法的基础上，根据轧制计划模型特点，通过重新设计状态转移策略、信息素更新策略，并引入局部搜索策略与精英保留策略，提出了一种多目标蚁群系统(Multi-objective Ant Colony System, MOACS)算法对轧制计划模型进行优化求解。

2.1 算法流程

MOACS中，设置有一个内部种群PS和一个外部档案ES。令L表示内部种群PS中的蚂蚁个数，m表示轧制计划中的轧制单元数，maxGen表示算法的最大迭代次数，则MOACS算法的流程如下：

Step 1:令l=1，k=1，Gen=1，初始化信息素矩阵。

Step 2:蚂蚁l从虚拟板坯0出发，从候选板坯集合中选择最大宽度的板坯作为第k个轧制单元主体材的第1块板坯。

Step 3:蚂蚁l根据状态转移策略在可行板坯集合Fl中选择下一块板坯，其中可行板坯集合Fl是指满足式(3)～式(11)约束条件的所有板坯。若Fl≠Ø，则返回Step 3继续选择下一块板坯；若Fl=Ø，则返回虚拟板坯0，转下一步。

Step 4:令k=k+1，若k≤m，转到Step 2开始下一轧制单元的构造；若k>m，按照局部搜索策略以概率PLS对蚂蚁l构造的路径(轧制计划)进行局部搜索，以改善解的质量。

Step 5:对蚂蚁l构造的路径上的信息素浓度进行局部更新(信息素更新策略)。

Step 6:令l=l+1，若l≤L，令k=1，转到Step 2开始构造下一只蚂蚁的路径；若l>L，说明所有蚂蚁均已完成路径构造，转下一步。

Step 7:根据精英保留策略将内部种群PS产生的非支配解更新到外部档案ES中，并删除ES中的被支配解。

Step 8:对本次迭代成功进入外部档案ES中的Pareto最优解进行信息素全局更新(信息素更新策略)。

Step 9:令Gen=Gen+1，若Gen≤maxGen，则令l=1，k=1，返回Step 2继续执行；若Gen>maxGen，则输出外部档案ES中的Pareto最优解，结束程序。

2.2 状态转移策略

在每次迭代中，蚁群需要根据状态转移策略来构造路径，其中有两个重要的参数：信息素浓度和启发式信息。对于处理单目标优化问题的ACS来说，其信息素矩阵与启发式矩阵均只有一个，本文算法选择两个信息素矩阵，分别对应轧制计划模型中的两个目标，另外选择一个启发式矩阵，综合考虑两个目标的启发式信息。

在MOACS中，每块板坯代表一个可能被蚂蚁访问的节点，位于节点i处的第l只蚂蚁根据以下状态转移策略来选择下一个节点s：

(14)

(15)

由式(15)可知，启发式信息ηij随着INj的改变而改变。对于每只蚂蚁，λ衡量两个目标的相对重要性，为了使每只蚂蚁搜索不同的目标空间，第l只蚂蚁对应的λ可表示为：

(16)

S∈Fl(i)表示按照下述概率分布确定的板坯：

(17)

2.3 局部搜索策略

为改善蚁群算法所得解的质量，MOACS中引入了局部搜索策略，包含3个算子：Insertion、2-opt和Swap。Insertion算子主要用于减少板坯未被编入轧坯所带来的惩罚，2-opt算子用于减少相邻板坯间的跳跃惩罚，Swap算子则兼顾两者。图2为局部搜索策略中3个算子的原理图，其中，i、j、k、r均代表板坯。3个算子的执行顺序为Insertion→2-opt→Swap。

(1)Insertion。Insertion算子考虑所有未被编入轧批的板坯，首先将这些板坯按照奖金降序排列，然后为每个未编入计划的板坯k寻找一个最好的位置插入到已有轧批中(判别标准为最小化dik+dkj-dij)，直到无可行插入为止。

(2)2-opt。2-opt算子是VRP与TSP中最常用的局部搜索算子，本文中用于减少每个轧制单元中相邻板坯间的跳跃惩罚。如图2中所示，2-opt算子首先删掉完整路径的两条边(r,i)与(j,k)，使其分成3个部分，然后通过引入新边(r,j)与(i,k)并反转节点i与j之间的路径以达到更小的跳跃惩罚。

(3)Swap：Swap算子通过交换轧批中板坯与收池中板坯来同时达到上述两种目的。具体来说，对每个收池中按照奖金降序排列的板坯r，如果满足以下两个条件：板坯j的奖金小于板坯r的奖金；dir+drk-dij-djk<0，则将板坯r与轧批中的板坯j交换。Swap算子亦可理解为插入板坯r与删除板坯j。

2.4 精英保留策略

MOACS中，内部种群PS用于构造蚂蚁路径，外部档案ES用于存储算法迭代过程中产生的Pareto最优解(或非支配解)，使得精英个体得以保留。具体来讲，算法在每次迭代中，需要将内部种群PS产生的非支配解更新到外部档案ES中，并删除外部档案ES中的所有被支配解。如果外部档案ES中的Pareto最优解个数超过一定上限，为了保证算法效率，需要删除一部分解。为了使外部档案ES中的解分布均匀，选用自适应网格策略[12]进行多样性保留。

2.5 信息素更新策略

在ACS中，信息素更新策略包含局部更新与全局更新两种。局部更新是指蚂蚁每选择下一个节点后，按照一定规则减小该边上的信息素浓度，其作用是降低下一只蚂蚁选择这条边的概率，有利于扩大搜索空间，避免算法过早收敛。而全局更新是指在一次迭代中，当所有蚂蚁完成路径构造后，对其中最好的一条路径进行信息素增强，诱导蚂蚁以更大的概率选择该条路径上的边，以此保证算法的收敛性。信息素的局部更新与全局更新体现了ACS算法对全局探索与局部开发的一种平衡。

在MOACS中，沿用这种思路，但需根据多目标优化特性，对信息素局部更新与全局更新公式进行改进。改进后的信息素局部更新公式如下：

(18)

在ACS中，仅对一个最优解进行信息素全局更新。多目标优化不存在惟一的最优解，可在每次迭代中，选择对应每个目标的最优解来更新相应的信息素矩阵，信息素全局更新公式如下：

(19)

(20)

式中：ft(best)为本次迭代中第t个目标的最优值。

3 实验验证

为验证轧制计划模型与算法的有效性，采用某钢铁公司的实际生产数据进行实验验证。测试数据中共包含331块板坯，轧制计划中包含3个轧制单元。使用3种方法进行比较研究，方法一为本文提出的MOACS算法；方法二为改进的ACS算法，即通过加权法将多目标优化问题转化为单目标优化问题，然后按照MOACS算法的思路对标准ACS算法进行适当改进，使之能够处理轧制计划编制问题；方法三为人工排程方法，是生产现场采用的一种基于规则和人工经验的方法。MOACS和ACS算法使用C++编程实现，算法参数设置如下：α=1，β=2，ρ=0.1，q0=0.9，L=30，maxGen=200，PLS=0.1。

3种方法的优化结果如表1和图3所示。由表1和图3中可知：

(1)表1中，为ACS算法选择了5组不同的目标权重系数进行优化，得到不同权重系数下的最优解。从表1中可知，不同的目标权重系数得到的最优解不同，因此在使用单目标优化算法编制轧制计划时，需要决策者具备一定的先验知识来合理确定目标权重系数,而MOACS算法则避免了目标权重系数的设置问题。

(2)从图3中可知，ACS算法在取均匀分布的目标权重系数时，最优解并未在整个解空间均匀分布，存在一定的“偏置”，表明在目标数量级不一致的情形下，目标权重系数并不能准确反映决策者对不同目标的偏好。与之相反，MOACS算法可在整个解空间得到均匀分布的Pareto最优解，为决策者提供了更全面的信息。

(3)在图3中，解越靠近图形的左下端，表明两个目标的值越小，优化精度越高。从图3中可知，MOACS算法的优化精度最高，ACS算法次之，人工排程的精度最差。人工排程方法属于典型的串行方法，类似于贪婪方法，容易陷入局部最优，当编制第一个轧制单元时，由于有足够多的候选板坯可选，计划员较容易就能编制出性能良好的轧制单元，而后随着候选板坯数的减少，编制效果越来越差，表现为相邻板坯间跳跃波动较大，排入轧制计划的板坯数减少；而MOACS和ACS算法属于并行算法，可有效地均衡各个轧制单元的排程质量，实现全局优化。另外，局部搜索策略的引入使得MOACS算法的性能得以显著提高。众所周知，ACS算法虽然有着良好的全局收敛性能，但其收敛速度较慢。本文针对轧制计划特性引入的局部搜索策略，集成了Insertion、2-opt和Swap 3个算子，在蚁群算法的基础上对两个目标进行了精细搜索，在提高优化精度的同时，加快了算法收敛的速度。

(4)从计算效率来看，虽然MOACS算法由于存在精英保留策略、局部搜索策略等额外运算，其单次运行的时间较ACS算法时间长，但MOACS算法一次运行可产生多个Pareto最优解，而ACS算法每次运行仅得到一个最优解，若想产生多个不同结果，需要在不同的目标权重系数下，多次重复运行算法，花费的总时间更长。人工排程方法所花费的时间最长，一般需要2 h才能排好一个轧制计划，给决策者带来很大的负担。

(5)决策者可在MOACS算法得到的Pareto最优解中，挑选出最终的轧制计划方案，属于后验决策。如图3所示，最终方案很好地兼顾了两个目标，与人工排程方案相比，相邻板坯间的跳跃惩罚更小，有利于减少轧辊磨损，同时该方案使得轧制计划中编入更多板坯，可提高轧制单元轧制长度，减少换辊次数，提高生产效率。

4 结语

本文提出的基于Pareto最优的多目标蚁群系统算法(MOACS)为热轧轧制计划优化问题的优化求解提供了一种新的解决方案，不仅避免了选择目标权重系数的问题，且算法一次运行可产生多个Pareto最优解，给决策者带来更大的决策自由度。现场数据测试表明，该算法无论是优化精度还是优化效率均明显优于ACS算法和人工排程方法，对实际生产具有很好的指导意义。

[1] Lopez L, Carter M W, Gendreau M. The hot strip mill production scheduling problem: a tabu search approach[J]. European Journal of Operational Research, 1998, 106(2-3): 317-335.

[2] Tang L X, Liu J Y, Rong A M, et al. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex[J]. European Journal of Operational Research, 2000, 124: 267-282.

[3] 黄可为，杜斌，刘青，等. 基于模型的热轧轧制计划排程系统的设计与实现[J]. 上海金属，2009，31(4)：41-45.

[4] 李耀华，王伟，徐乐江，等. 热轧生产轧制计划模型与算法研究[J]. 控制与决策，2005，20(3)：275-279.

[5] 贾佳，潘莉，屠乃威，等. 热轧批量计划多目标智能优化编制新方法[J]. 控制工程，2008，15(2)：220-224.

[6] Liu S X. Model and algorithm for hot rolling batch planning in steel plants[J]. International Journal of Information and Management Sciences, 2010, 21(3): 247-263.

[7] Jia S J, Zhu J, Yang G K. et al. A decomposition-based hierarchical optimization algorithm for hot rolling batch scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2012, 61(5-8): 487-501.

[8] Pan C C, Yang G K. A method of solving a large-scale rolling batch scheduling problem in steel production using a variant of column generation[J]. Computers & Industrial Engineering, 2009, 56: 165-178.

[9] 郭冬芬，李铁克. 约束满足技术在板坯排序中的应用[J]. 计算机工程与应用，2007，43(9)：1-3.

[10]贾树晋，朱俊，杜斌，等. Pareto最大最小蚂蚁算法及其在热轧批量计划优化中的应用[J].控制理论与应用，2012，29(2)：137-144.

[11]Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the travelling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.

[12]Knowles J D, Corne D W. Approximating the nondominated front using the Pareto archived evolution strategy[J]. Evolutionary Computation, 2000, 8(2): 149-172.

[责任编辑 郑淑芳]

Multi-objective optimization model and algorithm for the hot rolling batch scheduling problem

JiaShujin，LiWeigang，DuBin

(Automation Division of Central Research Institute, Baosteel Group Corporation, Shanghai 201900, China)

In view of the hot rolling batch scheduling problem,a multi-objective prize collecting vehicle routing problem (PCVRP) model is presented. This model has two objectives: the first objective is to minimize the penalties caused by jumps in width, gauge and hardness between adjacent slabs, and the second one is to maximize the collected prize,which means more slabs can be inserted into the rolling batch. Then, a multi-objective ant colony system algorithm based on Pareto optimal is proposed to solve the PCVRP model. This algorithm can not only avoid the selection of weight coefficients encountered in the single objective optimization but also obtain multiple Pareto-optimal solution, which provides more decision-making flexibility for the schedulers. Large numbers of site tests show that this algorithm has optimal performance and good practicability.

hot rolling batch scheduling; multi-objective optimization; Pareto optimal; ant colony algorithm

2014-08-05

贾树晋(1982-)，男，宝钢集团中央研究院工程师，博士.E-mail：jiashujin@baosteel.com

李维刚(1977-)，男，宝钢集团中央研究院高级工程师，博士.E-mail：liweigang@baosteel.com

TP27

A

1674-3644(2015)01-0016-07