应急物流多设施动态选址模型构建及检验

引言

应急物流是指以提供重大自然灾害、突发性公共卫生事件及公共安全事件等突发性事件所需应急物资为目的，以追求时间效益最大化和灾害损失最小化为目标的特种物流活动（欧忠文、王会云等，2004）。应急物流选址问题是应急物流系统中的关键问题，它不仅关系到能否快速高效地调度应急物资，同时也决定着能否有效减轻灾害损失。

近年来不少学者对应急物流设施选址问题进行了研究：方磊等（2003、2005、2006）比较深入地研究了应急系统优化选址模型及算法；Wei Yi等（2007）建深圳到运城物流立了以人员伤亡最小化为目标的自然灾害应急物资配送中心选址模型；杨锋、梁等（2008）运用DEA对多设施选址问题进行了研究；M.E.Bruni（2009）建立了在紧急状况下快速决定设施选址的概率模型并提出一种适合启发式算法；贺小容、秦江涛（2010）建立了基于P-中值问题的应急物流多层级选址模型；刘洪娟等（2010）在考虑道路特性的基础上，建立了物流多设施选址模型；殷代君、郭宏正（2011）在考虑设施的处理能力的基础上，建立了应急设施选址的双汕头到运城物流目标规划模型。以上文献建立的模型都是静态模型，并没有考虑到物资的需求量和道路的状况等信息是动态变化的，应急物资的调度问题是一个动态决策的过程。

突发性事件发生后，紧急救援是第一目的，应急物资是否有效配送的关键是如何在最短的时间内将应急救援物资送达灾区。因此，应急物资运达总时间最短是首要考虑的目标。本文在考虑应急物资需求量和道路状况信息变动的基础上，建立一个以应急物资到达需求点的总时间最短为目标的应急物流多设施动态选址模型。

模型构建

（一）问题描述

突发性事件发生后，需要在灾区建立一定数量和规模的应急物流设施，将应急物资及时准确地送到需求点。应急物资的需求量信息和道路状况信息在整个救援过程中是动态变化的，应急救援指挥中心需要根据当前获知的信息不断更新决策。决策面对的问题是：如何在设施容量限制的条件下，根据动态信息选择建立若干个应急物流设施，使得应急物资从应急物流设施到达需求点的总时间最短。

（二）模型假设

模型建立前作如下假设：

第一，各应急物流设施的容量有限。

第二，道路的状况以及各个应急物资需求点的需求量由灾区及时反馈。

第三，车辆的平均车速由道路设计的最大安全速度决定。

第四，应急物流设施一旦建立，在整个救援过程中不能关闭。

（三）符号说明

T={t|t=t1，t2，…，tN}表示道路状况和需求量等信息发生变动的时刻的集合；

S={g|g=1，2，…，n}表示应急物流设施候选点的集合；

Qgt表示t时刻应急物流设施的容量；

R={h|h=1，2，…，m}表示潜在的应急物资需求点的集合；

qht表示t时刻潜在的应急物资需求点的需求量；

D=S∪R表示所有节点的集合，i，j∈P；

Vk表示救援车辆的平均行驶速度；

αijt∈{0，1}表示t时刻道路的实际连接状况。αijt =1表示节点i与节点j之间存在连接的道路，αijt =0表示节点i与节点j之间不存在连接的道路或连接的道路已遭破坏不能通行；

表示t时刻节点i到节点j的距离。（xi，yi）表示节点i的坐标，（xj，yj）表示节点j的坐标，β表示道路的迂回因子；

rijt表示t时刻节点i与节点j之间的实际道路状况对救援车辆行驶速度的平均影响因子，0

（四）模型的建立

建立动态选址模型：

（1）

（2）

（3）

（4）

目标函数（1）是应急物流设施点到应急物资需求点的总时间最短；约束条件（2）表示应急物流设施的最大容量；约束条件（3）表示只有应急物流设施建成时才能给需求点进行物资配送；约束条件（4）为非负约束。

模型求解

在整个救援过程中，应急物资的需求量信息和道路状况信息不断变化，本文先利用动态规划算法把动态模型转化为多阶段的静态模型，再采用单亲遗传算法对静态模型进行逐一求解。算法的具体步骤如下：

第一，参数设定。设pop_size为种群规模，tM为最大迭代次数，Pc为基因重组概率，Pm为变异概率。

第二，编码方式。采用序号编码方式，编码位串的长度为应急物资需求点的个数，基因的数值为应急物流设施的编号，基因的位置为应急物资需求点的编号。例如有3个应急物流设施，6个应急物资需求点，染色体{1，3，3，2，1，1}就表示应急物流设施1给需求点1、5、6配送应急物资，设施2给需求点4配送物资，设施3给需求点2、3配送物资。

第三，生成初始种群。单亲遗传算法不要求初始种群具有广泛多样性，所以在满足编码方式的前提下，随机均匀产生pop_size条染色体，构成初始种群。

第四，适应度函数。采用fi=1/Z（i）作为适应度函数。为了满足应急物流设施容量限制的约束条件，对不满足约束条件的染色体的目标函数值乘上一个惩罚系数。

第五，选择操作。采用改进的比例选择算子实现选择。将每代群体中的染色体按照适应度排序，将适应度最大的染色体直接复制进入到下一代群体中。下一代群体中剩下的染色体按照比例选择算子进行选择。引入最优保持操作，可以使得算法在全局上收敛。 第六，基因重组。采用多点基因换位算子实现基因重组。先确定一个正整数Ue，再取随机数r（1≤r≤Ue），按照一定的概率Pc交换一条染色体中的r对位置的基因。比较重组后的染色体和父代染色体，按照优胜劣汰规则，选择性能优者进入种群。

第七，变异操作。采用单点基因突变算子实现基因变异。随机选择一条染色体上的某个位置上的基因，按照一定的概率Pm，用其同序基因集中的其他值作为该位置基因的数值。比较变异后的染色体和父代染色体，按照优胜劣汰规则，选择性能优者进入种群。

第八，停机条件。若进化代数t达到了预先规定的迭代次数tM，即t≥tM，则终止运算，并输出最优染色体和最优解，否则跳转步骤四。

算例分析

当需求量信息和道路状况信息发生变动时，决策者需要根据当前获知的最新信息调整决策，使方案符合当前应急物资配送的要求。本文对道路状况信息发生变化和道路状况、需求量信息同时发生变化这两种情况进行算例分析。在（0，0）到（50，50）公里范围内，随机产生20个应急物资需求点，5个应急物流设施备选点，αijt随机赋值为0或1；rijt随机赋值为0到1的非负实数；β=1.4；Vk=80km/h。各需求点的位置和各个时刻的需求量见表1；各应急物流设施的位置、容量见表2。

设置种群规模pop_size=200，最大迭代次数tM=500，基因重组概率Pc=0.7，基因变异概率Pm=0.04。按照求解的具体步骤，在电脑汕头到益阳物流上通过MATLAB编程对算例进行求解，平均运行时间34.5699s，各个阶段（t0初始阶段；t1道路状况信息发生变化；t2道路状况和需求量信息同时发生变化）的设施选址决策结果如表3所示。图1是t0阶段单亲遗传算法种群解和种群均值的变化轨迹，从图中可以看出，种群解在200代后趋于某一值，表明算法迅速收敛。

算例分析结果表明：单亲遗传算法具有较高的运算效率，且能得出较好的解。因此，本文提出的动态模型和算法能够满足突发性事件发生后设施选址的实时动态决策要求。