欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2019105696568
申请人: 浙江工业大学
专利类型:发明专利
专利状态:未下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.基于多车场多车型的低成本的车辆调度和路径规划方法,其特征在于,包括以下步骤:

步骤1,以所有车辆配送的总成本最低为目标建立目标函数如下:其中,第一部分为供给产品成本,第二部分为配送车辆的固定成本,第三部分为配送车辆的可变成本;

模型进一步的约束条件如下:

公式(2)表示每辆车的单次配送总量不超过其最大装载量;公式(3)表示调度车辆数不超过可用车辆总数;公式(4)和(5)表示一个客户被且仅被一辆车服务一次;公式(6)表示车辆从配送中心出发完成任务后返回原配送中心;公式(7)表示车辆不能从一个配送中心行驶到另一个配送中心;

其中,Z表示所有车辆配送的总成本,包括产品成本以及配送成本;H表示所有车场不同型号的车辆总数;h表示车辆;Qh表示车辆h的最大装载量;rj表示客户j的需求量;αh表示车辆h所代表的配送中心商品的单位供给成本; 表示从节点i到节点j由车辆h进行配送,当车辆h从节点i到节点j时,且i≠j, 否则,其值取0;Ch表示车辆h的固定成本;βh表示车辆h的行驶单位距离的可变成本;dij表示节点i到节点j之间的距离;N表示客户的总数量;

步骤2,对所有客户点以距离和成本为度量进行基于车场的聚类,每个车场服务指定的客户;

步骤3,编码:根据车场的车辆总数进行编码,对于一个包含N个客户、m个车场、H辆车的车辆调度问题,用数字1~N表示N个客户,数字N+1~N+H表示m个车场的共H辆车,对车辆进行编码,每辆车服务客户的顺序代表一个基因链,第一个基因代表车辆,称为车辆基因,其它基因代表客户,称为客户基因,客户基因的顺序代表被车辆依次服务的顺序,两个车场包含两种类型的车共4辆,将要服务10个客户,用数字1~10表示客户,11~14表示车辆,根据聚类结果,可能的编码方式为[11,1,6,4;12,2,7;13,8,5;14,3,10,9],分别表示车辆11从车场出发,依次服务客户1、6和4,最后回到原车场;其它以此类推;

步骤4,种群初始化:确定蛙群总数量规模F,族群数familyNum,族群中的青蛙数目subFamiSize,其中F=familyNum*subFamiSize,每个族群的局部搜索次数numSe,种群最大迭代次数G,初始温度T,降温速率q,生成F只青蛙;

步骤5,采用目标函数的相反数作为适应度函数对F只青蛙进行计算,然后按照适应度大小进行降序排列;

步骤6,将F只青蛙按照适应度值大小依次分给familyNum个族群,具体步骤如下:将适应度值最大的青蛙Pg,分给第一个族群,将适应度值大小排序第二的青蛙分给第二族群,依次类推,适应度值排序为familyNum的青蛙分配给第familyNum个族群,适应度值排序familyNum+1的青蛙分配给第一族群,依次循环下去,直至将所有青蛙依次分配到不同的族群;

步骤7,每个族群内部进行局部搜索、交流;

步骤8,对所有的青蛙进行混合重洗,具体步骤如下:步骤8.1,将familyNum个族群内部的青蛙全部进行混合;

步骤8.2,删除掉青蛙种群中完全相同的青蛙,只保留一只在种群中;

步骤8.3,按照步骤4的方法随机生成若干只青蛙进行补充,使青蛙种群的数量保持在F只;

步骤9,一次迭代完成,迭代次数g=g+1,当前温度Tg=T*q;

步骤10,判断是否满足终止条件,终止条件为迭代次数g达到最大迭代次数G,如果满足,继续执行步骤11,否则返回执行步骤5;

步骤11,计算F只青蛙的适应度,适应度最大的个体即为Pg,输出青蛙个体Pg及其适应度的相反数‑f(Pg);

步骤12,对最优青蛙Pg进行解码,Pg为[N+1,c,f,…,e;N+2,a,d,…,b;…;N+H‑1,k,n,…,x;N+H,m,g,…,y];其中,[a,b,…,m,…,y,…]表示N个客户,N+1~N+H表示m个车场的共H辆车,根据输出结果Pg,安排车辆N+1依次服务客户c、f、…、e,最后回到原车场,安排车辆N+2依次服务客户a、d、…、b,最后回到原车场,…,安排车辆N+H‑1依次服务客户k、n、…、x,最后回到原车场,安排车辆N+H依次服务客户m、g、…、y,最后回到原车场,此次车辆调度所需总成本为‑f(Pg)。

2.根据权利要求1所述的基于多车场多车型的低成本的车辆调度和路径规划方法,其特征在于,步骤4)中生成F只青蛙的具体过程如下:步骤4.1,对所有客户进行聚类分析,具体过程如下:步骤4.1.1,将每个车场及其所要服务的客户当作一个聚类,m个车场即有m个聚类;

步骤4.1.2,随机选择一个客户,计算其与每个聚类的平均距离,然后把该客户分配给平均距离最小的聚类;

步骤4.1.3,对所有客户执行步骤4.1.1到4.1.2,直至将每个客户分配给对应车场进行服务;

步骤4.2,根据聚类分析结果,把N个客户分成m类,分别由m个车场对应负责;

步骤4.3,根据聚类分析结果,从车场1所要服务的客户中随机选择一个客户i,随机分给一辆车,然后根据概率 i,j∈m1,选择该车的下一个服务客户j,式中,λ(i,j)表示客户i和客户j的邻近程度,例如,λ12=3表示客户2是距离客户1第3近的客户,m1表示车场1所要服务的客户集,然后再根据该概率公式选择客户j的下一个客户,直到该车饱和,无法再承担更多客户为止;

步骤4.4,对剩余的客户依次执行步骤4.3,直到将车场1所对应的客户都分给相应的车辆,客户被分配给车辆的顺序即为车辆的服务顺序;

步骤4.5,如果有客户无法安排给该车场的车辆服务,则将它安排给其它车场进行服务;

步骤4.6,对剩下的m‑1个车场依次执行步骤4.3到4.5,直至将所有客户安排给对应的车辆服务,所有车辆的服务顺序构成一只青蛙个体;

步骤4.7,执行以上步骤4.3到4.6共F/3次,产生F/3只青蛙;

步骤4.8,根据步骤4.1的聚类结果,将车场1所要服务的客户随机排序,构成一个序列list;

步骤4.9,在车场1的车辆中随机选择一辆车,然后将序列list的第一个客户分配给这辆车;

步骤4.10,判断该车是否超载,如果不超载,该客户即由该车进行服务,若超载,则在车场1的其余车辆中随机选择一辆车,并再次判断是否超载,如果车场1中没有可用车辆,则在附近车场中随机选择一辆车,以此类推,直至将该客户分配给某辆车;

步骤4.11,将序列list中的剩余客户按照上述方法依次分配给剩余车辆,客户被分配给车辆的先后顺序即为车辆服务客户的先后顺序;

步骤4.12,对剩下的m‑1个车场依次执行以上步骤4.8到4.11,所有车辆的服务顺序编码构成一只青蛙个体;

步骤4.13,执行以上步骤4.8到4.12共2F/3次,生成2F/3只青蛙,与步骤4.7的F/3只青蛙总和为F只青蛙。

3.根据权利要求1所述的基于多车场多车型的低成本的车辆调度和路径规划方法,其特征在于,步骤7)中每个族群内部进行局部搜索、交流的具体步骤如下:步骤7.1,在族群1中,随机选择Sz个青蛙形成一个子群,该子群中适应度值最大的青蛙命名为Pb,适应度值最小的青蛙命名为Pw,Sz

步骤7.2,对Pw执行跳跃操作,使它向Pb靠拢,具体过程如下:步骤7.2.1,在Pb属于车场1的车辆中随机选择一辆车的基因链,记为b,在Pw中也选择相同车辆的基因链,记为w;

步骤7.2.2,分别将b、w两条基因链中共有的客户基因存放到基因库Fbw中,而将其独有的基因分别存放在基因库Fb和Fw中;

步骤7.2.3,随机产生一个0到1之间的随机数r,如果r>0.5,则按照客户的服务顺序交换b、w两条基因链的客户基因,否则,将b、w两条基因链的客户基因倒置,然后再行交换;

步骤7.2.4,遍历Pw中除了基因链w以外的其它客户基因,并将其与Fb中的客户基因进行比较,删除所有的共有基因,以此类推,对Pb个体采取同样的操作;

步骤7.2.5,随机选择Fw中的一个客户基因,并将其插入到Pw中属于车场1的车辆的基因链中,并判断是否超载,若超载,则随机插入另一辆车的基因链中,如果该车场的车辆均无法满足要求,则随机插入到其它车场的车辆基因链中,直至Fw为空,即全部的客户基因分配出去为止;以此类推,对Pb个体采取同样的操作;

步骤7.2.6,对剩余的m‑1个车场的车辆依次执行步骤7.2.1~7.2.5;

步骤7.3,Pb跳跃过后的青蛙命名为P'b,计算其适应度f(P'b),与f(Pb)进行比较,如果f(P'b)>f(Pb),则用P'b替换Pb,否则保持Pb不变,其中f表示适应度计算公式,f(Pb)就表示原个体Pb的适应度;

步骤7.4,Pw跳跃过后的青蛙命名为P'w,计算其适应度f(P'w),与f(Pw)进行比较,如果f(P'w)>f(Pw),则用P'w替换Pw,否则将步骤7.2中的Pb替换成Pg重新进行跳跃操作,再次比较跳跃过后的f(P'w)与f(Pw),如果跳跃后的适应度值有所提高,即f(P'w)>f(Pw),那么则用P'w替换Pw,否则,按照步骤4的内容,随机生成一只青蛙替换Pw,f(Pw)表示原个体Pw的适应度;

步骤7.5,对Pb进行邻域搜索优化,具体过程如下:步骤7.5.1,在Pb中随机选取一个车场x,然后以概率 选择距离该车场较远的一个客户y,其中,s(x,y)表示车场x和客户y的远离程度,例如,S12=3表示客户2是距离车场1第3远的客户,mx表示车场x所要服务的客户集,然后再根据该概率公式选择下一个客户z,z≠y;

步骤7.5.2,根据概率 选择除车场x以外距离客户y较近的一个车场c,其中,λ(y,c)表示客户y和车场c的邻近程度,例如,λ12=3表示车场2是距离客户1第3近的车场,m'表示除车场x以外的车场集,然后将客户y随机插入到该车场c的车辆服务顺序中,以此类推,对客户z采取同样操作;

步骤7.5.3,如果客户y或z无法被安排给其它车场进行服务,即其它车场已经饱和,则将其安排给原有车场进行服务;

步骤7.5.4,邻域搜索后的青蛙命名为P'b,计算其适应度值f(P'b),并与f(Pb)进行比较,如果f(P'b)>f(Pb),则用P'b替换Pb,否则,以概率exp(f(P'b)‑f(Pb)/Tg)接受领域搜索后的结果,其中,Tg表示第g次迭代时的温度;

步骤7.6,执行以上步骤7.1至7.5共numSe次,使青蛙族群进行numSe局部搜索,进行充分的内部交流;

步骤7.7,对剩下的familyNum‑1个族群均执行以上操作,完成每个族群内部进行局部搜索、交流。