自然灾害下的紧急物流计划

,自然灾害下的紧急物流计划,Contents,1.,介绍,2.,数学模型提出,3.,实例检验,4.,总结,Authors,LINET ZDAMAR,Nanyang,Technological University,School of Mechanical and Production Engineering,EDIZ EKINCI,Captain,Turkish Armed Forces,Turkey,BESTE KKYAZICI,Yeditepe,University,Department of Systems Engineering,Turkey,Background introduction,1999,年土耳其的两次地震,自然灾害物流决策支持系统,物资运输计划与交通工具时间表,整数多阶段多物资网络流,在大规模自然灾害下（拉格朗日松弛法）,Research problem,1.,在紧急物流中，供给在当前时期和将来指定的时期里是有限的，需求在当前时期是已知的在将来的时期里可以预测,2.,收到物资的节点可以被看作一个形式上的仓库,3.,运输工具停在节点处等待物流协调中心的下一个命令,4.,文献综述,(VRP),contribution,整合了多物资网络流问题与运输路线问题,模型分解成两个多物资网络流问题,子模型运用拉格朗日松弛法,算法经过小事件测试和实际规模地震的检验,数学模型,运输方式（,transportation mode,）需要注意：,一对节点之间可能不止一条连线,(,弧,),每条连线代表一种运输方式,.,运输时间取决于运输方式,.,不失一般性,忽略运输方式之间的转换时间,.,如将火车的货物卸下,分装到货车上,即从铁路运输转换到地面运输,.(ground transportation),集合,T,:length of the planning horizon,(,计划期长度,),C,:set of all nodes,(,结点集,),M,:set of transportation modes,(,运输方式集,),CD,:set of demand nodes including transshipment nodes,(,需求结点集,),CS,:set of supply nodes,(,供给结点集,),do,:dummy node defined for expressing the availability of vehicles,(,虚结点,),RO,:set of nodes excluding dummy node;,RO,=,C,do,(,虚结点的补集,),A,:set of commodities,(,商品集,),Vm,:set of vehicle types defined for each transportation mode,m,(,运输方式,m,的车型集,),topm,:time required to traverse arc,(o,p),in transportation mode,m,;,topm,is zero for,non-existent,links,(o,p,的往返时间,),daot,:amount of commodity of type,a,demanded or supplied at node,o,at time,t,positive for supply and negative for,demand,(t,时段,o,结点,a,商品的需求量,(-),或供给量,(+),avovmt,:number of vehicles of type,v,transportation mode,m,at node,o added,to the,fleet at time,t,(t,时段,o,点,m,运输方式的,v,型型加入到车队的数量,),wa,:unit weight of commodity,a,(,单位,a,商品的数量,),capvm,:load capacity of vehicle type,v,transportation mode,m,（,m,运输方式的,v,型车的载重）,K,:a big number.,（一个大数）,参数,决策变量,Zaopmt,:amount of commodity type,a,traversing arc(,o,p,)at time,t,using transportation,mode,m,（,t,时段以,m,方式从,o,运送到,p,的商品,a,的数量）,devaot,:amount of unsatisfied demand of commodity type,a,at node,o,at time,t,（,t,时段结点,o,未满足的商品,a,的需求量）,Yopvmt,:integer number of vehicles of type,v,transportation mode,m,traversing the,arc(,o,p,)at time,t,（,t,时段往返于,o-p,之间的,m,运输方式,v,型车的数量）,surovmt,:number of vehicles of type,v,transportation mode,m,that wait at node,o,at,time,t,.,（,t,时段在,o,点等待的,m,运输方式,v,型车的数量）,模型,模型的第一部分（约束，）是一个线性多商品网络流问题。,第二部分（约束，,5,，,6,，）是一个整数多商品网络流问题但约束右边也含有变量，所以比一般的整数多商品网络流问题复杂。,第一部分的商品流驱动着第二部分的车辆流。,模型解释,重新作计划,（迭代运算时赋值问题）,实例分析,网络流：,车辆流：,公路运输,铁路运输,海上运输,空中运输,物资流,医疗用品,食品,注意：为了简单直观，并,没有在模型中标注虚拟节,点。,模型状态描述,局部最优解,模型,P,解决方法,t,时段弧,opm,运载能力不能满足需求的数量,t,时段弧,opm,运载能力超过需求的数量,t,时段弧,opm,不能满足运输的运载能力的数量,算法思想,第一部分的商品流驱动着第二部分的车辆流，首先计算,p1,根据有,p1,计算的最优商品流，来计算每条弧上对车辆运载能力的需求,然后计算,p2,，使,p2,的目标达到最小化，这时会得到最优的车辆流，但这时车辆流不能满足商品流对运载能力的需求在这种情况下，,p2,得到正的目标函数值接下来把最优车辆流反馈到,p1,中，作为商品流能获得的运载能力的上限然后计算,p1,，进行第二次迭代,就这样，,p1,和,p2,交替求解，彼此交换参数，直至达到一定的迭代次数，当,p2,的目标函数值为，拉格朗日松弛法收敛于一点，这意味着得到了可行解最终,p1,目标函数值是原模型目标函数值的一个上限（,B,）,算法步骤,子模型的分析,模型,P1,变化的多物资最小成本流问题,算法,改进的最短路径法,（,Orlin,1993,）,Decomposition based approaches and column generation technique,（,Aewrbuch,and Leighton;,Jones et,al.;Frangioni,）,模型,P2,整数型多物资网络流问题,算法,启发式算法,（,Barnhart1993,Aggarwal,et al.1995),穷举法,（,Barnhart et al.1996),割平面法,（,Brunetta,et al.1995),注意：在解决大型网络问题时，算法的高效率是非常重要的。,在一些假设条件进行测试,需求,/,供应,/,运输的节点数在,6-9,之间,1,物品的数量和交通工具的类型都是受限制的,2,每个点上需求,/,供应的量在,0,100,间平均分布,3,在网络拓扑中，需求,/,供应的分布是任意的,4,5,假设条件,从上面的表格，可以看出以下几点结论：,在所有问题中，枚举法需要的迭代次数非常多,除了,12,号和,16,号问题上，偏差稍大一些，总体平均而言，,AlgLR,与最优解决方案相比，它的偏差平均,1.96%,。,当计划系统需要经常更改或要提供一个快速答案时，应用枚举法就相当困难（如表中的问题,17,和,18,）,运输能力紧缺使得算法偏差偏大,拓扑结构的复杂程度也影响算法的偏差,1,地震区域及死伤人数,2,物品种类,/,需求,/,供应,3,交通工具的类型和负载能力,模型在现实紧急情况下的应用：,1999,年发生在土耳其的一次地震,震区死伤人数,物品种类,/,需求,/,供应,交通工具的类型和负载能力,拓扑结构,1,2,3,4,5,6,7,8,9,10,11,进取启发式算法,原理：与,Orlin,(1993),提出的修改后的最短路径算法相同,建立于一些假设条件（其中包括运输能力充足）,综合比较,总结,这篇文章提出了紧急物流计划的数学模型。,模型输出包括了这个区域不同地点的交通工具的分配。,模型在一个动态决策环境下考虑了依赖时间的供给,/,需求，交通工具限制以及计划变更 的灵活性。,这篇文章通过对一个具体例子的分析，认为,AlgLR,法是非常让人满意的,。,Thank You!,