一类动态车辆路径问题的策略研究

一类动态车辆路径问题的策略研究

0动态vrp模型车辆路径问题（rp）将运动理论与实际交通问题紧密相连。在过去，它被描述为一组车辆，沿着特定的路径从一个或多个场地运行运输服务，例如货物的装货、货物的运输、货物的销售和其他现场服务。以往的服务维度模型主要集中在静态模型上。在过去，随着通信技术和信息技术的发展，明显不同于静态模型的动态车辆路径问题，引起了人们的广泛关注。与静态模型相比，动态模型的特点是：1）建模者在制定车辆路径时并不完全了解所有相关信息。2）新信息在规划和执行过程中更新，现有信息也会发生变化。3）该计划只能通过一个系统包络化来执行。在这项工作中，我们使用了最小的等待时间作为系统目标，并研究了动态瑞普波的实时优化策略。计算系统的预期时间，通过数据模拟试验进行验证，表明它比传统的先来服务策略更有效。1基础知识1.1+a+2e2e的范围设Z1(xZ1,уZ1)、Ζ2(xΖ2‚уΖ2),是边长为ɑ的正方形区域A内服从均匀分布的两个随机点,并且相互独立.为了便于计算|Z1Z2|的均值和方差,先假设Z1为定点Z*(x1,у1),从而E(|Ζ*Ζ2|2)=∬A((xΖ2-x1)2+(уΖ2-у1)2)dxΖ2dуΖ2=∫ɑ2-ɑ2dxΖ2∫ɑ2-ɑ21ɑ2((xΖ2-x1)2+(уΖ2-у1)2)dуΖ2=(ɑ26+x21+у21)现用Z1替换Z*:E(|Ζ1Ζ2|2)=∫ɑ2-ɑ2dxΖ1∫ɑ2-ɑ21ɑ2(ɑ26+x2Ζ1+у2Ζ1)dуΖ1‚从而得到E(|Ζ1Ζ2|2)=ɑ23(1)类似地,可以求得设Z为A内服从均匀分布的一个随机点,Z0为A的中点,用上面的方法可以得到E(|Ζ0Ζ|2)=ɑ26(4)E(|Ζ0Ζ|)≈0.38ɑ(5)Var(|Ζ0Ζ|)=E(|Ζ0Ζ|2)-E(|Ζ0Ζ|2)≈0.02ɑ2(6)1.2平均等待时间在一个排队模型中,定义:λ——单位时间内有一个顾客到达的概率,简称概率强度;ˉs——单个顾客的平均服务时间;ρ——服务强度,即忙碌时间比,ρ=λˉs;W——平均等待时间,即顾客到达时刻与服务机构开始对其服务时刻之间的时间段的均值;T——平均系统时间,Τ=W+ˉs;N——系统中的平均顾客数,包括正被服务的顾客和等待服务中的顾客,根据Little公式有N=λT.对于单服务台的M/G/1模型,若输入过程为泊松过程,服务时间s的分布为一般任意分布(但是要求ˉs及Var(s)都存在),则有Ν=ρ+ρ2+λ2Var(s)2(1-ρ)(7)这就是M/G/1排队模型的P-K公式.2时间间隔que动态车辆路径问题可描述如下:一辆货车以恒定速度V在一个边长为ɑ的正方形区域A内执行送货任务.为了简化分析,假设这辆货车拥有足够的载能,即货车无需返回货场重新装载货物.且假设需求全部为动态需求,需求点的位置在区域A内服从独立均匀分布,相邻需求的时间间隔u服从负指数分布,并有ˉu=1λ‚Var(u)=1λ2.设货车在送货点停留的时间s′的分布是一般的,其平均值¯s′和方差Var(s′)都存在.定义Ti为需求i完成时刻与到来时刻之间的时间间隔,Wi为需求开始被服务时刻i与到来时刻之间的时间间隔,所以有Wi=Ti-si;稳态系统时间Τ=limi→∞E[Τi],稳态等待时间W=Τ-ˉs.研究的目的是找到一个服务策略来最小化T,记为T*.根据上述定义,该动态车辆路径问题可以看作是一个M/G/1排队模型.需要注意的是,对于某个需求i来说,服务时间si应包括货车在i点的停留时间si′和货车收到需求信息i后驶向i点的时间di/V,其中,di为行驶的距离,V为货车行驶的速度.对于稳态系统,有limn→∞1nn∑i=1si=limn→∞1nn∑i=1si′+limn→∞1nn∑i=1diV即ˉs=¯s′+ˉdV(8)假设si′和di不相关,则随机变量s′和d的分布是独立的,从而Var(s)=Var(s′)+Var(dV)(9)结合式(7)、(8)、(9)及Little公式,可得Τ=(¯s′+ˉdV)+λ2(¯s′+ˉdV)2+Var(s′)+Var(d)V2(1-λ(¯s′+ˉdV))(10)3动态车辆路径策略3.1系统时间顺序服务策略顺序服务策略是最简单也最自然的一种动态调整策略,可描述为:1)当需求连续出现时,货车将按照先到先服务的顺序从一个服务地点直接转向下一个地点;2)当货车服务完一个需求后没有新的需求到来时,它将停留在原地直到下一个需求到来.由于各需求点的位置在区域A内服从独立、均匀分布,所以根据式(2)、(3)有{ˉd=E(|Ζ1Ζ2|)≈0.52ɑVar(d)=Var(|Ζ1Ζ2|)≈0.06ɑ2(11)把式(11)代入式(10),得到顺序服务策略的系统时间Τ顺序服务策略=(¯s′+0.52ɑV)+λ2(¯s′+0.52ɑV)2+Var(s′)+0.06ɑ2V2(1-λ(¯s′+0.52ɑV))(12)3.2实现z0的重定位不同于静态车辆路径问题,在动态模型中减小动态需求的等待时间往往比减小货车行驶的总距离或时间更为重要.考虑在没有新的需求时调整货车停留地的策略以减小顾客等待时间.图1中,由定义可知|Z1Z2|=d,并设d′=|Z1′Z2|.当货车执行完Z1点的任务后,如果已有需求Z2排队,则货车立即从Z1驶向Z2;如果队列中没有需求,则货车返回中点Z0.返回途中如果在某点Z1′接收到新的需求Z2,则立即驶向Z2,否则返回到Z0待命.此时有Τ中点重定位策略=(¯s′+¯d′V)+λ2(¯s′+¯d′V)2+Var(s′)+Var(¯d′)V2(1-λ(¯s′+¯d′V))(13)因为E(|Ζ1′Ζ1|)=V(1λ-Τ′)≥V(1λ-Τ),所以有{xΖ1′=|Ζ1′Ζ0||Ζ1Ζ0|xΖ1≈0.38ɑ-V(1λ-Τ)0.38ɑxΖ1=CxΖ1уΖ1′=|Ζ1′Ζ0||Ζ1Ζ0|уΖ1≈0.38ɑ-V(1λ-Τ)0.38ɑуΖ1=CуΖ1C=0.38ɑ-V(1λ-Τ)0.38ɑ(14)按照公式(1),(2)的推导方法,可以求得{E((d′)2)=(1+C2)ɑ2bd′¯=∫-ɑ2ɑ2∫-ɑ2ɑ2(Cɑ)2(∫-ɑ2ɑ2∫-ɑ2ɑ21ɑ2⋅(xΖ2-CxΖ1)2+(уΖ2-CуΖ1)2⋅dxΖ2dуΖ2)dxΖ1dуΖ1Var(d′)=E((d′)2)-(d¯′)2(15)要显性地求出式(15)中的d′¯比较麻烦,实际计算时可运用计算软件(如Mathematica)求得具体数据.4顾客优化策略仿真表1给出了例子的系统参数.由式(9),可以求出顺序服务策略的系统时间T顺序服务策略≈1.76,而由式(10)、(11)、(12),得到中点重定位策略的系统时间T中点重定位策略≈1.65.根据表1中的系统参数,用Minitab软件生成仿真数据,由所生成的数据可计算出Τ¯顺序服务策略=150∑i=150Τi顺序服务策略≈1.74Τ¯中点重定位策略=150∑i=150Τi中点重定位策略≈1.60误差率|Τ¯顺序服务策略-Τ顺序服务策略|Τ¯顺序服务策略×100％≈1.15％|Τ¯中点重定位策略-Τ中点重定位策略|Τ¯中点重定位策略×100％≈3.12％可以看出仿真结果Τ¯顺序服务策略、Τ¯中点重定位策略都与各自理论计算值基本保持一致.中点重定位策略的系统时间比顺序服务策略的系统时间减少率为|Τ¯中点重定位策略-Τ¯顺序服务策略|Τ¯中点重定位策略×100％≈8.05％仿真结果表明了中点重定位策略比顺序策略更能减小顾客的平均等待时间.5确定正常模型的消除条件与静态模型相比,动态车辆路径问题的研究更具有实际意义.本文应用排队论、几何概率论等理论导出了一类动态车辆路径问题系统时间的公式.虽然在公式推导过程中作了一些简化,但这一结果可以推