石群 , 杨镇铭 , 赵千川
清华大学 自动化系, 北京 100084

收稿日期：2017-07-07
基金项目：国家自然科学基金资助项目（61425027）
作者简介：石群(1983-), 男, 博士研究生
通信作者：赵千川, 教授, E-mail:zhaoqc@tsinghua.edu.cn

摘要：自然灾害发生后，需要向灾区运输救灾物资。该文研究在救灾物资供给灾民人数最大化的基础上，最小化救灾物资运输费用的方法。该文首先给出救灾物资、救灾车辆之间的替换和搭配关系的一些定义和命题，采用整数规划求解救灾物资供给灾民最大人数。在此基础上，采用整数规划最小化救灾物资运输费用。仿真实验表明：将救灾物资配车问题分解为若干子问题后，时间复杂度显著降低；考虑了替换和搭配关系，可以在最小化救灾物资运输费用的同时，保持救灾物资供给灾民人数最大化。
关键词：替换关系搭配关系救灾物资整数规划
Vehicle dispatch problem considering substitutions and collocations
SHI Qun, YANG Zhenming, ZHAO Qianchuan
Department of Automation, Tsinghua University, Beijing 100084, China


Abstract: Relief materials need to be rapidly transported to disaster areas after natural disasters. This paper describes how to minimize the transport by maximizing the number of victims supplied by the relief materials. This integer programming method involves the substitution and collocation of relief materials and vehicles to maximize the number of victims served and minimize the transport costs. Simulations show that the time complexity of the vehicle dispatch is significantly reduced after the problem is decomposed into sub-problems. The substitution and collocation reduces the transport costs while maximizing the number of victims supplied by relief materials.
Key words: substitutioncollocationrelief materialsinteger programming
自然灾害发生后交通状况恶化，需要根据运输车辆特点向灾区运输灾民所需的各种救灾物资，确保供给灾民人数最大化。国内外****在救灾物流领域开展了大量研究工作。
谢如鹤等^[1]系统介绍了应急救灾物流产生过程、涵义和特点。李阳等^[2]设计了适合国情的救灾物流体系。程琦等^[3]系统研究了自然灾害应急物流管理体系的构成。王旭坪等^[4]研究了应急救灾物流系统的要素、特点和设计原则。姜玉宏等^[5]研究了应急救灾物资分类、特点以及应急救灾物资的管理要求和流程。孟参等^[6]建立了一种应急救灾物流系统运作流程的基本框架。傅志妍等^[7]指出应急救灾物流管理是应急救灾管理体系中的重要组成部分。关于救灾物资分发工作，Anaya-Arenas等^[8]总结了多位****的研究成果。?zdamar等^[9]对应急救灾物流的研究工作进行了综述。李创^[10]针对中国应急物流发展的主要问题，研究了应对措施。
高建国等^[11]总结了中国救灾物资储备体系的历史和现状。张红^[12]指出中国应急物资储备制度存在的诸多问题。丁斌等^[13]按照应急救灾物资的多种特性，构建了应急物资储备分类体系。邹铭等^[14]构建了救灾活动中运输救灾物资的评价指标体系。张馨予^[15]提出了一种基于多层约束理论的救灾物资保障配置多级库存优化模型。Sun等^[16]采用模糊优化方法分析灾民对救灾物资的需求，并进行分类预测。Day等^[17]从供应链角度分析了救灾物资需求。CHEN等^[18]指出灾后向灾区配送合理数量比例的救灾物资对挽救灾民生命具有重要意义。赵千川等^[19]提出了一种随机的库存控制策略。现有救灾物资储备管理工作没有从灾民需求角度考虑救灾物资的结构特点。
缪成等^[20]对多货物、多起止点运输网络的运输车辆调度问题进行求解。刘春林等^[21]研究了多出救点的救灾物资调度问题。刘北林等^[22]建立了时间最短、成本最低的多目标优化模型。戴更新等^[23]研究了多种物资应急调配问题。管晓宏等^[24]研究了大规模应急救灾物资供应点选择及运输路径规划问题。计国君等^[25]研究了不确定性条件下的救灾物资调度方案。现有关于救灾物资配车调度工作没有将灾民对救灾物资的需求和运输车辆的额定载重结合起来考虑。
本文首先给出了救灾物资使用单元、运输单元和救灾车辆的定义。然后，对救灾物资、救灾车辆之间的替换和搭配关系进行了定量描述，对救灾物资配车问题建立了数学模型，并给出了将原问题分解为子问题的求解方法。最后，对一个救灾物资配送问题进行了仿真实验，并分析了求解方法的时间复杂度。
1 定义和命题灾后需要评估灾民的物资需求，根据车辆能够运输物资种类及额定载重，确定配车方案。本节提出一个两阶段优化问题：第一阶段针对筹集到的救灾物资，最大化供给灾民人数；第二阶段在第一阶段优化结果基础上，最小化运输救灾物资的总运费。为了便于描述上述优化问题，列出若干定义和命题及符号说明如下。
定义1 ?将运输救灾物资至灾区的车辆称为救灾车辆，记作X_i(i=1, 2, …, m)。将一辆救灾车辆X_i正常行驶能够运输救灾物资的重量称为额定载重，记作X_i⁰。将救灾车辆X_i能够运输救灾物资的总重量称为X_i的实际载重，记作x_i。将救灾车辆X_i的数量记作V_i。将救灾车辆X_i单位重量、单位里程的运费记作F_i。
定义2 ?从救灾车辆运输的角度，将救灾物资的最小单元称为运输单元，记作Y_j(j=1, 2, …, n)。将装入救灾车辆的运输单元Y_j总重量称为Y_j的车辆运重，记作y_j。
定义3 ?从满足灾民需求的角度，将运输至灾区的向灾民手中发放的救灾物资的最小单元称为使用单元，记作Z_k(k=1, 2, …, p)。将运输至灾区的使用单元Z_k的总重量称为灾区运重，记作z_k。
定义4 ?对于运输单元Y_j(j=1, 2, …, n)，将维持灾民生存一段时间T的平均需求重量称为Y_j的人均需求量，记作A_j^Y(j=1, 2, …, n)。
使用单元由运输单元组成，运输单元是组成使用单元的最小单元。将运输单元之间的关联耦合关系定义为替换关系和搭配关系两类。
定义5?组成同一种使用单元Z_k的2种运输单元Y_a和Y_b之间存在替换关系，即一定重量的Y_a和Y_b可以替换使用。采用“‖”表示Y_a和Y_b之间的替换关系，记作Z_k=‖(Y_a, Y_b)。替换关系的定义可以推广至多种运输单元组成使用单元的情形。
定义6 ?必须组合起来使用才能组成使用单元Z_k的两种运输单元Y_c和Y_d之间存在搭配关系，即一定重量的Y_c和Y_d可以搭配使用。采用“ & ”表示Y_c和Y_d之间的搭配关系，记作Z_k= & (Y_c, Y_d)。搭配关系的定义可以推广至多种运输单元组成使用单元的情形。
定义7?由于运输单元的运输条件不尽相同，不同种类的救灾车辆能够运输的运输单元也不尽相同。可以运输同一种运输单元Y_j的两种救灾车辆X_e和X_f之间存在替换关系，即能够运输相同重量Y_j的X_e和X_f可以替换运输。采用“‖”表示X_e和X_f之间的替换关系，记作Y_j=‖(X_e, X_f)。
救灾物资使用单元、运输单元和救灾车辆之间的关联耦合关系如图 1所示。

图 1 使用单元、运输单元和救灾车辆的关系

图选项

在图 1中：

${Z_1} = {Y_1},{Y_1} = {X_1};$

${Z_2} = \& \left( {{Y_2},{Y_3}} \right),{Y_2} = {X_2},{Y_3} = \left\| {\left( {{X_3},{X_4}} \right)} \right.;$

${Z_3} = \left\| {\left( {{X_4},{X_5}} \right)} \right.,{Y_4} = {X_5},{Y_5} = \left\| {\left( {{X_1},{X_3},{X_6}} \right)} \right..$

下面针对救灾物资使用单元、运输单元和救灾车辆之间关联耦合关系，介绍若干定量计算的命题。
命题1 ?若车辆运重为y_j的运输单元Y_j能够供给人数为h_j^Y的灾民维持生存一段时间T，则

$h_j^Y = \left\lfloor {\frac{{{y_j}}}{{A_j^Y}}} \right\rfloor ,\;\;\;\;j = 1,2, \cdots ,n.$

命题2 ?若Z_k=‖(Y_a, Y_b)，运输单元Y_a和Y_b的车辆运重分别为y_a^k和y_b^k，设灾区运重为z_k的使用单元Z_k能够供给人数为h_k^Z的灾民维持生存一段时间T，则

$h_k^Z = h_a^k + h_b^k,\;\;\;\;\;h_a^k = \left\lfloor {\frac{{y_a^k}}{{A_a^Y}}} \right\rfloor ,\;\;\;\;\;h_b^k = \left\lfloor {\frac{{y_b^k}}{{A_b^Y}}} \right\rfloor .$

(1)

其中h_a^k和h_b^k分别为替换组成使用单元Z_k的运输单元Y_a和Y_b能够供给维持生存一段时间T的灾民人数。式(1)可以推广至多种运输单元替换组成使用单元时，计算使用单元供给灾民人数的情形。
命题3 ?若Z_k= & (Y_c, Y_d)，运输单元Y_c和Y_d的车辆运重分别为y_c^k和y_d^k，设灾区运重为z_k的使用单元Z_k能够供给人数为h_k^Z的灾民维持生存一段时间T，则

$h_k^Z = \min \left\{ {h_a^k,h_b^k} \right\},\;\;\;\;\;\;h_a^k = \left\lfloor {\frac{{y_a^k}}{{A_a^Y}}} \right\rfloor ,\;\;\;\;\;h_b^k = \left\lfloor {\frac{{y_b^k}}{{A_b^Y}}} \right\rfloor .$

(2)

其中h_a^k和h_b^k分别为搭配组成使用单元Z_k的运输单元Y_a和Y_b能够供给维持生存一段时间T的灾民人数。式(2)可以推广至多种运输单元搭配组成使用单元时，计算使用单元供给灾民人数的情形。
命题4 ?若Y_j=‖(X_e, X_f)，则Y_j的车辆运重y_j根据X_e和X_f的实际载重x_e^j和x_f^j计算：

${y_j} = x_e^j + x_f^j.$

其中x_e^j和x_f^j分别为X_e和X_f运输Y_j的实际载重。
2 问题描述下面考虑救灾物资、救灾车辆的替换关系和搭配关系，建立救灾物资配车问题的两阶段优化数学模型。
第一阶段优化问题针对筹集到的救灾物资，最大化能够供给灾民的人数。
决策变量包括：
1) 使用单元供给灾民的人数h^Z, ${h^Z} \in \mathbb{Z}$；
2) 每种救灾车辆的实际载重x_i(i=1, 2, …, m)；
3) 每种救灾车辆运输的各种运输单元的实际载重x_i^j(i=1, 2, …, m; j=1, 2, …, n)；
4) 在各种使用单元中，由每种救灾车辆运输的各种运输单元的实际载重x_i^{j, k}(i=1, 2, …, m; j=1, 2, …, n; k=1, 2, …, p);
5) 每种救灾车辆的数量V_i(i=1, 2, …, m), ${V^i} \in \mathbb{Z}$。
目标函数为maxh^Z。
当各种使用单元Z_k(k=1, 2, …, p)的供给灾民人数h_k^Z均等于h^Z时，救灾物资可以供给的灾民人数为h^Z:

$h_1^Z = h_2^Z = \cdots = h_p^Z = {h^Z},$

(3)

${h^Z} \geqslant 0,\;\;\;\;{h^Z} \in \mathbb{Z}.$

(4)

h_k^Z分为2种情形计算：
1) 使用单元Z_k由多种运输单元替换组成，即Z_k=‖(Y₁, Y₂, …, Y_n), 有

$h_k^Z = \sum\limits_{j = 1}^n {h_j^k} .$

(5)

2) 使用单元Z_k由多种运输单元搭配组成，即Z_k= & (Y₁, Y₂, …, Y_n), 有

$h_k^Z = \min \left\{ {h_1^k,h_2^k, \cdots ,h_n^k} \right\}.$

(6)

式(5)和(6)中，

$h_i^k = \left\lfloor {\frac{{y_i^k}}{{A_i^Y}}} \right\rfloor ,\;\;\;\;j = 1,2, \cdots ,n.$

(7)

式(7)中，

$y_j^k = \sum\limits_{i = 1}^m {x_i^{j,k}} ,\;\;\;j = 1,2, \cdots ,n;x_i^{j,k} \ge 0.$

(8)

x_i、x_i^j、x_i^{j, k}之间的关系为

${x_i} = \sum\limits_{j = 1}^n {x_i^j} ,\;\;\;i = 1,2, \cdots ,m;{x_i} \ge 0.$

(9)

$x_i^j = \sum\limits_{k = 1}^p {x_i^{j,k}} ,\;\;\;i = 1,2, \cdots ,m;j = 1,2, \cdots ,n.$

(10)

每种救灾车辆X_i的数量V_i计算如下：

${V_i} = \left\lceil {\frac{{{x_i}}}{{X_i^0}}} \right\rceil ,\;\;\;\;i = 1,2, \cdots ,m.$

(11)

式(14)中，V_i满足数量约束：

$0 \leqslant {V_i} \leqslant {{\hat V}_i},\;\;\;\;i = 1,2, \cdots ,m;{V_i} \in \mathbb{Z}.$

(12)

其中$ {\hat V_i}$表示救灾车辆X_i的数量上界。
第一阶段优化问题的约束条件按照使用单元的2种组成情形，分别整理如下：
1) 使用单元由运输单元替换组成。
将式(5)代入式(3)，得

$\sum\limits_{j = 1}^n {h_j^1} = \sum\limits_{j = 1}^n {h_j^2} = \cdots = \sum\limits_{j = 1}^n {h_j^p} = {h^Z}.$

(13)

将式(7)代入式(13)，得

$\sum\limits_{j = 1}^n {\left\lfloor {\frac{{y_j^k}}{{A_j^Y}}} \right\rfloor } = {h^Z},\;\;\;\;k = 1,2, \cdots ,p.$

(14)

将式(8)代入式(14)，得

$\sum\limits_{j = 1}^n {\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{j,k}} }}{{A_j^Y}}} \right\rfloor = {h^Z}} ,\;\;\;k = 1,2, \cdots ,p.$

(15)

2) 使用单元由运输单元搭配组成。
将式(6)代入式(3)，得

$\begin{array}{*{20}{c}} {\min \left\{ {h_1^1,h_2^1, \cdots ,h_n^1} \right\} = \min \left\{ {h_1^2,h_2^2, \cdots ,h_n^2} \right\} = \cdots = } \\ {\min \left\{ {h_1^p,h_2^p, \cdots ,h_n^p} \right\} = {h^Z}.} \end{array}$

(16)

将式(7)代入式(16)，得

$\begin{array}{*{20}{c}}{\min \left\{ {\left\lfloor {\frac{{y_1^1}}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{y_2^1}}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{y_n^1}}{{A_n^Y}}} \right\rfloor } \right\} = }\\{\min \left\{ {\left\lfloor {\frac{{y_1^2}}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{y_2^2}}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{y_n^2}}{{A_n^Y}}} \right\rfloor } \right\} = \cdots = }\\{\min \left\{ {\left\lfloor {\frac{{y_1^p}}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{y_2^p}}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{y_n^p}}{{A_n^Y}}} \right\rfloor } \right\} = {h^Z}.}\end{array}$

(17)

将式(8)代入式(17)，得

$\begin{array}{*{20}{c}}{\min \left\{ {\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{1,1}} }}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{2,1}} }}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{n,1}} }}{{A_n^Y}}} \right\rfloor } \right\} = }\\{\min \left\{ {\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{1,2}} }}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{2,2}} }}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{n,2}} }}{{A_n^Y}}} \right\rfloor } \right\} = \cdots = }\\{\min \left\{ {\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{1,p}} }}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{2,p}} }}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{n,p}} }}{{A_n^Y}}} \right\rfloor } \right\} = {h^Z}.}\end{array}$

(18)

总结约束条件为式(4)、(9)~(12)、(15)、(18)。
求解第一阶段优化问题，得到目标函数值maxh^Z，即全部救灾物资供给灾民人数最大值，记作H。
第二阶段优化问题在第一阶段优化结果基础上，即在全部救灾物资供给灾民人数保持为H的条件下，最小化运输救灾物资的总运费。
决策变量包括：
1) 每种救灾车辆的实际载重x_i(i=1, 2, …, m);
2) 每种救灾车辆运输的各种运输单元的实际载重x_i^j(i=1, 2, …, m; j=1, 2, …, n);
3) 在各种使用单元中，由每种救灾车辆运输的各种运输单元的实际载重x_i^{j, k}(i=1, 2, …, m; j=1, 2, …, n; k=1, 2, …, p);
4) 每种救灾车辆的数量V_i(i=1, 2, …, m), ${V^i} \in \mathbb{Z}$。
目标函数为$\min \sum\limits_{i = 1}^m {({F_i}{x_i}{L_i})} $, 其中L_i表示救灾车辆X_i运输救灾物资行驶的总里程。
分别将式(15)和(18)中的h^Z代入第一阶段优化结果H，得

$\sum\limits_{j = 1}^n {\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{j,k}} }}{{A_j^Y}}} \right\rfloor } = H,\;\;\;k = 1,2, \cdots ,p;$

(19)

$\begin{array}{*{20}{c}}{\min \left\{ {\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{1,1}} }}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{2,1}} }}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{n,1}} }}{{A_n^Y}}} \right\rfloor } \right\} = }\\{\min \left\{ {\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{1,2}} }}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{2,2}} }}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{n,2}} }}{{A_n^Y}}} \right\rfloor } \right\} = \cdots = }\\{\min \left\{ {\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{1,p}} }}{{A_1^Y}}} \right\rfloor ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{2,p}} }}{{A_2^Y}}} \right\rfloor , \cdots ,\left\lfloor {\frac{{\sum\limits_{i = 1}^m {x_i^{n,p}} }}{{A_n^Y}}} \right\rfloor } \right\} = H.}\end{array}$

(20)

总结约束条件为式(9)~(12)、(19)、(20)。
救灾物资配车两阶段优化问题可采用整数规划方法求解。当组成不同种类使用单元的运输单元采用不同种类的救灾车辆运输时，上述两阶段整数规划问题可分解为若干个小规模整数规划子问题，即某些种类使用单元的配车问题可以独立求解。
3 仿真实验本节仿真实验的计算机配置如下：CPU为Intel(R) Core(TM) i3-3220，3.30 GHz；RAM大小为4.00 GB，其中3.88 GB可用。
?zdamar等^[26]研究了救灾物资配送问题。本文对文[26]中救灾物资和车辆之间的替换和搭配关系进行假设，救灾物资运输单元信息如表 1所示。
表 1 救灾物资运输单元信息

运输 单元	物资	人均需求
		kg
Y1	食物	3.28
Y2	帐篷帆布	13.48
Y3	帐篷支架	27.50
Y4	衣物	8.74
Y5	药品	0.03
Y6	血清	0.02
Y7	设备A	0.13
Y8	设备B	0.20

表选项






救灾车辆信息如表 2所示。
表 2 救灾车辆信息表

运输车辆	额定载重	数量	运费
	t		元·t-1·km-1
X1	5	279	1.00
X2	7	298	0.80
X3	10	372	0.60
X4	20	205	0.45
X5	30	223	0.35
X6	40	298	0.30
X7	50	186	0.25

表选项






救灾物资和车辆之间的关系如图 2所示。

图 2 救灾物资和救灾车辆之间替换和搭配关系

图选项

文[26]中指出全部救灾车辆合计1 861辆，额定载重合计39 211 t。采用本文的模型和解法可得，现有数量的救灾车辆只需运输25 745.2 t救灾物资，最多供给灾民482 317人，每辆救灾车辆行驶260 km，最低总运费为2 451 631元。各种救灾车辆的配车方案如表 3所示。
表 3 救灾车辆配车方案

救灾车辆	运输单元	实际载重
		t
X2	Y1	568.23
X3	Y1	1 012.95
X4	Y2	0
X5	Y2	0
X6	Y2	3 404.29
X7	Y2	3 096.35
X4	Y3	0
X5	Y3	0
X6	Y3	7 156.47
X7	Y3	6 107.19
X2	Y4	1 509.39
X3	Y4	2 707.05
X1	Y5	16.84
X2	Y6	8.38
X4	Y7	0
X6	Y7	61.59
X7	Y8	96.46

表选项






下面分析求解方法的时间复杂度。采用分支定界法求解整数规划模型，每次分支需要求解两个线性规划模型。第m代分支共有2^m条，采用椭球算法求解线性规划的时间复杂度为O(n⁴)。因此，本文求解救灾物资配车问题的时间复杂度为O(2^mn⁴)，其中n为决策变量的个数。
根据使用单元、运输单元和救灾车辆之间的关系，将原整数规划问题分解为p个子问题，在不同的子问题中，不存在同种运输车辆。对应地，将n个决策变量分为p组，各组决策变量的个数满足：

${n_1} + {n_2} + \cdots + {n_p} = n.$

求解p个子问题的时间复杂度为O(2^mn_*⁴)，其中n_*=max{n₁, n₂, …, n_p}。
O(2^mn_*⁴)≤O(2^mn⁴)，即求解p个子问题的时间复杂度占原问题时间复杂度的比例为

$\eta = \frac{{{2^m}n_ * ^4}}{{{2^m}{n^4}}} = {\left( {\frac{{\max \left\{ {{n_1},{n_2}, \cdots ,{n_p}} \right\}}}{{{n_1} + {n_2} + \cdots + {n_p}}}} \right)^4} \times 100\% .$

将17个决策变量分为3组：
1) x₂^{1, 1}、x₃^{1, 1}、x₂^{4, 3}、x₃^{4, 3}、x₂^{6, 5}，即n₁=5；
2) x₄^{2, 2}、x₅^{2, 2}、x₆^{2, 2}、x₇^{2, 2}、x₄^{3, 2}、x₅^{3, 2}、x₆^{3, 2}、x₇^{3, 2}、x₄^{7, 6}、x₆^{7, 6}、x₇^{8, 6}，即n₂=11；
3) x₁^{5, 4}，即n₃=1。

$\eta = {\left( {\frac{{\max \left\{ {{n_1},{n_2},{n_3}} \right\}}}{{{n_1} + {n_2} + {n_3}}}} \right)^4} \times 100\% = 17.53\% .$

实际启用救灾车辆合计1 126辆，仅占全部1 861辆的60.51%，既能最大化供给灾民的人数，节省救灾车辆的运输能力。求解原整数规划问题用时3 964 s，分解为子问题用时仅为42 s，降低了求解时间复杂度。
当某些种救灾车辆数量增加时，分支的代数增加Δm，采用分支定界法求解时间复杂度为

$O\left( {{2^{m + \Delta m}}{n^4}} \right) = O\left( {{2^{\Delta m}}{2^m}{n^4}} \right).$

当救灾车辆种类增加时，决策变量的个数增加Δn，采用分支定界法求解时间复杂度为

$O\left( {{2^m}{{\left( {n + \Delta n} \right)}^4}} \right) = O\left( {{2^m}{n^4}} \right){\left( {1 + \frac{{\Delta n}}{n}} \right)^4}.$

设原问题有n个决策变量，分解为p个子问题。当某个子问题有(n-p+1)个决策变量，其余(p-1)个子问题各有1个决策变量时，得到求解p个子问题时间复杂度的上界，即

$\begin{array}{*{20}{c}}{{n_ * } = \max \left\{ {{n_1},{n_2}, \cdots ,{n_p}} \right\} = n - p + 1,}\\{O{{\left( {{2^m}n_ * ^4} \right)}_{\max }} = O\left( {{2^m}{{\left( {n - p + 1} \right)}^4}} \right).}\end{array}$

4 结论本文考虑了各种救灾物资之间的替换和搭配关系并给出了定量描述，确定了救灾物资能够供给灾民人数最大值，突出了救灾活动中“救人优先”的原则。研究了救灾物资和救灾车辆之间的装载关系，在保证运输至灾区的救灾物资能够供给最多灾民的基础上，最小化各种救灾车辆的总费用。对提出的救灾物资运输问题建立了数学模型，给出了将原问题分解为多个子问题的求解方法，分析了求解时间复杂度，并通过仿真实验进行了验证。

参考文献

[1]	谢如鹤, 邱祝强. 论应急物流体系的构建及其运作管理[J]. 物流技术, 2005(10): 78–80. XIE R H, QIU Z Q. Discussion on the construction and operating management of emergency logistics system[J]. Logistics Technology, 2005(10): 78–80. DOI:10.3969/j.issn.1005-152X.2005.10.024(in Chinese)
[2]	李阳, 李聚轩, 滕立新. 大规模灾害救灾物流系统研究[J]. 科技导报, 2005, 23(7): 64–67. LI Y, LI J X, TENG L X. Study on disaster relief logistics system design of large scale disaster[J]. Science & Technology Review, 2005, 23(7): 64–67. (in Chinese)
[3]	程琦, 云俊. 论自然灾害应急物流管理体系的构建[J]. 武汉理工大学学报(社会科学版), 2009, 22(1): 18–22. CHENG Q, YUN J. Theoretical issues about constructing an emergency logistics management system for natural disasters[J]. Wuhan University of Technology (Social Science Edition), 2009, 22(1): 18–22. (in Chinese)
[4]	王旭坪, 傅克俊, 胡祥培. 应急物流系统及其快速反应机制研究[J]. 中国软科学, 2005(6): 127–131. WANG X P, FU K J, HU X P. Research on emergency logistics system and its emergent response mechanism[J]. China Soft Science, 2005(6): 127–131. (in Chinese)
[5]	姜玉宏, 颜华, 欧忠文, 等. 应急物流中应急物资的管理研究[J]. 物流技术, 2007, 26(6): 17–19. JIANG Y H, YAN H, OU Z W, et al. Study on emergency materials management in emergency logistics[J]. Logistics Technology, 2007, 26(6): 17–19. (in Chinese)
[6]	孟参, 王长琼. 应急物流系统运作流程分析及其管理[J]. 物流技术, 2006(9): 15–17. MENG C, WANG Z Q. Analysis and management of operation process in emergency logistics system[J]. Logistics Technology, 2006(9): 15–17. (in Chinese)
[7]	傅志妍, 陈坚. 灾害应急物资需求预测模型研究[J]. 物流科技, 2009, 32(10): 11–13. FU Z Y, CHEN J. Research on emergency material demand forecast model in disaster[J]. Logistics Sci-Tech, 2009, 32(10): 11–13. DOI:10.3969/j.issn.1002-3100.2009.10.005(in Chinese)
[8]	ANAYA-ARENAS A M, RENAUD J, RUIZ A. Relief distribution networks:A systematic review[J]. Annals of Operations Research, 2014, 223(1): 53–79. DOI:10.1007/s10479-014-1581-y
[9]	?ZDAMAR L, ERTEM M A. Models, solutions and enabling technologies in humanitarian logistics[J]. European Journal of Operational Research, 2015, 244(1): 55–65. DOI:10.1016/j.ejor.2014.11.030
[10]	李创. 我国应急物流发展的主要问题与应对措施研究[J]. 物流科技, 2017, 40(3): 1–3. LI C. Study on the main problems and countermeasures of emergency logistics development in China[J]. Logistics Sci-Tech, 2017, 40(3): 1–3. (in Chinese)
[11]	高建国, 贾燕, 李保俊, 等. 国家救灾物资储备体系的历史和现状[J]. 国际地震动态, 2005(4): 5–12. GAO J G, JIA Y, LI B J, et al. The historical and present situation of the state reserve system of rescue goods and materials[J]. Recent Developments in World Seismology, 2005(4): 5–12. (in Chinese)
[12]	张红. 我国应急物资储备制度的完善[J]. 中国行政管理, 2009(3): 44–47. ZHANG H. Improvement of emergency materials reserves system in China[J]. Chinese Public Administration, 2009(3): 44–47. (in Chinese)
[13]	丁斌, 王鹏. 基于聚类分析的应急物资储备分类方法研究[J]. 北京理工大学学报(社会科学版), 2010, 12(4): 10–13. DING B, WANG P. A method of reserve classification on emergency materials based on clustering analysis[J]. Journal of Beijing Institute of Technology (Social Sciences Edition), 2010, 12(4): 10–13. (in Chinese)
[14]	邹铭, 李保俊, 王静爱, 等. 中国救灾物资代储点优化布局研究[J]. 自然灾害学报, 2004, 13(4): 135–139. ZOU M, LI B J, WANG J A, et al. Study on optimized distribution of storage spot of disaster relief materials in China[J]. Journal of Natural Disasters, 2004, 13(4): 135–139. (in Chinese)
[15]	张馨予. 救灾物资多级库存优化模型研究[J]. 物流技术, 2014, 33(4): 126–128. ZHANG X Y. Study on multi-echelon inventory optimization model in disaster relief material support[J]. Logistics Technology, 2014, 33(4): 126–128. (in Chinese)
[16]	SUN B Z, MA W M, ZHAO H Y. A fuzzy rough set approach to emergency material demand prediction over two universes[J]. Applied Mathematical Modelling, 2013, 37(10-11): 7062–7070. DOI:10.1016/j.apm.2013.02.008
[17]	DAY J M, MELNYK S A, LARSON P D, et al. Humanitarian and disaster relief supply chains:A matter of life and death[J]. Journal of Supply Chain Management, 2012, 48(2): 21–36. DOI:10.1111/jscm.2012.48.issue-2
[18]	CHEN Y W, JIANG D L, QI L, et al. The study on multi-base direct joint distribution of emergency relief materials in large-scale emergencies[J]. Revista de la Facultad de Ingeniería, 2016, 31(3): 187–197.
[19]	沈挺, 赵千川, 郑大钟. 一种库存控制策略[J]. 自动化学报, 1999, 25(3): 337–343. SHEN T, ZHAO Q C, ZHENG D Z. An inventory control policy[J]. Acta Automatica Sinica, 1999, 25(3): 337–343. (in Chinese)
[20]	缪成, 许维胜, 吴启迪. 大规模应急救援物资运输模型的构建与求解[J]. 系统工程, 2006, 24(11): 6–12. MIAO C, XU W S, WU Q D. A transportation modal and solution of large-scale emergency relief commodities[J]. Systems Engineering, 2006, 24(11): 6–12. DOI:10.3969/j.issn.1001-4098.2006.11.002(in Chinese)
[21]	刘春林, 何建敏, 施建军. 一类应急物资调度的优化模型研究[J]. 中国管理科学, 2001, 9(3): 29–36. LIU C L, HE J M, SHI J J. The study on optimal model for a kind of emergency material dispatch problem[J]. Chinese Journal of Management Science, 2001, 9(3): 29–36. (in Chinese)
[22]	刘北林, 马婷. 应急救灾物资紧急调度问题研究[J]. 哈尔滨商业大学学报(社会科学版), 2007(3): 3–5, 17. LIU B L, MA T. Research on the scheduling problem of emergency materials[J]. Journal of Harbin University of Commerce (Scial Science Edition), 2007(3): 3–5, 17. (in Chinese)
[23]	戴更新, 达庆利. 多资源组合应急调度问题的研究[J]. 系统工程理论与实践, 2000, 20(9): 52–55. DAI G X, DA Q L. The study of combinatorial scheduling problem in emergency systems[J]. Systems Engineering-Theory & Practice, 2000, 20(9): 52–55. (in Chinese)
[24]	HAN Y J, GUAN X H, SHI L Y. Optimization based method for supply location selection and routing in large-scale emergency material delivery[J]. IEEE Transactions on Automation Science and Engineering, 2011, 8(4): 683–693. DOI:10.1109/TASE.2011.2159838
[25]	计国君, 朱彩虹. 突发事件应急物流中资源配送优化问题研究[J]. 中国流通经济, 2007, 21(3): 18–21. JI G J, ZHU C H. Study on the distribution optimal problem in emergency logistics for emergency ecent[J]. China Business and Market, 2007, 21(3): 18–21. (in Chinese)
[26]	?ZDAMAR L, EKINCI E, KV?VKYAZICI B. Emergency logistics planning in natural disasters[J]. Annals of Operations Research, 2004, 129(1-4): 217–245. DOI:10.1023/B:ANOR.0000030690.27939.39