针对物流配送实时仓储车辆调度问题，提出了一种基于RFID技术的免疫萤火虫车辆动态调度框架。建立了基于配送成本的带约束条件车辆路径问题数学模型，运用免疫萤火虫优化算法求解该模型，免疫萤火虫优化算法将萤火虫优化及免疫克隆技术融合，采用多层进化模式，在低层萤火虫操作中及高层免疫操作中分别引入多态子种群自适应机制和全局极值筛选策略，以提高算法全局收敛效率，在此基础上设计了仓储车辆动态调度框架，将车辆动态调度过程分为车辆调度任务控制和路径优化两个阶段，给出了车辆动态调度任务处理流程。实验仿真表明，该车辆动态调度算法能够有效地解决大规模动态物流车辆调度问题。
李雪竹:基于免疫萤火虫算法的RFID仓储车辆动态调度 2014,50(6)237 空间内进行精细度搜索,提高了算法精度。 方案,为此,本文结合约東条件,给出了萤火虫粒子编码 定义萤火虫种群进化因子D()为: 方式:在 IGSOA中,定义萤火虫位置为序列为X=(0,x, D() X2()-X2(t (12) x2…,0,…,0,A…,x,0)(x∈[,川,X∩,n≠⑦) 而且编码中取值为θ的编码位数量为m+1。萤火虫编 其中,α为极小正数:D()取值代表了种群进化程度,码位取0表示为配送中心,取1~n则表示对应的需求 根据D()的大小可以自适应的调整精英群和搜索群规点。例如某个萤火虫编码序列为(0,3,5,0,4.1,2,0 模ε对于F:,其搜索群规模N,()按式(13)更新 6,0),它表示配送中心共3辆汽车,服务于6个需求点, N(t)=round[Nox(l-D(o)] (13)而且3辆汽车配送路线分别为0→>3→>5→0、0-4→ 通常设定N≤N,(0)≤N。从式(12)(13)可以看出,1→2→0,0→6→0。对于该萤火虫编码方式如果仍 算法运算初期D(取值较大,表明样本空间比较大,因然采用式(9)、(10)、(17)粒子更新方式会产生大量不符 此搜索群规模较小;算法运算后期,D()取值减少,表明合约束条件的解,严重降低了算法求解效率,为此,本文 种群多样性降低,而搜索群规模变大,使得粒子能在更 参考文献[12],在式(9)、(10)、(17)的基础上给出了适 大的空间屮寻找最优解。得到M()后精英群规模用于ⅤRP萤火虫编码方式的个体更新策略。通过观察 约東条件及萤火虫编码定义,可以发现,不同的粒子编 N,()按式(14)确定。 码可以相互转化,例如对于编码A和0,1,2,0,3,0)和编 (14)码B(0,3,2,0,1,0),将编码A编码位2和5进行调換 22高层CSA操作 就可以转化为编码B,因此可以定义编码为调换操作 全局极值筛选策略:设F极值点集合为P={X"},EX(1),其中2表示编码位。任意两个编码都可 萤火虫整个群体全局极值点集合为Pnm。取E,中的以通过一系列调换操作进行转化,定义调换序列为 X为Pi第一点,然后依次从P中取x',如果X满CH(AB)={EX1EX2,…,EM},显然0≤≤m+n。编 足式(15),则X为种群全局极值点。 码转换可以描述为B=A+CH(AφB)(如图1所示) f(X!)-f(z川≤E (15) Route l Route 2 Route 3 其中,f(∠)为理论全局极值,为判定常数。定义CAx,国面四凶[mt 亲和度函数为a(a)。对于高层CSA操作,其种群C XA+Ex1(2.5) 由低层E的P-组成。高层CSA操作工作过程可以描 04国[6国[0四画[0 述为 X,+Ex+EX, (5,ID) 步骤1克隆扩增。对于Pm中的抗体按照式(16)x[01[7[[481[0[6[[0[[ 进行克隆扩增。 图1改进的GSOA粒子更新策略 C"x∑a(E 对于式(9),修改后的萤火虫更新策略为: B round l6) X(+1)=X()+D (18 aff(e) D={(EX)EX,∈CH(xX)}+ 其中,a∥(E)为低层E中最优个体亲和度值。显然具 (EX)EX∈CH(XX)} (19) 有较优适应度的了种群获得了较大的克隆倍数,充分保 is rand(o, CH(XA ()X)), 留了优秀个体信息 步骤2自适应变异。克隆后的抗体C按式(17)进 ≤nd(2CH(x>x, 行变异 其中,CH(X。X表示CH(x4X)中调换操作的个 =C4+exp(=m)×(C-C)xN(0,1) 数,式(20)表示分别取调换序列的前i、j个调换操作。 (17 对j式(17),修改后的更新策略为 其中,C、C1为C上下限。式(17)说眀Ck能够根据进 =Ck+{(E)EX∈CH(CC (21) 化过程自动调整粒子变异空间。 7≤rad(Pexp(-mCH(C分→C (22) 步繫3免疫选择。对于C(),其克降及变异后抗 对于式(10).采用逆转算子进行领域搜索,逆转算 体集合为S,取S中亲和度最优个体C"A(O并判断C()子对编码内子线路进行操作,从子路径内随机选择某编 是否优于C4(),若是,则C(+1)C:(),否则C()保码位进行逆转(如图2所示),修改后的更新策略为: 持个变 X,(t+1)=, (D)+EX+.+EX, i-randuTmax m/t(23) 2、3VRP中 IGSOA粒子编码方式及更新策略其中,EX表示第i个子路径调换操作,为控制系数, 对于ⅤRP问题,每只萤火虫代表了一种路径优化在算法进化初期,算法选择较多的子路径进行逆转算子 238 014,50(6) Computer Engineering and4 pplications计算机工程与应用 操作,提高搜索空间,算法后期,只选择少量子路径进行据装载夲和系统剩余派送车辆之间的关系动态控制待 转换,提高了收敛速度。 处理任务,当判定条件满足时,调用 IGSOA车辆调度算 Route 1 Route 2 法.完成调度任务处理,任务处理完成后,进入下一次工 x国国四尚面国国作局期。RFD技术主要为仓储车辆 j动态调度提供配送 EX(2、3) Ex(7,8) EX(10,11) 车辆实时状态、配送任务处理情况等信息。 x[0国3[4[0[5[60[82[o 判定条件1预配送车辆数m估算根据任务请求 图2逆转算子过程小意图 时间,对待处理任务进行排序,序列集为R={R1,R2 24 IGSOA算法实现流程 R,…},其中R的需求量为q,。在R中取前j个任务 本文采用采用 IGSo对VRP数学模型进行求解, 组成预处理任务集合R={R1、R2,…,R},则有 因此, IGSOA目标函数为f(X)=minE。 IGSOA算法 +1≤m'≤ rand 流程描述为 1. Stepl初始化。根据文献3产生符合VRP约束条件其中,O为车辆装载控制因子,gm:、Qmn分别为配送 的初始萤火虫种群,相关参数设定。 车辆最大和最小装载量。 2.Step2 While(终止条件不满足) 判定条件2装载率τ计算当配送中心剩余车辆大 ∥多态子种群自适应GSO操作 于m时,定义此时剩余车辆总载量为Qm,则有: For每个萤火虫子种群F1 3.根据式(13)(14)计算精英群和搜索群规模;根据 qk 式(23)对精英群内粒子进行更新,根据式(18)~(20)对搜索群 (25) 个体进行更新; 4.更新个体极值集合P与全局极值集合Pn; 般设定装载率阙值τmn(通常取0.85),只有当满 5. End for 足τ≥τ时才进行任务分配。 6.t←-t+1 7.Ift-1≥Tc,Tc为高层开始迭代次数 4仿真实验 /高层CSA操作 8.根据式(16)进行抗体克隆,根据式(21)(22)进行变 1实例仿真 异,执行兔疫选择操作 为了验证 IGSOA算法求解性能,构造30个需求点 9.更新个体极值集合P与全局极值集合P转到step2;的算例:配送中心坐标为(50,50)(单位:km),共有1辆 10.Else转到step2 6t、3辆8t和1辆16t的配送汽车,3种车型成本费用如 11. End if 表1所示。30个需求点位置信息及需求量如表2所示。 12. End whilc IGSOA具体参数设置为:N=500,M=5,c1=0.8,2= 13.Step3输出结果,算法结東。 0.2,g=1×10-4,bo=5,p=0.4,?=0.6,5=0.03、B=0.08, 3仓储车辆动态调度 表1配送车辆使用成本 图3给出了仓储钅辆动态调度框架,仓储车俩动态 车型回定成本/元空载油耗几满载油耗L 调度框架是指将车辆动态调度过程分为车辆调度任务 0)45 1.8 控制和路径优化两个阶段。车辆调度任务控制就是根 16 150 3.2 任务实时时间 表2需求点信息 匚待外理在务排疗词用 IGSO调度算法 i (x/km, wkm)q:i (xikm, y/km)g,i (x/km, ykm)q: 辆实时状态 车辆调度 在务处 02160,271.3 任务控制 理成功 0.522 确定倾处理任务集合 28|1330,90 2.023 42,75 L.9 RFID 输出配送结果 :数据处理 估算需要派送车辆数 55,171.31411,54102464,93 更新系统状态 29,23042592,70 统剩杀 辆满 有任务~N 处理完毕 740,1 091794,40222757,70 1.2 <要我多 结束 940,71.01980,60092952,93 图3仓储乍辆动态调度架构 1032,610.720354083010,91.1 李雪竹:基于免疫萤火虫算法的RFID仓储车辆动态调度 2014,50(6)239 M=5,设初始时刻r与值相同,取值为30,Tm、=500 IGS e=1×10 000 假设30个需求点按照需求点序号发出请求,而且 -SFLA 800 配送中心所有车辆都已经完成上次任务,根据式(24)计 c600 算有m≥rnd∑qk1Qm+1=rmn42(16×07)+1=4 400 通过式(24),可以看出30个需求点的装载率r=42/46= 050100150200250300 0.913,因此可以同时对30个任务点进行配送。采用 迭代次数 IGSOA对算例进行求解,运行50次,表3给出了车辆调 图5路径长度随迭代次数变化曲线 度分配方案,图4给出了车辆调度仿真结果。 5结语 苌3车辆调度分配方案 对物流配送实时仓储车辆调度问题进行了研究,建 车型 线路 距离km装载率/(%) 立了车辆路径问题数学模型,给出了 IGSOA算法求解 0-1-20-14-11-10-0 23-13-2927-0 43.19 ⅤRP流程,设计了萤火虫特殊编码方式和更新策咚,并 0-2-24-26-25-190 50.84 分析了基于RFID技术的仓储车辆动态调度框架,给出 0-15-30-22-9-7-4-12-0 5609 90.0 了车辆动态调度仁务处理流程。实验结果表明, IGSOA 160-16-17-18-28-8653-21-05000%4可以快速有效地给出优化物流配送车辆调度方案。 参考文献 8 t 「1张维泽,林剑波,吴洪森,等基于改进蚁群算法的物流配送 16t1 路径优化[J浙江大学学报:工学版,2008,42(4):574-578 [2 Bell J E, Mcmullen P R Ant colony optimization tech- niques for the vehicle routing problem[J].Advanced Engi neering Informatics. 2004.18(1):41-48 3]朱玲玲,杨爱琴吴宽亻:基于协同自适应禁忌的多时窗ⅤRP 0 102030405060708090100 算法实现[J计算机应用研究,2012,29(12):4542-4545 4]田青,缪立新,郑力基于运输规划和组合GA的基本物流 图4车辆调度仿真结果 N络设计[J清华大学学报,2004,44(11):1441-14. 4.2ISOA算法性能分析 [5]张潜,高立群,刘雪梅,等,定位-运输路线安排问题的两阶 为了进一步分析 IGSOA性能,分别采用 IGSOA 段启发式算法[门控制与决策.2004,19(7):773-77 GSO、SFLA对算倒进行解算,运行50次,表4给出了36 atl. afarzadch M. nonlincar neural nctworks for 种算法性能比较(S表示最优总运行距离,§表示平均 solving the shortest path problem J.Applied Mathematics 总运行距离,表示算法平均运行时间,7表示算法平 and Computation, 2007, 189(1): 567-574 均迭代次数,表示算法搜索成功率),图5给出了路径 [7]孔宁,李晓东,罗万明,等物联网资源寻址模型[J.软件学 报,2010.21(7):1657-1666 长度随迭代次数变化曲线。 [8 Krishnanand K N, Ghosc D Thcorctical foundations for 表4不同算法性能比较 rendezvous of glow worm-inspired agent swarms at mul- 算法,km S/km T/h t (%) tiple locations [J]. Robotics and Autonomous Systems, 2008 IGSOA 56(7):549569 258301891213 [9 Eusuff MM, Lansey K E Optimization of water distribu- SFLA 264296132.8287 tion network design using the shuffled frog leaping algo 从表3及图4可以看出,IGSO∧能够有效地给出配 rithm[J]. Water Resources Planning and Management, 2003 129(3):210-225 送汽车调度方案,而且每辆车辆的装载率在85%以 I0]彭扬,陈了侠,吴承键定位-运输路线安排问题的改进离 从表4及图5可以看出, IGSOA在运行时间、运输距离 散粒子群优化算法[J智能系统学报,2010,5(1):74-79. 和求解成功率方亩都高于其他两种算法,这是因为IG [l1]li庆莹,王联国基于领域正交叉算子的混合蛙跳算法[J] SOA采用低层多态子种群自适应操作机制,因此具有很 计算机工程与应用,2011,47(36):54-56. 强的局部搜索能力,同时高层CS∧操作进一步提高了12]罗雪晖,杨烨,李霞改进混合蛙跳算法求解旅行蔺问题 算法收敛精度,优化结果更符合实际情况 通信学报,2009,30(7):130-135