Loading [MathJax]/jax/output/SVG/jax.js
  • ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

铁水运输调度双层多目标约束优化模型

马亮 胡宸瀚 金福才 董炜

马亮, 胡宸瀚, 金福才, 董炜. 铁水运输调度双层多目标约束优化模型[J]. 西南交通大学学报, 2023, 58(2): 357-366, 397. doi: 10.3969/j.issn.0258-2724.20220008
引用本文: 马亮, 胡宸瀚, 金福才, 董炜. 铁水运输调度双层多目标约束优化模型[J]. 西南交通大学学报, 2023, 58(2): 357-366, 397. doi: 10.3969/j.issn.0258-2724.20220008
MA Liang, HU Chenhan, JIN Fucai, DONG Wei. Double-Layer and Multi-objective Constraint Optimization Model for Transportation Scheduling of Molten Iron[J]. Journal of Southwest Jiaotong University, 2023, 58(2): 357-366, 397. doi: 10.3969/j.issn.0258-2724.20220008
Citation: MA Liang, HU Chenhan, JIN Fucai, DONG Wei. Double-Layer and Multi-objective Constraint Optimization Model for Transportation Scheduling of Molten Iron[J]. Journal of Southwest Jiaotong University, 2023, 58(2): 357-366, 397. doi: 10.3969/j.issn.0258-2724.20220008

铁水运输调度双层多目标约束优化模型

doi: 10.3969/j.issn.0258-2724.20220008
基金项目: 中国国家铁路集团有限公司科技研究开发计划(L2021X001);四川省科技计划(2021YJ0070)
详细信息
    作者简介:

    马亮(1987—),男,讲师,研究方向为交通运输信息化与优化,E-mail:maliang@swjtu.edu.cn

  • 中图分类号: U294.1;N94

Double-Layer and Multi-objective Constraint Optimization Model for Transportation Scheduling of Molten Iron

  • 摘要:

    为实现铁水运输作业排程与资源分配的协同优化,基于约束程序累积调度和字典序多目标优化理论,研究了铁水运输调度双层多目标约束优化方法. 首先,基于铁水罐周转率最高和作业效率最高2个字典序优化目标,考虑作业时序、作业实施逻辑、铁水温降时限、铁水罐作业次数限制、资源容量限制和铁水罐资源池等约束条件,建立了上层的铁水运输作业排程约束优化模型;其次,以资源利用均衡度最高为目标,将作业实施唯一性和资源容量限制作为约束条件,建立了下层的铁水运输资源分配约束优化模型;最后,通过约束传播与多点构建性搜索的混合算法迭代求解整个模型. 通过实例验证表明:设计的混合算法求得的铁水罐周转率目标和运输作业效率目标,比基本深度优先回溯算法分别提高了14.29%和60.53%;字典序多目标模型比加权和单目标模型求解效率和求解质量分别提高了20.3%和11.11%.

     

  • 铁水运输调度优化是智慧钢铁厂的核心内容,在整个智慧铁水运输智能管控系统中起到承上启下的作用,是在上层的钢铁厂生产管理计划的基础上制定可实施的铁水运输生产作业计划,对现场运输作业、资源分配和机车运行进行优化排程和统筹安排,为下层作业执行的调车勾计划编制和信号联锁进路选排提供基础. 在铁水运输调度仿真研究中:李维刚等[1]通过铁水运输调度系统仿真模型评估论证了铁水处理能力、最佳的车辆配置数量和道路规划方案;卢绍文等[2]考虑了“起重机 + 过跨车”铁水运输过程中多种动态因素,对多场景的物流方案的可行性和性能指标进行仿真和评估;赵业清等[3]建立了高炉出铁和铁水预处理的时间Petri 网模型,设计了机车径路的优先级调度算法. 然而,计算机仿真方法只是从战术层面对运输调度性能进行验证和评估,未对决策层的运输调度方案特别是日常运输计划优化决策进行研究. 针对铁水运输调度优化研究:Tang 等[4]建立了炼钢车间生产与运输的协调调度的0-1整数规划模型,设计了带最坏情况算法和禁忌搜索算法,研究方法对于多种作业和多种资源的复杂运输过程存在模型爆炸和求解困难问题,且未对资源分配进行研究;范波等[5]建立了“一罐制”工艺下的运行径路选择与动态调度的多目标优化模型,未考虑资源容量受限约束和资源分配问题;杨小燕等[6]研究了铁水运输路径选择及自动避碰的动态规划方法,提高了鱼雷罐周转率和连续性,将速度相同的运输环节合并处理提高了求解效率,但也导致模型失真;陈在根等[7]分别建立了能力平衡层和实时调度层的数学优化模型,设计了基于人机界面的辅助实时调度系统,但是未进行优化求解;庞新富等[8]将铁水生产罐次优化调度问题划分为罐次批次划分、特殊罐次指派、特殊罐次加工时间确定、普通罐次指派与加工时间确定4个子问题,开发了铁水调度系统软件,但是对特殊罐次与普通罐次分别进行调度,降低了整体问题优化的全局性和综合性. 黄辉等[9-10]针对铁水重调度问题对扰动事件的模拟与识别模型、扰动的调整方法进行了离散事件仿真研究,并建立了铁水重调度问题的混合整数非线性规划模型,提出了两阶段求解方法[10],但是重调度时未考虑调整前后计划之间的摄动,降低了计划的延续性.

    上述文献在铁水调度仿真和优化方面取得了丰硕的研究成果,在一定程度上提高了运输效率和优化了资源配置. 但是部分优化和仿真模型考虑因素不全,只适用于固定工艺和场景,数学优化算法与模型之间耦合性较强,可扩展性较弱,同时未进行运输排程与资源分配的协同优化研究. 本文针对铁水运输调度优化问题提出更加贴近实际、扩展性更好的模型和求解效率更高、适用性更强的算法.

    某钢厂铁水运输主要流水线式作业包括:配空、受铁、取重、配重、倒罐和取空,主要有两种运输模式:“分段接续”与“一罐到底”.

    “分段接续”:调车机车工作区域比较固定,分为高炉区和钢厂区两个作业区,两者的衔接区域是调车场,高炉调机负责炉下配空和取重作业,钢厂调机负责配重和取空作业,高炉调机将重罐取至调车场供钢厂调机配重使用,钢厂调机将空罐取至调车场供高炉调机配空使用.

    “一罐到底”:调车机车无作业区域限制,铁水罐从配空、受铁、取重、配重、倒罐和取空整个作业过程由一台调机完成,中途不更换调机.

    铁水运输调度优化问题指在已知运输模式、生产工艺、作业流程、资源能力、高炉生产计划和炼钢生产计划的基础上,以铁水罐周转率最高、生产作业效率最高、资源利用均衡度最高等为目标,实现作业排程和资源分配的优化,达到兑现钢铁生产计划和降本增效的目的,为具体的调车作业和信号联锁进路控制提供决策支持. 整个问题包括铁水运输作业排程与铁水运输资源分配2个优化子问题:铁水运输作业排程问题是在资源容量限制下依据运输模式等要求对各作业进行安排,消除各作业在时空上的冲突,达到资源利用率最高的目的;铁水运输资源分配问题是指在作业排程的基础上,对各作业分配资源,满足资源均衡使用的目的. 这两个子问题之间存在明显的先后求解顺序,即:作业排程问题求解的结果是资源分配问题求解的输入.

    依据铁水运输调度优化2个子问题之间的关系,同时为了提高模型的求解效率,本文建立“分段接续”模式下铁水运输调度的双层优化模型:首先,基于约束程序(constraint programming, CP)[11]中的累积调度(cumulative scheduling problem, CuSP)[11-12]和字典序多目标优化(lexicographic multi-objective optimization, LMO)[12-13]理论,建立铁水运输作业排程约束优化模型;然后,在获得最优的作业排程方案的基础上,建立铁水运输资源分配约束优化模型;最后,通过约束传播(constraint propagation, CPr)[11]和多点构建性搜索(multi-point constructive search, MPCS)[14]的混合迭代算法(IAIS-CPr-MPCS)[15]求解整个铁水运输调度双层多目标约束优化模型,得到优化的作业排程与资源分配计划,整个问题求解思路如图1所示.

    图  1  铁水运输调度优化问题求解思路
    Figure  1.  Solving process of scheduling molten iron transportation

    1) 铁水区包含多座高炉,每座高炉独立平行地出铁水,每座高炉包含多个出铁厂,每座高炉的多个出铁厂之间交替循环出铁.

    2) 铁水罐全作业流程为:配空→受铁→取重→配重→倒罐→取空→配空→……,采用“分段接续”运输方式.

    3) 同种类型作业的持续时间相同,采用统计的标准作业时间,所有作业实施过程中不可中断.

    4) 通过相邻出铁计划合并取整方法,将所有的出铁计划转化为出铁量为1个整罐的出铁计划.

    5) 铁水分配无限制,即任意高炉的铁水可以提供给任意钢厂,运输过程中不存在径路冲突问题.

    6) 初始时刻所有的铁水罐等待去高炉配空作业.

    铁水运输作业排程前可以根据高炉生产管理信息系统获得铁水出铁计划和各资源设备的初始状态,根据历史信息统计得到各作业的平均持续时间. 已知量定义如表1所示.

    表  1  铁水运输作业排程约束优化模型常量符号定义
    Table  1.  Constant definitions for constrained optimization model for transportation scheduling of molten iron
    常量符号说明
    T 铁水运输计划周期,精度为 1 min
    sT 计划周期的开始时间
    eT 计划周期的结束时间
    tT 铁水运输计划周期的索引下标
    NK 铁水罐数量
    iNK 铁水罐的索引下标
    NP 出铁总次数
    jNP 出铁计划的索引下标
    stpjT j次出铁开始时间,min
    etpjT j次出铁结束时间,min
    dtpj j次出铁持续时间,min
    NTL 钢厂倒罐作业的倒罐线数量
    NTK 每条倒罐线同时进行倒罐作业的铁水罐数
    NPL 高炉调机数量
    NPK  空罐从调车场到铁水区运输和重罐从铁水区到调车场运输的固定编组罐数
    NSL 钢厂调机数量
    NSK  重罐从调车场到钢厂运输和空罐从钢厂到调车场运输的固定编组罐数
    NJO  铁水运输作业种类总数,包括取空、配空、受铁、取重、配重、倒罐
    k  作业种类索引下标,1:取空,2:配空,3:受铁,4:取重,5:配重,6:倒罐
    tk 每一种作业持续标准时间,min
    tLP 铁水罐从受铁到倒罐持续时间上限,min
    LTC 铁水罐每日出铁倒罐作业次数上限
    下载: 导出CSV 
    | 显示表格

    铁水运输作业排程模型主要在满足资源容量限制的前提下决策各作业的起止时间,变量定义如表2所示.

    表  2  铁水运输作业排程约束优化模型变量符号定义
    Table  2.  Variable definitions for constrained optimization model for transportation scheduling of molten iron
    变量符号说明
    Ji,j,k  第i个铁水罐的第j次出铁周期内的第k种作业变量
    oi,j,k{0,1} Ji,j,k作业的是否实施变量
    si,j,kT Ji,j,k作业的开始时间变量,min
    ei,j,kT Ji,j,k作业的结束时间变量,min
    di,j,k=ei,j,ksi,j,k Ji,j,k作业的持续时间变量,min
    JTCi,j  第i个铁水罐第j次出铁周期包含所有作业的全流程作业变量
    oTCi,jsTCi,jeTCi,jdTCi,j  作业JTCi,j的是否实施、开始时间、结束时间、持续时间变量
    JBFj 高炉第j次出铁作业变量
    oBFjsBFjeBFjdBFj  作业JBFj的是否实施、开始时间、结束时间、持续时间变量
    JKi  第i个铁水罐全出铁周期全流程作业变量
    oKisKieKidKi  分别为作业JKi的是否实施、开始时间、结束时间、持续时间变量
    下载: 导出CSV 
    | 显示表格

    采用约束程序中逻辑谓词的方式[11-12]描述约束条件与目标函数.

    1) 对于同一个铁水罐,整个计划周期内所有作业不得在时间上重叠,

    i,t:j,k,t{si,j,k,,ei,j,k}oi,j,k1. (1)

    2) 各种作业持续时间约束,

    i,j,k:(oi,j,k==1)(di,j,k==tk). (2)

    3) 同一个铁水罐每一次出铁周期内作业间先后实施时序关系,

    i,j,1kNJO1:ei,j,ksi,j,k+1. (3)

    4) 同一个铁水罐每一次出铁周期内作业间实施逻辑关系为

    i,j,1kNJO1:(oi,j,k+1==1)(oi,j,k==1). (4)

    5) 铁水温降时间限制.

    a) 铁水罐受铁之后必须完成倒罐作业,

    i,j:oi,j,3==oi,j,6; (5)

    b) 铁水从出铁到倒罐完毕低于温降时间上限,

    i,j:(oi,j,6==1)(ei,j,6ei,j,3tLP). (6)

    6) 铁水罐每日受铁倒罐作业次数约束:铁水罐使用一定次数之后需要进行排渣作业确保铁水罐工作质量,同时为了确保各铁水罐间使用均衡,

    i:NPj=1oTCi,jLTC. (7)

    7) 每一个铁水罐每一周期全流程和全周期全流程作业实施与起止时间约束.

    a) 只要铁水罐每一周期中有一个作业实施,则该铁水罐该周期的全流程作业实施,

    i,j:(oTCi,j==1)(NJOk=1oi,j,k1); (8)

    b) 只要铁水罐任意周期的全流程作业实施,则该铁水罐全周期全流程作业实施,

    i,j:(oKi==1)(NPj=1oTCi,j1); (9)

    c) 铁水罐每一周期全流程作业的开始时刻等于该周期所有作业最早开始时刻,

    i,j:sTCi,j==min(si,j,k|1kNJO); (10)

    d) 铁水罐全周期全流程作业的开始时刻等于所有周期全流程作业最早开始时刻,

    i:sKi==min(sTCi,j|1jNP); (11)

    e) 铁水罐每一周期全流程作业的结束时刻等于该周期所有作业最晚结束时刻,

    i,j:eTCi,j==max(ei,j,k|1kNJO); (12)

    f) 铁水罐全周期全流程作业的结束时刻等于所有周期全流程作业最晚结束时刻,

    i:eKi==max(eTCi,j|1jNP). (13)

    8) 满足出铁计划约束:高炉出铁作业必定实施,且存在铁水罐受铁作业与高炉出铁作业起止时间相同,

    j,i:(oBFj==1)(oi,j,3==1)(si,j,3==sBFj==stpj)(ei,j,3==eBFj==etpj). (14)

    9) 同一个铁水罐不同作业周期间的衔接约束.

    a) 后一次的配空作业开始时刻晚于前一次取空作业结束时刻,受铁作业进行先后排序,

    i,j{1,,NP1},j{j+1,,NP}:(ei,j,1si,j,2)(si,j,3si,j,3); (15)

    b) 后一次的配空作业实施蕴含着前一次取空作业实施,

    i,j{1,,NP1},j{j+1,,NP}:(oi,j,2==1)(oi,j,1==1). (16)

    10) 倒罐线使用约束,

    tT:i,j,t{si,j,6,,ei,j,6}oi,j,6NTLNTK. (17)

    11) 调机使用.

    a) 高炉调机使用约束:配空和取重作业过程不超过高炉调机牵引限制,

    tT:(i,j,t{si,j,2,,ei,j,2}oi,j,2)+(i,j,t{si,j,4,,ei,j,4}oi,j,4)NPLNPK; (18)

    b) 钢厂调机使用约束:配重和取空作业过程不超过钢厂调机牵引限制,

    tT:(i,j,t{si,j,1,,ei,j,1}oi,j,1)+(i,j,t{si,j,5,,ei,j,5}oi,j,5)NSLNSK. (19)

    12) 铁水罐资源池约束:“分段接续”模式下调车场可以看作空罐和重罐的资源池.

    a) 空铁水罐资源池约束:配空的时候调车场里有空罐车,

    tT:i,j{2,,NP},t{si,j,1,,ei,j,1}oi,j,1i,j{2,,NP},t{si,j,2,,ei,j,2}oi,j,20; (20)

    b) 重铁水罐资源池约束:配重的时候调车场里有重罐车,

    tT:i,j,t{si,j,4,,ei,j,4}oi,j,4i,j,t{si,j,5,,ei,j,5}oi,j,50. (21)

    为了提高铁水运输效率和降低成本,在满足出铁计划、生产工艺、作业流程和资源容量等限制下,提高铁水罐的周转率和减少作业等待时间,建立2个具有字典序的目标函数.

    在满足锅炉生产需求和钢厂生产需求的前提下,参与运输的铁水罐总数最少,铁水罐的周转率最高目标为

    min f1=NKi=1oKi. (22)

    铁水罐作业等待时间最少、效率最高目标为

    min f2=NKi=1NPj=1(oTCi,jdTCi,j). (23)

    为了解决线性加权和法将多目标转为单目标,在实际应用中权值无法确定导致模型稳定性较差的问题,需要按照目标函数的优先级设计成字典序多目标,优先级高的目标求解是优先级低目标求解的基础. 本文以式(22)和式(23)为基础,为了满足现场对于降低运输成本和提高调车机车周转率的优先需求,结合本模型特点建立的字典序多目标函数为

    lex{ min f1,min f2}. (24)

    同时,在本模型中增加“中途不换调车机车约束”和删除“铁水罐资源池约束”即可变为“一罐到底”模式下的铁水运输调度模型. 针对不同的生产工艺和运输模式,可以通过增加或者删除作业变量来实现.

    在满足资源容量限制的前提下对铁水运输作业排程优化之后,可以建立资源分配约束优化模型,实现作业与资源的选择与配对.

    依据铁水运输作业排程约束优化模型求解之后得到各种作业实施的开始时间与结束时间常量,如表3,其他资源相关已知量同表1所示.

    表  3  铁水运输资源分配约束优化模型常量符号定义
    Table  3.  Constant definitions for constrained optimization model of resource allocation in metal iron transportation
    常量符号说明
    Mk  作业排程优化之后可实施的铁水罐第k种作业总数
    mk  作业排程优化之后可实施的铁水罐第k种作业索引下标
    JPRk,mk 铁水罐第k种的第mk个可实施作业
    sPRk,mk JPRk,mk作业的开始时间,min
    ePRk,mk JPRk,mk作业的结束时间,min
    dPRk,mk=ePRk,mksPRk,mk JPRk,mk作业的持续时间,min
    1n1NPL 高炉调机索引下标
    1n2NSL 钢厂调机索引下标
    1n3NTL 钢厂倒罐线索引下标
    下载: 导出CSV 
    | 显示表格

    铁水运输资源分配主要决策各资源执行作业情况,包括各作业的起止时间,变量定义如表4所示.

    表  4  铁水运输资源分配约束优化模型变量符号定义
    Table  4.  Variable definitions for constrained optimization model of resource allocation in metal iron transportation
    变量符号说明
    JEDn1,m2 高炉调机执行配空作业变量
    oEDn1,m2{0,1} JEDn1,m2作业的是否实施变量
    sEDn1,m2eEDn1,m2  作业JEDn1,m2的开始时间和结束时间变量,sEDn1,m2=sPR2,m2eEDn1,m2=ePR2,m2
    JFTn1,m4 高炉调机执行取重作业变量
    oFTn1,m4{0,1} JFTn1,m4作业的是否实施变量
    sFTn1,m4eFTn1,m4  作业JFTn1,m4的开始时间和结束时间变量,sFTn1,m4=sPR4,m4eFTn1,m4=ePR4,m4
    JETn2,m1 钢厂调机执行取空作业变量
    oETn2,m1{0,1} JETn2,m1作业的是否实施变量
    sETn2,m1eETn2,m1  作业JETn2,m1的开始时间和结束时间变量,sETn2,m1=sPR1,m1eETn2,m1=ePR1,m1
    JFDn2,m5 钢厂调机执行配重作业变量
    oFDn2,m5{0,1} JFDn2,m5作业的是否实施变量
    sFDn2,m5eFDn2,m5  作业JFDn2,m5的开始时间和结束时间变量,sFDn2,m5=sPR5,m5eFDn2,m5=ePR5,m5
    JTPn3,m6 倒罐线执行倒罐作业变量
    oTPn3,m6{0,1} JTPn3,m6作业的是否实施变量
    sTPn3,m6eTPn3,m6  作业JTPn3,m6的开始时间和结束时间变量,sTPn3,m6=sPR6,m6eTPn3,m6=ePR6,m6
    下载: 导出CSV 
    | 显示表格

    1) 作业实施的唯一性约束

    a) 配空作业实施唯一性约束为

    m2:NPLn1=1oEDn1,m2==1; (25)

    b) 取重作业实施唯一性约束为

    m4:NPLn1=1oFTn1,m4==1; (26)

    c) 配重作业实施唯一性约束为

    m5:NSLn2=1oFDn2,m5==1; (27)

    d) 取空作业实施唯一性约束为

    m1:NSLn2=1oETn2,m1==1; (28)

    e) 倒罐作业实施唯一性约束为

    m6:NTLn3=1oTPn3,m6==1. (29)

    2) 资源容量限制

    a) 高炉每一台调机容量约束为

    n1,tT:(m2,t{sEDn1,m2,,eEDn1,m2}oEDn1,m2)+(m4,t{sFTn1,m4,,eFTn1,m4}oFTn1,m4)NPK; (30)

    b) 钢厂每一台调机容量约束为

    n2,tT:(m1,t{sETn2,m1,,eETn2,m1}oETn2,m1)+(m5,t{sFDn2,m5,,eFDn2,m5}oFDn2,m5)NSK; (31)

    c) 每一条倒罐线容量约束为

    n3,tT:m6,t{sTPn3,m6,,eTPn3,m6}oTPn3,m6NTL. (32)

    1) 各高炉调机之间承担作业数量最大差表达式为

    fPL=max((M2m2=1oEDn1,m2+M4m4=1oFTn1,m4)|n1)min((M2m2=1oEDn1,m2+M4m4=1oFTn1,m4)|n1). (33)

    2) 各钢厂调机之间承担作业数量最大差表达式为

    fSL=max((M1m1=1oETn2,m1+M5m5=1oFDn2,m5)|n2)min((M1m1=1oETn2,m1+M5m5=1oFDn2,m5)|n2). (34)

    3) 各倒罐线之间承担作业数量最大差表达式:

    fTL=max(M6m6=1oTPn3,m6|n3)min(M6m6=1oTPn3,m6|n3). (35)

    4) 各种资源均衡使用,各种资源所承担的作业任务数量相差较少:

    min f3=fPL+fSL+fTL. (36)

    令约束优化模型的变量集记为X,变量论域集记为D,约束集记为C,目标函数集记为F,则上层铁水运输作业排程约束优化模型表示为OSCO=(X1,D1,C1,lex{ min f1,min f2),下层铁水运输资源分配约束优化模型表示为RACO=(X2,D2,C2,min f3). 使用约束传播与多点构建性搜索的混合迭代算法(IAIS-CPr-MPCS)[15]求解整个模型的步骤如下:

    步骤1 使用CPr[11]与MPCS[14]的混合算法(CPr-MPCS)求解模型X1,D1,C1,min f1,若得到解集S1不为空且最优的目标函数值为 fopt1,则转到步骤2,否则,返回“无解”;

    步骤2 将解s1S1作为模型X1,D1,C1,min f2的初始解,并增加避免目标函数f1劣化的约束f1 fopt1,通过CPr-MPCS求解得到解集S2不为空且最优的目标函数值为 fopt2,则转到步骤3,否则,返回铁水运输作业排程约束优化模型(OSCO)的最优解为s1

    步骤3 在铁水运输资源分配约束优化模型(RACO)中增加避免目标函数f2劣化的约束f2 fopt2,通过CPr-MPCS求解得到解集S3不为空且最优的目标函数值为 fopt3,则返回铁水运输资源分配最优解为s3S3,否则,返回RACO“无解”.

    CPr包括:变量论域约减和约减后的传播两部分[11]. 针对式(10)~(12)累积资源约束,使用基于边缘搜索(Edge-finding)策略[11]的累积资源约束减域算法. 对于剩余约束,使用弧边界相容(Arc-B-Consistency)[11]减域算法. 在多点构建性搜索算法(MPCS)中引入约束传播技术(CPr)可以用已实例化变量进行相容性检查避免未来冲突,缩小了决策变量的临时论域,加快了求解效率. CPr-MPCS混合算法步骤见文献[15].

    根据现场调研得知调度员对计划的误差容忍度和编制计划时间上限为3分. 因此,设定第一层求解时间为30 s,第二层求解时间上限为120 s,第三层求解时间上限为30 s. 带精英解的回溯算法search(e,b)在基本深度优先回溯算法(backtracking algorithms, BT)引入搜索失效重启策略[11],设定初始失败次数为100,失败次数增长率为1.1,设置精英解集合基数为10. 同时,在search(e,b)算法中引入取值排序启发式算法提高算法收敛速度和可能性.

    CPr-MPCS算法与模型自身结构关联不紧密,只与变量类型、变量论域和变量间的约束关系相关.

    某钢铁厂目前有铁水罐18台,高炉调机2台(调机1和调机2),钢厂调机2台(调机3和调机4),每台调机最多可以牵引2台铁水罐. 钢厂有2条倒罐线(倒罐线1和倒罐线2),每一条倒罐线同时最多可以翻转2台铁水罐. 取重运输标准时间为20 min,配空作业标准时间为5 min,配重作业标准时间为5 min,取空运输标准时间为5 min,倒罐作业标准时间为15 min. 铁水从出铁完毕到倒罐间隔时间上限为120 min,一台铁水罐1天最多受铁倒罐4次. 有A、B两座高炉同步出铁,每座高炉有两个出铁厂交替出铁. 每一个出铁厂一次出铁周期平均时间为150 min,一次出铁平均2.5罐,每个出铁周期内第2罐出铁时间是第1罐出铁时间的0.4倍,最后半罐出铁时间是第1罐的0.5倍. 铁水罐需要装满罐之后方可被取走,对上述出铁计划中相邻铁次的两个半罐合并取整处理成每次出铁均为1个整罐的计划. 令整个计划周期的开始时刻为0,将A、B两座高炉同步出铁计划合并后,预处理后的该钢厂某日出铁计划如表5所示.

    表  5  某钢厂某日高炉出铁计划
    Table  5.  Blast furnace tapping plan of of steel plant in one day min
    出铁次/次高炉出铁厂开始时间结束时间
    1/2A/B铁厂 1585
    3/4A/B铁厂 185115
    5/6A/B铁厂 1115345
    7/8A/B铁厂 2155235
    9/10A/B铁厂 2235265
    11/12A/B铁厂 2265495
    13/14A/B铁厂 1345375
    15/16A/B铁厂 1375455
    17/18A/B铁厂 2495525
    19/20A/B铁厂 2525605
    21/22A/B铁厂 1605685
    23/24A/B铁厂 1685715
    25/26A/B铁厂 1715945
    27/28A/B铁厂 2755835
    29/30A/B铁厂 2835865
    31/32A/B铁厂 28651095
    33/34A/B铁厂 1945975
    35/36A/B铁厂 19751055
    37/38A/B铁厂 210951125
    39/40A/B铁厂 211251205
    41/42A/B铁厂 112051285
    43/44A/B铁厂 112851315
    45/46A/B铁厂 113151545
    47/48A/B铁厂 213551435
    下载: 导出CSV 
    | 显示表格

    在Inter Core i7 2.3GHz & DRAM 16G & Windows 10环境下的PC机上,使用Visual Studio 2019开发环境和C# 语言建立铁水运输作业排程约束优化模型,该模型共计有6 978个变量和74 057个约束条件. 各目标函数求解过程如图23所示,最后得到:总计需要12台调车机车执行所有作业,各铁水罐各出铁周期全流程作业持续时间总计为6 835 min. 目标函数值在整个求解过程中均呈现单调递减趋势,未出现波动,表明算法求解收敛效果较好、比较稳定、效率较高,达到了在使用最少调车机车的情况下铁水运输作业效率最高的目的.

    图  2  铁水罐周转率最高目标f1求解过程
    Figure  2.  Solution process of highest turnover rate of molten iron tankf1
    图  3  运输作业效率最高目标f2求解过程
    Figure  3.  Solution process of highest operation efficiency f2

    在铁水运输作业排程优化结果的基础上,以资源利用均衡度最高为目标,建立铁水运输资源分配约束优化模型,该模型共计有717个变量和245个约束条件,通过计算得到最优解搜索过程如图4所示,最终得到各资源承担作业数量最大差额为1.

    图  4  资源使用均衡度最高目标f3求解过程
    Figure  4.  Solution process of highest resource utilization balance f3

    附加材料图S1所示为铁路运输作业排程和铁水运输资源分配优化结果的甘特图界面. 通过该界面调度人员能够全面掌握各铁水罐各作业的时间安排和各资源所承担作业任务情况,可以对各作业的执行效率、各铁水罐的周转率和各资源使用率进行定量分析,达到辅助调度指挥的目的.

    通过图234和附加材料图S1可以验证本模型的有效性和算法的高效性:铁水罐受铁作业覆盖了所有的出铁计划,所有铁水罐受铁倒罐次数不超过4次,各铁水罐使用比较均衡,每一个铁水罐各作业间不存在时间冲突,各出铁周期内铁水罐各作业之间不存在等待情况,作业效率最高;高炉调机覆盖了所有的铁水罐配空和取重作业,钢厂调机覆盖了所有的铁水罐配重和取空作业,倒罐线覆盖了所有的倒罐作业;各资源承担的作业数量未超出资源容量限制,且各资源间承担的总作业次数相差最小,达到资源利用均衡度最高目标.

    为了验证CPr-MPCS算法的高效性,在算例数据和算法运行环境不变的前提下,设置铁水运输作业排程模型每一个目标函数求解时间上限均为120 s,采用基本深度优先回溯算法(BT)对铁水运输作业排程约束优化模型进行求解,得到2个目标函数的求解过程如图56所示,在达到求解时间上限时得到:总计需要14台调车机车,各铁水罐各出铁周期全流程作业持续时间总计为17 319 min.

    图  5  使用BT算法求解f1过程
    Figure  5.  Solution process of f1 with BT algorithm
    图  6  使用BT算法求解f2过程
    Figure  6.  Solution process of f2 with BT algorithm

    对比图23图56可得:CPr-MPCS算法比BT算法求解效率高;在铁水罐周转率最高目标求解时高了14.29%,在运输作业效率最高目标求解时高了60.53%.

    将铁水运输作业排程约束优化模型的两个目标函数通过线性加权和法转化为单目标进行求解. 加权和单目标表示为

    minfW = α1f1+α2f2, (37)

    式中:α1α2分别为铁水罐的周转率最高目标 f1和铁水罐作业等待时间最少目标 f2对应的权值.

    由于f1 f2的数量级分别是十和万,分别选取α1=500α2=1α1=2000α2=1两组权值,令求解时间上限为150 s,使用CPr-MPCS算法求解加权和单目标minfW,求解过程如图7所示.

    图  7  加权和单目标fW求解过程
    Figure  7.  Solution process of fWwith weights and single objective

    图7可得:当α1=500α2=1,在111.3 s时得到的最优目标值分别是f1=14 f2=6835;当α1=2000α2=1,在129.6 s时得到的最优目标值分别是f1=13 f2=6835. 与5.1节对比分析得到:加权和单目标法求解时,不同的目标权值会得到不同的求解结果;字典序多目标方法比加权单目标方法,求得最优解耗时平均缩短20.30%,目标函数f1平均求解质量提高11.11%;在加权和单目标求解过程中f1 f2的值存在波动,收敛稳定性不如字典序多目标方法. 因此,基于字典序多目标方法建立的模型在实际应用中更易操作、更稳定高效.

    若优先求解 f2,再求解 f1,即将式(24)建立的字典序多目标改为

    lex{min f2,min f1}. (38)

    经测试,在不到1 s的计算时间得到min f2=0,且所有的作业均未实施,该最优解无效. 因此,目标函数f2只有在目标函数f1求解的基础上再求解才有意义,验证了本模型和算法的正确性.

    本文建立的铁水运输调度双层多目标约束优化模型考虑了铁水运输工艺流程和资源容量限制等现场各种因素. 通过适当修改作业流程时序和实施逻辑等约束,即可使得优化模型适用于其他运输模式和生产工艺场景,具有较高的可扩展性. 在本模型中增加“中途不更换调机约束”和删除“铁水罐资源池约束”即可适应“一罐到底”模式;通过增加或者删除作业变量,模型可以适应不同运输生产流程.

    所提出的双层优化模型降低了整个模型的求解空间,提高了作业排程与资源分配计划的求解效率. 字典序多目标与加权和单目标相比提高了模型的稳定性和求解效率,更便于实际应用. 所使用的约束传播与多点构建性搜索的混合迭代算法,与模型结构相关性较小,求解效率比基本回溯算法较高,对于发生扰动事件之后的实时重新调度提供了理论基础. 本论文的研究为未来作业执行的调车勾计划自动编制和信号进路自动选排提供支撑.

    备注:附加材料在中国知网该论文详情页中获取.

  • 图 1  铁水运输调度优化问题求解思路

    Figure 1.  Solving process of scheduling molten iron transportation

    图 2  铁水罐周转率最高目标f1求解过程

    Figure 2.  Solution process of highest turnover rate of molten iron tankf1

    图 3  运输作业效率最高目标f2求解过程

    Figure 3.  Solution process of highest operation efficiency f2

    图 4  资源使用均衡度最高目标f3求解过程

    Figure 4.  Solution process of highest resource utilization balance f3

    图 5  使用BT算法求解f1过程

    Figure 5.  Solution process of f1 with BT algorithm

    图 6  使用BT算法求解f2过程

    Figure 6.  Solution process of f2 with BT algorithm

    图 7  加权和单目标fW求解过程

    Figure 7.  Solution process of fWwith weights and single objective

    表  1  铁水运输作业排程约束优化模型常量符号定义

    Table  1.   Constant definitions for constrained optimization model for transportation scheduling of molten iron

    常量符号说明
    T 铁水运输计划周期,精度为 1 min
    sT 计划周期的开始时间
    eT 计划周期的结束时间
    tT 铁水运输计划周期的索引下标
    NK 铁水罐数量
    iNK 铁水罐的索引下标
    NP 出铁总次数
    jNP 出铁计划的索引下标
    stpjT j次出铁开始时间,min
    etpjT j次出铁结束时间,min
    dtpj j次出铁持续时间,min
    NTL 钢厂倒罐作业的倒罐线数量
    NTK 每条倒罐线同时进行倒罐作业的铁水罐数
    NPL 高炉调机数量
    NPK  空罐从调车场到铁水区运输和重罐从铁水区到调车场运输的固定编组罐数
    NSL 钢厂调机数量
    NSK  重罐从调车场到钢厂运输和空罐从钢厂到调车场运输的固定编组罐数
    NJO  铁水运输作业种类总数,包括取空、配空、受铁、取重、配重、倒罐
    k  作业种类索引下标,1:取空,2:配空,3:受铁,4:取重,5:配重,6:倒罐
    tk 每一种作业持续标准时间,min
    tLP 铁水罐从受铁到倒罐持续时间上限,min
    LTC 铁水罐每日出铁倒罐作业次数上限
    下载: 导出CSV

    表  2  铁水运输作业排程约束优化模型变量符号定义

    Table  2.   Variable definitions for constrained optimization model for transportation scheduling of molten iron

    变量符号说明
    Ji,j,k  第i个铁水罐的第j次出铁周期内的第k种作业变量
    oi,j,k{0,1} Ji,j,k作业的是否实施变量
    si,j,kT Ji,j,k作业的开始时间变量,min
    ei,j,kT Ji,j,k作业的结束时间变量,min
    di,j,k=ei,j,ksi,j,k Ji,j,k作业的持续时间变量,min
    JTCi,j  第i个铁水罐第j次出铁周期包含所有作业的全流程作业变量
    oTCi,jsTCi,jeTCi,jdTCi,j  作业JTCi,j的是否实施、开始时间、结束时间、持续时间变量
    JBFj 高炉第j次出铁作业变量
    oBFjsBFjeBFjdBFj  作业JBFj的是否实施、开始时间、结束时间、持续时间变量
    JKi  第i个铁水罐全出铁周期全流程作业变量
    oKisKieKidKi  分别为作业JKi的是否实施、开始时间、结束时间、持续时间变量
    下载: 导出CSV

    表  3  铁水运输资源分配约束优化模型常量符号定义

    Table  3.   Constant definitions for constrained optimization model of resource allocation in metal iron transportation

    常量符号说明
    Mk  作业排程优化之后可实施的铁水罐第k种作业总数
    mk  作业排程优化之后可实施的铁水罐第k种作业索引下标
    JPRk,mk 铁水罐第k种的第mk个可实施作业
    sPRk,mk JPRk,mk作业的开始时间,min
    ePRk,mk JPRk,mk作业的结束时间,min
    dPRk,mk=ePRk,mksPRk,mk JPRk,mk作业的持续时间,min
    1n1NPL 高炉调机索引下标
    1n2NSL 钢厂调机索引下标
    1n3NTL 钢厂倒罐线索引下标
    下载: 导出CSV

    表  4  铁水运输资源分配约束优化模型变量符号定义

    Table  4.   Variable definitions for constrained optimization model of resource allocation in metal iron transportation

    变量符号说明
    JEDn1,m2 高炉调机执行配空作业变量
    oEDn1,m2{0,1} JEDn1,m2作业的是否实施变量
    sEDn1,m2eEDn1,m2  作业JEDn1,m2的开始时间和结束时间变量,sEDn1,m2=sPR2,m2eEDn1,m2=ePR2,m2
    JFTn1,m4 高炉调机执行取重作业变量
    oFTn1,m4{0,1} JFTn1,m4作业的是否实施变量
    sFTn1,m4eFTn1,m4  作业JFTn1,m4的开始时间和结束时间变量,sFTn1,m4=sPR4,m4eFTn1,m4=ePR4,m4
    JETn2,m1 钢厂调机执行取空作业变量
    oETn2,m1{0,1} JETn2,m1作业的是否实施变量
    sETn2,m1eETn2,m1  作业JETn2,m1的开始时间和结束时间变量,sETn2,m1=sPR1,m1eETn2,m1=ePR1,m1
    JFDn2,m5 钢厂调机执行配重作业变量
    oFDn2,m5{0,1} JFDn2,m5作业的是否实施变量
    sFDn2,m5eFDn2,m5  作业JFDn2,m5的开始时间和结束时间变量,sFDn2,m5=sPR5,m5eFDn2,m5=ePR5,m5
    JTPn3,m6 倒罐线执行倒罐作业变量
    oTPn3,m6{0,1} JTPn3,m6作业的是否实施变量
    sTPn3,m6eTPn3,m6  作业JTPn3,m6的开始时间和结束时间变量,sTPn3,m6=sPR6,m6eTPn3,m6=ePR6,m6
    下载: 导出CSV

    表  5  某钢厂某日高炉出铁计划

    Table  5.   Blast furnace tapping plan of of steel plant in one day min

    出铁次/次高炉出铁厂开始时间结束时间
    1/2A/B铁厂 1585
    3/4A/B铁厂 185115
    5/6A/B铁厂 1115345
    7/8A/B铁厂 2155235
    9/10A/B铁厂 2235265
    11/12A/B铁厂 2265495
    13/14A/B铁厂 1345375
    15/16A/B铁厂 1375455
    17/18A/B铁厂 2495525
    19/20A/B铁厂 2525605
    21/22A/B铁厂 1605685
    23/24A/B铁厂 1685715
    25/26A/B铁厂 1715945
    27/28A/B铁厂 2755835
    29/30A/B铁厂 2835865
    31/32A/B铁厂 28651095
    33/34A/B铁厂 1945975
    35/36A/B铁厂 19751055
    37/38A/B铁厂 210951125
    39/40A/B铁厂 211251205
    41/42A/B铁厂 112051285
    43/44A/B铁厂 112851315
    45/46A/B铁厂 113151545
    47/48A/B铁厂 213551435
    下载: 导出CSV
  • [1] 李维刚,叶欣,赵云涛. 铁水运输调度系统仿真[J]. 计算机应用,2019,39(增2): 206-210.

    LI Weigang, YE Xin, ZHAO Yuntao. Simulation of iron melt transportation dispatching system[J]. Journal of Computer Applications, 2019, 39(S2): 206-210.
    [2] 卢绍文,罗小川. “起重机 + 过跨车”铁水物流多场景仿真[J]. 系统仿真学报,2017,29(10): 2549-2555.

    LU Shaowen, LUO Xiaochuan. Design of multi-scenario simulation of molten iron logistics system with cranes and cross-train AGVs[J]. Journal of System Simulation, 2017, 29(10): 2549-2555.
    [3] 赵业清. 基于时间影响网络的铁水运输系统时间Petri网建模[J]. 冶金自动化,2015,39(2): 35-40. doi: 10.3969/j.issn.1000-7059.2015.02.007

    ZHAO Yeqing. Modeling of molten iron transportation system in the steel enterprise based on time influence net and time Petri net[J]. Metallurgical Industry Automation, 2015, 39(2): 35-40. doi: 10.3969/j.issn.1000-7059.2015.02.007
    [4] TANG L, JING G, HU G. Steelmaking and refining coordinated scheduling problem with waiting time and transportation consideration[J]. Computers & Industrial Engineering, 2010, 58(2): 239-248.
    [5] 范波,蔡乐才. “一罐制”铁水调度优化模型的研究[J]. 四川理工学院学报(自然科学版),2014,27(1): 49-52.

    FAN Bo, CAI Lecai. Research on scheduling optimization model of hot metal can of system[J]. Journal of Sichuan University of Science & Engineering (Natural Science Edition), 2014, 27(1): 49-52.
    [6] 杨小燕,崔炳谋. 钢铁企业铁水运输调度优化与仿真[J]. 计算机应用,2013,33(10): 2977-2980. doi: 10.3724/SP.J.1087.2013.02977

    YANG Xiaoyan, CUI Bingmou. Molten iron transportation scheduling optimization and simulation of iron and steel enterprises[J]. Journal of Computer Applications, 2013, 33(10): 2977-2980. doi: 10.3724/SP.J.1087.2013.02977
    [7] 陈在根,李子阳,卢敏,等. 大型钢铁企业铁水物流动态平衡与实时调度技术研究[J]. 计算机应用与软件,2012,29(8): 115-117,179. doi: 10.3969/j.issn.1000-386X.2012.08.030

    CHEN Zaigen, LI Ziyang, LU Min, et al. Research on dynamic balance and real-time scheduling of HM logistics in large steel enterprise[J]. Computer Applications and Software, 2012, 29(8): 115-117,179. doi: 10.3969/j.issn.1000-386X.2012.08.030
    [8] 庞新富,黄辉,姜迎春,等. 面向鱼雷罐车运输模式的铁水生产罐次调度方法及应用[J]. 计算机集成制造系统,2018,24(6): 1468-1482.

    PANG Xinfu, HUANG Hui, JIANG Yingchun, et al. Hot metal production scheduling method for torpedo car transportation[J]. Computer Integrated Manufacturing Systems, 2018, 24(6): 1468-1482.
    [9] 黄辉,柴天佑,郑秉霖,等. 铁水调度仿真系统的设计与实现[J]. 系统仿真学报,2012,24(6): 1192-1199.

    HUANG Hui, CHAI Tianyou, ZHENG Binglin, et al. Design and development of molten iron scheduling simulation system[J]. Journal of System Simulation, 2012, 24(6): 1192-1199.
    [10] 黄辉,罗小川,郑秉霖,等. 炼铁-炼钢区间铁水重调度方法及其应用[J]. 系统工程学报,2013,28(2): 234-247.

    HUANG Hui, LUO Xiaochuan, ZHENG Binglin, et al. Hot metal rescheduling method and its application between the iron-making and steel-making stages[J]. Journal of Systems Engineering, 2013, 28(2): 234-247.
    [11] ROSSI F, VAN BEEK P, WALSH T. Handbook of constraint programming[M]. Amsterdam: Elsevier, 2006
    [12] 马亮,郭进,陈光伟. 编组站静态配流的约束传播和启发式回溯算法[J]. 西南交通大学学报,2014,49(6): 1116-1122.

    MA Liang, GUO Jin, CHEN Guangwei. Constraint propagation and heuristics backtracking algorithm for static wagon-flow allocation at a marshalling station[J]. Journal of Southwest Jiaotong University, 2014, 49(6): 1116-1122.
    [13] OJHA A K, BISWAL K K. Lexicographic multi-objective geometric programming problems[J]. International Journal of Computer Science Issues, 2009, 6(2): 20-24.
    [14] BECK J C. Solution-guided multi-point constructive search for job shop scheduling[J]. Journal of Artificial Intelligence Research, 2007, 29: 49-77. doi: 10.1613/jair.2169
    [15] 马亮,郭进,陈光伟,等. 铁路编组站动态配流的约束传播和多点构建性搜索的混合算法[J]. 信息与控制,2015,44(2): 230-237. doi: 10.13976/j.cnki.xk.2015.0230

    MA Liang, GUO Jin, CHEN Guangwei, et al. Hybrid algorithm of constraint propagation and multi-point constructive search for the dynamic wagon-flow allocation problem at a railway marshalling station[J]. Information and Control, 2015, 44(2): 230-237. doi: 10.13976/j.cnki.xk.2015.0230
  • 加载中
图(7) / 表(5)
计量
  • 文章访问数:  774
  • HTML全文浏览量:  202
  • PDF下载量:  61
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-01-04
  • 修回日期:  2022-06-13
  • 网络出版日期:  2023-02-27
  • 刊出日期:  2022-10-14

目录

/

返回文章
返回