摘要：在应急物流中，合理的车辆调度优化可以极大地节约物流成本。本文结合实际情况，对应急物流车辆调度问题的特点进行了分析，构建了一般性非满载应急物流车辆调度优化的数学模型，并采用智能优化算法中的遗传算法该问题进行求解。仿真结果表明，该算法是可行和有效的。
关键词：应急物流；车辆配送；遗传算法
1 引言
近年来，自然灾害和人为灾害頻发，造成了巨大的人员伤亡和财产损失。如2003年的SARS造成经济损失176亿美元，2008年的汶川大地震8451亿人民币，2011年的日本海啸和核污染事件的经济损失更达到了1000亿美元以上。在这些损失中，由于应急物流造成的损失约占总损失的15%至20%。[1]
应急物流是以提供应急物资为目的，以追求时间效益最大化和灾害损失最小化为目标的特殊物流活动，具有突发性、非常规性和不确定性、时间约束紧迫性等特点。[2]目前国内外对应急物流系统的研究主要有应急车辆书的配置[3]、应急资源调配[4]和应急配送车辆调度 [5]。
针对应急物流车辆调配问题的研究，国外起步于上世纪90年代。而在我国从2006年底，经国资委、民政部批准全国第一个从事应急物流的专业组织——中国物流与采购联合会应急物流专业委员会成立之后，关于应急物流中的车辆调配问题的研究逐步展开。我国幅员辽阔，每年突发灾害都较多，目前系统地、定量地对我国灾害救助应急物流配送车辆调度优化模型基本没有进行研究，对突 发性事件的决策还存在着应对迟缓、缺少科学依据等问题。因此，本文所研究的问题具有重要的现实意义。
2 模型描述
使用图G(V,E)描述物资储备中心和受灾点的交通情况，其中V为所有的节点的集合（包括物资储备中心节点、受灾点和其他相关节点），V0∈V为物资储备中心；E为图所有边的集合，eij∈E表示节点Vi，Vj之间的边。G为无向图，即边eij是无方向的。有n个受灾地区向救灾指挥中心请求救灾物资的配送，第i个受灾节点对于救灾物资的需求量为gi，卸货时间为UTi，最迟允许车辆到达时间为LTi，物资储备中心与受灾节点、受灾节点之间的广义运输（距离）费用为cij，运输时间为tij（i，j=0，1，2，…，n，物资储备中心编号为0，受灾节点编号为1，2，…，n），配送卡车单车装载容量为q（q>gi，i=1，2，…，n）。
把物资储备中心和受灾节点统一看作是运输网络中的节点。设在同一线路上点h是点i前面的相邻点，车辆到达点h的时间为RTh，到达点i的时间为RTi，则有：
模型中，ctj表示为从点i到点j的运输成本，它的定义可以是距离、费用、时间等，一般根据实际情况确定，可同时考虑车辆数和运行费用，如下确定：
其中，c1为相对于运行时间的费用系数；c0为车辆的固定费用，即增加一辆车的边际费用。一般认为，派出一辆车的固定费用远远高于车辆行驶费用，因此该模型是在极小化车辆数的前提下，在极小化运行费用。减小c0的值将会使使用的车辆数增多，而线路长度缩短。若令C1=0，C0>0，则模型目标是使用的车辆数最少。
在数学模型中，目标函数(2)表示总运输里程（费用）最低，约束条件(3)表示任一台单车装载量不允许超过车辆容量约束，约束条件(4)救灾物资送到各个需求节点的时间必须在时间窗范围内，约束条件(5)表示任何一个受灾地区需求节点只有1台车停靠卸货，约束条件(6)表示车辆k只驶入分配给其运输任务的客户，约束条件(7)表示车辆k只驶出分配给其运输任务的需求节点，约束条件(8)表示车辆k的线路必须是连通的。
3 应用遗传算法对问题求解
由于车辆调配问题已经被证明为NP-H问题[6]，本文将采用智能优化算法中的遗传算法，对问题进行求解。对于遗传算法的描述如下。
3.1 解的编码和初始解构造
3.1.1 编码原则
本文中染色体采用简单直观的自然数编码（序数编码），用0表示物资储备中心，用1，2，…，n表示各节点。例如：染色体021035406780表示行驶线路：
子线路1：物资储备中心0→节点2→节点1→物资储备中心0
子线路2：物资储备中心0→节点3→节点5→节点4→物资储备中心0
子线路3：物资储备中心0→节点6→节点7→节点8→物资储备中心0
染色体中的每个子路线称为一个基因，则示例染色体中包含了3个基因，分别是,0210,03540和06780；每个基因以0开始，以0结束，表示子路线从物资中心出发，回到物资中心。
在本文的编码方式中，基因中的每个子基因位是有序的，即若表示子线路的基因中相邻两位互换位置，会使目标函数值改变；而子线路之间是无序的，若表示子线路的基因互换位置不会改变目标函数值。
3.1.2 初始解构造算法
基于3.1.1节中解的编码方式，采用如下算法构造遗传算法的初始解。
步骤1：判断是否所有受灾节点都访问到，是则转步骤:3；
步骤2：随机选择一个受灾节点添加到染色体中，转步骤1；
步骤3：判断可用车辆数m的值是否大于0，如果是，则转步骤4；否则转步骤5；
步骤4：随机选择染色体中的一个位置插入0，m--，转步骤3；
步骤5：则染色体构造完毕。
采用上述的构造方法，可能得到连续的0，则表明该方案中有空闲的车辆。
3.2 初始种群的构造
初始抗体群是按照上面3.1节中编码原则随机生成的。抗体群的规模 定义为抗体群中抗体的个数，它是影响算法性能的一个重要的因素。按经验N一般定义在20-100之间，同时取网络中节点个数的2倍左右作为抗体群规模，如网络中节点个数为V时，抗体群的规模为Vx 2。按照上述的编码方式，随机产生N个编码长度为l的抗体，l=任务节点数+车辆数+1。
3.3 适应度函数
适应度函数用来描述解的优化程度，适应度函数的值越小，解就越优化。本文的适应度函数公式如下：
上式的第二项和第三项表示对违反车辆载重约束和时间约束的解给予惩罚，M取比较大的正数（如果允许晚到即软时间窗，可以把M定义为一个合适的值）。
3.4遗传算子
3.4.1 交叉算子
对换算子采用单点交叉，交叉后可能出现某一个或者几个城市重复通过，而某些城市却没有走到的情况，即交叉后的染色体不合法。对于不合法的新染色体，采用3.1.2节中的算法重新生成新的染色体替换。
3.4.2 变异算子
本文采用单点基因变异的变异算子，即随机选取染色体中的一个基因（对应一条子路线），将子路线中的节点重新排序得到新的染色体。则对于染色体021035406780，选取第2个基因位进行变异后得到的一个可能的结果是021054306780。
3.4.3 选择算子
本文中将染色体的适应度值取倒数后，采用轮盘赌法对种群中的染色体执行选择操作，以使得适应度小的染色体对应较小的选择概率。
3.5 算法停止条件
设置最大不进化代数 ，如果每代染色体的最小适应度经过 代仍没有进化，则算法停止。
3.6 对算法的改进
算法中使用了精英保留策略，设置安全阀，保存每代的最优染色体，使其不经过交叉和变异直接进入下一代。
4 仿真研究与讨论
作者编写了遗传算法的程序，按照上述步骤对算例进行了求解，编程环境： Windows XP + Visual Studio；计算机硬件：CPU主頻2.4G，内存2G。
遗传算法的参数为：染色体数量N=20；编码长度l=12；交叉概率pc=0.6；变异概率pm=0.15。程序执行结果随最大不进化代数 变化情况如表1所示（表1中结果为程序执行50次的平均值）。
从以上结果可以看出，①遗传算法可以从大量的不可行解中有效地找到可行解；②遗传算法搜索到最优解的概率较大，最大不进化代数设置越大，算法的解与最优解越接近；③遗传算法的平均运算结果较优，平均结果比最优解大5.3%，并且当最大不进化代数达到100时，算法的平均结果仅比最优解大0.3%。
5 结论
我国属于自然灾害頻发的国家，每年为救灾所进行的物流活动花费了大量的社会财富，使用合理的配送算法可用有效地节约物流成本，并且能够保障物资的即时送达。
本文主要所研究的是应急物流过程的最后一个阶段——应急物资配送的车辆调度优化问题。本文以应急物流配送环境下的应急物资配送为运用背景，在对车辆调度算法进行研究的基础上，结合应急物资配送的实际特点，建立了数学模型，并在此基础上运用遗传算法进行求解，结果证明遗传算法应用于该问题有较好的收敛性和全局搜索性。
6 下一步研究方向
本文的应急物流车辆调配算法是基于一个物资中心的情况进行的，并且物资运输的方式也是单一的。在较大的灾害中，对于多个物资中心、运用多种运输方式进行全局的统筹管理，将会更加有助于物资的即时送达和总体成本的控制。
因此，在后续的工作中，将把研究重点放在对多中心点的物资调配问题，以及多交通工具的统筹调配问题的研究上。
