多车批量配送的应急物流模型

多车批量配送的应急物流模型

基于sdrsp的应急物流管理据统计，世界上突发事件（自然灾害、感染疾病、流血冲突等）的频率和烈度逐年增加。应急物流研究在突发事件下如何将救援物资及时、可靠、高效地送达各灾点,直接影响到人员伤亡和财产损失,意义重大。应急物流一般抽象为车辆路径规划问题(VehicleRoutingProblem,VRP),具有强时效性、弱经济性等特点。采用VRP经典框架,但以最终(或平均)送达时间最小化为目标。为提高运输车辆的灵活性和使用率,建立多车场VRP模型,进一步提出多周期的分层VRP方案。突发事件背景下,一方面,灾点的物资需求量往往超过单车单次供应量,故只能由多车多批次予以满足。另一方面,分批配送可保证各灾点都能获得及时救援,又避免了过量物资同时送达造成的囤积乃至混乱。考虑到分批配送的车辆路径问题(SplitDeliveryVehicleRoutingProblem,SDVRP)将各顾客点(即本文中的灾点)的总需求进行拆分,允许其被多车多次服务,可以节约运输车辆或配送路径,因此适用于道路受损、车辆有限的应急物流。VRP是一种典型的非线性规划(NP)难题,精确求解代价过大,实践中往往采用亚启发式算法,如禁忌搜索(tabusearch,TS)、遗传算法(GA)、蚁群算法(ACO)等,近年来SDVRP的研究也取得重大进展,但用于应急物流还鲜有报道。为此本文建立应急物流的SDVRP模型,分别设计适用于该模型的GA、ACO以及ACO-GA混合算法,并通过数值算例仿真说明混合算法的优势。1批发供应车辆路径的建模1.1救援物资状态假设突发事件(如大规模自然灾害)在某地区造成A个灾点。该地区有且仅有一个车场。V台车辆由车场出发,依次对若干灾点配送救援物资,最后空载返回车场,可能形成R条(闭合)路径。为简化分析,做如下假设(1)救援物资为统一包装(重量、体积)的单元(包括药品、饮用水、食物等)。(2)运输车辆运载容量相同,行驶速度一致(3)各灾点与车场均有道路连通,车辆无需原路返回(4)各灾点各周期的需求已知或可准确估计,且在该规划周期内保持不变。(5)车场库存可满足所有灾点的需求总量,故只需关注如何将足量物资送达。(6)各灾点物资需求量较大,单车单次配送无法满足,必须由多车分批配送。(7)车辆从车场出发,前往通行距离(由道路长度及损毁程度共同决定)最远的灾点,也可当日返回。(8)救援行动将在T个周期内终止,在灾后T个周期之外送达的物资无效。(9)模型中所有变量均为整数,属于整数规划问题。1.2周期t的需求t:周期集中的编号结合救灾72小时黄金时间的一般原则,设T(28)3,即尽量将救援物资在3天内送达灾点。qarv(t,t):为满足灾点a在周期t的需求,车辆v经由路径r在周期t送达的物资量,显然为如期配送,为无效配送tr:车辆在路径r上的行驶时间tr是路径里程、行车速度和灾害破坏状况的函数,路径越长、车速越低、损毁越严重,tr越大;反之则tr越小。路径决策函数,若车辆v在周期t经过路径r,Q:单车的额定容量H:车辆在每个周期内的工作时间表示救援行动终止时,灾点a获得的救灾物资总量与其需求总量之比值。sa越大,需求满足得越充分,则该灾点的满意度越高。1.3救援+分区z1为受灾地区所有灾点总需求与总配送的差值,最小化(3)式要求尽量满足灾区的物资需求。z2为所有车辆在救援路网中的总耗时,最小化(4)式反映了救援的及时性要求。z3为任意两灾点i,j的满意度差异的最大值,最小化(5)式力求均衡各灾点的供需比,反映了救援的公平性原则。1.4需求总量不得超过已达需求总量单车单次需给至少一个灾点配送救援物资单车单次配送物资量不得超过其额定容量各灾点获得物资总量不应超过其需求总量结合式(2),有灾害损毁交通设施,限制了运输车辆的运行时段。即车辆在一个周期内的总行驶时间存在上限1.5确定目标函数应急物流配送模型兼顾效用、时间、均衡三方面的要求,属于多目标优化问题。各目标相互独立,且有矛盾关系(例如保证物资供应,就需用较多车辆经由较多路径;而缩减路径则往往导致各灾点物资配送不均),因此必须做折中考虑。本文采用加权求和法,应用层次分析法(AHP)确定各目标权值。根据专家经验,结合灾情实际,得出各目标重要性的相对关系,即重要度比较矩阵故权值向量为经实际计算发现,各函数的取值区间大致为z1:60~100,z2:0~24,z3:0~5。故对z1和z2取对数,z3不做变换,依(11)式,得到单一目标函数2遗传计算方法的改进2.1车场的编码染色体编码是遗传算法的关键和难点。结合本文模型的具体特点,将需求量为d的灾点视为需求量为1的d个同名灾点,规定:(a)一条染色体表示一个周期的配送方案,由相互独立的段基因组成;(b)每段基因表示一辆车的配送路径,由Q位组成(c)每位表示一份物资,该位上的数字即为物资送达的灾点编号;由于车辆不一定满载出发,故基因上可能出现的空位用0补齐。考虑SDVRP,车场记为D,6个灾点记为1~6,总需求量单车额定容量Q=5,故需3条配送路径,为便于后续遗传操作,编码时将车场省去。编码后的染色体分为3段,每段5位显然三条路径整体互换不影响目标函数值,性能优化主要通过两种方式实现:(1)不同路径之间,基因段的交换(2)同一路径内部,基因位的重新排序2.2灾点i用量累积概率由于本文模型为分阶段规划问题,而各灾区在各周期的需求量动态变化,因此必须将灾区的需求信息编入种群。设周期t时,各灾点需求集为Dmd={d1,…,dA},uf072i为灾点i需求量的累积概率。借鉴赌盘轮转思想,算法伪代码如下Step.1设置ρi=0,Dmd为初始值Step.2计算Step.3生成一个之间的随机数,若落在(ρi,ρi+1],则将灾点i写入当前位Step.4更新DmdStep.5若单条染色体还有剩余的位,回到Step.2;否则,转Step.6Step.6若种群数未到达n,回到Step.1;否则,初始种群Pop生成完毕周期t规划结束时,将各灾点未被满足的需求量与周期t(10)1产生的新需求相累加,进入下一周期的规划。2.3遗传实践与创新2.3.1父代种群和子代种群同样采用赌盘轮转法对种群进行选择操作,保证父代的优质个体以较大概率被选中。种群的适应度集为其中fi为染色体i适应度,与目标函数反相关,ρi为fi的累积概率,记父代种群为Pop,子代种群为PopNext。算法伪代码如下Step.1设置ρi=0,计算fiStep.3生成之间的随机数,若落在(ρi,ρi+1],则选择染色体i,编入PopNextStep.4若已达到子代种群数n,转Step.5;否则,回到Step.3,选择另一条染色体Step.5选择结束,PopNext={Pop,PopNext}为了保证解的多样性,将种群父代也编入子代进行交叉变异操作,因此选择后生成的子代种群为PopNext={Pop,PopNext}。2.3.2chromissschromi的交叉操作采用部分交叉法,使种群在当前解附近寻找更优解。设交叉概率为CP,算法伪代码如下。Step.1从种群PopNext中随机选择两条染色体1Chromi,Chromi(10)Step.2生成之间随机数rand,若进行交叉操作Step.3随机生成两个交叉位x,y,将Chromi,Chromi+1内x,y之间的基因位交换,得到新的染色体Step.4若回到Step.1;否则,转Step.5Step.5交叉操作结束,用更新PopNext随机得x=4,y=8,交叉后得到的分别为2.3.3变异矩阵采用多点变异,设变异概率为PM,算法伪代码如下2.3.4同一路径内同一灾点,重复基因型经交叉、变异得到的染色体,很可能出现同一路径内同一灾点被分割的情况,这显然不符合救灾实际,必须避免,为此调整基因位序,将同一路径内的同名灾点放在一起。例如:变异操作后的为调整后,得到合理的染色体对PopNext中的所有染色体均作上述处理。2.4路径行驶时间遗传操作完成后,必须应用单周期的工作时间约束验证解的可行性,检验其是否服从(9)式约束。算法伪代码如下Step.1对染色体Chromi,从第一位开始,每Q位构成一条完整路径Step.2累计上述每条路径的行驶时间,如果均小于H,则转Step.3;否则,转Step.4Step.3Chromi可行,保留,转Step.5Step.4Chromi不可行,淘汰,转Step.5Step.5验证下一条染色体Chromi+1,直至生成规定数量的可行种群,作为下一轮遗传操作的父代种群Pop3蚂蚁-遗传混合算法的设计3.1灾点随机配送规划上述遗传操作基于随机生成的初始种群,大量计算时间消耗于淘汰初始种群中可行却明显劣质的个体,收敛时间长,寻优效率低。为此考虑利用ACO的正反馈机制,通过较少次数迭代,对问题的解空间做一粗略搜索,提高初始种群质量;再应用GA进一步优化。基本流程如图1所示。采用蚁群算法依次完成以下步骤第一,规划出遍历路径第二,根据各灾点的实时需求生成一个配送额第三,根据车辆载荷约束,插入车场,完成规划。设Tabu(k)为蚂蚁k的禁忌表,算法伪代码如下Step.1蚂蚁k随机处于灾点i,其禁忌表Tabu(k)={i}Step.3由转移概率的最大值,确定下一步的灾点并更新禁忌表Step.4根据灾点j的实时需求,生成一个配送量Step.5若已遍历所有灾点,转Step.6;否则回到Step.2Step.6Tabu(k)为蚂蚁k的旅行路径Step.7根据式(3)~(5)评价Tabu(k),结束由于灾区的物资需求量一般大于车辆额定载荷,所以若根据灾区需求随机生成配送量,可能出现单次配送过多,当前周期负荷过重的情形,导致物资配送的周期不均衡性。因此,需要对配送量设置阈值,本文取车辆载重的60%。3.2基于信息素与启发因子的路径选择算法由于式(5)引入了满意度指标以保证救援物资的公平发放,因此要求蚂蚁在每一步选择下个灾点时,不仅应关注路径信息素与两点间距,同时还需考虑待选灾点的需求量,故上述算法Step.3中的转移概率为其中和η分别为信息素与启发因子,为灾点j在周期t的需求量函数。将蚁群若干次迭代后寻得的路径按照2.1的编码规则映射为染色体,即获得较为优质的遗传初始种群,之后可沿用第2节的遗传操作步骤进一步寻优。4数值模拟验证4.1仿真结果与分析利用VRPWeb上的通用数据集p01,取其中的点0-10构成问题n-10(含1个车场与10个灾点,见表1);取其中的点0-20构成问题n-20(含1个车场与20个灾点,见表2),进行数值仿真。模型参数:最大工作时间H(28)12h,规划周期T(28)3d(一般救援物资需在72h内送达),车辆载重Q(28)15,速度20。算法参数:GA:染色体数50,进化20代,PC=0.7,PM=0.1;ACO-GA:蚁群规模10,迭代20次,染色体数30,进化10代;其它参数不变运行环境:Matlab8.0,IntelPentiumDualCPUE2160@1.80GHz,2.00GBDDR-IIRAM。4.2单车单次容量无法被服务为便于对比,以问题n-10为例,同时给出三种进化算法的求解结果:单纯遗传算法(表3),单纯蚁群算法(表4)和本文提出的蚁群-遗传混合算法(表5)。由表3,对于问题n-10,为保证所有灾区需求72小时内满足,GA算法所需车辆数为6。如果采取基本VRP模型,则至少为15。这是由于本文模型采用分批配送,使车辆得以重复利用,从而节约了车辆数。此外,如果不对需求进行拆分,将有部分灾点由于需求大于单车单次容量而不能被服务,即产生不可行解。表4显示了ACO同样可以较好地求解本文模型,并且寻优结果效果比GA改善了9%,且收敛速度更快,路径数更少,这源于蚁群算法的分步求解过程:每次先生成TSP路径,再根据灾点需求生成配送额,最后根据车辆容量插入车场,从而避免了遗传算法初始种群的过度随机性,降低了重复回路出现的可能性。如图2,为ACO-GA混合算法针对问题n-10求得的3个周期内的配送路径。结合表5可以看出,ACO-GA不仅能有效地求解本文模型,而且与单纯的GA或ACO相比,寻优效能进一步提高。如图3,为三种算法对问题n-10和n-20的求解结果(目标函数值)对照。尽管蚁群规模及遗传代数都较单纯ACO,GA有所减少,但ACO-GA的寻优效果更佳。进一步求其平均值列于表6。对于问题n-10,ACO-GA的结果比GA小14.5%,比ACO小6%;对于问题n-20,ACO-GA的结果比GA小12%,比ACO小7%。这是由于ACO的粗略搜索对GA初始种群的生成起到了良好的指导作用,使得种群更高效地向最优解方向进化。另外,由于引入公平度这一评价指标,每条路径经过的灾点数相对增加,而单个灾点的单次配送额不大,但这样提高了物资配送的均衡性,即而每条配送路线覆盖的灾点较多。从而避免部分灾点因大量物资同时送达造成囤积,而另一部分灾点却因为缺乏物资而造成灾情扩大化的局面。5遗传算法求解本文应用SDVRP思想,建立应急物流调度模型,分别针对灾点的未满足需求量、物资配送时间、满意度差异进行最小化,通过对各目标加权求和,兼顾救援的效果、速度和公平。设计与