基于动态规划的铁水运输智能调度方法

1、文章编号 :167226987 (2009) 0120070204基于动态规划的铁水运输智能调度方法赵海霞1 ,刘梅2( 1 . 青岛科技大学 机电工程学院 , 山东 青岛 266061 ; 2 . 青岛大学 高等职业技术学院 ,山东 青岛 266061)摘要 :以钢铁企业的铁水运输为背景 ,以机车和鱼雷混铁车 ( to rp e do ca r ,简称 t pc)为运输工具 ,依托厂区铁路网络 ,建立了路段预约机制和碰撞检测模型 ,提出了近邻分配 、 进程调度和分组优化的铁水优化调度方法 ,并根据铁水需求和运输距离等因素 ,采用动态规划确定车辆的最佳数量 。在开发的两层 c/ s 分布式铁水

2、智能调度仿真系统上 ,应用现 场采集的原始数据进行仿真 ,结果表明智能调度方法具有先进性和实用性的特点。 关键词 :动态规划 ;铁水运输 ;智能调度 ;避碰算法中图分类号 : t p 391文献标识码 : aintell igent schedul ing method of molten ironstransportat ion ba sed on t he dyna mic progra mzhao ha i2xia1 ,l iu me i2( 1 . cololege of elect ro mechanical engi neeri ng , qi ngdao u niver sit

3、y of science a nd technolo gy , qi ngdao 266061 ,chi na ;2 . vocatio nal a nd technical school ,qi ngdao u niver sit y ,qi ngdao 266061 ,chi na)abstract : thi s a r ticle wit h t he bac kgro u nd of t he molt e n i ro n s t ra n spo rt atio n e st a b2li she d t he re ser vi ng mec ha ni sm a nd t h

4、e colli sio n det ectio n mo del co ncer ni ng o n u si ng lo2 co mo tive s a nd to rp edo ca r s ( t pc) dep e ndi ng o n t he f acto r y s railwa y net . it ca r ried o ut t he molt e n i ro n s op ti mal sche duli ng met ho d such a s nea r by di st ri buti ng , t he t e no r scheduli ng a nd t h

5、e gro upi ng op ti mizi ng met ho d u si ng t he dyna mic p ro gra m to co nfi r mt he op ti mal n umber s ba se d o n t he f acto r s li ke t he requi re me nt of t he molt e n i ro n , t he t ra n spo r t ed di st a nce a nd so o n . it u sed t he i nitialized dat a collect ed o n t he sce ne ba s

6、ed o n t he t wo tie r s c/ s molt e n iro ns di st ri buti ng i nt elli ge nt sc heduli ng si mulatio n sy st e m , w hic h i ndicat ed t he i nt ellige nt sc he duli ng met ho d i s a dva nce d a nd p ractical .key words : dyna mic p ro gra m ; molt e n i ro ns t ra n spo r t atio n ; i nt elli ge

7、 nt sc he duli ng ; colli2sio n avoi d al go rit h m钢铁企业的铁水运输属于产销平衡的运输问题 ,即高炉生产的铁水总量等于炼钢厂消耗的铁 水总量。目前国内外解决这一运输问题的调度方 法 (包括智能调度 ) 大多都是建立产销平衡运输 计划模型 124 ,依据此模型建立的总路径最短的目 标函数没有考虑生产成本和能耗 。近年来 ,有许多专家学者和工程技术人员将人工智能与优化算法应用于运输系统 ,以解决调度的实时性和智能 化问题 5210 。文献 11 对钢铁企业铁水运输路径 选择及自动避碰算法进行了研究 ,但其提出的路 段预约机制有一定的局限性 ,因

8、此 ,基于碰撞检测 模型的避碰算法在生产实际中实用性不强。事实收稿日期 :2008203205作者简介 :赵海霞( 1970) ,女 ,副教授.上 ,铁水运输调度最基本 、最重要的两个要求是运输成本最低和重 t pc ( 鱼雷混铁车) 的运输时间 最短。为此应先建立铁路网络模型、机车预约机制和碰撞检测模型 ,设计和实现动态路径选择算 法和避碰算法 ,使得重 t pc 的运输时间最短 ,然 后采用近邻分配、进程调度和分组优化的铁水优 化调度方法 ,并根据铁水需求和运输距离等因素 , 运用动态规划法确定机车和 t pc 的数量 ,使得铁水的运输成本最低。约成功 , 判断机车运行前方是否会发生碰撞

9、, 即查询路段 x i +3 是处于空闲 s ( em p t y , em p t y ) 状态还 是预约 s ( bes p e a k , tr ai n) 状态。若为预约状态 , 还需进一步确定预约对象是否是当前机车。如果预 约成功 , 则对该路段进行占用 , 机车继续前行 , 否 则进行避碰处理。当碰撞检测模型检测到路段预约失败时 , 表明有 2 辆机车可能发生碰撞 , 需要进行避碰处理。避碰处理有等待避碰和让路避碰 2 种处理方式 ,具体采用何种处理方式由机车所接受任务的优先 级和现场调度情况来确定 11 。铁路路径选择铁路路径选择是采用图论的理论和方法将铁 路网络简化为边和顶点两

10、种图形元素 ,从而对复 杂的铁路网络进行数学描述 ,建立物理分区和逻 辑分级的铁路网络拓扑模型 ,然后依据铁路网络 模型 ,运用 dij k st ra 算法原理进行路径静态选择 , 并根据实际运输情况适时地进行路径动态调 整 11 。其中物理分区包括铁水生产区 、炼钢区 、 铁水预处理区、t pc 清理区 。与物理区域的划分 相对应的是将铁路网络从逻辑上抽象成两级 : 第 一级着重描述铁路网络中几个物理分区的宏观特 性及其相互之间的联系 ,第二级表示同一物理分 区内部元素之间的关系。13 优化调度3 . 1 近邻分配厂区铁路网络物理分区中的铁水生产区可进 一步细分为一高炉区、二高炉区 、三高

11、炉区和四高 炉区 , 类似的 , 炼钢区也可细分为一炼钢区、二炼 钢区和电炉区 。在制订生产计划时 , 各高炉铁水的 分流都采用近邻分配的原则优先向邻近的炼钢厂供应铁水。铁水智能调度就是根据生产计划将四 个高炉区的铁水按需求优化调度到三个炼钢厂 。3 . 2 进程调度高炉的生产过程是炼铁和出铁周期性循环的 过程 , 而高炉有停产和生产两种状态 , 因此 , 高炉出铁和运输过程可近似成按时间单元推进的进 程 , 出铁和运输是进程推进 , 高炉停产是进程挂 起 , 炼铁是进程临时挂起 。每个进程包括炉下出2 机车避碰2 . 1路段预约机制路段预约机制是指机车运行过程中 , 对其未 来行走路径中的前

12、 k 个路段 ( k 一般在 2 到 5 之间 取值) 先提前预定 , 然后占用的使用方式 。本系统中综合考虑各种因素后 , 将 k 值确定为 3 。因此铁 路网络中机车预约和占用的路段集合可用数组m ( x i , x i +1 , x i +2 , x i +3 ) 来表示 , 其中 x i 为当前时刻 机车所在的路段。2 . 2碰撞检测模型设路段状态用 s ( st ate , tr ai n) 表示 , 路段空闲 时 , 状态用 s ( em p t y , em p t y ) 表示 , 即路段状态和 机车都为空 , 若路段被占用时 , 状态可表示为 s ( occ u p y ,

13、tr ai n) , 路段被预约时 , 状态可表示为 s ( bes p e a k , tr ai n) 。碰撞检测模型是基于预约机制的路段状态查 询方法 , 其功能是在机车行驶过程中能够预先检 测到未来可能发生碰撞的冲突路段 , 方法是利用机车在行驶时预约和占用路段的集合数组 m ( x i , x i +1 , x i +2 , x i +3 ) 中最后一个路段元素 x i +3 是否预铁 、牵引重 t pc 、前扒、预处理、后扒 、避撞、倒铁、倒灌、清渣和卸档 , 再牵引空 t pc 返回到炉下出铁口的循环的过程 。4 座高炉 3 个炼钢厂就有 12 个进程 ,但由于铁水分流采用近邻分

14、配的原则 ,所 以最常见的情况是一座高炉对应一个炼钢厂 。因 此 ,铁水运输过程就是以高炉的出铁时间间隔为 周期 ,按时间单元在高炉之间循环推进的进程调度 。3 . 3 分组优化由于前扒 、预处理和后扒工位相互之间距离 较近 ,机车在这些工位之间行驶时 ,不会进行加减 速 ,故可将这三个工位合并为一个工位 ,即前处理工位 ,类似地 , 可将倒灌、清渣和卸挡三个工位合 并成后处理工位。合并后高炉至炼钢厂的铁水运 输过程可抽象地看成机车牵引 t pc 作圆周运动 , 如图 1 所 示 , 圆 周 底 部 b f 表 示 高 炉 (bla st fur nace) ,顶部 ss 表示炼钢 ( st

15、eel ma ki ng) , f t 表示前 处 理 ( fo re treat me nt ) , p t 表 示 后 处 理( po st treat me nt ) 。形 , 有t1 ( v , k)t ( x , k , v 3 , n ( v 3 ) ) 。( 3)=其中 v 3 是机车在 x , x + 1 ,机车速度满足下列条件的最小值 :(i) v v ;(ii) v0 v v3 ;(iii) 使 i nt tave ( x , k , v) / tmax 最小 。根据 bell ma n 最优化原理 , 由式 ( 1) 和 ( 3) 可 得到 n 组机车的最优分组递推公式

16、:t n ( v , k) = mi n ma x t n- 1 ( v 3 , x - 1) , t ( x ,0 x k, k 路段行驶时 ,图 1 铁水运输过程的抽象表示fig . 1 the no no bjective sho w of t he molt en i ro ns t ra n spo r t atio n p rocess33 ) )k , v , n ( v 。约束条件为 :( 4)(i) 机车的分组数介于 1 和 4 之间的整数;(ii) 机车的速度受最小速度 v0 限制 , v0 为机 车起动速度 ;(iii) 每组机车数目向上取整数 , 且在出铁期 间至少有两

17、辆机车在高炉下待命;(iv) q ( x , k) 为对应到高炉出铁时间的炼钢厂铁水需求量 。假设铁路网络中所有路段的长度均相等为lc ( 若长度不等 , 可进行等距离划分和标记) , tmax 为最大允许等待时间 , 机车的可行速度集合为 v v0 , v1 , v2 , v3 , n 为一 组 机 车 中 的 机 车 数 目 ,tave ( x , k , v) 为速度为 v , 运输路段为 x , x + 1 ,k 的平均环行运行时间 , t ( x , k , v , n) 为速度为 v的 n 辆机车运输 x 到 k 路段的运输时间 , ctpc 为t pc 的容量 , q ( x ,

18、 k) 为从 x 到 k 路段运输的总铁 水量 , 则速度为 v 的 n 辆机车从 x 到 k 路段的运输 时间等于运输该路段的总铁水量 q ( x , k) 和平均 环行运行时间 tave ( x , k , v) 的乘积 , 即根据高炉的日产量 、每次出铁量、出铁时间、出铁时间间隔 、炼钢厂的铁水日需求量等参数 , 并取铁水注满 t pc 所需时间为最大允许等待时间 tmax , 考虑以上 4 个约束条件和机车速度的 3 个满 足条件 , 对式 ( 4) 求动态规划的最优解 , 即可得到 以出铁时间间隔为周期的机车分组数和每组的机 车数目。q ( x , k) tave ( x , k ,

19、 v) 。( 1)t ( x , k , v , n) =ctpcn其中平均环行运行时间 tave ( x , k , v) 包括机车对空、重 t pc 的挂车时间、卸车时间 、避碰处理 时间等其他损失时间 。另外 , 机车所作的环行圆周 运动是非匀速运动 , 如在起点、终点和中间经停站在高炉出铁期间不应等待空 t pc , 令 tmax=0 , 取分组数为 1 , 对式 ( 4) 求动态规划的最优解可得到 t pc 的数目。实际生产中 ,由于每座高炉有 4个出铁口 ,为保证生产安全 , 在高炉出铁期间 , 应 至少有 4 辆空 t pc 在高炉下备用 ,故实际需要的t pc 数目是在最优解的

20、基础上加 4 。既有加速运动 , 也有减速运动 , 故按式 ( 2) 进行计算 。可tave ( x , k , v) ( k - x + 1) lc vtave ( x , k , v)+ ( m + 1) += va仿真验证为研究铁水运输系统智能调度涉及的关键技 术 ,运用 co m 组件技术 ,开发了 2 层 c/ s 分布式 铁水智能调度仿真系统 , 系统结构和各组件之间 的相互关系如图 2 所示 。实时数据库系统运行于 仿真服务器上 , 工位状态查询组件、铁水调度组 件 、避碰处理组件 、机车运行组件、路经选择组件 和铁路网络组件分别运行在仿真客户端。以分布式铁水智能调度仿真系统为实

21、验平 台 ,采用现场记录的原始数据对铁水运输调度过 程进行仿真验证 , 铁水日产量为 112 罐 (297591 8 吨) , 铁 水 分 流 运 量 一 炼 钢 为 65 罐 ( 分 流 比4( k -x + 1) lc+ 11 2 t+ t+ t1ulco nv(2) 其中第一项为重 t pc 运输时间 , m 为中间经 停站点数 , a 为加速度; 第二项为空 t pc 返回时 间; 第三项为包含挂车、卸车和避碰处理时间在内 的其他损失时间 , tl 为挂车时间 , tul 为卸车时 间 , tco n 为避碰处理时间 , 1 . 2 为时间损失系数 。假设机车组 1 , 2 , n 牵

22、引 t pc 经过 x , x +, k 路段速度不超过 v 时 , 用 t n ( v , k) 表示按1 ,最优方案所需的运输时间。对于一辆机车运输 t pc 从 x 到 k 路段的情va581 04 %) ,二炼钢为 43 罐 (分流比 381 39 %) ,电炉为 4 罐 (分流比 31 57 %) 时 , 采用智能调度关键技 术前后的铁水调度指标、机车和 t pc 运行指标见表 1 , 其中, dtem ,tre s ,avo ,e xi 分别为机车利用 率、t pc 平均周转率 (次 / 日) 、铁水平均温度损失( ) 、铁水平均滞留时间 ( 分钟) 、避碰次数 、紧急 次数。可以

23、看出智能调度关键技术有效地优化和 提高了铁水运输调度的一些重要指标。究 ,建立了路段预约机制和碰撞检测模型 ;提出了近邻分配、进程调度和分组优化的铁水优化调度 方法 ;根据铁水需求和运输距离等因素 ,采用动态规划确定车辆的最佳数量 。仿真结果表明 , 采用 智能调度关键技术后的铁水调度、机车和 t pc 运 行指标均得到了不同程度的优化。参考文献 1 刘峰. 宝钢铁水运输组织及运输能力分析 j . 宝钢技术 ,2001 ,8 ( 5) : 126 . 2 徐冬 , 费炳铨. 钢厂铁水运输系统的计算机控制研究 j . 上 海大学学报 :自然科学版 , 1999 , 5 ( 2) : 144214

24、8 . 3 l ee h s , murt hy s s , haider s w , et al . pri ma r y p ro duc2 tio n scheduli ng at st eel ma ki ng i ndust rie s j . ibm j re s &develop , 1996 , 40 ( 2) : 2312252 . 4 j aya mo ha n m s , rajendra n c. new di sp at chi ngr ule s fo r shop scheduli ng : a st ep fo r wa r d j . int er natio

25、 nal j o ur nal of pro ductio n re sea rch , 2000 , 38 ( 3) : 5632586 . 5 ho nko mp s j , reklaiti s g v . ro bust scheduli ng wit h p ro2ce ssi ng ti me uncert ai nt y j . co mp ut er s a nd che mical engi2neeri ng , 1997 ,21 ( s1) :105521060 . 6 hagha n i a , ba ni ha she m i m . heuri stic app ro

26、ache s fo r sol2 vi ng la r ge scale bus t ran sit ve hicle scheduli ng p ro blem wit h ro ut e ti me co n st rai nt s j . tra n spo rt atio n re search , 2002 ,36 ( 4) : 3092333 . 7 bait a f , pesenti r , u ko vich w. a co mp a ri so n of diff erent sol utio n app roaches to t he vehicle scheduli ng p ro ble m i n a p ractical ca se j . co mp ut er s & operatio n s re sea rch ,2000 ,27 ( 13) : 124921269 . 8 chen h , yao d d. dyna mic scheduli ng co nt rol of a multi2cla ss f l