利索能及
我要发布
收藏
专利号: 2019101507887
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-08-12
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于K-means和离散粒子群算法的多无人车任务分配方法,其特征在于,所述方法包括以下步骤:S1、物流场景信息初始化;

S2、物流任务打包:使用K-means算法确定最佳打包结果,其打包个数为k;

S3、取k辆可用无人车,匹配每个任务包的执行无人车;

S4、对每一辆无人车用离散粒子群算法确定其任务序列。

2.根据权利要求1所述的基于K-means和离散粒子群算法的多无人车任务分配方法,其特征在于,所述步骤S1包括任务信息初始化、仓库信息初始化以及无人车信息初始化。

3.根据权利要求1所述的基于K-means和离散粒子群算法的多无人车任务分配方法,其特征在于,所述步骤S2包括:S21、获取任务点数量和可用无人车数量,确定需要打包的任务包数量上限;

S22、使用K-means算法实现k个任务包的打包结果;

S23、根据k个任务包的打包结果计算其类外距、类内距和相似度,取最小的相似度值所对应的k值和打包方案,其中类外距为每个任务包中心到全任务包中心的距离值之和,类内距为每个任务包中所含任务点到该任务包中心的距离值之和,相似度为类外距和类内距之和。

4.根据权利要求3所述的基于K-means和离散粒子群算法的多无人车任务分配方法,其特征在于,所述步骤S22包括:step 1:随机初始化k个任务包的包中心a1(x1,y1),a2(x2,y2),...,ak(xk,yk);

step 2:对于每个任务点Task(x,y,id),将其归为距离最近的任务包中心aj(xj,yj)所在的任务包j中,该划分规则满足如下公式:其中,labelid为任务点Task(x,y,id)的包划分、Task.x表示任务点的地理纬度、Task.y表示任务点的地理经度、Task.id表示任务点的编号、aj(xj,yj)表示第j个任务包中心、i从1到2表示一个纬度一个经度、sub是指求这个aj的下标j;

step 3:更新每个任务包的包中心aj(xj,yj),新包中心的属性值为隶属该任务包的所有任务点的属性值均值,满足如下公式:其中,aj(xj,yj)表示新的包中心、cj是新的任务包划分、n_cj指的是新任务包cj内所含的任务点个数;

step 4:当各包中心变化率小于某给定值,或达到最大迭代次数时,结束本次打包,反之,回到step 2。

5.根据权利要求1所述的基于K-means和离散粒子群算法的多无人车任务分配方法,其特征在于,所述步骤S4通过离散化更新粒子速度和位置,计算目标函数的值,从而确定使无人车付出代价最小的任务序列。

6.根据权利要求5所述的基于K-means和离散粒子群算法的多无人车任务分配方法,其特征在于,所述目标函数包括:其中,runi,j表示第i个阶段行驶到任务点j的时长、Xi,j表示第i个阶段是否执行任务j、delayi,j表示第i个阶段执行第j个任务点的时延、performi,j表示第i个阶段执行第j个任务的执行时间。

7.根据权利要求5所述的基于K-means和离散粒子群算法的多无人车任务分配方法,其特征在于,所述离散化更新粒子速度和位置按照以下更新公式:其中,Xt为粒子,表示任务包中任务点的当前排列方式,Vt是随机生成的循环右移向量,即根据该向量对任务序列进行循环右移操作,Pbestt是个体极值,Gbestt是全局极值,指转化成个体极值所需的循环右移向量集合, 指转化成全局极值所需的循环右移向量集合,R1、R2分别表示随机性选择循环右移向量。