自然灾害发生后交通状况恶化，需要根据运输车辆特点向灾区运输灾民所需的各种救灾物资，确保供给灾民人数最大化。国内外学者在救灾物流领域开展了大量研究工作。

谢如鹤等^[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中：

$ {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所示。

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

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

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

下面分析求解方法的时间复杂度。采用分支定界法求解整数规划模型，每次分支需要求解两个线性规划模型。第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 结论

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