1.一种基于多种群进化算法的带时间窗的车辆路径规划方法,其特征是应用于由1个仓库c0、N个客户以及K辆运输车所组成的配送服务区域中,在所述配送服务区域中,将N个客户记为c={c1,c2,…,ci,…,cN},1≤i≤N;ci表示第i个客户,令第i个客户ci的时间窗记为[ei,li],其中,ei和li分别表示对第i个客户ci服务的最早开始时间和最晚结束时间;令第i个客户ci所需要的服务时长记为si,车辆到达第i个客户ci的时间点记为ti,车辆从第i个客户ci到达第j个客户cj的时间记为Tij,wi表示车辆在第i个客户ci的等待时间;
在所述配送服务区域中将所述仓库c0和N个客户分别作为节点,记为点集V={c0,c1,c2,…,ci,…,cN};将所述仓库c0与各个客户之间以及N个客户之间直线路径作为边集E={|i,j∈V,i≠j};其中,表示任意第i个节点和第j个节点之间的直线路径;记所述直线路径的距离矩阵为dij;假设K辆运输车的最大载重量均为Q;假设所有的车辆均是以仓库c0为起点和终点;所述车辆路径规划方法是按如下步骤进行:步骤1、建立带时间窗的车辆路径规划模型forigin:
步骤1.1、利用式(1)建立带时间窗的车辆路径规划的第一目标函数f1:f1=K (1)
步骤1.2、利用式(2)建立带时间窗的车辆路径规划的第二目标函数f2:式(2)表示所有车辆的总行驶路程,其中,aijk表示第k辆运输车是否经过第i个节点和第j个节点之间的直线路径;若aijk=1,则表示第k辆运输车经过第i个节点和第j个节点之间的直线路径,若aijk=0,则表示第k辆运输车不经过第i个节点和第j个节点之间的直线路径;
步骤1.3、利用式(3)建立总目标函数f:
min f=(f1,f2) (3)
步骤1.4、利用式(4)‑式(10)构建约束条件:
tj=ti+wi+si+Tij for i,j∈{1,...,N},i≠j (9)ei≤ti+wi≤li for i∈{1,...,N} (10)式(4)表示所述运输车从仓库c0出发后,完成服务任务后必须全部返回仓库c0;当ai0k=
1时,表示第k辆运输车经过所述第i个节点和仓库c0之间的直线路径<i,0>;当a0jk=1时,表示第k辆运输车经过所述仓库c0和第j个节点之间的直线路径<0,j>;
式(5)表示在每个客户处的第k辆运输车的出度等于入度;当ajik=1时,表示第k辆运输车经过所述第j个节点与第i个节点之间的直线路径<j,i>;当ajik=0时,表示第k辆运输车不经过所述第j个节点与第i个节点之间的直线路径<j,i>;
式(6)和式(7)表示每个客户都能被访问到并且仅被访问一次;
式(8)表示在所述第k辆运输车行驶路径上的容积约束;在第k辆运输车的服务路线上的所有客户需求之和不能多于运输车的最大载重量Q;
式(9)和式(10)表示时间窗约束,运输车要保证在要求的时间窗口内完成对客户的服务,tj表示车辆到达第j个客户cj的时间点;且ti‑ei表示违反程度;
步骤2、从车辆路径规划模型forigin中去除时间窗约束后构成辅助车辆路径规划模型fhelp;
步骤3、基于辅助车辆路径规划模型fhelp,利用双种群协同进化算法求解车辆路径规划模型forigin;
步骤3.1:初始化大小均为N的两个种群Population1与Population2;其中,两个种群中的每个个体均由所有客户的下标序列组成,并根据运输车的最大载重量在客户的需求达到最大载重量时在下标序列中插入0作为不同路线的分隔符;
步骤3.2、根据式(1)和式(2)计算第一种群Population1中每个个体在车辆路径规划模型forigin下的目标函数值,并根据式(9)和式(10)计算每辆车到达指定客户的时间点以及时间窗约束的违反程度;
步骤3.3、根据式(1)和式(2)计算第二种群Population2中每个个体在辅助车辆路径规划模型fhelp下的目标函数值;
步骤3.4、定义当前迭代次数t,并初始化t=1;设置最大迭代次数为tmax;以第一种群Population1作为第t代种群 以第二种群Population2作为第t代辅助种群步骤3.5、交配池选择:步骤3.5.1、采用NSGA‑Ⅱ算法中的交配池选择方案,对第t代种群 中的个体根据其目标函数值和时间窗约束进行非支配排序,并对不满足时间窗约束的个体在其每一维的目标值上加上其违反程度后再进行非支配排序;再计算排序后的个体的拥挤距离后进行二元锦标赛选择,直至选出N/2个个体作为第t代父代并记作步骤3.5.2、采用NSGA‑Ⅱ算法中的交配池选择方案,对第t代辅助种群 中的个体根据目标函数值进行非支配排序并计算拥挤距离后,再进行二元锦标赛选择,直至选出N/2个个体作为第t代辅助父代并记作步骤3.6、产生子代;
步骤3.6.1、对第t代父代 中的个体执行基于序列的遗传算子以产生大小为N/2的第t代子代种群步骤3.6.2、对第t代辅助父代 中的个体执行基于序列的遗传算子以产生大小为N/2的第t代辅助子代种群步骤3.7、合并种群:
步骤3.7.1、将 与 合并组成临时种群Population'1;
步骤3.7.2、将 与 合并组成临时辅助种群Population
'2;
步骤3.8、评价种群:
步骤3.8.1、根据式(1)和式(2)计算临时种群Population'1中每个个体在车辆路径规划模型forigin下的目标函数值,并根据式(9)和式(10)计算每辆车到达指定客户的时间点以及时间窗约束的违反程度,并将违反程度为零的个体作为可行解;
步骤3.8.2根据式(1)和式(2)计算临时辅助种群Population'2中每个个体在辅助车辆路径规划模型fhelp下的目标函数值;
步骤3.9、环境选择:
步骤3.9.1、对临时种群Population'1中的每个个体进行非支配排序,并对不满足时间窗约束的个体在其每一维的目标值上加上其违反程度后再进行非支配排序;
步骤3.9.2、按照非支配等级从高到低的顺序依次选取每个等级的个体并判断所选取的所有等级中的个体总数量是否小于N,若小于,则重复执行步骤3.9.2,否则,执行步骤
3.9.3;
步骤3.9.3、对当前所选取等级中的个体计算拥挤距离,并删除拥挤距离最小的个体后,判断所有等级中的个体总数量是否等于N,若是,则组成第t+1代种群 否则,重复执行步骤3.9.3、直到所有等级中的个体数量为N为止;
步骤3.9.4、对临时种群Population'2中的个体进行非支配排序;
步骤3.9.5、按照非支配等级从高到低的顺序依次选取每个等级的个体,并判断所选取的所有等级中的个体总数量是否小于N,若小于,则重复执行步骤3.9.5,否则,执行步骤
3.9.6;
步骤3.9.6、对当前所选取等级中的个体计算拥挤距离,并删除拥挤距离最小的个体后,判断所有等级中的个体总数量是否等于N,若是,则组成第t+1代种群 否则,重复执行步骤3.9.6、直到所有等级中的个体数量为N为止;
步骤3.10、判断t与阈值δ的余数是否为“0”,若是执行局部搜索,否则,执行步骤3.11;
步骤3.11、将t+1赋值给t,判断t>tmax是否成立,若成立,则将第tmax代种群中非支配等级最高的个体作为路径规划的最优方案;否则返回到步骤3.5顺序执行。
2.根据权利要求1所述的基于多种群进化算法的带时间窗的车辆路径规划方法,其特征是,所述步骤3.10中的局部搜索是按如下过程进行:步骤3.10.1、将每个客户的邻域客户定义为距离自身最近的前n个客户组成的区域;
步骤3.10.2、定义随机数为rand,若rand≤1/3,则执行步骤3.10.3;否则,若2/3≥rand>1/3,则执行步骤3.10.4;否则,执行步骤3.10.5;
步骤3.10.3、对第t+1代种群 以及第t+1代辅助种群 中的每个个体执行以下操作:
个体从自身的客户下标序列中随机选择两条路线,然后依次判断第一条路线上的第i个客户是否与第二条路线上的客户为邻居客户,若是,则在满足车辆最大载重量的情况下将两个客户进行交换,计算交换后的总行驶距离以及约束违反,是否比未交换时的总行驶距离更短且约束违反为0,若是,则将交换后的个体替换原来的个体并退出局部搜索;否则,对第一条路线上的第i+1个客户进行判断,直到第一条路线上的所有客户遍历完毕;
步骤3.10.4、对第t+1代种群 以及第t+1代辅助种群 的每个个体执行以下操作:
个体从自身的客户下标序列中随机选择两条路线,然后依次判断第一条路线上的第i个客户是否与第二条路线上的客户为邻居客户,若是,则在满足车辆最大载重量的情况下在邻居客户后插入第i个客户,并计算交换后的总行驶距离以及约束违反是否比未插入时的总行驶距离更短且约束违反为0,若是,则将插入后的个体替换原来的个体并退出局部搜索;否则,对第一条路线上的第i+1个客户进行判断,直到第一条路线上的所有客户遍历完毕;
步骤3.10.5、对第t+1代种群 以及第t+1代辅助种群 的每个个体执行以下操作:
个体从自身的客户下标序列中随机选择一条路线,然后调换所选择的路线上的第i个客户与第i+1个客户的位置,并计算交换后的总行驶距离以及约束违反,是否比未调换时的总行驶距离更短且约束违反为0,若是,则将交换后的个体替换原来的个体并退出局部搜索;否则,对第一条路线上的第i+1个客户进行判断,直到所选择的路线上的所有客户遍历完毕。