财 经 管 理
基于最小费用流的应急物资运输问题研究
李 广 兴 何 珊
(华 北 电 力 大 学 ，北 京 102206)
摘 要 ：自然 灾 害 的 发 生 是 不 可 避 免 的 ，同 时 也 是 难 以 预 测 的 _ 灾 害 发 生 后 ，其 破 坏 程 度 很 大 一 部 分 取 决 于
应急救 援 工 作 的 实 施 是 否 顺 利 9 应 急 物 资 的 运 输 ，是 实 施 紧 急 救 助 的 基 础 和 保 障 ，直接影响应急物流系统的反应
速 度 和 最 终 成 效 。首 先 将 应 急 物 资 运 输 问 题 模 型 化 ，使 其 成 为 一 个 总 量 一 定 的 最 小 费 用 流 问 题 ；其 次 ，对已有的
最 小 费 用 流 算 法 进 行 调 整 ，使 其 适 用 于 运 输 问 题 ；最 后 ，利 用 具 体 算 例 ，进 行 实 例 分 析 。利用最小费用流算法解决
应 急 物 资 运 输 问 题 ，有 助 于 国 家 减 少 灾 害 造 成 的 损 失 ，节 约 社会资源 $
关键词：应 急 物 资 ；运 输 问 题 ；最小费用流
中图分类号：F23 文献标识码 ： A
1 引言
应急物资就是预防、应对灾害过程中为保证各个
环节的顺利进行而储存应急资源。应对灾害需要有充
足的应急物资，并能够在最短的时间内将物资运输到
灾害发生地，以最大程度减少人民生命财产损失9 如
何制定调运方案，将物资运往指定地点，而且实现运输
成本的最小化和运输时间的最短，即为运输问题9 与
一般线性规划问题不同，它的约束方程组的系数矩阵
具有特殊的结构，这就需要采用不同的甚至更为简便
的求解方法来解决这种在实际工作中经常遇到的问
题。
1 . 1 应急物资运输问题
从应急救援角度来看早在1984年 Kembell Cook
对索马里旱灾的救援行动就考虑了应急物流的问题6
随后，研究学者对应急物流问题提出了不同的线性规
划模型来研究这一问题，Knott R ath i等人将大规模应
急物流描述为具有时间窗限制的多物品、多模式网络
流问题，并给出了求解方法。Haghani和 O h把大规模
灾害的救援物资运输问题作为多物资多模式网络流模
型推导出单目标函数，它以时空网络概念为基础，在模
型中时变的物资需求和运输网络中的载运工具的位移
由路径、运输、供需执行三种类型连接起来，简化了多
物资多模式多需求导致的复杂网络流问题a 应急物流
活动中，物资配送的关键是出救点到需求点之间的物
流网络中选择最优路径，从而使应急物流活动的耗时
最短，成本最低。“应急物流”这一'概念是由欧忠文在
菌内首先提出的，他给出了应急物流的定义，即“以提
供突发性自然灾害、突发性公共卫生事件等突发性事
件所需应急物资为目的，以追求时间效益最大化和灾
害损失最小化为目标的特种物流活动”。孟参探讨了
应急物资的库存控制及运输配送。谢征等人提出求解
各种最小费用流问题的算法。如果最小费用流问题中
给定的流值为最大流，则为最小费用最大流问题。寇
doi：10. 19311/j. cnki. 1672-3198. 2016. 16. 042
玮华、董雪、■林剑等人利用最小费用流算法，解决了
交通运输网络中两个结点之间有流量约束的最小费用
最大流分配问题。
1 . 2 最小费用流的引入
一般情况下，运输问题可利用以下几种方法解决：
表上作业法、最短线路法和智能搜索算法等。这些研
究方法，都能解决运输网络的设计问题，但也都各有优
缺点。本文试图利用网络流中的最小费用流问题的方
法 ，来解决应急物资网络运输的问题。
(1) 表上作业法。_ 已知某些物资从出发地运往
不同目的地单位物资的运输费用时，常采用表上作业
法 ，求出使运输费用最省、时间最短的物资合理调配方
案。
然而有时会出现迭代次数较多，X 作量繁琐的情
况。
(2) 最短路线法。_ 已知某物资从出发地运往目
的地，可有多条运输路线供选择，这时，可构造费用网
络图，用求最短路线的方法，选择最优的运输方案，使
运输时间最短、费用最省e 对于这类运输问题，只：画
出各种运输路线的线路图及图上每一条边（或弧）上的
距离或费用（也可以用邻接矩阵表示），然后用狄克斯
特拉的标号法或邻接矩阵法求最优运输路线。
基于此，本文在应急物资运输网络问题中试图寻
找一种更加简便有效的方法来进行求解，因此引人了
最小费用流的方法。众所周知，在一个网络中每段路
径都有“容量”和“费用”两个限制的条件下，此类问题
的研究试图寻找出：流 量 从 A 到 B ( A 指出救点，B 指
需求点，出救点可以是多个地点），如何选择路径、分配
经过路径的流量，可以在流量一定的前提下，达到所用
的费用最小的要求。如 n 辆卡车要运送物品，从 A 地
到 B 地。由于每条路段都有不同的路费要缴纳，每条
路能容纳的车的数量有限制，最小费用流问题指如何
分配卡车的出发路径可以达到费用最低，物品又能全
作者简介：李广兴（1990—），华北电力大学经济与管理学院硕士研究生，研究方向：物流工程规划设计；何珊（1992 — :)，华北电
力大学经济与管理学院硕士研究生，研究方向：电力企业管理A
4 8 2 现 代 商 贸 工 业 丨 2016年 第 1 6 期
现代商贸工业
部送到 a
因此，本文基于最小费用流的方法，设计使用与供
应链网络运输问题的最小费用流算法，用以处理供应
急物资运输网络模型，并利州具体例乎来验证该算法
的有效性。
2 应急网络运输问题描述
应急运输网络一般有三级组成，即出救点、中转中
心和需求点。因此，中转中心选址问题可描述为对于 i
个出救点经过 j 个的中转中心，为 k 个 S 求点配送物
品，使得在所选路线及路线的流在满足配送需求的
前提下，使得总费用最低，其运输网络结构如图 1 所
〇
在应急网络运输问题中，出救点的个数和需求点
的数量和位置以及儒求量是固定的，物流中转中心的
地点也是固定的但流经各中转中心的流量不定，因此，
该运输问题的目标是在需求节点需求量得到满足的前
提下使得总费用最小。
为了方便说明问题并且提高本文算法的通用性，
对运输问题进行如下假设：
(1) 从出救点到中转中心、从中转中心到需求点之
间的运输距离是已知的；
(2) 各个需求点的需求量已知或可预测；
(3) 物流经过中转节点的相关成本已知；
(4) 只考虑一种物资的运输，运输费用只和运输量
和距离有关且已知；
(5) —个中转中心可由多个出救点配送物资，一个
需求点的需求也可由多个中转中心提^[共。
(6) 各线路的容M 已知。
基于上述的假设条件，接下来进行模型涉及的参
数和变最进行定义：
i 表示出救点，I 为出救点的集合，则 i€I。
j 表 中 转 中 心 ，J 为中转中心的集合，则 j € J D
k 表示需求点，K 为需求点的集合，则 k€K 。
也表示从出救点 i 向中转中心 j 的运输距离(单
位 ：km) 0
如表示从中转中心 j 向需求点 k 的运输距离（单
位 ：km) 〇
Qij表示从出救点 i 向中转中心 j 的实际运输M (单
位:0 。
Qjk表示从中转中心 j 向需求点 k 的实际运输量
(单位:t)。
Qj表示从出救点 i 向中转中心 j 的最大运输 t t (单
位:0 。
qk表示从中转中心 j 向需求点k 的最大运输量（单
位:0
Pij表示从出救点 i 向中转中心 j 的单位运输费率
(单位:Yuan/(t • km))。
P jk表示从中转中心 j 向需求点 k 的单位运输费率
(单位：Yuan/(t • km))。
P j表示中转中心 j 的库存费用。
M j为第 j 个中转中心的最大容量(单位
Dk为第 k 个需求点的需求总量(单位：t)@
A i S 出救点 i 的供应能力（单位：t)0
3 算法设计
运输问题的目的是要求一个目标函数 F ，使得总
费用 W(F )达到最小，本文算法的模型如下：
约束条件（1)为救援物资供应能力限制；
约束条件(2)是中转中心的物资进出 t t 平衡约束，
即运注中转中心 j 的物资总量，等于从中转中心 j 运出
的物资总t t 。
约束条件(3)为中转中心的容董限制，即从出救点
运往中转中心 j 的运输总量必须小于中转中心 j 的最
大容量 a
约束条件(4)为满足需求约束，即从所有选中的中
转中心向需求点k 的运输翁量必须满足需求点k 的需
求。
约束条件(5)和（6)为各线路的容量限制，
另外，本模型涉及的所有参量均为非负参量&
W (F ) = S (dij X Qij X + d jk X Qjk X pjk)
J = i ' . -
s. t. Ai — X) Qijj=i
S Q tj = S Qjk
i=i
j> S Q jk
JMi
( 1 )
( 2 )
(3)
k= SQjk (4)
j 丨- 3 —
(、.i k . Q .i k ( 5 )
( 6 )
利用最小费用流算法处理该模型，在算法求解过
程中，保持总流量保持不变（即出救节点发出的物流不
变），并逐步向最优性条件过渡，直到满足最优性条件，
算法步骤如下:
(1) 初始化，根据实际情况构建运输网络图（将各
中转节点当成一条有容Id：限制的弧），并确定各供应节
点的产量，各中转中心的容量及各®求节点的 S 求量，
并确定各路线的距离及单位运费率；
(2) 在初始网络中，找到一条满足条件的可行流；
(3) 若在网络中存在可调整的负代价圈，则转人
(4)，若不存在则转人（5);
现代商贸工亚 I 2016年 第 1 6 期 | 83
财 经 管 理
(4) 增量构造新流（保持总流量不变），转至（3);
(5) 将当前流保存为最小费用流，输出。
为使得算法更为迅捷，在 第 （4)步构造新流过程
中，取增量0 = min{容量一正向弧流量；逆向弧流量} a
图2 算法流程图
4 算例分析
图 3 为一个简易的公路网络，为简便起见，下例只
有一个出救节点 S 和I 个 S 求 节 点 T ，并有两个中转
节点（中转点1 和中转点2,且 1 可以向 2 输送物资），
且将各路线的距离转化为单隹物流费用表示& 每条弧
上的数据从左至右分别为单位物流费用、当前流 t t 、容
量。出救节点需要将8 吨的物资经过两个中转节点送
到需求节点。
构建应急物资运输网络时将中转节点当成一条有
流量限制的弧，该弧费用为该中转节点的库存费用，给
各节点编号，并给出一个初始可行流：
图4 初始可行流图
该初始可行流的运输总费用W(F) = 20 + 9 + 4 + 3
+ 5 + 18 + 15 = 74,寻找到的第|个可调整负代价圈是
圈①④⑩，对该圈增加一个增量0=2,得到新流如图5。
该调整后的图的运输总费用W(F) = 12 + 15+3 + 5
+ 18 + 15 = 68,寻我到的第二个可调整负代价圈是圈③
⑤⑥，对该圈增加一个增增量0=2,得到新流如图6a
该调整后的图的运输总费用W(F) = 12 + 15 + 3 +
S + 4 + 21十6 = 6 6，此时图中不存在可调整的负代价
圈，调整结束，得到最小费用流。相比与初始可行流，
图5 第一次调整结果图
图6 第二次调整结果图
费用由74减少到了 68,调整结果较好。
5 结论
应急物资运输问题的核心是运输成本最小化，即
寻找最佳的运输方案使得总费用最低，不同的线路流
量设计将导致不同的费用，这个过程可以抽象为一个
有流量限制的最小费用流问题。本文首先将应急物资
运输网络问题模型化，使其成为一个总量一定的最小
费用流问题;其次，对已有的最小费用流算法进行相应
调整，使其适用于应急物资运输网络问题；最后，利用
具体算例，进行实例分析。利用最小费用流算法解决
应急物资运输网络问题，能够减少运输成本，提高社会
效益。本文考虑的情况较为简单，后继研究可以对应
急物资运输网络问题的各项费用进行更精细的划分，
使得算法更符合实际情况。
参考文献
[1] K em ballC ook, StephensQii R . Lessoninlogisticsfrom Som alia [J ].
D isaster, 1984： f (8) ： 87-66.
[2] R ath iA . K . , C hurchR. L . , SolankiR. S . . Allocating resources to
support, a mul t i ⑩ Wi t h window#[J ]. Logisties:
and Trans Portation R ev iew , 1992?28(2) ： 167-188.
[3j H aghaniA. , O hS. — C. ForHiulation gud sokitioti of a multicoin-
m odity, multimodal network Flow model for disaster relief opera-
tionsCj^ Transportation Research Part A , 1196,30(3) ：231-250,
欧 忠文，王 会云，姜大立等.应急物流 DO.重庆大学学报，2004,27
(3):164-166.
[ 5 ]孟 参 等 .应 急 物 流 系 统 运 作 流 程 分 析 及 其 管 理 [J ] .物 流 技 术 ，
2006,(9)：15-17.
:.[€]谢 政 ，汤泽滢 .带模糊约束的最小费用流问题 [J :].模糊系统与数
学 ，1999,13(2) :940-941,
[ 7 ]寇 玮 华 ，董 雪 ，吕林剑.交通运输网络中两个结点间有流量约束的
最 小 费 用 最 大 流 算 法 兰 州 交 通 大 学 学 报 ，2009,28 (|> : 104
109.
84 现代商贸工业丨2016年 第 1 6 期
