震后初期应急物资配送的多目标混合—联运问题

沈晓冰　杨保华

摘要：针对震后应急物流系统优化问题，以所有受灾点的物资需求未满足量最小以及送达时间最短作为目标，建立了一个带中转设施的双层混合联运多目标优化模型，并根据所建模型的特点，设计了一种基于矩阵编码的混合遗传算法进行求解。最后，以青海玉树地震为例，验证了该模型和算法的可行性。

Abstract： In response to the post-earthquake emergency logistics system optimization problems， a multi-objective optimization model of the bi-level mixed transport facilities with transshipment facilities is established. The goal is to minimize the relief delivery time and the total loss. Then a hybrid genetic algorithm based on sub stage decoding method is designed according to the characteristics of the model. Finally， the validity of the model and algorithm are demonstrated by a numerical example derived from Yushu earthquake. The results show that the proposed genetic algorithm has good performance.

关键词：震后；应急物资；双层混合联运；混合遗传算法

Key words： post-earthquake；relief；bi-level programming and mixed transportation；hybrid genetic algorithm

中图分类号：U291 文献标识码：A 文章编号：1006-4311（2016）30-0022-03

0 引言

地震是一种突发性自然灾害，短时间内损伤巨大，优化震后应急资源的配置对以提高救援效率。近几年来，不少学者开始关注震后应急物资配送问题。Viswanath[1]设计了一个救援运输费用最小化和关键路径覆盖灾区最大化的多目标规划；Haghani et al.[2]基于路径—分配问题，构建了含时间窗的确定型网络流模型；？魻zdamar et al[3]考虑到应急时间的动态性，构建了车辆路径和物资网络流的集成优化模型。然而，目前大部分研究要么只针对定位分配问题[1，4]，要么只考虑调度问题[2，3]，而在实际救援中，这两个问题并不是孤立存在的，有必要对这两个问题进行集成优化与管理[5-9]。以上文献大多假设应急物资的供应量大于需求量，采用单层配送，忽略了震后初期应急物资供不应求及物资分配时间有限。本文针对上述已有工作的分析，建立了一个带双层混合联运多目标优化模型，上层物资运输量较大，采用航空、铁路、直升机和公路4种配送方式，而下层仅需公路、直升机运输，各运输方式均有运力限制，可多次往返运输；其中公路和直升机有一定的数量限制，航空和铁路定点间隔运输，并对其进行混装，提高满载率；对紧迫性要求高的物资进行优先配送。

1 模型构建

1.1 符号说明

式（1）为最小化未满足物资带来的相对损失：灾民的损失与物资未满足量为凸函数关系[11]，其中β为灾情指数，β？叟1；式（2）为应急救援时间最短。式（3）为供应点公路和直升机的数量约束；式（4）为中转站公路和直升机的数量限制；式（5）为供应点自身的物资流守恒；式（6）为供应点到受灾点的物资流守恒；式（7）为应急物资供不应求；式（8）为上层运输工具重量和体积的单次运力限制；式（9）为下层运输工具重量和体积的单次运力限制；式（10）为m将物资c从供应点i运输至中转站j的时间；式（11）为m将物资c从中转站j运输至受灾点k的时间；式（12）为只有中转站开启时，上下层才有物资流；式（13）为0-1变量、非负和整数约束。

2 求解算法

本文所建模型比较复杂，因此选用基于矩阵编码的遗传算法进行求解，收敛性好、计算时间短。

2.1 染色体编码

第一阶段Part1.k.c.n为受灾点k接收到n单位的c物资。该基因位的取值为随机正整数，且保证受灾点各类物资的和为 Sic。第二阶段Part2.k.j.c.m.n为由中转站j采用n辆/架m类运输工具运c物资至受灾点k。先随机生成中转站选址，再对运输工具数量生成随机矩阵并对其进行归一化处理使其满足约束（4）。第三阶段Part3.j.c.i.m.n为由供应中心i运输c物资到中转站j采用m类运输工具的数量为n。对于运输工具数量，先生成随机矩阵，然后对车辆、直升机数量进行归一化处理使其满足约束（3）。

2.2 初始化种群和适应度计算

采用线性加权评价函数转化为单目标，然后用标准化法对其进行无量纲处理，继而得到适应度函数。

2.3 遗传操作

染色体第一段利用随机基因位交叉，第二、三段采用矩阵交叉法且三段均采用随机基因位加减法变异。

2.4 终止条件

算法迭代到终止迭代次数时结束。

3 算例分析

以玉树地震为例，取西宁火车站、曹家堡机场2个供应点，编号为1、2，分别提供帐篷18000、37000单位，食品470000、600000单位，车辆190、120辆；震中地势险峻，离供应点较远，不适合铁路、直升机运输；取玉树、治多、称多3个中转站，编号为1、2、3，分别提供车辆数65、73、55辆，直升机14、4、5架；各受灾点的物资需求情况如表1所示。

设popsize=1000，maxite=300，λ=0.5，交叉、变异概率分别为0.7、0.01，运行的两目标函数为：minT=1028704，minA=337426，计算结果如表2、表3所示。

由表2知，上层运输中只有中转站1玉树采用了航空运输，因为灾区仅有巴塘一处机场，而其他地区没有机场，只能被限制为车辆运输。由收敛图1可知，该算法收敛较好且运行效率较高。

4 结束语

为提高震后应急救援效率，以应急物资短缺和时间的紧迫性为基础，建立了一个双层混合联运模型，并设计了一种基于分阶段解码的混合遗传算法求解。但是随着时间的推移，一些基础设施逐渐恢复，可以对应急物资配送的动态优化作进一步研究。

参考文献：

[1]Viswanath K， Peeta S. The multicommodity maximal covering network design problem[C]// The IEEE， International Conference on Intelligent Transportation Systems， 2002. Proceedings. 2002：505-510.

[2]Haghani A， Oh S C. Formulation and solution of a multi-commodity， multi-modal network flow model for disaster relief operations[J]. Transportation Research Part A Policy & Practice， 1996， 30（3）：231-250.

[3]？魻zdamar L， Ekinci E， Kü ükyazici B. Emergency Logistics Planning in Natural Disasters[J]. Annals of Operations Research， 2004， 129（1-4）：217-245.

[4]Tavakoli A， Lightner C. Implementing a mathematical model for locating EMS vehicles in fayetteville， NC[J]. Computers & Operations Research， 2004， 31（9）：1549-1563.

[5]文仁强，钟少波，袁宏永，等.应急资源多目标优化调度模型与多蚁群优化算法研究[J].计算机研究与发展，2013，50（7）：1464-1472.

[6]Rath S， Gutjahr W J. A math-heuristic for the warehouse location-routing problem in disaster relief[J]. Computers & Operations Research， 2014， 42（2）：25-39.

[7]马祖军，代颖，李双琳.带限制期的震后应急物资配送模糊多目标开放式定位-路径问题[J].系统管理学报，2014（5）：658-667.

[8]Yi W， Kumar A. Ant colony optimization for disaster relief operations[J]. Transportation Research Part E Logistics & Transportation Review， 2007， 43（6）：660-672.

[9]郑斌，马祖军，李双琳.基于双层规划的震后初期应急物流系统优化[J].系统工程学报，2014，29（1）.

[10]苏幼坡.城市生命线系统震后恢复过程优化的研究[D].天津大学，2001.

[11]葛洪磊，刘南，张国川，等.基于受灾人员损失的多受灾点、多商品应急物资分配模型[J].系统管理学报，2010，19（5）：541-545.