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

摘要:

权利要求书:

1.一种基于集成学习的适用于车辆配送任务的路径规划方法,应用于由单个仓库、K辆卡车和N个配送任务节点所构成的车辆配送任务中,并按照如下步骤进行:步骤1、建立车辆配送任务模型;

步骤1.1、定义由一个仓库节点v0和N个配送任务节点构成的节点集合V={vi,i=0,1,

2,...,N},vi表示第i个节点;定义路径集合E={eij|i,j=0,1,2,...,N},eij表示第i个节点vi到第j个节点vj的路径;

步骤1.2、利用式(1)构建车辆路径规划模型的目标函数f:式(1)中,cij表示第i个节点vi到第j个节点vj的距离,xij表示路径规划方案中是否包含从第i个节点vi到第j个节点vj的路径;若xij=1,则表示包含,若xij=0,则表示不包含;目标是为车辆找到一组路线,使得在满足约束的前提下,总行驶距离最小化;

步骤1.3、利用式(2)‑式(8)构建车辆路径规划模型的约束条件:ui‑uj+Qxij≤Q‑dj,i,j=1,2,…,N,i≠j    (6)di≤ui≤Q                    (7)xij∈{0,1},0≤i,j≤N            (8)式(2)‑式(8)中,ui表示访问第i个配送任务节点vi时车辆的负载,uj表示访问第j个配送任务节点vj时车辆的负载,Q表示一辆卡车所服务配送任务节点的总需求量上限,di表示第i个配送任务节点vi的需求量;

步骤2、全局变量的初始化;

步骤2.1、记路径规划的开始运行的时刻为timestart,运行时间上限为timemax;

步骤2.2、记模拟退火方法的初始温度 其中,k表示初始温度的系数,且k∈[0,1];

步骤2.3、记当前路径规划方案为s,使用节约算法初始化s,并利用式(1)计算s的行驶距离为fs;

* *

步骤2.4、记最优路径规划方案为s,并令s←s;记最优路径规划方案的行驶距离为令 ←表示赋值符号;

步骤2.5、记局部搜索算子集合OP={op1,op2,...,opm,...,opM},其中,M表示局部搜索算子的数量,且M≥2,opm表示第m个局部搜索算子,且m∈[1,M];

步骤2.6、记局部搜索算子的贡献度向量为CV=[1,1,...,1]1×M;

步骤2.7、记局部搜索算子的协同度矩阵为CM,并有:步骤2.8、记线程池中最大线程数为T,T为当前计算机中CPU的物理核心数;

步骤三、得到适用于当前任务的局部搜索算子集合:步骤3.1、利用式(10)生成临时贡献度向量CV′:式(10)中,CVm表示贡献度向量CV在第m个维度上的贡献度;

步骤3.2、生成一个M维的随机向量randVector,且randVector中每一维上的值均在0到

1之间;

步骤3.3、利用式(11)生成一个M维掩码向量maskVector:式(11)中,maskVectorm、randVectorm、CV′m分别表示maskVector、randVector、CV′中在第m维度上的值;

‑1

步骤3.4、记函数g为m到maskVectorm的映射,即g(m)=maskVectorm,m∈[1,M];记g 为g‑1的反函数,令局部搜索算子集合为索引向量idxVector=g (1),即maskVector中所有值为1的维度的集合;利用式(12)得到索引向量idxVector的长度L:步骤四、得到适用于当前任务的多样化的局部搜索算子排列组合方式:步骤4.1、记局部搜索算子排列组合方式的集合为opSets,且opSets初始化为空集、容量为T,即opSets最多存放T个排列组合方式;

步骤4.2、利用式(13)生成一个M×M维的临时协同度矩阵CM′:式(13)中,CM′ij、CMij分别表示CM′、CM在第i行第j列上的值;

步骤4.3、生成临时算子排列组合方式tmpOpSet={};

步骤4.4、随机产生一个正整数int1,且int1∈idxVector;将int1追加至tmpOpSet的末尾,并将CM′中第int1列的值置为零;

步骤4.5、取CM′的第int1行的行向量,利用轮盘赌方法从所述行向量中选中某一维度,并将所选中维度的索引记为int2;

步骤4.6、将int2追加至tmpOpSet的末尾,并将CM′中第int2列的值置为零;

步骤4.7、令int1←int2;

步骤4.8、若CM′中第int1行上的值不全为零,则返回步骤4.5;否则,执行步骤4.9;

步骤4.9、将tmpOpSet添加入opSets;

步骤4.10、若opSets未满,则返回步骤4.2;否则,执行步骤五;

步骤五、利用多样化的局部搜索算子排列组合方式,生成多样化的临时路径规划方案:步骤5.1、使用扰动算子δ扰动当前路径规划方案s,得到扰动后的路径规划方案s′;

步骤5.2、将T个算子排列组合方式opSets={opSet1,opSet2,...,opSett,...,opSetT}依次分配至线程池中的T个线程threads={thread1,thread2,...,threadt,...,threadT},其中,第t个局部搜索算子排列组合方式opSett被分配给第t个线程threadt,且表示opSett中第l个算子,且t∈[1,T],步骤5.3、T个线程根据各自分配到的算子排列组合方式,并行搜索s′,并生成T个临时贡献度向量 T个临时协同度矩阵T个临时路径规划方案

其中, 表示第t个临时贡献度向量, 表示第t个临时协同度矩阵, 表示第t个临时路径规划方案;

步骤5.4、当所有线程均已结束时,执行步骤六;

步骤六、更新当前路径规划方案与最优路径规划方案;

步骤6.1、利用式(14)更新CV:

步骤6.2、利用式(15)更新CM:

步骤6.3、更新当前路径规划方案:

步骤6.3.1、利用式(16)所示的贪心策略从T个临时路径规划方案中选择一个精英临时路径规划方案selite:

6.3.2、利用式(17)计算当前温度E:式(17)中,ε为模拟退火方法温度衰减函数的底数,且ε∈(0,0.01];timenow为当前时刻;

6.3.3、利用式(18)计算当前温度E下接受selite的概率p:式(18)中, 表示selite的行驶距离;

6.3.4、产生一个随机数randNum,且randNum∈[0,1],若randNum<p,则更新当前路径规划方案,即令s←selite, 否则,s和fs保持不变;

*

步骤6.4、更新最优路径规划方案s:

* *

若 则令s←selite, 否则,s和 保持不变;

*

步骤七、若timenow‑timestart>timemax,则输出s;否则,返回步骤三。

2.根据权利要求1所述的基于集成学习的适用于车辆配送任务的路径规划方法,其特征在于,是按如下方式生成步骤5.3.1、令

步骤5.3.2、令l←1;

步骤5.3.3、应用第 个局部搜索算子 对 进行局部搜索,得到搜索后的临时路径规划方案s″;

步骤5.3.4、若s″的行驶距离fs″小于 的行驶距离 则执行步骤5.3.5;否则,直接执行步骤5.3.6;

步骤5.3.5、若l≥2,则令

并返回步骤5.3.2;否则,令

不做更新,并返回步骤5.3.2;其中, 表示 中第 准度上的值, 表示 中第 行第 列上的值;

步骤5.3.6、l←l+1;若l≤L,则返回步骤5.3.3;否则,结束第t个线程threadt。

3.一种电子设备,包括存储器以及处理器,其特征在于,所述存储器用于存储支持处理器执行权利要求1或2所述车辆路径规划方法的程序,所述处理器被配置为用于执行所述存储器中存储的程序。

4.一种计算机可读存储介质,计算机可读存储介质上存储有计算机程序,其特征在于,所述计算机程序被处理器运行时执行权利要求1或2所述车辆路径规划方法的步骤。