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

摘要:

权利要求书:

1.一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,包括如下步骤:

1)通过启发式构造方法生成初始种群,并将非占优解保存到存档解集S中,令Count=

0,对于所有生成的非占优解,按照各个目标函数进行评估;

2)初始化邻域操作库lib、邻域操作池pool、概率矩阵NS和邻域操作质量矩阵NQ;

3)从存档解集S中随机选择一个解X,对解X的各个目标函数值进行归一化处理来评估其优化潜力,并根据其潜力值确定选择概率;

4)根据各个目标的选择概率自适应选择一个优化目标作为当前搜索方向,记选中的目标为obj,若obj=1,则通过用于减少调度使用的车辆数目的邻域操作对解X在当前搜索方向上进行局部搜索,得到解X′,并更新存档解集S,进入步骤7);否则,进入步骤5);

5)根据概率矩阵NS,自适应选择邻域操作Nk,利用邻域操作Nk对解X进行局部搜索,得到解X′并更新存档解集S、邻域操作质量矩阵NQ和概率矩阵NS;若存档解集S有发生更新,则Count=0,进入步骤7);否则Count=Count+1,进入步骤6);

6)判断Count>limit是否成立,limit为预设的阀值,若是,则触发邻域操作动态调整策略,进入步骤7);否则,直接进入步骤7);

7)判断是否满足终止条件,若否,则返回步骤3);若是,程序结束,输出存档解集S中的所有解。

2.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述按照各个目标函数进行评估,各个目标函数包括:f1=|R|

f3=max{Ti|i=1,…,R}

其中,f1表示调度使用的车辆数目,R表示路径集合;f2表示总行驶距离,Di表示第i条路径的行驶距离;f3表示所有路径中,最长的行驶时间,Ti表示第i条路径的行驶时间;f4表示因车辆早到,所有车辆的等待时间之和,Wi表示第i条路径上的所有客户点的等待时间总和;f5表示因车辆迟到,所有客户点的延误时间之和,TDi表示第i条路径上的所有客户点的延迟时间总和。

3.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤2)包括选择8个常用的邻域操作加入到邻域操作库lib中,从邻域操作库lib中随机选择L个不同邻域操作加入到邻域操作池pool中,L<8,令NSk,j=1/L,NQk,j=0,其中k=1,2,...,5,j=1,2,...,L。

4.如权利要求2所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤3)中,归一化如下公式所示:其中,fk为当前解X的第k个目标函数值, 是由存档解集S中

所有解的各目标的最小值构成的向量,而 是存档解集S中所

有解的各目标的最大值构成的向量。

5.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤4)中,将解X的各个目标归一化的值作为该目标的选择概率,根据各目标的选择概率,利用轮盘赌方法选择一个目标作为解X的优化方向,记选中的目标为obj。

6.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤5)中,根据概率矩阵NS中第obj-1行中各个邻域操作对应的概率值,利用轮盘赌方法从邻域操作池pool中选择一个邻域操作,记为Nk。

7.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤5)中,根据解X′更新邻域操作质量矩阵NQ的第k列,并根据邻域操作质量矩阵NQ计算概率矩阵NS。

8.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤6)中,所述触发邻域操作动态调整策略包括:根据概率矩阵NS,从邻域操作池pool中移除表现最差的邻域操作,将其放回邻域操作库lib中,并从邻域操作库lib中随机选取一个当前未使用的邻域操作添加到邻域操作池pool,Count=0,重新初始化概率矩阵NS和邻域操作质量矩阵NQ。

9.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤7)中,所述终止条件即运行时间是否大于预设的计算时间。