1引言大型钢铁企业的原料场是用来存放高炉、烧结等所需各种原燃料的场地,它主要有贮存和缓冲 两种机能.由于钢铁企业所需的原材料品种繁多且数量大,如何制订一个好的料场存储分配计划是 降低原料运输与存储费用,保持原料品质的关键所在.这也使得该类问题成为一类急需解决的优化 问题.原料场存储分配问题与已引起学术界广泛关注的选址问题<1~3>和集装箱码头存储分配 问题<4~6>有着一定的相似性.尽管这些现有的模型和算法已成功地解决了多种问题,但由于 钢铁企业原料贮存的特殊性,使得以上这些模型和算法不能直接用于描述和求解该类问题.目前已 有的关于钢铁行业的研究成果多集中在生产研究上,而对原料场存储分配问题的研究则很难找到相 关文献<7>.本文以上海宝山钢铁公司(宝钢)为背景,研究静态料场存储分配问题.首先为该 类问题建立能够充分体现钢铁企业原料场原料存储特点的数学模型,然后提出了多种禁忌搜索算法 和多点下降算法,并对该问题进行求解和性能比较.2问题描述和数学模型2.1问题描述用于宝 钢生产的原料主要可分为矿石、副原料、煤和混匀料4大类,为保持原料成分稳定,宝钢将不同种 类的原料存放在不同类别的料场中,并尽量将成分相同或相近的原料堆放在同一料堆上.这种管理 方式基本上消除了同一料堆上的原料成分差异所造成的原料成分变化,但对于存放过程中不同料堆 间的相互影响而造成的原料变质却无能为力.因此将这些品种繁多的原料配置在合适的位置上,使 得节约费用的同时又保证原料品质的稳定成为典型的优化问题.本文所研究的钢铁企业原料场存储 分配问题由于原料之间存在相互影响而使得料场存储分配问题不仅是分配问题,而且在同一料场内 部还存在着排序问题.因而在制定存储分配计划时,除需要确定所开设的料场和每种原料所放置的 料场外,还需要计算出各原料在所属料场中的具体堆积位置.原料场静态分配问题的特性使得其不 同于常规的分配问题和选址问题,从而增加了钢铁企业原料场存储分配问题的数学建模的难度.2 .2数学模型用Ω表示所有原料(料堆)集合,Ω1表示矿石集,Ω2表示所有副原料集,Ω3表 示所有煤原料集,Ω4表示匀矿集.Ω={1,…,N}=Ω1∪Ω2∪Ω3∪Ω4,这里N为所 有原料(料堆)总数.用Ψ表示所有料场集合,Ψ1表示矿石料场集,Ψ2表示副原料场集,Ψ3 表示煤场集,Ψ4表示匀矿料场集.Ψ={1,…,M}=Ψ1∪Ψ2∪Ψ3∪Ψ4,这里M为所 有料场总数.wi为料堆i的重量;Wj为料场j对每个料堆的最大重量限制;Vj为料场j总重 量限制;li为料堆i的长度;Dj为料场j任意相邻两料堆间的间隔距离;Lj为料场j总长度 ;hi为料堆i的高度;Hj为料场j对每个料堆的最大高度限制;cij为原料i分配至料场j 的费用;fj为开放料场j的固定费用;iαi′j为原料i与原料i′在料场j相邻堆放时所引 起的惩罚费用;M是一个很大的数.决策变量xij当原料i被分配至料场j存储为1,否则为0 ;yj如果开设料场j为1,否则为0;zii′j如果原料i和原料i′在料场j相邻为1,否则为0.sij是原料i在料场j的起始存放单元;eij是原料i在料场j的末尾存放单元,eij=sij+li-1.min∑i∈Ωj∈∑Ψcijxij+∑j∈Ψfjyj+∑i∈Ω∑i′∈Ω\{i}j∈∑Ψi αi′jzii′j;∑j∈Ψ(Wj-wi)xij≥0,i∈;Ω(1)∑j∈Ψ(Hj-h i)xij≥0,i∈Ω;(2)∑i∈Ωwixij≤Vjyj,j∈Ψ;(3)∑i∈Ω(li+Dj)xij≤(Lj+Dj)yj,j∈Ψ;(4)max(sij,si′j)-m in(eij,eij′)+M(2-xij-xi′j)≥Dj,i∈,Ωi′∈Ω\{i},j ∈Ψ;(5)∑j∈Ψkxij=1,i∈Ωk,k=1,…,4;(6)xij∈{0,1}, i=1,…,N;j=1,…,M;(7)yj∈{0,1},j=1,…,M;(8)Zii′ j∈{0,1},i,i′=1,…,N;j=1,…,M;(9)sij和eij是整数,i= 1,…,N;j=1,…,M.(10)目标函数的第1项表示各原料被分配至料场的运输费用总 和.第2项为所开设料场的固定费用之和,其包括料场管理和维护费用及料场内堆取料机作业费用 等.第3项为任意两种原料相邻时由状态差异或成分差异所引起的惩罚费用之和.约束(1)和( 2)表示在任一料场存放原料时,每堆原料的重量和高度不能超过该料场单个料堆的最大重量和高 度限制.约束(3)指出存放在某一料场的所有原料的重量之和不能超过该料场的总重量限制.约 束(4)表示存放在某一料场的所有料堆长度之和再加上相邻两料堆之间的间距应小于该料场的总 长度.为尽量保持原材料的成份在料场存放的时候不发生改变,约束(5)确保在同一料场堆放的 任两个料堆之间应保持一个安全距离.约束(6)表示每一类原料只能存放在与之相应的料场中, 而每一种原料必须且只能在一个料场里堆放.约束(7)~(10)为变量类型约束.以上模型充 分体现了钢铁企业原料场静态存储分配问题的特性,但却使得问题的求解变得更加困难.物料间并 不相互独立的特性转化为目标函数的第3项后,由于不能将此问题分解为子问题,从而导致常用于 求解选址问题的拉格朗日松弛算法并不适用;同样,分支定界算法也因为难以确定下界而不适用, 因此需寻求近优算法来求解该问题.3两类邻域结构目前的近优算法多为邻域搜索算法,其性能的 优劣与邻域选择有着密切的联系.本文拟选用两交换邻域和环交换邻域来测试各种近优算法的性能 .3.1两交换邻域两交换邻域是将两个原料进行交换所得到的所有解的集合.由于本文所研究的 原料间存在相关性,所以除考虑料场间的两交换移动外,还要考虑在同一料场内的两交换移动.3 .2环交换邻域环交换邻域是一种两交换邻域的扩展邻域,将其用于本文所研究的问题可定义如下 :对于原料集合Ω={1,…,N},将Ω分为M个两两不相容的子集(料场){A1,A2,… ,AM},其中Aj表示存储在料场j的所有原料的集合.如果所有的子集都满足模型的约束条件 ,则称这是一个对集合Ω的可行分配A.图1(a)所示的环交换移动是指对应于A的如下一些操 作:原料a1从A1移到A2,原料a2从A2移到A3,以此类推,直至原料aK从AK移到A 1而形成一个环交换移动W=(a1,a2,…,aK,a1).对于一类图1(b)所示的路径 交换,如果对每一个子集引入一个虚拟原料(用-1表示),且虚拟原料也与真正的原料一样可以 参与交换移动,则该类路径交换可转换为带有虚拟节点的环交换移动.本文所研究的环交换移动均 指这类引入虚拟节点的环交换移动.图1路径交换和环交换经过这样构建的环交换邻域具有非常多 的邻居,并且邻域规模随着参与移动的子集个数K的增长而成指数倍的增长,因此该邻域属于大规 模邻域.对每一个环交换移动来说,只有当参与该环交换中的各移动所形成的总费用为负时,才能使得目标函数减少.因此,如何在一个环交换邻域中找到具有最小负费用的环交换移动,是一个关键问题.由于寻找最小负费用是一个NP-Comp lete问题,这里将采用基于动态规划算法的启发式方法来近似寻找该最小负费用.根据环交换的 特点,可依照环交换的起点(终点)来设计动态规划算法.任选某一料场内的某一原料作为动态规 划的起点和终点,环交换所涉及到的料场数即为阶段总数k,每一个料场即为一个阶段j,1≤j ≤k.各料场内所存放的原料个数为该阶段j的状态总数Tj,每一个原料即为该阶段的一个状态 Sji,1≤i≤Tj,1≤j≤k.则图2所示的动态规划可表示为f1(Si1)=cost(Sk1,Si1),i=1,…,T1;fj(Sji)=min1≤i′≤Tj-1{cost(Sj-1i′,Sji)+fj-1(Sji-′1)},i =1,…,T;j=2,…,k.(11)其中cost(Sji-′1,Sij)表示原料Sj i-′1进入料场j和原料Sji离开料场j所引起的目标函数的改变,这一共包含3方面的因素 :两种原料运输费用的改变、料场j的固定费用改变和原料的相邻关系发生变化所造成的惩罚费用 的变化.当原料Sji-′1进入料场j时,并不直接占用Sji的位置,而在所有可能的位置上 进行插入测试,以便找到一个最佳的插入位置.图2以某一原料为起点和终点的动态规划以上的动 态规划可以找到所有具有同一起点的环交换的最负费用.当各原料为起点的动态规划均被搜索过后 ,即可找到整个环交换邻域的近似最小负费用环.4嵌入迭代局域搜索策略的禁忌搜索算法禁忌搜 索算法是可以为许多难解的优化问题在较短时间内提供较好近优解的启发式算法.其本身所具有的 长短期禁忌表和回跳等机制使得其在整个运算过程的前期可以成功地跳出局部最优而得以快速下降 ,但在运行的后期靠其自身的力量已难以找到良好的搜索方向而最终仍要陷入局部最优.为进一步改进解的质量,在禁忌搜索运行后期引入基于随机kick移动的迭代局域搜索策略,该策略的随机特性增强了算法脱离局部最优的能力,从而有可能将 搜索引入一个更为有利的空间以找到更好解.4.1禁忌搜索算法本文所采用的禁忌搜索算法的主要结构与Now ick i<8>中的相似,为节省篇幅这里只介绍重点部分.初始解:首先按照料场的能力与固定费用的比 值对料场进行排序,之后开设未开料场中该比值最大的那个料场并将其设为当前料场.将所有未安 排存储空间的原料按其存在的状态分为块状原料、粉状原料和其他原料.对每一类原料,按照各原 料运至当前料场的运输费用分别对它们进行排序.之后以块状原料、其他原料和粉状原料的顺序, 将所有未分配原料排成一个未分配存储空间的原料序列并依次放入当前料场,直至该料场能力已被 充分利用.重复前面的步骤直到所有的原料都已被分配存储空间,此时得到问题的一个初始解.将原料按状态分类存放可以避免状态差别较
More summaries about the 大型钢铁企业原料场存储分配问题的研究