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

自然灾害下的紧急物流计划Contents1.介绍2.数学模型提出3.实例检验4.总结AuthorsLINETÖZDAMAR∗NanyangTechnologicalUniversity,SchoolofMechanicalandProductionEngineeringEDIZEKINCICaptain,TurkishArmedForces,TurkeyBESTEKÜÇÜKYAZICIYeditepeUniversity,DepartmentofSystemsEngineering,TurkeyBackgroundintroduction1.1999年土耳其的两次地震2.自然灾害物流决策支持系统3.物资运输计划与交通工具时间表4.整数多阶段多物资网络流5.在大规模自然灾害下（拉格朗日松弛法）Researchproblem1.在紧急物流中，供给在当前时期和将来指定的时期里是有限的，需求在当前时期是已知的在将来的时期里可以预测2.收到物资的节点可以被看作一个形式上的仓库3.运输工具停在节点处等待物流协调中心的下一个命令4.文献综述(VRP)contribution1.整合了多物资网络流问题与运输路线问题2.模型分解成两个多物资网络流问题3.子模型运用拉格朗日松弛法4.算法经过小事件测试和实际规模地震的检验数学模型运输方式（transportationmode）需要注意：1.一对节点之间可能不止一条连线(弧),每条连线代表一种运输方式.2.运输时间取决于运输方式.3.不失一般性,忽略运输方式之间的转换时间.如将火车的货物卸下,分装到货车上,即从铁路运输转换到地面运输.(groundtransportation)集合1.T:lengthoftheplanninghorizon,(计划期长度)2.C:setofallnodes,(结点集)3.M:setoftransportationmodes,(运输方式集)4.CD:setofdemandnodesincludingtransshipmentnodes,(需求结点集)5.CS:setofsupplynodes,(供给结点集)6.do:dummynodedefinedforexpressingtheavailabilityofvehicles,(虚结点)7.RO:setofnodesexcludingdummynode;RO=C\{do},(虚结点的补集)8.A:setofcommodities,(商品集)1.Vm:setofvehicletypesdefinedforeachtransportationmodem,(运输方式m的车型集)2.topm:timerequiredtotraversearc(o,p)intransportationmodem;topmiszerofor3.non-existentlinks,(o–p的往返时间)4.daot:amountofcommodityoftypeademandedorsuppliedatnodeoattimet,5.positiveforsupplyandnegativefordemand,(t时段o结点a商品的需求量(-)或供给量(+))6.avovmt:numberofvehiclesoftypev–transportationmodematnodeoaddedtothe7.fleetattimet,(t时段o点m运输方式的v型型加入到车队的数量)8.wa:unitweightofcommoditya,(单位a商品的数量)9.capvm:loadcapacityofvehicletypev–transportationmodem,（m运输方式的v型车的载重）10.K:abignumber.（一个大数）参数决策变量1.Zaopmt:amountofcommoditytypeatraversingarc(o,p)attimetusingtransportation2.modem,（t时段以m方式从o运送到p的商品a的数量）3.devaot:amountofunsatisfieddemandofcommoditytypeaatnodeoattimet,（t时段结点o未满足的商品a的需求量）4.Yopvmt:integernumberofvehiclesoftypev–transportationmodemtraversingthe5.arc(o,p)attimet,（t时段往返于o-p之间的m运输方式v型车的数量）6.surovmt:numberofvehiclesoftypev–transportationmodemthatwaitatnodeoat7.timet.（t时段在o点等待的m运输方式v型车的数量）模型模型的第一部分（约束１，２，４）是一个线性多商品网络流问题。第二部分（约束３，5，6，７）是一个整数多商品网络流问题．但约束５右边也含有变量，所以比一般的整数多商品网络流问题复杂。第一部分的商品流驱动着第二部分的车辆流。模型解释重新作计划（迭代运算时赋值问题）实例分析网络流：1.车辆流：1.公路运输2.铁路运输3.海上运输4.空中运输2.物资流1.医疗用品2.食品注意：为了简单直观，并没有在模型中标注虚拟节点。模型状态描述局部最优解模型P解决方法t时段弧opm运载能力不能满足需求的数量t时段弧opm运载能力超过需求的数量t时段弧opm不能满足运输的运载能力的数量算法思想1.第一部分的商品流驱动着第二部分的车辆流，首先计算p1,根据有p1计算的最优商品流，来计算每条弧上对车辆运载能力的需求．2.然后计算p2，使p2的目标达到最小化，这时会得到最优的车辆流，但这时车辆流不能满足商品流对运载能力的需求．在这种情况下，p2得到正的目标函数值．接下来把最优车辆流反馈到p1中，作为商品流能获得的运载能力的上限．然后计算p1，进行第二次迭代．3.就这样，p1和p2交替求解，彼此交换参数，直至达到一定的迭代次数．，当p2的目标函数值为０，拉格朗日松弛法收敛于一点，这意味着得到了可行解．最终p1目标函数值是原模型目标函数值的一个上限（ＵB）．算法步骤子模型的分析模型P1变化的多物资最小成本流问题算法改进的最短路径法（Orlin1993）Decompositionbasedapproachesandcolumngenerationtechnique（AewrbuchandLeighton;Jonesetal.;Frangioni）模型P2整数型多物资网络流问题算法启发式算法（Barnhart&Sheffi;1993Aggarwaletal.1995)穷举法（Barnhartetal.1996)割平面法（Brunettaetal.1995)注意：在解决大型网络问题时，算法的高效率是非常重要的。在一些假设条件进行测试需求/供应/运输的节点数在6-9之间1物品的数量和交通工具的类型都是受限制的2每个点上需求/供应的量在[0,100]间平均分布3在网络拓扑中，需求/供应的分布是任意的4……5假设条件从上面的表格，可以看出以下几点结论：★在所有问题中，枚举法需要的迭代次数非常多★除了12号和16号问题上，偏差稍大一些，总体平均而言，AlgLR与最优解决方案相比，它的偏差平均1.96%。。★当计划系统需要经常更改或要提供一个快速答案时，应用枚举法就相当困难（如表中的问题17和18）★运输能力紧缺使得算法偏差偏大★拓扑结构的复杂程度也影响算法的偏差1地震区域及死伤人数2物品种类/需求/供应3交通工具的类型和负载能力模型在现实紧急情况下的应用：1999年发生在土耳其的一次地震震区死伤人数物品种类/需求/供应交通工具的类型和负载能力拓扑结构1234567891011进取启发式算法原理：与Orlin(1993)提出的修改后的最短路径算法相同建立于一些假设条件（其中包括运输能力充足）综合比较总结※这篇文章提出了紧急物流计划的数学模型。※模型输出包括了这个区域不同地点的交通工具的分配。※模型在一个动态决策环境下考虑了依赖时间的供给/需求，交通工具限制以及计划变更的灵活性。※这篇文章通过对一个具体例子的分析，认为AlgLR法是非常让人满意的。ThankYou!