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

马亮; 胡宸瀚; 金福才; 董炜

doi:10.3969/j.issn.0258-2724.20220008

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

doi: 10.3969/j.issn.0258-2724.20220008

马亮^{1, 2,},
胡宸瀚³,
金福才³,
董炜⁴

1.
西南交通大学信息科学与技术学院，四川成都 611756
2.
国家铁路智能运输系统工程技术研究中心，北京 100081
3.
中国铁道科学研究院集团有限公司电子计算技术研究所，北京 100081
4.
马鞍山钢铁股份有限公司运输部，安徽马鞍山 243021

基金项目: 中国国家铁路集团有限公司科技研究开发计划（L2021X001）；四川省科技计划（2021YJ0070）

详细信息

作者简介:
马亮（1987—），男，讲师，研究方向为交通运输信息化与优化，E-mail：maliang@swjtu.edu.cn

中图分类号: U294.1；N94
计量
- 文章访问数: 698
- HTML全文浏览量: 176
- PDF下载量: 60
- 被引次数: 0
出版历程
- 收稿日期: 2022-01-04
- 修回日期: 2022-06-13
- 网络出版日期: 2023-02-27
- 刊出日期: 2022-10-14

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

MA Liang^{1, 2
,},
HU Chenhan³,
JIN Fucai³,
DONG Wei⁴

1.
School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China
2.
The Center of National Railway Intelligent Transportation System Engineering and Technology, Beijing 100081, China
3.
Institute of Computing Technologies, China Academy of Railway Sciences Corporation Limited, Beijing 100081, China
4.
The Transportation Department of Maanshan Iron and Steel Co., Ltd., Maanshan 243021, China

摘要

摘要:
为实现铁水运输作业排程与资源分配的协同优化，基于约束程序累积调度和字典序多目标优化理论，研究了铁水运输调度双层多目标约束优化方法. 首先，基于铁水罐周转率最高和作业效率最高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.
- molten iron transportation /
- operation scheduling /
- lexicographic multi-objective /
- constraint optimization /
- search algorithm

HTML全文

致谢: 2014年度西南交通大学博士研究生创新基金; 第四届西南交通大学轨道交通行业拔尖创新人才培育项目.

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

Figure 1. Solving process of scheduling molten iron transportation

下载: 全尺寸图片幻灯片

图 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}$

下载: 全尺寸图片幻灯片

图 5 使用BT算法求解 ${f_1}$ 过程

Figure 5. Solution process of ${f_1}$ with BT algorithm

下载: 全尺寸图片幻灯片

图 6 使用BT算法求解 ${f_2}$ 过程

Figure 6. Solution process of ${f_2}$ with BT algorithm

下载: 全尺寸图片幻灯片

图 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

参考文献(15)

[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