空箱调运的随机机会约束规划模型

空箱调运的随机机会约束规划模型 空箱调运的随机机会约束规划模型 科技值息0高校讲t20SCIENCE&TECHNOLOGYINFORMATION2011年第27期 空箱调运的随机机会约束规划模型 杨楠 (兰州交通大学甘肃兰州730000) 【摘要】本文研究了国内外铁路集装箱运输的现状和发展状况,进而重点分析了我国铁路集装箱运输的基本流程和影响因素.探讨了空 箱产生的原因以及空箱调运的特点,研究了现有的空箱调运的相关措施.在研究和分析现有文献的基础上提出了空箱调运的基本原则和具体 要求,在考虑不同影响因素和优化目标的前提下,分别建立了基于运输r--]~的铁路空箱调运的一般化模型,具有容量约束的空箱调运网络流模 型,基于不确定理论的空箱调运随机机会约束模型,根据测试,所建立模型能够比较准确刻画集装箱调运的实际问题.能够为铁路运输生产提 供一定的参考作用. 【关键词】铁路集装箱;空箱调运:优化模型:运输组织 1随机机会约束规划3.2 随机机会约束规划是由A.ChainesW.W.Cooper于1959年提出的. 是在一定的概率意义下达到最优的理论.它是一种随机规划方法.针 对约束条件中含有随机变量.并且必须在观测到随机变量的实现之前 做出决策的问题机会约束规划考虑到所做决策在不利的情况发生时 可能不满足约束条件.而采用一种原则:即允许所做决策在一定程度 上不满足约束条件.但该决策使约束条件成立的概率不小于某一个足 够小的置信水平机会约束规划主要特点是约束条件中含有随机参 数 2机机会约束规划模型 设K:{klk=1,2,3,…l为集装箱空箱种类集合.w={wlw=l,2,3,…l 为集装箱重箱种类集合若w=k表示重箱和空箱的箱型相同.M={ml m=1,2,3,…}为集装箱办理站的集合.假设区域内有部分办理站为集 装箱空箱供应站.部分办理站为空箱需求站.现在问题是如何最小成 成本实现空箱调运.实现集装箱使用效率的最大化. 在3.2中提出了空箱调运的一般模型.其本质为运输问题模型. 属于确定型规划模型,空箱供应站的空箱数a,,空箱需求站需要的空 箱数bj都是确定的.而且铁路运输能力不受限制.但大多数情况往往 受铁路运输能力制约.只能以一定的概率满足运输需求.这些空箱数 据都是服从某些分布的随机变量.实际上每天供应站产生的空箱数皂 由于作业延误,到达信息不准确等不确定性因素影响,成为服从某一 随机分布的随机变量,需求站需要的空箱数'Pi由于意外情况导致的 货主需求不同和资金等不确定性因素影响也服从某一随机分布.需要 对确定性模型进行改进,建立随机规划模型进行优化. 建立空箱调运随机机会约束规划模型(ccl,)~IY: Z_n pT{?%?ft?iE1J=1 prt??竹}?岛eI %?{0,1,2,…} 式中,I:f1,2,…,n},I为空箱供应站;J={1,2,…,m},J为空箱需求 站在以上模型中.我们依然以寻求最短运输距离为优化目标.第一个 约束条件的意思是在置信水平a上,空箱供应站Si产生的空箱数,i? ,,毒服从随机分布;第二个约束条件的意思是在置信水平JB.上,满足空 箱需求站的空箱数,.,,,服从随机分布;最后一个为整数约束.模 型中假定为供需平衡的空箱调运问题.如实际中供需不平衡,可通过 增加虚产地和虚销地的方法转化为供需平衡的空箱调运问题,当然相 关的运输距离应该为O 3随机机会约束模型的求解算法 3.1求解算法概述 机会约束规划的解法大致有两种.其一,将机会约束规划转化为 确定性规划,然后用确定性规划的理论去解决;其二,应用现在智能优 化算法进行求解. 算法设计 机会约束转化为确定性的等价类 本文考虑如下的机会约束: pr{g(x,)?0}? 定理假设随机变量的分布函数为妒.若函数g(,)的形式为 g(,)^),则prlg(x,)-<ot?a当且仅当()?,其中K= sup{KIK=~p(1一d)}. (1)混合智能算法 综合运用遗传算法和蚁群算法来求解以上CCP模型初始时在n 个空箱供应站放置一只蚂蚁每只蚂蚁从供应张开始向需求站进行搜 索. (2)信息素更新 当所有蚂蚁完成1次搜索后.各路径上的信息索为: (t+l一1)=(1).(f)+? ?=A4 . f,若蚂蚁k在本次周游中经过边(?) ?={ 【O.否则 其中,Q为正常数;G表示目标函数值.P表示信息挥发系数;z表 示所有顶点数. (3)改进状态转移规则 为了扩大蚂蚁算法搜索的解空间.又不降低搜索速度.蚂蚁K在 供应站i按以下策略选择需求站点f: ,?. ?(t)r.[1他 sE? 其中,()蚂蚁k下一步允许选择的顶点集合W?()是随机选 择的,q为给定的常数,O<q.<1,q是(O,1)之间均匀分布的,在每一次 选择目标节点时r机产生.这样就增加了信息素值较小的节点被选择 的可能性,跳出局部最优解.表示顶点i与. f之间的关系,如果从顶 点到顶点J有一条实线定向边,则d为正的最小,否则d为负的最 小.A表示路径的重要程度,B表示路径的能见度. (41动态结束时机设置 在基本蚁群算法中对于算法的结束条件均设置为固定迭代次数, 这样会使得算法的求解结果在全局最优解和局部最优解之间震荡,因 此适时地结束蚂蚁算法可以提高算法的求解效率,避免冗余迭代.具 体方法如下:?设置蚂蚁算法最大迭代次数Ant一;?在迭代过程中 统计子代群体最优解的进化率,如果连续Ant代,子代最优解的进化 率都小于Am,则可以结束蚁群算法,输出最优解. (5)变异算子.. 变异算子是遗传算法中提出来酊,在本文中,如果将第k只蚂蚁 在一次遍历结束后的禁忌表tabu看成一个染色体,我们将随机选择 两个染色体同等基因位互换.得到新的染色体.但是,变异算子可能违 反空箱调运原则,可以提高其花费代价其不能在下一(下转第106页) l33 2011年第27期SCIENCE&TECHNOLOGYINFORMATIONO机械与电子0科技信息 模糊决策一般采用Mamdani"s(mlr卜max)决策法.反模糊化,也就 是模糊量的精确化,本设计采用重心法计算公式如(1)式所示: I u(k)=Kpe(k)+KiTe(k)+Ke()/7"(1) 重心法比较全面的反应了各个控制信息.它的缺点是运算量较 大.不过在实际的控制过程中,输出论域的元素一般不会太多.再次, 清晰化方法选择重心法.此设计的模糊控制输入输出曲面如图7所 刀 3仿真 (b) (c) 图7模糊PID控制器输入输出曲面图 图8模糊PID控制器的仿真模块 在MATLAB命令窗口中键人"Simulink",在Simulink环境下,建 立模糊PID的仿真模型如图8所示.模糊PID的仿真结果曲线如图9 所示. 根据仿真结果可知.采用模糊控制策略整定PID参数相对于普通 PID控制策略,其系统的鲁棒性增强,响应时间大大减少,超调量也得 到了一定的改善.提高了系统的总体性能161. 4总结 本文以电锅炉的温度作为研究对象.采用了较新的控制方法—— 模糊PID控制.该控制系统选用单片机AT89C51作为控制芯片.完成 数据采集,参数整定,LED显示,键盘输入,报警等功能,由理论向实际 迈出了一步,具有一定的理论和实用价值.e 【参考文献】 [I]李朝青.单片机原理及接口技术【M].北京:北京航空航天大学出版社,2005. [2]陈杰,黄鸿.传感器与检测技术[M】.北京:高等教育出版社,2002,8. [3]谢仕鸿.MATLABR2008控制系统动态仿真实例教程【M】.北京:化学工业出版 社,2009.1. [4]王正林,王胜开,等.MATALB/Simulink与控制系统仿真【M].北京:机械工业出 版社.2008,7. [5]南新元,陈志军,程志江.基于模糊HD的电锅炉温度控制系统研究叨.自动化 仪表.2008. [6]秦文虎.程序温控仪中PID参数自整定算法[J】.自动化仪表,2000,21(1):17— 24.5,29(5). [7]GodhwaniA,BaslerMj.Adialexcitationcontrol,systemforuseOilbrushes excitedsynchronousgenera--totsIEEETrans.OnEC1996,11(3):616-620. (上接第133页)步搜索中被选择. (6)具体算法步骤 ?初始化个点及边上的信息素;设定蚂蚁算法控制参数 (d1,p=O.6,Q=I,m=lO). ?设置蚂蚁算法的结束条件(Ant=500,Ant一5,Ant一= 1%). ?生成m个初始值为空的,u数组 ?将m只蚂蚁放置在初始节点0处.把节点0放入到每个蚂蚁 的脚u数组中 ?按着式(6)计算的概率,选择蚂蚁k到达的下一个节点,并将其 加入到该蚂蚁的tabu数组中,直到蚂蚁遍历完所有的节点. ?判断是否满足蚁群算法的结束条件,若满足则输出最优解.结 束算法,否则转步骤?. ?将每个蚂蚁的?6u数组看成一个.对每个染色体都按给定的 概率pm=O.8进行变异操作,生成新的染色体.将变异后的每个染色体 加人到种群中 ?步骤7结束后.种群中有m+u个染色体.按目标函数大小选出 m个染色体将m只蚂蚁的tabu数组分别换成本次选出的m个染色 体 106 [责任编辑:常鹏飞] ?按式(5)进行图中边上信息素的更新,清空tabu数组,转步骤 ?. 通过一些实例的计算,结果得出,对于铁路集装箱空箱调运问题. 引入随机因素后建立的机会约束模型更接近铁路现场的实际但是在 上述模型中没有考虑箱型,空重箱协调等因素,另外还有用户满意度, 时间窗等因素.在以后的研究中可以建立相关机会约束模型和模糊机 会约束等等模型.l 【参考文献】 [1]刘彦元.我国铁路集装箱办理站计算机管理系统fJ】.中国铁路,1991(10):13— 17. [2]周红梅,方芳.航运集装箱空箱调运优化模型的研究m.武汉理工大学: 交通科学与工程版.2003.270). [31刘宝碇,赵瑞清,王纲.不确定规划及应用fM1.北京:清华大学出版社,2003. [4]杨浩,何世伟.铁路运输组织学[M】.北京:中国铁道出版社,2001:215. 作者简介:杨楠(1985一),男,甘肃兰州人,兰州交通大学硕士研究生,研究 方向为交通运输规划与管理. [责任编辑:王静]