基于时间约束的救灾运输模型研究

　　摘要：针对救灾物资运输方特征，在满足各灾区救灾物资需求量的前提下使运输时间最短，运用最短时间最大流理论建立数学模型，讨论了该理论在地震救灾物资运输中的运用，最后给出一个算例验证了该模型的有效性。
　　关键词：最短时间最大流；救灾物资；运输
　　随着近些年自然灾害突发事件频频出现，应急救援物资运输理论成为各国学者研究的重点。应急救援往往具有很强的时间约束，本文在对最短时间最大流理论研究的基础上，建立应急救灾物资运输数学模型，得出在满足各灾区救灾物资最小需求的前提下，以最短的运输时间将救灾物资运送到各灾区。
　　1最短时间最大流理论[1-3]
　　定义1：整个应急物流网络可以分解为若干条自起点到终点的链，每条链由若干个弧组成，若链上弧的方向与链的方向相同（起点到终点），则称这个弧为链的正向弧,记为；否则称为逆向弧，记为。
　　定义2：设是一个可行流，是从起点到终点的一条链，若满足下列条件，则称之为一条增广链。（1）在弧上，，即中每一条弧是非饱和弧；（2）在弧上，，即中每一条弧是非饱和弧。
　　1.2最短时间最大流问题的描述
　　在网络中，对应每一条弧，除了已给弧的容量外，还给了一个单位流量通过弧的费用。是的一条可行流，则其总费用为。则求使得为最小且流量最大的问题称为最短时间最大流问题。
　　1.3最短时间最大流理论的算法思想
　　若是流量为的可行流中费用最小者，而是关于的所有增广链中费用最小的增广链，那么沿着以去调整，得到的可行流就是流量为（）的所有可行流中的最短时间流。这样，当为最大流时，它也就是我们所要求的最短时间最大流了。根据这个结论，如果已知是流值为的最短时间流，则关键是要求出关于的最短时间的增广链。为此，需要在原网络的基础上构造一个新的赋权有向图，使其顶点与的顶点相同，且将中每条弧均变成两个方向相反的弧和。新图中各弧的权值与中弧的权值有密切关系，图中各弧的权值定义为:
　　
　　
　　由增广链费用的概念及图中权的定义可知，在网络中寻求关于可行流的最短时间增广链，等价于在图中寻求从源点到汇点的最短路。
　　2数学模型
　　2.1救灾物资模型建立
　　自然灾害突发时间救灾物资运输要求在满足各灾区救灾物资需求的前提下，以最短的时间用将尽可能多的救灾物资从各救灾物资收集点运送到各灾区，因此，假设运输时间与数量成线性关系。定义两个常量和。为运送物资从第救灾物资收集点到第灾区所需时间；为从第救灾物资收集点到第灾区运送救灾物资的数量。构建模型如下：
　　式中为第个仓库的物资储备数量；为第个灾区至少所需要的物资数量；为从第个仓库到第个灾区道路运输能力；表示起点，表示终点。第1个约束条件表示各节点救灾物资流量守恒；第2个约束条件表示从第个仓库到第个灾区救灾物资运输量必须在运输能力范围内。第3个约束条件表示从第个仓库运走的所有物资数量必须小于第个仓库的物资储备量；第4个约束条件表示运送到第个灾区的所有物资数量必须不小于第个灾区最少需求量。
　　2.2模型求解
　　该模型求解过程是对单一源点到单一汇点进行的，当救灾物资运输问题涉及到多个储存物资的仓库(源点)和多个需求物资的水库(汇点)时就需要引进点作为单源，引进点作为单汇。
　　定义1：规定从点到第个仓库的道路运输能力为个仓库的物资储备量，从点运送到第个仓库的单位物资运输时间为0；
　　定义2：规定从第个灾区到点的道路运输能力为，从第个灾区运送到点的单位物资运输时间为0。
　　这样一来，运输的总时间不会变，也可以应用最小费用最大流算法对模型进行求解。求解步骤如下:
　　(1)确定初始可行流，它是运输量为0的最短时间流；
　　(2)记为经k次调整得到的最短时间流，构造赋权有向图；
　　(3)在赋权有向图中寻求从源点到汇点的最短时间路(调用Dijkstra算法)，若不存在最短时间路，则就是最短时间最大运量流，计算终止；若存在最短时间路，则此最短时间路即为原网络中相应的增广链,转入下一步；
　　(4)在增广链μ上对进行调整,调整量为:
　　令
　　(5)得到新的可行流,使流值增大,令,返回到第(2)步骤。
　　3结语
　　该模型可以求解出任意的对应于某个最低运输量的运输方案，即只要给定灾区的最低需求量，就可以根据最小费用最大流理论求解出在这个最低运输量限制下的运输方案，实际中可以根据灾情的变化，随时根据灾区的实际需求量，改变运输方案。
　　参考文献
　　[1]欧忠文,王会云,姜大力等.应急物流[J].重庆大学学报,2004,27(3):164-167.
　　[2]李德,钱颂迪.运筹学[M].北京:清华大学出版社,1982.
　　[3]郭耀煌等.运筹学原理与方法[M].成都:西南交通大学出版社,2000.