Double-Layer and Multi-objective Constraint Optimization Model for Transportation Scheduling of Molten Iron
-
摘要:
为实现铁水运输作业排程与资源分配的协同优化，基于约束程序累积调度和字典序多目标优化理论，研究了铁水运输调度双层多目标约束优化方法. 首先，基于铁水罐周转率最高和作业效率最高2个字典序优化目标，考虑作业时序、作业实施逻辑、铁水温降时限、铁水罐作业次数限制、资源容量限制和铁水罐资源池等约束条件，建立了上层的铁水运输作业排程约束优化模型；其次，以资源利用均衡度最高为目标，将作业实施唯一性和资源容量限制作为约束条件，建立了下层的铁水运输资源分配约束优化模型；最后，通过约束传播与多点构建性搜索的混合算法迭代求解整个模型. 通过实例验证表明：设计的混合算法求得的铁水罐周转率目标和运输作业效率目标，比基本深度优先回溯算法分别提高了14.29%和60.53%；字典序多目标模型比加权和单目标模型求解效率和求解质量分别提高了20.3%和11.11%.
Abstract:In order to realize the collaborative optimization of operation scheduling and resource allocation in molten iron transportation, based on the theory of the cumulative scheduling with constraint programming and lexicographic multi-objective optimization, a double-layer and multi-objective constraint optimization method is explored for the transportation scheduling of molten iron. Firstly, setting the highest turnover rate of molten iron tanks and the highest operation efficiency as two lexicographic objectives, the upper-level constraint optimization model is built for molten iron transportation operation. In the model, the constraints are involved, such as operation sequence, operation implementation logic, time limit of molten iron cooling, limited operation times of molten iron tank, resource capacity limit, and resource pool of the molten iron tanks. Secondly, with the highest resource utilization balance, the lower-level constrained optimization model is established for resource allocation in molten iron transportation, in which the uniqueness of operation implementation and resource capacity are taken as constraints. Finally, the hybrid algorithm of constraint propagation and multi-point constructive search is developed to solve the whole model iteratively. The case study shows that, the turnover rate target and transportation efficiency target obtained by the hybrid algorithm are 14.29% and 60.53% higher than those obtained by the basic depth first backtracking algorithm respectively. Compared with weighted and single objective models, lexicographical multi-objective model improves the efficiency and quality of solution by 20.3% and 11.11%, respectively.
-
图 2 铁水罐周转率最高目标
$ {f_1} $ 求解过程Figure 2. Solution process of highest turnover rate of molten iron tank
$ {f_1} $ 
图 3 运输作业效率最高目标
$ {f_2} $ 求解过程Figure 3. Solution process of highest operation efficiency
$ {f_2} $ 
图 4 资源使用均衡度最高目标
$ {f_3} $ 求解过程Figure 4. Solution process of highest resource utilization balance
$ {f_3} $ 
图 7 加权和单目标
$ {f_{\rm{W}}} $ 求解过程Figure 7. Solution process of
$ {f_{\rm{W}}} $ with weights and single objective表 1 铁水运输作业排程约束优化模型常量符号定义
Table 1. Constant definitions for constrained optimization model for transportation scheduling of molten iron
常量符号 说明 $ T $ 铁水运输计划周期，精度为 1 min $ {s^{\text{T}}} $ 计划周期的开始时间 $ {e^{\text{T}}} $ 计划周期的结束时间 $ t \in T $ 铁水运输计划周期的索引下标 $ {N^{\text{K}}} $ 铁水罐数量 $ i \in {N^{\text{K}}} $ 铁水罐的索引下标 $ {N^{\text{P}}} $ 出铁总次数 $ j \in {N^{\text{P}}} $ 出铁计划的索引下标 $ s_j^{{\text{tp}}} \in T $ 第$ j $次出铁开始时间，min $ e_j^{{\text{tp}}} \in T $ 第$ j $次出铁结束时间，min $ d_j^{{\text{tp}}} $ 第$ j $次出铁持续时间，min $ {N^{{\text{TL}}}} $ 钢厂倒罐作业的倒罐线数量 $ {N^{{\text{TK}}}} $ 每条倒罐线同时进行倒罐作业的铁水罐数 $ {N^{{\text{PL}}}} $ 高炉调机数量 $ {N^{{\text{PK}}}} $ 空罐从调车场到铁水区运输和重罐从铁水区到调车场运输的固定编组罐数 $ {N^{{\text{SL}}}} $ 钢厂调机数量 $ {N^{{\text{SK}}}} $ 重罐从调车场到钢厂运输和空罐从钢厂到调车场运输的固定编组罐数 $ {N^{{\text{JO}}}} $ 铁水运输作业种类总数，包括取空、配空、受铁、取重、配重、倒罐 $ k $ 作业种类索引下标，1：取空，2：配空，3：受铁，4：取重，5：配重，6：倒罐 $ {t_k} $ 每一种作业持续标准时间，min $ {t^{{\text{LP}}}} $ 铁水罐从受铁到倒罐持续时间上限，min $ {L^{{\text{TC}}}} $ 铁水罐每日出铁倒罐作业次数上限 
下载: 导出CSV
表 2 铁水运输作业排程约束优化模型变量符号定义
Table 2. Variable definitions for constrained optimization model for transportation scheduling of molten iron
变量符号 说明 $ {J_{i,j,k}} $ 第$ i $个铁水罐的第$ j $次出铁周期内的第$ k $种作业变量 $ {o_{i,j,k}} \in \{ 0,1\} $ $ {J_{i,j,k}} $作业的是否实施变量 $ {s_{i,j,k}} \in T $ $ {J_{i,j,k}} $作业的开始时间变量，min $ {e_{i,j,k}} \in T $ $ {J_{i,j,k}} $作业的结束时间变量，min $ {d_{i,j,k}} = {e_{i,j,k}} - {s_{i,j,k}} $ $ {J_{i,j,k}} $作业的持续时间变量，min $ J_{i,j}^{{\text{TC}}} $ 第$ i $个铁水罐第$ j $次出铁周期包含所有作业的全流程作业变量 $ o_{i,j}^{{\text{TC}}} $、$ s_{i,j}^{{\text{TC}}} $、$ e_{i,j}^{{\text{TC}}} $、$ d_{i,j}^{{\text{TC}}} $ 作业$ J_{i,j}^{{\text{TC}}} $的是否实施、开始时间、结束时间、持续时间变量 $ J_j^{{\text{BF}}} $ 高炉第$ j $次出铁作业变量 $ o_j^{{\text{BF}}} $、$ s_j^{{\text{BF}}} $、$ e_j^{{\text{BF}}} $、$ d_j^{{\text{BF}}} $ 作业$ J_j^{{\text{BF}}} $的是否实施、开始时间、结束时间、持续时间变量 $ J_i^{\text{K}} $ 第$ i $个铁水罐全出铁周期全流程作业变量 $ o_i^{\text{K}} $、$ s_i^{\text{K}} $、$ e_i^{\text{K}} $、$ d_i^{\text{K}} $ 分别为作业$ J_i^{\text{K}} $的是否实施、开始时间、结束时间、持续时间变量
下载: 导出CSV
表 3 铁水运输资源分配约束优化模型常量符号定义
Table 3. Constant definitions for constrained optimization model of resource allocation in metal iron transportation
常量符号 说明 $ {M_k} $ 作业排程优化之后可实施的铁水罐第$ k $种作业总数 $ {m_k} $ 作业排程优化之后可实施的铁水罐第$ k $种作业索引下标 $ J_{k,{m_k}}^{{\text{PR}}} $ 铁水罐第$ k $种的第$ {m_k} $个可实施作业 $ s_{k,{m_k}}^{{\text{PR}}} $ $ J_{k,{m_k}}^{{\text{PR}}} $作业的开始时间，min $ e_{k,{m_k}}^{{\text{PR}}} $ $ J_{k,{m_k}}^{{\text{PR}}} $作业的结束时间，min $ d_{k,{m_k}}^{{\text{PR}}} = e_{k,{m_k}}^{{\text{PR}}} - s_{k,{m_k}}^{{\text{PR}}} $ $ J_{k,{m_k}}^{{\text{PR}}} $作业的持续时间，min $ 1 \leqslant {n_1} \leqslant {N^{{\text{PL}}}} $ 高炉调机索引下标 $ 1 \leqslant {n_2} \leqslant {N^{{\text{SL}}}} $ 钢厂调机索引下标 $ 1 \leqslant {n_3} \leqslant {N^{{\text{TL}}}} $ 钢厂倒罐线索引下标
下载: 导出CSV
表 4 铁水运输资源分配约束优化模型变量符号定义
Table 4. Variable definitions for constrained optimization model of resource allocation in metal iron transportation
变量符号 说明 $ J_{{n_1},{m_2}}^{{\text{ED}}} $ 高炉调机执行配空作业变量 $ o_{{n_1},{m_2}}^{{\text{ED}}} \in \{ 0,1\} $ $ J_{{n_1},{m_2}}^{{\text{ED}}} $作业的是否实施变量 $ s_{{n_1},{m_2}}^{{\text{ED}}} $、$ e_{{n_1},{m_2}}^{{\text{ED}}} $ 作业$ J_{{n_1},{m_2}}^{{\text{ED}}} $的开始时间和结束时间变量，$ s_{{n_1},{m_2}}^{{\text{ED}}} = s_{2,{m_2}}^{{\text{PR}}} $，$ e_{{n_1},{m_2}}^{{\text{ED}}} = e_{2,{m_2}}^{{\text{PR}}} $ $ J_{{n_1},{m_4}}^{{\text{FT}}} $ 高炉调机执行取重作业变量 $ o_{{n_1},{m_4}}^{{\text{FT}}} \in \{ 0,1\} $ $ J_{{n_1},{m_4}}^{{\text{FT}}} $作业的是否实施变量 $ s_{{n_1},{m_4}}^{{\text{FT}}} $、$ e_{{n_1},{m_4}}^{{\text{FT}}} $ 作业$ J_{{n_1},{m_4}}^{{\text{FT}}} $的开始时间和结束时间变量，$ s_{{n_1},{m_4}}^{{\text{FT}}} = s_{4,{m_4}}^{{\text{PR}}} $，$ e_{{n_1},{m_4}}^{{\text{FT}}} = e_{4,{m_4}}^{{\text{PR}}} $ $ J_{{n_2},{m_1}}^{{\text{ET}}} $ 钢厂调机执行取空作业变量 $ o_{{n_2},{m_1}}^{{\text{ET}}} \in \{ 0,1\} $ $ J_{{n_2},{m_1}}^{{\text{ET}}} $作业的是否实施变量 $ s_{{n_2},{m_1}}^{{\text{ET}}} $、$ e_{{n_2},{m_1}}^{{\text{ET}}} $ 作业$ J_{{n_2},{m_1}}^{{\text{ET}}} $的开始时间和结束时间变量，$ s_{{n_2},{m_1}}^{{\text{ET}}} = s_{1,{m_1}}^{{\text{PR}}} $，$ e_{{n_2},{m_1}}^{{\text{ET}}} = e_{1,{m_1}}^{{\text{PR}}} $ $ J_{{n_2},{m_5}}^{{\text{FD}}} $ 钢厂调机执行配重作业变量 $ o_{{n_2},{m_5}}^{{\text{FD}}} \in \{ 0,1\} $ $ J_{{n_2},{m_5}}^{{\text{FD}}} $作业的是否实施变量 $ s_{{n_2},{m_5}}^{{\text{FD}}} $、$ e_{{n_2},{m_5}}^{{\text{FD}}} $ 作业$ J_{{n_2},{m_5}}^{{\text{FD}}} $的开始时间和结束时间变量，$ s_{{n_2},{m_5}}^{{\text{FD}}} = s_{5,{m_5}}^{{\text{PR}}} $，$ e_{{n_2},{m_5}}^{{\text{FD}}} = e_{5,{m_5}}^{{\text{PR}}} $ $ J_{{n_3},{m_6}}^{{\text{TP}}} $ 倒罐线执行倒罐作业变量 $ o_{{n_3},{m_6}}^{{\text{TP}}} \in \{ 0,1\} $ $ J_{{n_3},{m_6}}^{{\text{TP}}} $作业的是否实施变量 $ s_{{n_3},{m_6}}^{{\text{TP}}} $、$ e_{{n_3},{m_6}}^{{\text{TP}}} $ 作业$ J_{{n_3},{m_6}}^{{\text{TP}}} $的开始时间和结束时间变量，$ s_{{n_3},{m_6}}^{{\text{TP}}} = s_{6,{m_6}}^{{\text{PR}}} $，$ e_{{n_3},{m_6}}^{{\text{TP}}} = e_{6,{m_6}}^{{\text{PR}}} $
下载: 导出CSV
表 5 某钢厂某日高炉出铁计划
Table 5. Blast furnace tapping plan of of steel plant in one day
min 出铁次/次 高炉 出铁厂 开始时间 结束时间 1/2 A/B 铁厂 1 5 85 3/4 A/B 铁厂 1 85 115 5/6 A/B 铁厂 1 115 345 7/8 A/B 铁厂 2 155 235 9/10 A/B 铁厂 2 235 265 11/12 A/B 铁厂 2 265 495 13/14 A/B 铁厂 1 345 375 15/16 A/B 铁厂 1 375 455 17/18 A/B 铁厂 2 495 525 19/20 A/B 铁厂 2 525 605 21/22 A/B 铁厂 1 605 685 23/24 A/B 铁厂 1 685 715 25/26 A/B 铁厂 1 715 945 27/28 A/B 铁厂 2 755 835 29/30 A/B 铁厂 2 835 865 31/32 A/B 铁厂 2 865 1095 33/34 A/B 铁厂 1 945 975 35/36 A/B 铁厂 1 975 1055 37/38 A/B 铁厂 2 1095 1125 39/40 A/B 铁厂 2 1125 1205 41/42 A/B 铁厂 1 1205 1285 43/44 A/B 铁厂 1 1285 1315 45/46 A/B 铁厂 1 1315 1545 47/48 A/B 铁厂 2 1355 1435
下载: 导出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.007ZHAO 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.02977YANG 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.030CHEN 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.0230MA 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 -
-
下载:
点击查看大图
计量
- 文章访问数: 554
- HTML全文浏览量: 117
- PDF下载量: 56
- 被引次数: 0