基于最短路的应急物资库存问题研究

摘 要：借助运筹学中最短路问题的思想，尝试将应急物资储备中心的进货计划抽象为一个有向网络最短路问题，在确保应急物资能够及时满足需求的前提下，对应急物流系统库存管理环节的成本进行优化。

关键词：最短路；应急物资；网络计划

为应对突发自然灾害，相关地区需要储备一定量应急救灾物资，以保证及时满足救急需求，及控制灾害损失扩大的速度。由于应急救援物资的需求时间、品种、数量等方面都是不可精确预测的[1]，救灾物资储备中心容易面临物资储备不足，或某类救援物资的库存量过大的问题。

应急物资订货提前期可以认为是零，由于应急的重要性，延期到货的成本非常高[2]。目前在应急物资的管理要求和流程上已经有比较成熟的研究[3]。本文借鉴运筹学中对最短路问题的研究思想，将处于应急状态下的储备中心的进货计划抽象为一个有向网络最短路问题，在确保满足应急物资能够及时满足需求的基础上，对应急物流系统库存管理环节的成本进行优化。

1 问题描述

自然灾害发生后，由于预测与现实需求的不对称性[3]，应急物资储备中心往往会面对某些救援物资的事先库存不足需要“订货”。这些供不应求的物资的“订货”，在应急时间要求下，容易发生过量的订货，导致过剩的库存不仅引起不必要的系统运作成本，还影响其他地区的储备中心对于这些物资的供应。因此，这类物资的进货及持有库存量的管理，无论是对于应急救援供应工作的展开，还是对于系统成本优化，都比其他救援物资更需要优先考虑。本文的研究对象即为此类物资的库存问题。

本文将实际应急物资库存问题做一定程度的简化，假定应急事故发生后，某灾区的储备中心在连续供应救援物资一段时间后，物资A开始进入紧缺的状态。该储备中心对这类物资实际供应的历史数据，得到灾区在未来一个较短时期L对物资A的需求量D。同时假定，储备中心在L时期有已确定的，派遣车辆运送物资的计划，这些计划将L分成更短的若干时期，每个时期对物资A的需求为di·D=d1+d2+d3+d4；L=T1+T2+T3+T4。

将L细分出来的每个时期看做一个时段，储备中心的供应目标是满足各时段对物资A的需求。将时段的起始时间定义为储备中心对包括A以内的救援物资进行装载，运输的时间点。设定第一时段的期初库存为储备中心对物资A设定的安全库存，由于救援物资的缺货成本被视作无限大，因此，当各时段期初库存达到安全库存时，即以0表示该阶段的期初库存，以表示不使用安全库存。

储备中心通过将派遣车辆将库存运送至指定地点来满足各时段对包括A在内的物资需求，并通过向其他物资中心调货来补充库存，在这里，我们设定物资A不存在订货提前期，即发生订货的同时，物资A的库存即得到补充。受灾当地物资储备中心从其他储备中心调运物资A，最终送达灾区整个过程发生的成本包括以下内容：（1）在调运物资A之前各个环节的运作费用；（2）物资A从某一储备中心调运至另一储备中心的费用；（3）物资A从物资中心运送至灾区的费用；（4）库存费用。

由前文的假定可知，受灾当地的储备中心在时期L已有确定的车辆派遣计划，考虑必须满足各时段物资A需求量及运输成本最小化两个目标。于每个时段运送物资A数量分别等于该时段的需求量可以使时期L的运输成本最小化。因此我们只需考虑（1）（2）（4）构成的总成本。

2 问题的一般形式及求解

某地应急物资储备中心为满足受灾地区需求，对已达到安全库存的物资A发起紧急订货（调货）。根据物资A的历史供应数据，结合储备中心未来几个时段的车辆派遣计划，储备中心确定了接下来每个时段送往受灾中心的物资A的数量。如果发生订货，则调运物资A所需的单位运输费用为a，运输物资前发生的各项运行费用总和为s，单件物资A的单位库存费用为b.假设初始库存为0，问题就是：储备中心应如何安排订货计划，可以保证及时给受灾地区运送足够的物资A，同时使物资A到达受灾中心的成本最小。储备中心所做的决策是“什么时候发起订货”及“订货量为多少”，实际上就是物资A的库存管理问题。通过合理的决策，可以优化物资A送达受灾地区的总成本。

假设在时段t物资A的订货量为xt，期末产品的库存为it（i0=0）。考虑所有可能的订货计划，可以得到一个L时期的由期初到期末的有向网络图。

储备中心将未来的某个时期按照车辆派遣计划分成了几个时段，并决定了各时段向灾区供应物资A的数量。储备中心在各时段期初发起订货（调运）时，订货的数量可以是满足一个或多个时段需求的。网络中的弧表示储备中心在时段期初的订货数量可以满足时段的需求，根据假设，瞬时到达的物资将在被运走，剩余的将作为备用储存，需要计算其库存费用，其它有向弧表示的意义以此类推。所有头尾相接，将第一个节点和最后一个节点连起来的有向弧线集即为一种满足几个时段物资需求的订货方案。

为弧（i，j）的权，表示第i时段订货量为时所导致的费用，包括其他物资中心为调运物资A发生的运输费用、发生在运输前各个准备环节的费用、该地储备中心储存物资A的库存费用。即：？棕ij=s+dixi+？撞■■CtIt；

其中：It=di+1+di+2+…dj-1；Ct=Tib。

综上所述，求得最佳的订货方案，维持合理库存，使得物资A到达灾区的费用最小，就相当于求得上述赋权有向图从首节点到末节点的最短路。

最后可以采用Dijkstra标号法对赋权有向图进行最短路求解，首先定义个参数值，物资A的单位运输费用a；运输物资A前发生的各项运行费用总和s；单件物资A的单位库存费用b；各时段时长。用MS Excel对给定数据作简单处理后即可得到各有向弧的费用，然后用Dijkstra标号法对问题进行求解，就可以得到最短路以及弧的组合，这样就可以得到储备中心需要在什么时段发起订货，可以使得各时段对物资A的需求被满足的同时，总费用最小。

参考文献

[1]Beamon B M. Humanitarian Relief Chains： Issues and Challenges[A].Proceedings of the 34thInternational Conference on Computers and Industrial Engineering，San Francisco，CA，USA，2004.

[2]姜玉宏，颜华，欧忠文，等.应急物流中应急物资的管理研究[J].物流技术.2007（6）.

[3]孟参.基于模糊评判及灰色神经网络的应急物资库存管理研究[D].武汉理工大学.2007.