基于 Dijkstra 算法的抗灾物资调运研究
周柳阳
中国矿业大学计算机学院,江苏徐州（221008）
摘要：每年，洪涝灾害都会使我国人民的生命财产遭受严重损失。因此，提前做好抗灾物
资的调运工作，对于防洪抗涝具有重要意义。本文以 A 地区为例，用计算机模拟该地区，首先从该
地区的交通状况图中提炼出两个矩阵，根据 Dijkstra 算法的原理建立了最优路径模型。利用这个模
型，我们求出了任意两个调运节点之间运费最小的路径，以总运费最小为目标函数，就可以求解出
最优调运方案。
当汛期到来，需要对物资进行紧急调运的情况下我们引入“量程积”的概念建立了以量程积最
小为目标函数的优化模型。得出了最终调运方案
关键词：Dijkstra算法 费用最小流 量程积 计算机模拟
1．背景分析
我国洪涝灾害历来很频繁。据统计，自公元前 206 年至 1840 年的 2046 年中，我国
发生较大洪水灾害共计 984 次，平均两年左右就发生 1次。1949 年以来，我国因洪涝灾
害年均农田受灾面积 6667 万hm2，大约也是两年左右发生一次较大洪灾。1990 年以来全
国年均洪涝灾害损失在 1100 亿元左右，约占同期全国GDP的 2％。遇到发生流域性大洪
水的年份，如 1991 年、1994 年、1996 年和 1998 年，该比例可达到 3％～4％。从总体
上讲，在今后相当长的一个时期内，洪涝灾害仍然是中华民族的心腹之患，洪涝灾害的
防治仍然是我们水利部门的中心工作。
我国气候复杂多变，降雨量时空分布异常，防汛形势相当严峻和艰巨。现在全国各
地正在陆续进入主汛期，长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害，汛期
来临时，如果物资储备匮乏，将严重威胁人民和国家的人身、财产安全。因此，我们应
该提前做好防洪抗涝物资储备工作，以便于将风险和损失降到最低。
2.基本假设
1、高等级公路与普通级公路的调运速度是恒定且相等的，因此运输时间只与路程
远近有关。
2、由于该地区任意两点之间的距离不大，认为运输能力没有限制，即无论运输路
程多远、运输件数多少，运输都能在一天内完成。
3、各企业、物资仓库及国家级仓储库之间的物资可以通过公路运输互相调运。
4、企业可以生产也可以不生产。
5、预测值指的是各库存最终需要尽量满足的目标值。
3.变量符号说明
为了便于描述问题，我们在此列出文中主要使用一些符号和基本变量，其他一些变
量将在文中陆续说明。
表 1 符号说明
符号 意义 单位
ijs 从图上点 i到图上点 j 之间的路程 公里
ijp 从图上点 i到图上点 j 之间的运输成本 元/公里•百件
iv 调运节点（企业） 生产速度，i 1, 2,3i = 百件/天
1
it 调运节点（企业） i在调运计划中的生产天数 天
ε 可容相对误差，即与调运节点 预测库存的偏离程度 i
y 总调运费用 元
4.模型的建立与求解
该地区交通的示意图上，分布着 42 个不同的点。任意两个相连的点之间的距离在
图上标出。因此，我们可以从中提炼出一个 42×42 的矩阵，用 表示从图上点 到图上
点
ijs i
j 之间的路程，用 表示从图上点 到图上点ijp i j 之间的运输成本。根据这个矩阵，我
们建立了模型Ⅰ，用来找出任意两个调运节点之间的最优路径。
模型准备
显然，这是图论中的“最短路问题”。我们首先对这地区地况做出一些定义和说明：
定义 1
图 中 是有限集合，( , )G V E 1 2{ , , , }nV v v v= " {( , ) | , }i j i jE v v v v V= ∈ 。称V 中的元素
为图的顶点 ，( 1,2, ,iv i n= " ) (vertex) E 中的元素 ( , )i je v v= 为图的边 或弧 (a 。 (edge) rc)
定义 2
如果 是一个图，并且V V( , )G V E′ ′ ′ ′ ⊂ ，E E′ ⊂ ，则称G′是 的子图 。
对于图 ，如果对 ，赋予一个实数 ，则称 为边 ( , 的
权 ， 连同边上的权重称为赋权图 。
( , )G V E (subgraph)
( , )G V E ( , )i jv v E∈ ( , )i jw v v ( , )i jw v v )i jv v
(weight) G (weighted graph)
定义 3
如果 ，则称( , )i jv v E∈ jv 和 邻接，具有 个顶点的图的邻接矩阵 (
是一个 阶矩阵
iv n adjacency matrix)
n n× ( )ij n nA a ×= ，其分量为
1, ( , ) ,
0,
i j
ij
v v E
a
∈⎧= ⎨⎩ Others.
n个顶点赋权图的赋权矩阵是一个n n× 阶矩阵 ( )ij n nW w ×= ，其分量为
( , ), ( , ) ,
,
i j i j
ij
w v v v v E
w
∈⎧= ⎨∞⎩ Others.
模型Ⅰ的建立
Dijkstra算法[4]是解决最短路问题的一种很有效的方法，它的原理如下：
假设 是V 的真子集且 ，并以S 0u S∈ S 记 。若\V S 0P u uv= "" 是从 到0u S 的最短
路，则显然u ∈S 且 的P 0( , )u u 节必然是最短 0( , )u u 路。所以，
0 0( , ) ( , ) ( )d u v d u u w uv= +
并且从 到0u S 的距离由公式
0 0( , ) min{ ( , ) ( )}u S
v S
d u S d u u w uv∈
∈
= +
给出。这个公式便是 Dijkstra 算法的基础。
在整个算法中，每个顶点 v给以标号 ，它是 的一个上界。开始时( )l v 0( , )d u v 0( ) 0l u = ，
而对 ，则有0v u≠ ( )l v = ∞。在算法进行时，这些标号不断被修改：在第 步结束时 i
2
0( ) ( , )l u d u u= 对 iu S∈ 成立
0( ) min{ ( , ) ( )}
iu S
l v d u u w uv∈= + 对 iv S∈ 成立
下面是具体的 Dijkstra 算法操作流程图：
图 1 Dijkstra 算法操作流程图
当算法结束时，从 到 的距离由标号 的终值给出。 0u v ( )l v
假设图有 个顶点，现需要求从顶点1到顶点 的最短路。设决策变量为n n ijx ，当
，说明弧 位于顶点1到顶点 的路上；否则1ijx = ( , )i j n 0ijx = 。由此，我们可以写出求解
此问题的模型Ⅰ——最优路径模型[1]：
( , )
min ij ij
i j E
W w
∈
= x∑
1 1
( , ) ( , )
1, 1,
0, 1, ,
. .
1, ;
0, ( , )
n n
ij ji
j j
i j E j i E
ij
i
x x i
s t
i n
x i j E
= =
∈ ∈
⎧ =⎧⎪⎪ − = ≠⎨⎪⎨ ⎪− =⎩⎪⎪ ≥ ∈⎩
∑ ∑ n
x
模型Ⅰ的求解。
在利用这个模型求解任意两点之间的最优路径时，需要注意目标函数中的每段路线
上的权重 。 的含义不同，最终的结果也不同。当情况紧急，需要寻找一条最短最
快捷的路径时，可以将 定义为两点之间路线的长度 ，目标函数变为这样的形式：
ijw ijw
ijw ijs
( , )
min ij ij
i j E
W s
∈
= ∑
所求出来的结果就是出发点与目的地之间的最短路径。
如果情况不是很紧急，则应该综合考虑运输费用，此时，我们可以定义权重为单位
运输成本与路程的乘积[2]： ，这样得到的目标函数是： ij ij ijw p s= ⋅
3
( , )
min ij ij ij
i j E
W p s
∈
= x∑
这样求出来的路径就是运输费用最低的路径。
要得到一个最合理的调运方案，就需要建立一个优化模型，用来求出最佳调运量以
及调运路线。
1、约束条件的确定[3]
我们令按照模型求出的从 i 调运节点到 j 调运节点的调运量为 ijx ， 。则调运
结束后各个节点的库存 为：
0ijx ≥
ir
13 13
1 1
13 13
1 1
, 1, 2,
, 4,5, ,1
i ij ji i i
j j
i
i ij ji
j j
c x x v t i
r
c x x i
= =
= =
⎧ − + + =⎪⎪= ⎨⎪ − + =⎪⎩
∑ ∑
∑ ∑ "
3
3
题目列出了各库库存与需求情况，其中列出了预测库存一项。我们认为，按照运输
方案进行调度之后，各个运输节点的库存，应该尽可能地接近或大于预测库存。 令ε 为
能够接受的实际库存与预测库存的偏离程度， if 预测库存量，有：
, 4,5, ,1i i
i
f r i
f
ε 1− ≤ = "
另外，一个节点需要的库存能力有限制，必须不超过最大库存，有：
1, 2, ,13i ir M i≤ = "
此外，要重点保证国家级储备库的库存。因此，我们要求的方案必须使国家级储备
库的库存达到或者超过其预测值，即：
, 12,1i if r i 3≤ =
2、目标函数的建立
我们希望我们的调运方案在满足各项要求的基础上，所花费的运输费用最小。从第
一问的结果中，我们已经得到了任意两个调运节点之间花费最小的最优路径，该路径的
每百件物资的运输费用为 元。显然，如果从调运节点 i 运输ijW ijx 百件物资到调运节点 j，
一定会从已经求得的最优路径进行运输。这样，调运结束之后，花费的总费用为：
13 13
1 1
ij ij
i j
y W
= =
=∑∑ x
模型Ⅱ建立
根据上面的分析，我们建立了模型Ⅱ—最优调运模型：
4
13 13
1 1
min
, 1,2, ,13
, 4,5, ,1
. . , 12,13
0, , 1,2, ,13
0 ,
ij ij
i j
i i
i i
i
i i
ij
i
y W x
r M i
f r i
f
s t f r i
x i j
t T t
ε
= =
=
≤ =⎧⎪ −⎪ ≤ =⎪⎪ ≤ =⎨⎪ ≥ =⎪⎪ ≤ ≤⎪⎩
∑∑
"
"
"
为整数
1
3
3
其中：
13 13
1 1
13 13
1 1
, 1, 2,
, 4,5, ,1
i ij ji i i
j j
i
i ij ji
j j
c x x v t i
r
c x x i
= =
= =
⎧ − + + =⎪⎪= ⎨⎪ − + =⎪⎩
∑ ∑
∑ ∑ "
通过这个模型，在给定了偏离程度ε 以及调运天数 T 的情况下，就可以求出相应的
最优方案。
一种情况下的最优方案
我们用一种特殊情况来演示模型Ⅱ的效果。
由于不知道汛期何时到来，我们需要尽快做好准备，在最短的时间内使各个调运节
点的预测库存得到尽量满足。我们可以先进行一个粗略的估算：各个调运节点的原有库
存之和 ，而各个调运节点的预测库存之和 ，即相差 670。因此，
要基本满足要求，需要各企业至少生产 8 天。我们就以 8 天为调运期，求出最优方案。
我们假定
13
1
8380i
i
c
=
=∑ 13
4
9050i
i
f
=
=∑
ε 取 ，于是模型Ⅱ变为：
13 13
1 1
min
, 1,2, ,13
, 4,5, ,11
. . , 12,13
0, , 1, 2, ,13
0 8,
ij ij
i j
i i
i i
i
i i
ij
i
y W x
r M i
f r i
f
s t f r i
x i j
t t
= =
=
≤ =⎧⎪ −⎪ ≤ =⎪⎪ ≤ =⎨⎪ ≥ =⎪⎪ ≤ ≤⎪⎩
∑∑
"
"
"
为整数
利用模型Ⅱ，我们可以很容易地求出结果。仍令ε 取 ，此时，模型为：
5
13 13
1 1
min
, 1,2, ,13
, 4,5, ,11
. . , 12,13
0, , 1, 2, ,13
0 20,
ij ij
i j
i i
i i
i
i i
ij
i
y W x
r M i
f r i
f
s t f r i
x i j
t t
= =
=
≤ =⎧⎪ −⎪ ≤ =⎪⎪ ≤ =⎨⎪ ≥ =⎪⎪ ≤ ≤⎪⎩
∑∑
"
"
"
为整数
编程求解可求得最优调运方案。此时的运输费用为 299763 元
5 模型的进一步讨论
1、调运期的长短与运费的关系
在求解问题 2和问题 3的时候，我们发现，在调运期为 8天的时候，总运费为 321680
元，调运期为 20 天的时候，总运费为 299763 元。显然，调运时间的长短对最终运费有
着显著影响。
我们希望能够找到一个最佳的时间，使得总运费能够达到最小，同时，各个调运点
的能够达到或超过预测值。为了找出这个最佳时间，我们在模型Ⅱ的基础上作了一点改
动，建立了模型Ⅲ——最佳时间模型：
Min
13 13
1 3 1 1
{ }i ii i j
j ijz Max t w x≤ ≤ = =
= ⋅∑∑
, 1, 2, ,1
. . 0, , 1, 2, ,13
, 1, 2,3
i i i
ij
i
f r M i
s t x i j
t T i
⎧ ≤ ≤ =⎪ ≥ =⎨⎪ ≤ =⎩
"
"
3
由于模型Ⅱ中与预测库存的偏差ε 的取值对最终费用的大小有影响，因此，在这个模型
中，我们对于调运后的库存量进行了强制约束，要求在调度完毕之后，各库的库存都要
达到或超过预测值。通过这个模型，代入不同的 T 值，将求出的结果互相比较，就可以
得到最佳的调运期限。
我们将 T 从 8 开始，逐渐增加后代入求解。最终，我们得到每次的 T 值与其对应的总运
费，如图 2 所示：
6
图 2 强约束预测库存条件下企业生产天数与总调运费用关系图
从图 2中我们能不难看出，随着调运期的增加，总的调运费用不断下降。当 T增加
到 22 天的时候，调运费用趋于平衡，不再发生改变。
造成这种情况的原因是，随着调运期限的增加，企业可用来生产的天数也增加，因
而企业能够运出的物资量也增加，相应的输出选择面和灵活度也增加，从而使总运费降
低。
因此，我们能够得出如下结论：
（1） 调运期限越长，所要花费的总运费越少。
（2） 22 天是最佳调运期限，此后的调运费用不发生改变，因此没有必要制定多
于 22 天的调运计划。
（3） 如果能够对于汛期的到来进行比较准确的预测，则在汛期到来之前 22 天开
始进行调运，到汛期到来前一天结束，能够得到最合适的结果。
2、调运期的长短、ε 的取值对于费用的影响
ε 的取值对于费用也有着重要的影响。因此，我们希望能够找到ε 和 T 对于总费用
的影响效果。
模型Ⅱ： 中同时含有
13 13
1 1
min ij ij
i j
y W
= =
=∑∑ x ε 和 T两个因素，因此，我们分别取不同的
ε 和 T值，得到不同的费用，作出了图 3 ：
图 3 总费用与可容相对误差和物资生产天数二元关系
从上述图表中我们可以很容易地看到：总调运费用 y 是关于普通仓库预测库存相对
7
误差ε 和调运周期 T 的二元函数；且总调运费用 y 均随着可容相对误差ε 和物资生产天
数 T 的增加而减少。
这是非常符合实际情况的，因为当可容相对误差ε 的增大使得调运工作的约束条件
减弱，自由度增加，因而总的调运费用降低；物资生产天数 T 的增加使得各个企业的输
出能力增大，故导致调运任务的灵活性增加，因而总的调运费用降低。
同时，从上图中我们也可以很明显地看出：可容相对误差ε 的波动对总调运费用 y
的影响比物资生产天数 T 的改变对总调运费用 y 的影响要大。
6 结论:本文通过对该地区的计算机模拟，利用 Dijkstra 算法建立了合理的优化模型，
可以针对不同的目标求出最精确最合适的路径。建立的模型充分考虑了各个仓库的库存
情况，得出的方案也尽可能地满足各个仓库的库存要求。研究了不同因素对总运费的影
响情况，对如何预测汛期和制定方案提出了自己的建议。本文虽然选取的为 A地区，但
是不失一般性，对其他相应地区只要作相应调整，也能起到很好效果。
参考文献：
[1]姜启源，数学模型，北京：高等教育出版社，2004 年
[2]胡寿松，自动控制原理简明教程，北京：科学出版社，2003 年
[3]韩中庚，数学建模方法及其应用，北京：高等教育出版社，2005 年
[4]殷剑宏 吴开亚， 图论及其算法， 合肥：中国科学技术大学出版社， 2003 年
8
Material dispatching disaster research
Zhou Liuyang
Computer Science and Technology,China University of Mining and Technology,Xuzhou(221008)
Abstract
Every year, floods in China will make people's lives and property suffered heavy losses. As a
result, disaster-resistant materials in advance to do a good job of transport, for flood
prevention is of great significance. A region with this article, for example, using computer
simulation in the region, starting with the traffic situation in the region of the map to extract
the matrix of the two, according to the Dijkstra algorithm [4] established the principle of the
best path to the model. Take advantage of this model, we derive any two of the freight
transport between the nodes of the smallest path to the total freight for the minimum objective
function, we can solve the optimal transport program.
When the arrival of flood season, the need to transport emergency supplies of the introduction
of our "product range," the concept of the establishment of a product range in order to
minimize the objective function of optimization model. Come to the end of the transport
program
Keywords: Dijkstra algorithm, Minimum cost flow, Product Range, Computer Simulation
9
