基于最小费用流的应急物资运输问题研究

摘 要：自然灾害的发生是不可避免的，同时也是难以预测的。灾害发生后，其破坏程度很大一部分取决于应急救援工作的实施是否顺利。应急物资的运输，是实施紧急救助的基础和保障，直接影响应急物流系统的反应速度和最终成效。首先将应急物资运输问题模型化，使其成为一个总量一定的最小费用流问题；其次，对已有的最小费用流算法进行调整，使其适用于运输问题；最后，利用具体算例，进行实例分析。利用最小费用流算法解决应急物资运输问题，有助于国家减少灾害造成的损失，节约社会资源。

关键词：应急物资；运输问题；最小费用流

中图分类号：F23

文献标识码：A

doi：10.19311/ki.1672-3198.2016.16.042

1 引言

应急物资就是预防、应对灾害过程中为保证各个环节的顺利进行而储存应急资源。应对灾害需要有充足的应急物资，并能够在最短的时间内将物资运输到灾害发生地，以最大程度减少人民生命财产损失。如何制定调运方案，将物资运往指定地点，而且实现运输成本的最小化和运输时间的最短，即为运输问题。与一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。

1.1 应急物资运输问题

从应急救援角度来看早在1984年Kembell Cook对索马里旱灾的救援行动就考虑了应急物流的问题。随后，研究学者对应急物流问题提出了不同的线性规划模型来研究这一问题，Knott Rathi等人将大规模应急物流描述为具有时间窗限制的多物品、多模式网络流问题，并给出了求解方法。Haghani和Oh把大规模灾害的救援物资运输问题作为多物资多模式网络流模型推导出单目标函数，它以时空网络概念为基础，在模型中时变的物资需求和运输网络中的载运工具的位移由路径、运输、供需执行三种类型连接起来，简化了多物资多模式多需求导致的复杂网络流问题。应急物流活动中，物资配送的关键是出救点到需求点之间的物流网络中选择最优路径，从而使应急物流活动的耗时最短，成本最低。“应急物流”这一概念是由欧忠文在国内首先提出的，他给出了应急物流的定义，即“以提供突发性自然灾害、突发性公共卫生事件等突发性事件所需应急物资为目的，以追求时间效益最大化和灾害损失最小化为目标的特种物流活动”。孟参探讨了应急物资的库存控制及运输配送。谢征等人提出求解各种最小费用流问题的算法。如果最小费用流问题中给定的流值为最大流，则为最小费用最大流问题。寇玮华、董雪、吕林剑等人利用最小费用流算法，解决了交通运输网络中两个结点之间有流量约束的最小费用最大流分配问题。

1.2 最小费用流的引入

一般情况下，运输问题可利用以下几种方法解决：表上作业法、最短线路法和智能搜索算法等。这些研究方法，都能解决运输网络的设计问题，但也都各有优缺点。本文试图利用网络流中的最小费用流问题的方法，来解决应急物资网络运输的问题。

（1）表上作业法。当已知某些物资从出发地运往不同目的地单位物资的运输费用时，常采用表上作业法，求出使运输费用最省、时间最短的物资合理调配方案。

然而有时会出现迭代次数较多，工作量繁琐的情况。

（2）最短路线法。当已知某物资从出发地运往目的地，可有多条运输路线供选择，这时，可构造费用网络图，用求最短路线的方法，选择最优的运输方案，使运输时间最短、费用最省。对于这类运输问题，只需画出各种运输路线的线路图及图上每一条边（或弧）上的距离或费用（也可以用邻接矩阵表示），然后用狄克斯特拉的标号法或邻接矩阵法求最优运输路线。

基于此，本文在应急物资运输网络问题中试图寻找一种更加简便有效的方法来进行求解，因此引入了最小费用流的方法。众所周知，在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B（A指出救点，B指需求点，出救点可以是多个地点），如何选择路径、分配经过路径的流量，可以在流量一定的前提下，达到所用的费用最小的要求。如n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，最小费用流问题指如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。

因此，本文基于最小费用流的方法，设计使用与供应链网络运输问题的最小费用流算法，用以处理供应急物资运输网络模型，并利用具体例子来验证该算法的有效性。

2 应急网络运输问题描述

应急运输网络一般有三级组成，即出救点、中转中心和需求点。因此，中转中心选址问题可描述为对于i个出救点经过j个的中转中心，为k个需求点配送物品，使得在所选路线及路线的流量在满足配送需求的前提下，使得总费用最低，其运输网络结构如图1所示。

在应急网络运输问题中，出救点的个数和需求点的数量和位置以及需求量是固定的，物流中转中心的地点也是固定的但流经各中转中心的流量不定，因此，该运输问题的目标是在需求节点需求量得到满足的前提下使得总费用最小。

为了方便说明问题并且提高本文算法的通用性，对运输问题进行如下假设：

（1）从出救点到中转中心、从中转中心到需求点之间的运输距离是已知的；

（2）各个需求点的需求量已知或可预测；

（3）物流经过中转节点的相关成本已知；

（4）只考虑一种物资的运输，运输费用只和运输量和距离有关且已知；

（5）一个中转中心可由多个出救点配送物资，一个需求点的需求也可由多个中转中心提供。

（6）各线路的容量已知。

基于上述的假设条件，接下来进行模型涉及的参数和变量进行定义：

i表示出救点，I为出救点的集合，则i∈I。

j表示中转中心，J为中转中心的集合，则j∈J。

k表示需求点，K为需求点的集合，则k∈K。

dij表示从出救点i向中转中心j的运输距离（单位：km）。

djk表示从中转中心j向需求点k的运输距离（单位：km）。

Qij表示从出救点i向中转中心j的实际运输量（单位：t）。

Qjk表示从中转中心j向需求点k的实际运输量（单位：t）。

cij表示从出救点i向中转中心j的最大运输量（单位：t）。

cjk表示从中转中心j向需求点k的最大运输量（单位：t）

Pij表示从出救点i向中转中心j的单位运输费率（单位：Yuan/（t・km））。

Pjk表示从中转中心j向需求点k的单位运输费率（单位：Yuan/（t・km））。

pj表示中转中心j的库存费用。

Mj为第j个中转中心的最大容量（单位：t）。

Dk为第k个需求点的需求总量（单位：t）。

Ai为出救点i的供应能力（单位：t）。

3 算法设计

运输问题的目的是要求一个目标函数F，使得总费用W（F）达到最小，本文算法的模型如下：

约束条件（1）为救援物资供应能力限制；

约束条件（2）是中转中心的物资进出量平衡约束，即运往中转中心j的物资总量，等于从中转中心j运出的物资总量。

约束条件（3）为中转中心的容量限制，即从出救点运往中转中心j的运输总量必须小于中转中心j的最大容量。

约束条件（4）为满足需求约束，即从所有选中的中转中心向需求点k的运输总量必须满足需求点k的需求。

约束条件（5）和（6）为各线路的容量限制。

另外，本模型涉及的所有参量均为非负参量。

利用最小费用流算法处理该模型，在算法求解过程中，保持总流量保持不变（即出救节点发出的物流不变），并逐步向最优性条件过渡，直到满足最优性条件，算法步骤如下：

（1）初始化，根据实际情况构建运输网络图（将各中转节点当成一条有容量限制的弧），并确定各供应节点的产量，各中转中心的容量及各需求节点的需求量，并确定各路线的距离及单位运费率；

（2）在初始网络中，找到一条满足条件的可行流；

（3）若在网络中存在可调整的负代价圈，则转入（4），若不存在则转入（5）；

（4）增量构造新流（保持总流量不变），转至（3）；

（5）将当前流保存为最小费用流，输出。

为使得算法更为迅捷，在第（4）步构造新流过程中，取增量θ=min{容量-正向弧流量；逆向弧流量}。

4 算例分析

图3为一个简易的公路网络，为简便起见，下例只有一个出救节点S和一个需求节点T，并有两个中转节点（中转点1和中转点2，且1可以向2输送物资），且将各路线的距离转化为单位物流费用表示。每条弧上的数据从左至右分别为单位物流费用、当前流量、容量。出救节点需要将8吨的物资经过两个中转节点送到需求节点。

构建应急物资运输网络时将中转节点当成一条有流量限制的弧，该弧费用为该中转节点的库存费用，给各节点编号，并给出一个初始可行流：

该初始可行流的运输总费用W（F）=20+9+4+3+5+18+15=74，寻找到的第一个可调整负代价圈是圈①④②，对该圈增加一个增量θ=2，得到新流如图5。

该调整后的图的运输总费用W（F）=12+15+3+5+18+15=68，寻找到的第二个可调整负代价圈是圈③⑤⑥，对该圈增加一个增增量θ=2，得到新流如图6。

该调整后的图的运输总费用W（F）=12+15+3+5+4+21+6=66，此时图中不存在可调整的负代价圈，调整结束，得到最小费用流。相比与初始可行流， 费用由74减少到了68，调整结果较好。

5 结论

应急物资运输问题的核心是运输成本最小化，即寻找最佳的运输方案使得总费用最低，不同的线路流量设计将导致不同的费用，这个过程可以抽象为一个有流量限制的最小费用流问题。本文首先将应急物资运输网络问题模型化，使其成为一个总量一定的最小费用流问题；其次，对已有的最小费用流算法进行相应调整，使其适用于应急物资运输网络问题；最后，利用具体算例，进行实例分析。利用最小费用流算法解决应急物资运输网络问题，能够减少运输成本，提高社会效益。本文考虑的情况较为简单，后继研究可以对应急物资运输网络问题的各项费用进行更精细的划分，使得算法更符合实际情况。

参考文献

[1]KemballCook，Stephenson R.LessoninlogisticsfromSomalia[J].Disaster，1984，（8）：57-66.

[2]RathiA.K.，ChurchR.L.，SolankiR.S..Allocating resources to support a multicommodity flow With time windows[J].Logisties and Trans Portation Review，1992，28（2）：167-188.

[3]HaghaniA.，OhS.-C.Formulation and solution of a multicommodity，multimodal network Flow model for disaster relief operations[J].Transportation Research Part A，1996，30（3）：231-250.

[4]欧忠文，王会云，姜大立等.应急物流[J].重庆大学学报，2004，27（3）：164-166.

[5]孟参等.应急物流系统运作流程分析及其管理[J].物流技术，2006，（9）：15-17.

[6]谢政，汤泽滢.带模糊约束的最小费用流问题[J].模糊系统与数学，1999，13（2）：940-941.

[7]寇玮华，董雪，吕林剑.交通运输网络中两个结点间有流量约束的最小费用最大流算法[J].兰州交通大学学报，2009，28（6）：104-109.