多出救点应急调度研究

王玲玲

（广西工学院 汽车工程系，广西 柳州 545006）

1 概述

近几年来，我国先后爆发了非典、禽流感、雪灾及地震等突发公共事件。面对时有发生的各类突发事件，积极开展应急物流调度研究，在短时间内高效地调集相关物资，并将其快速运送、及时发放，对于提高应急响应能力、减少灾害影响、降低生命财产损失具有重要的意义。应急物资大致可分为满足抢救需求、满足灾民生活需求、满足灾后初期重建需求等3类。应急物流是以提供应急物资为目的，以追求时间效益最大化和灾害损失最小化为目标的特殊物流活动。应急物流具有突发性、非常规性和不确定性等特点。目前，国内外对应急物流系统的研究主要有应急车辆数的配置[1]、应急资源调配[2]和应急配送车辆调度[3-8]等。

应急配送车辆的调度方案对提高应急物流服务水平有着重要的影响。在应急物流调度中受灾点数目不确定，各点的地理条件比较复杂，分布不均匀，应急物资需求存在差异，而且对时间都有一定的限制期限。在现有的研究成果中，针对单个出救点-多个受灾点问题，建立了以运输里程最短为目标函数的数学模型[5]，以及运输距离最短与车辆数最少的优化调度模型[6]；针对多个出救点-单个受灾点问题，建立了在应急时间最早的前提下出救点数目最少和限制期限时间内出救点最少的应急模型[7]，以及以应急出救点数最少、应急开始时间最早的两层优化数学模型[8]。上述模型大多都假设应急物流中心仓库存放的货物数量充足，或者默认其能够完全满足受灾点对物资的需求，而对于多个出救点-多个受灾点应急物流配送问题的研究较少。但是，在实际中可能会发生由于应急库存量不足，单个应急中心无法满足应急点货物需求数量的情况。

现结合实际情况，针对应急系统中多出救点-多受灾点、多种物资应急配送问题，建立模型使运输车辆数最少、总运输距离最短，最大程度地节省物流资源。按照受灾点物资需求量，对应急物资采用多种方式配送，分两阶段基于遗传算法求解调度方案，力求得到可操作的行车路线近似最优解。

2 建立模型

2.1 问题的假设条件

（1）物资的流向都是从应急物流中心流向受灾点，物资可以混装。

（2）应急物流中心有多个，储备的各类物资数量及配送车辆数一定。

（3）每辆车仅属于一个物流中心，完成任务后返回其所属应急物流中心。

（4）采用同一车型运输，车辆的容积和额定载重量一定。

（5）应急物流中心与各受灾地点的位置已知。

2.2 模型的数学描述

N＝(A，B，E，K，T，D)代表应急物流调度的网络模型。其中，A 代表应急物流中心节点集合{1,2,…，m}；B 代表受灾点节点集合{m+1，…，m+n }；E 代表网络的弧集合{(i，j)｜i，j∈C＝A∪B，i≠j }；K 表示各应急物流中心运输车辆集合{K1，…，Kp，…，Km}，其中Kp表示应急物流中心 p 的可用车辆数集合，k 表示应急运输车辆，且k∈Kp∈K；T 代表网络中各弧上运输时间集合{tij｜(i，j)∈E}；D 代表运输距离集合{dij｜(i，j)∈E }。

L 表示应急物资的种类集合{1，2，…，h}，l表示应急物资，且有l∈L；表示受灾点 j 对应急物资 l 的需求量；表示应急物流中心 i 对应急物资l 的供应量；W 表示运输车辆的额定装载量；Fl表示应急物资 l 的重量(体积)系数。

m 个应急物流中心将储备的应急物资向服务区域内的 n 个受灾点运送，所有物资在接到运输指令后 T 时间内必须送达，求满足运输需求的条件下，使运输成本最低、车辆数最少的配送方案。

为建立调度模型，将模型中涉及的二进制决策变量定义如下。

建立应急配送车辆调度的数学模型如下。

上述模型中，公式⑴表示目标函数为求最短应急运输距离；公式⑵表示目标函数为使用最少的运输车辆；约束条件⑶表示如果受灾点 j 由车辆 k 配送，则车辆 k 至少要访问受灾点 j 一次；约束条件⑷表示每个应急物流中心可用车辆数的限制；约束条件⑸表示每辆车装货不超过其额定载重；约束条件⑹表示车辆配送的物资总量不超过库存量；约束条件⑺表示每辆车运输时间不超过T，即所有货物都在时间 T 内送达；约束条件⑻表示车辆从所属应急物流中心出发返回该物流中心。

3 模型求解

该问题的求解主要包括以下3个方面。首先，划分各应急物流中心的配送范围，即确定每个应急物流中心需要配送的受灾点。其次，分配应急车辆的配送任务。最后，制定各车辆的运输线路，使行程最短。这样由 m 个应急物流中心与 n 个受灾点组成的应急运输调度方案，属于混合整数规划问题。随着规模的扩大，不仅模型解的搜索空间急剧扩大，而且需要两两比较解的运输距离及运输车辆数，所以目标函数计算过程比较复杂。针对模型的特点，设计两阶段算法如下。

第二阶段：对于物资需求量较小或有剩余物资的受灾点，采用分送式配送。用遗传算法求解获得分送式配送的应急调度方案。遗传算法的基本步骤如下[10]。

（1）确定表示可行解的染色体编码方法及搜索空间。

（2）确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则。

（3）设计遗传算子，确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。

（4）确定有关运行参数，包括群体规模N、交叉概率Pc、变异概率Pm和终止进化代数等。

4 实例分析

4.1 实例数据

柳州市7月连降大雨，河流沿线多处受灾，急需从柳南、柳北、鱼峰的3个应急物流中心调运储备的2类应急物资。2类物资的重量系数分别为F1＝0.2t/件，F2＝0.3t/件。对3个物流中心和19个受灾地点以城市应急物流指挥中心为原点，得到其相对坐标位置，对各物流中心和受灾点顺序编号。3个应急物流中心相关坐标及储备参数如表1所示，19个受灾点坐标及需求参数如表2所示。每个物流中心的车辆数均为8辆。要求所有物资在2h内必须送达，车辆平均速度为50km/h。运送车辆的载重量为10t。试制定一个应急调度方案，使参与运输车辆数最少，总行程最短。

表1 各应急物流中心坐标及储备参数

4.2 实例求解

计算应急配送网络中各受灾点间和应急物流中心间的距离dij。

4.2.1 第一阶段——直送调度方案

（2）寻找受灾点中符合条件1≥βj≥β 的点记为R1，采用整车直送配送。经过计算 Q5＝9.0t，Q7＝9.6t，Q16＝9.5t；由β5＝0.90，β7＝0.96，β16＝0.95可知，受灾点5、7、16符合此条件，采用整车直送。

（3）判断 βj＞1＞β 的受灾点记为R2，将该受灾点的物资总重表示为Qj＝QZj＋QSj。按照车辆额定载重将QZj采用整车直接运送，剩余物资QSj采用分送方式配送。算例中受灾点9、14、18超重，先采用整车直接运送部分物资到这些受灾点，剩余物资QS9＝0.5t，QS14＝5.5t，QS18＝4.2t，转入第二阶段配送。

（4）确定各直送受灾点对应的应急物流中心。若直送受灾点共有 R 个，则 R＝R1＋R2。对 R 个受灾点，依次寻找符合供给量和运输时间条件的最近应急物流中心。应用Dijkstra算法计算各直送受灾点与所服务的应急物流中心之间的最短路径。经计算，实例中应急物流中心1派1辆车为受灾点7配送，应急物流中心2派2辆车为受灾点5、18运送物资，应急物流中心3派3辆车为受灾点9、14、16运送物资。

4.2.2 第二阶段——分送调度方案

（1）染色体编码方式。结合模型，m 个应急物流中心 n 个受灾点中分送的受灾点为n－R1个。采用受灾点序号，以自然数进行编码，代码串的长度为m＋1＋n－R1。对于每个应急物流中心的配送点范围，顺序地用多个“0……0”隔开表示，即编码中有m＋1个“0”，其他数字为n－R1个受灾点的序号。主要考虑车辆的载重约束和线路运输时间约束，根据编码中受灾点序号的顺序，分配各应急物流中心的配送任务和车辆对受灾点的配送顺序。这种编码方式线路内是有序的，若交换其中任何两个位置，都会使配送的范围和顺序发生改变，从而使目标函数值发生改变。实例中3个应急物流中心、19个受灾点中采用分送的有16个点，因此染色体长度为20。初始种群随机生成，例如(0，4，6，8，9，10，0，11，12，13，14，15，0，17，18，19，20，21，22，0)表示物流中心1为受灾点4、6、8、9、10配送，物流中心2为受灾点11、12、13、14、15配送，物流中心3为受灾点17、18、19、20、21、22配送。

表2 各受灾点坐标及需求参数

（2）约束条件的处理。采用罚函数的方法来处理约束条件，以确保那些符合约束条件而较优的个体有较大的生存机会。把各种约束条件加入目标函数中得到公式⑼。

（3）适应度函数。该目标函数是极小值问题，公式⑼表明如果应急物流中心与受灾点之间运输时间或需求量不满足，则赋予其一个很大的 M 值。该过程已经包括判断各种节点组合的运输车辆的时间约束与载重约束条件，所以该函数可以很好地代替各染色体的适应度。设Vg为染色体，Fg为染色体Vg对应的适应度。Z′为群体中最好染色体的目标值(按公式⑼计算得到的目标函数值)，Zg为染色体Vg对应的目标值。由于Z值是非负，适应度函数表示为：Fg＝Z′/Zg。经过处理，染色体越优对应的适应度值越大。

表3 应急调度方案

（4）采用随机取值的方法，在解空间里随机取C个个体作为初始群体。

（5）遗传算子。①选择算子。采用指数排序选择方法，其基本思想是将染色体根据其适应值大小从好到坏排序，按照它们在顺序中的位置而不是原适应值指定选择概率。与常用的转轮式选择相比可使染色体之间保持合理的差距。设群体大小为N，q 表示最好染色体的选择概率，r 为染色体在排序中的位置，最好染色体的序数为1；种群中排在第 r 位的染色体选择概率 Pr为：Pr＝q′(1－q)r-1。式中：r＝1，2，…，N；q′＝q/{1－(1－q)N}。②交叉算子。采用部分匹配交叉算子。变异算子：采用连续多次对换作为变异算子。

（6）运行参数。取群体规模50、Pc交叉概率0.55、Pm变异概率0.006、终止进化代数取500。

（7）终止条件。①若算法迭代到第500代，算法终止；②若有连续10代最佳染色体相同，算法终止。

运用 C 语言编制程序实现上述算法。经过计算机运算得到最优解：最小运输距离为378km；车辆数为12辆。对应染色体个体为(0，13，17，8，19，6，20，0，10，12，15，21，18，0，4，11，9，22，14，0)。

采用两阶段启发式算法得到最优应急调度方案，如表3所示。

5 结束语

在分析应急配送车辆调度问题特点的基础上，建立双目标数学模型，考虑运输车辆载重和运输时间的限制，将受灾点物资需求数量与应急物流中心储备的物资数量作为应急调度的影响因素对问题进行求解。根据受灾点的物资需求量大小，将受灾点按配送方式分为整车直送和分送两类：对于整车直送受灾点，找到符合条件的最近应急物流中心，并求解出最短路径即可确定直送调度方案；对于分送配送受灾点，采用遗传算法求解分送调度方案。最后运用 C 语言编制程序完成模型的求解。

：

[1]刘 杨，马 立，云美萍，等. 基于随机过程的城市应急车辆数量配置模型[J]. 中国安全科学学报，2008，18(5)：46-48.

[2]记国君，朱彩虹. 突发事件应急物流中资源配送优化问题研究[J]. 中国流通经济，2007，21(3)：18-21.

[3] 唐伟勤，张 敏，张 隐. 大规模突发事件应急物资调度的过程模型[J]. 中国安全科学学报，2009，19(1)：33-37.

[4]Ozdamar L. Emergency logistics planning in natural disasters[J]. Annals of Operation Research，2004，129(3)：218-219.

[5]陈明华，李迎秋，罗耀琪. 应急物流车辆调配问题的研究[J]. 计算机工程与应用，2009，45(24)：194-197，245.

[6]张裕华，潘 郁. 基于蚁群算法的应急物流配送车辆调度研究[J]. 物流科技，2009，32(5)：47-50.

[7]刘春林，何建敏，施建军. 一类应急物资调度的优化模型研究[J]. 中国管理科学，2001，9(3)：29-36.

[8]李连宏，王永军，李俊峰，等. 多资源非恒定消耗应急调度优化模型研究[J]. 北京理工大学学报，2006，26(z1)：157-160.

[9]胡运权. 运筹学教程[M]. 北京：清华大学出版社，1998.

[10]陈国良，王煦法，庄镇泉，等. 遗传算法及其应用[M]. 北京：人民邮电出版社，2001.