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

1、自然灾害下的紧急物流计划Contents1.介绍 2. 数学模型提出3. 实例检验4. 总结AuthorsLINET ZDAMAR Nanyang Technological University, School of Mechanical and Production EngineeringEDIZ EKINCI Captain, Turkish Armed Forces, TurkeyBESTE KKYAZICI Yeditepe University, Department of Systems Engineering, TurkeyBackground introduction 199

2、9年土耳其的两次地震年土耳其的两次地震 自然灾害物流决策支持系统自然灾害物流决策支持系统 物资运输计划与交通工具时间表物资运输计划与交通工具时间表 整数多阶段多物资网络流整数多阶段多物资网络流 在大规模自然灾害下（拉格朗日松弛法）在大规模自然灾害下（拉格朗日松弛法）Research problem1.在紧急物流中，供给在当前时期和将来指定的时期在紧急物流中，供给在当前时期和将来指定的时期里是有限的，需求在当前时期是已知的在将来的时里是有限的，需求在当前时期是已知的在将来的时期里可以预测期里可以预测2.收到物资的节点可以被看作一个形式上的仓库收到物资的节点可以被看作一个形式上的仓库3.运输工具停

3、在节点处等待物流协调中心的下一个命令运输工具停在节点处等待物流协调中心的下一个命令4.文献综述文献综述(VRP)contribution 整合了多物资网络流问题与运输路线问题整合了多物资网络流问题与运输路线问题 模型分解成两个多物资网络流问题模型分解成两个多物资网络流问题 子模型运用拉格朗日松弛法子模型运用拉格朗日松弛法 算法经过小事件测试和实际规模地震的检验算法经过小事件测试和实际规模地震的检验数学模型数学模型运输方式（运输方式（transportation mode）需要注意：）需要注意：一对节点之间可能不止一条连线一对节点之间可能不止一条连线(弧弧),每条连线代表一种运输方式每条连线代表

4、一种运输方式.运输时间取决于运输方式运输时间取决于运输方式.1. 不失一般性不失一般性,忽略运输方式之间的转换时间忽略运输方式之间的转换时间.如将火车的货物卸如将火车的货物卸下下,分装到货车上分装到货车上,即从铁路运输转换到地面运输即从铁路运输转换到地面运输.(ground transportation) 集合集合T : length of the planning horizon,(计划期长度计划期长度) C : set of all nodes,(结点集结点集)M: set of transportation modes, (运输方式集运输方式集)CD: set of demand nod

5、es 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 = Cdo,(虚结点的补集虚结点的补集) A: set of commodities, (商品集商品集)Vm: set of vehicle types defined for each tr

6、ansportation 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商品

7、的需求商品的需求量量(-)或供给量或供给量(+) avovmt : number of vehicles of type v transportation mode m at node o added to thefleet 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型车的载重）型车的载

8、重）K: a big number.（一个大数）（一个大数） 参数参数决策变量决策变量 Zaopmt : amount of commodity type a traversing arc (o, p) at time t using transportationmode 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 :

9、integer number of vehicles of type v transportation mode m traversing thearc (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 attime t .（t时段在时段在o点等待的点等待的m运输方式运输方式v型车的数量）型车的数量） 模型模型 模型的第一部分（约束，）是一个线性多商品网络流问题。

10、模型的第一部分（约束，）是一个线性多商品网络流问题。 第二部分（约束，第二部分（约束，5 5，6 6，）是一个整数多商品网络流问，）是一个整数多商品网络流问题但约束右边也含有变量，所以比一般的整数多商品网络流题但约束右边也含有变量，所以比一般的整数多商品网络流问题复杂。问题复杂。 第一部分的商品流驱动着第二部分的车辆流。第一部分的商品流驱动着第二部分的车辆流。 模型解释重新作计划重新作计划 （迭代运算时赋值问题）（迭代运算时赋值问题）实例分析实例分析网络流：网络流：车辆流：车辆流：n公路运输n铁路运输n海上运输n空中运输物资流物资流n医疗用品n食品注意：为了简单直观，并注意：为了简单直观，并没

11、有在模型中标注虚拟节没有在模型中标注虚拟节1. 点。点。模型状态描述模型状态描述局部最优解局部最优解模型模型P解决方法解决方法t时段弧opm运载能力不能满足需求的数量 t时段弧opm运载能力超过需求的数量 t时段弧opm不能满足运输的运载能力的数量 算法思想算法思想第一部分的商品流驱动着第二部分的车辆流，首先计算第一部分的商品流驱动着第二部分的车辆流，首先计算p1,根据有根据有p1计算的最优商品流，来计算每条弧上对车辆运载能力的需计算的最优商品流，来计算每条弧上对车辆运载能力的需求求 然后计算然后计算p2，使，使p2的目标达到最小化，这时会得到最优的车的目标达到最小化，这时会得到最优的车辆流，

12、但这时车辆流不能满足商品流对运载能力的需求在这辆流，但这时车辆流不能满足商品流对运载能力的需求在这种情况下，种情况下，p2得到正的目标函数值接下来把最优车辆流反得到正的目标函数值接下来把最优车辆流反馈到馈到p1中，作为商品流能获得的运载能力的上限然后计算中，作为商品流能获得的运载能力的上限然后计算p1，进行第二次迭代进行第二次迭代就这样，就这样，p1和和p2 交替求解，彼此交换参数，直至达到一定的交替求解，彼此交换参数，直至达到一定的迭代次数，当迭代次数，当p2的目标函数值为，拉格朗日松弛法收敛于一的目标函数值为，拉格朗日松弛法收敛于一点，这意味着得到了可行解最终点，这意味着得到了可行解最终p

13、1目标函数值是原模型目标函目标函数值是原模型目标函数值的一个上限（数值的一个上限（B） 算法步骤算法步骤子模型的分析子模型的分析模型模型P1变化的多物资最小成本流问题变化的多物资最小成本流问题算法算法n改进的最短路径法 （Orlin 1993）nDecomposition based approaches and column generation technique （Aewrbuch and Leighton; Jones et al.;Frangioni）模型模型P2整数型多物资网络流问题整数型多物资网络流问题算法算法n启发式算法 （Barnhart&Sheffi;1993 Ag

14、garwal et al.1995)n穷举法 （Barnhart et al.1996)n割平面法 （Brunetta et al. 1995)注意：在解决大型网络问题时，算法的高效率是非常重要的。注意：在解决大型网络问题时，算法的高效率是非常重要的。在一些假设条件进行测试在一些假设条件进行测试需求/供应/运输的节点数在6-9之间1物品的数量和交通工具的类型都是受限制的2每个点上需求/供应的量在0,100间平均分布3在网络拓扑中，需求/供应的分布是任意的45假设条件假设条件从上面的表格，可以看出以下几点结论：从上面的表格，可以看出以下几点结论：在所有问题中，枚举法需要的迭代次数非常多 除了12

15、号和16号问题上，偏差稍大一些，总体平均而言， AlgLR与最优解决方案相比，它的偏差平均1.96%。 。当计划系统需要经常更改或要提供一个快速答案时，应用枚举法就相当困难（如表中的问题17和18）运输能力紧缺使得算法偏差偏大拓扑结构的复杂程度也影响算法的偏差地震区域及死伤人数物品种类/需求/供应交通工具的类型和负载能力模型在现实紧急情况下的应用：模型在现实紧急情况下的应用：1999年发生在土耳其的一次地震年发生在土耳其的一次地震震区死伤人数震区死伤人数物品种类物品种类/需求需求/供应供应交通工具的类型和负载能力交通工具的类型和负载能力拓扑结构拓扑结构1234567891011进取启发式算法进取启发式算法原理：与原理：与Orlin (1993)提出的修改后的最短路径算法相同提出的修改后的最短路径算法相同 建立于一些假设条件（其中包括运输能力充足）建立于一些假设条件（其中包括运输能力充足）综合比较综合