1.一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,包括如下步骤:
1)通过启发式构造方法生成初始种群,并将非占优解保存到存档解集S中,令Count=
0,对于所有生成的非占优解,按照各个目标函数进行评估,各个目标函数包括:f1=|R|
f3=max{Ti|i=1,…,R}
其中,f1表示调度使用的车辆数目,R表示路径集合;f2表示总行驶距离,Di表示第i条路径的行驶距离;f3表示所有路径中,最长的行驶时间,Ti表示第i条路径的行驶时间;f4表示因车辆早到,所有车辆的等待时间之和,Wi表示第i条路径上的所有客户点的等待时间总和;f5表示因车辆迟到,所有客户点的延误时间之和,TDi表示第i条路径上的所有客户点的延迟时间总和;
2)初始化邻域操作库lib、邻域操作池pool、概率矩阵NS和邻域操作质量矩阵NQ;
3)从存档解集S中随机选择一个解X,对解X的各个目标函数值进行归一化处理来评估其优化潜力,并根据其潜力值确定选择概率;
4)根据各个目标的选择概率自适应选择一个优化目标作为当前搜索方向,记选中的目标为obj,若obj=1,则通过用于减少调度使用的车辆数目的邻域操作对解X在当前搜索方向上进行局部搜索,得到解X′,并更新存档解集S,进入步骤7);否则,进入步骤5);
5)根据概率矩阵NS中第obj‑1行中各个邻域操作对应的概率值,利用轮盘赌方法从邻域操作池pool中选择一个邻域操作,记为Nk,利用邻域操作Nk对解X进行局部搜索,得到解X′并更新存档解集S、邻域操作质量矩阵NQ的第k列,并根据邻域操作质量矩阵NQ计算概率矩阵NS;若存档解集S有发生更新,则Count=0,进入步骤7);否则Count=Count+1,进入步骤
6);
6)判断Count>limit是否成立,limit为预设的阈值 ,若是,则触发邻域操作动态调整策略,所述触发邻域操作动态调整策略包括:根据概率矩阵NS,从邻域操作池pool中移除表现最差的邻域操作,将其放回邻域操作库lib中,并从邻域操作库lib中随机选取一个当前未使用的邻域操作添加到邻域操作池pool,Count=0,重新初始化概率矩阵NS和邻域操作质量矩阵NQ,进入步骤7);否则,直接进入步骤7);
7)判断是否满足终止条件,若否,则返回步骤3);若是,程序结束,输出存档解集S中的所有解;
其中,存档更新策略如下:通过邻域操作产生新的解X’,将其与存档解集S中的所有解进行非占优比较,如果存档解集S中存在劣于X’的解,则将劣解从存档解集S中删除;如果X’劣于存档解集S中的解,则将X’丢弃;否则,将X’加入到存档解集S中;
当存档解集S中解的数量超出|S|的上限时,使用平行格坐标系统对|S|中的所有解进行密度估计,并将密度最大的解从存档解集S中移除;具体过程如下:首先,将存档解集S中的每一个解Xi与一个标识数组Bi={bi1,...,bi5}相对应,标识数组中的元素bim的计算公式如下:其中, 和 分别是存档解集S中所有解在第m个目标上的最大值和最小值,|S|表示存档解集S中解的数量,当 时,则bim取值为1;
接着,根据每个解的标识数组,计算存档解集S中任意两个解Xi,Xj之间的平行格距离PCD(Xi,Xj),计算方式如下:然后,根据两两解之间的平行格距离,计算每个解的密度Density(Xi),计算方式如下:最后,比较所有解的密度,将密度最大的解从存档解集中删除。
2.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤2)包括选择8个常用的邻域操作加入到邻域操作库lib中,从邻域操作库lib中随机选择L个不同邻域操作加入到邻域操作池pool中,L<8,令NSk,j=1/L,NQk,j=0,其中k=1,2,…,5,j=1,2,…,L。
3.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤3)中,归一化如下公式所示:其中,fk为当前解X的第k个目标函数值, 是由存档解集S中
所有解的各目标的最小值构成的向量,而 是存档解集S中所
有解的各目标的最大值构成的向量。
4.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤4)中,将解X的各个目标归一化的值作为该目标的选择概率,根据各目标的选择概率,利用轮盘赌方法选择一个目标作为解X的优化方向,记选中的目标为obj。
5.如权利要求1所述的一种求解带时间窗车辆路径问题的自适应多目标优化方法,其特征在于,所述步骤7)中,所述终止条件即运行时间是否大于预设的计算时间。