基于免疫粒子群算法的应急物流配送车辆调度研究_粒子群算法论文

基于免疫粒子群算法的应急物流配送车辆调度研究，本文主要内容关键词为：粒子论文,算法论文,免疫论文,物流配送论文,车辆论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。

       文章编号：1002-3100(2014)11-0001-04

       近年来，地震、泥石流、旱涝等自然灾害的频频发生，造成了巨大的人员伤亡和财产损失。在目前的科技水平下，这些自然灾害事件是不可避免的，所造成的损失也是无法估量的[1-2]。因此自然灾害发生时，科学合理的资源配置能对应急救援起到事半功倍的作用，然而应急物流配送车辆调度优化就是其中的关键环节，越来越多的人认识到应急物流配送车辆调度优化问题的重要性。

       应急物流与普通物流相比，有很多相同的地方，不过也存在很多不同的地方，节约成本是普通物流主要考虑的因素，然而应急物流配送过程中要受到严格的时间约束，因此应急物流更体现了应急服务的时效性。目前国内外对应急物流系统的研究主要有应急车辆的配置、应急资源调配和应急配送车辆调度，在应急物流配送车辆调度模型以及算法上都有了一定的研究，Eqi等人建立以运输成本最小为目标的调度模型[3]，宋远清等在研究了需求随机的车辆调度模型，但是没有考虑运输成本和运输时间[4]；石玉峰等建立了最短运输时间和最小运输费用的多目标组合优化调度模型[5]；文仁强等通过蚁群算法对应急物资配送车辆调度优化问题进行了求解[6]；张裕华等在带有时间窗的基础上考虑运输费用与距离构建应急物流配送车辆调度模型，并运用了蚁群算法进行求解[7]；陈明华建立了一般性非满载应急物流车辆调度模型，采用人工免疫算法进行了求解[8]。综上所述，在车辆调度问题中多注重时间方面的及时性，忽略了应急运输车辆的体积和载重对配送调度的影响以及应急配送车辆资源的有限性，通过本文的研究，建立更符合实际的多目标应急配送车辆调度优化模型，运用针对该模型的混合算法求解模型得到的结果可以作为救灾指挥中心制定车辆调配方案科学决策的依据。因此，本文所研究的问题具有重要的现实意义。

       1 模型构建

       1.1 模型的问题假设

       (1)所有受灾点在物资数量方面和运输时间方面的需求都能够得到满足，同时单个需求节点的需求量小于单车最大荷载；(2)同种车型运输，车辆的额定载重量和车辆的容积一定；(3)各受灾点均在救灾点的配送范围之内，运输到受灾点的时间不超过最迟到达时间；(4)路网为完全网络，即所有节点之间都有线路连通；(5)救灾点与各受灾点、各受灾点之间的运输距离作为已知量；(6)每辆车完成配送任务后回到配送中心。

       1.2 模型的数学描述

       有n个受灾地区向救灾指挥中心请求救灾物资的配送，第i个受灾节点对于救灾物资的需求量为

(i≠0)，救灾中心与各受灾节点、各受灾节点之间的广义运输距离为

，运输时间为

(i，j=0，1，2，…，n，配送中心编号为0，受灾节点编号为1，2，…，n)；卸货时间为

，最迟允许车辆到达时间为

；G是一系列需要应急服务的受灾点集合；K表示应急运输车辆集合；

，分别表示受灾点i应急物资的体积和重量；V和Q分别表示运输车辆额定体积载重；可用车辆数为k；车辆不能超载且必须在规定时间之前把物资送到受灾节点。要求指派运输车辆，并确定每辆车运输路线，使得总运输距离最低，并且使运输车辆最少。

       把应急配送中心即救灾点和受灾节点统一看做是运输网络中的节点。设在同一线路上点i是点j前面的相邻点，车辆到达点i的时间为

，到达j点的时间为

。

       将模型中所涉及的二进制变量定义如下：

      

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

       目标函数：

      

       上述模型中，式(1)表示目标函数为求最短的应急运输距离；式(2)表示目标函数为使用最少的运输车辆数；式(3)表示每辆车装货不超过其额定容积；式(4)表示车辆装货不超过其额定载重；式(5)表示救灾物资送到各个受灾节点的时间必须在规定的时间窗范围内；式(6)表示每一个受灾地区节点仅由一辆车提供卸载救灾服务；式(7)、(8)表示车辆k应离开已经驶入过的受灾节点，并且只停靠于分配给其运输任务的受灾点；式(9)中表示，如果车辆k有货物，则该车执行任务，此时目标函数(2)增加1。

       2 免疫粒子群算法求解

       粒子群优化算法(Particle Swarm Optimization，PSO)是一种基于粒子群算法(PSO)同遗传算法类似，是一种基于迭代的优化工具，一种基于群体的随机优化技术。它是Kennedy和Eberhart于1995年提出的一种新的进化计算方法，它源于鸟群和鱼群群体觅食运动行为研究结果的启发[9-10]。

       在PSO算法中有两个主要的操作，其中一个操作是利用适应性函数来计算适应值，并且依照适应值的比较结果来决定是否更新每个粒子本身的最佳经验(pBest)以及所有粒子群体的最佳解(gBest)。第二个操作为每一个粒子的位置转移，首先每个粒子会根据公式(10)计算出新的速度，然后根据此新的速度依照公式(11)产生出新的位置：

      

       其中向量

代表一个粒子；向量

代表粒子的速度；r(0，1)是在范围[0，1]内的随机数；

是加权系数，惰性系数

代表粒子相信自己的程度，社会学习系数

代表粒子相信经验的程度，社会认知系数

代表粒子相信周围个体的程度。

       生物免疫系统是一个分布式、自组织和具有动态平衡力的适应性复杂系统。它面对外界入侵的抗原，能够产生相应的抗体，其抗体上有特定的物质，可以结合或消除抗原，以维持免疫平衡。这样的免疫原理可以应用到许多现有的智能信息处理的技术中，构成了许多更加有效的智能方法，如免疫神经网络，免疫遗传算法等。

       在本文中我们将免疫机理和粒子群算法结合，构造了一个启发式的免疫粒子群算法。在免疫粒子群算法中，定义抗体用来表示对问题的候选解，定义抗原代表问题及其约束。具有免疫优势的抗体即为当前抗体种群中的有效解或非劣最优解[11]。在本文算法中，对于车辆k、n个受灾点的车辆分配，首先将个体编码为一个

大小的矩阵，用粒子

来进行表示。求解该应急物流配送中的车辆调度问题的免疫粒子群算法步骤如下：

       步骤一：初始化具有V个个体的粒子群。

       步骤二：计算每个粒子的适应度函数(取式目标函数的倒数)，选择适应度函数最大的个体。

       步骤三：判断是否满足停机条件，满足条件退出，不满足条件则继续。

       步骤四：按照公式(11)、(12)计算粒子新的位置，取符号变为二进制的0，1。

       步骤五：检查个体的7个约束是否满足，满足约束的粒子保留。

       步骤六：对不满足约束的个体注射疫苗：对个体按照对问题的先验知识修改个体位置，执行注射疫苗的操作，对群体中注射了疫苗的粒子进行免疫检测，满足条件的保留。

       步骤七：转到步骤二。

       免疫粒子群算法的流程如图1所示。

       3 实例分析

       为考察上述模型和算法的有效性，选用某地区所测算的原始数据为依据进行分析。具体描述如下：

       某地区发生自然灾害，所在地区的救灾物资储备中心需要向8个受灾节点进行救灾物资配送。受灾节点i(i=1，2，…，8)的需求量为g[，i]，卸货时间为UT[，i]，物资最晚送到时间为LT[，i]，装载容量为8吨，运送车辆的容积为18m[3]，车速为60公里/小时。车辆不能超载且必须在规定时间之前把物资送到受灾节点。各节点的物资需求量及物资储备中心与各需求点之间、各需求点相互之间的距离见表1和表2。

      

       图1 免疫粒子群算法求解过程图

      

      

       以Matlab7.4.0为工具运用本文的免疫粒子群算法对上述问题进行求解，参数设置如下：

。重复运行50次，发现有39次收敛到最优解，即找到最优解的概率是78％，得到最终车辆行驶路线见表3，在同样条件下，运用粒子群算法求解，发现有32次收敛到最优解，即找到最优解的概率是64％，而且运用本文中的算法最终结果优于粒子群算法。

      

       4 结论

       本文针对应急物流配送车辆调度问题，在满足时间约束的条件下，综合考虑运输车辆体积和载重条件，建立模型使运输车辆数最少、总运输线路最短，最大程度的节省物流资源，而不是把车辆调度的研究目的仅仅局限在应急时间最短或运输成本最小。在求解模型时，运用免疫算法和粒子群算法的混合算法，快速求解应急物流配送车辆调度问题，有效提高寻优精度和响应速度。并对其进行实证研究，通过不同算法的比较，验证本文模型和算法的可行性和有效性，为应急管理部门提供有效的辅助建议。

标签：粒子群算法论文;  免疫算法论文;  应急物资论文;