1.一种基于多目标烟花算法的物流车辆低碳路线规划方法,其特征在于,包括以下步骤:
S1,读取问题输入的信息,定义优化目标,设定约束条件:所述问题输入的信息包括车辆需要访问的客户点数量n和具体坐标信息、燃油排放参数、耗油量、客户所需的物品重量以及车辆的自重;
所述优化目标为所规划路线中所有车辆的总碳排放量和子回路最长耗时最小;
所述约束条件包括:
(1)每个客户必须被服务且仅被服务一次;
(2)对于每个被服务的客户点,一定会有一辆车从某个地点行驶到该客户点,并从该客户点离开;
(3)保证每辆车的行驶路线中没有子回路;
(4)车辆装载货物不能超过车辆最大容量;
(5)配送中心出发的车辆数不能超过可用车辆数,且车辆从配送中心出发最终回到该处;
S2,初始化区域增强型多目标烟花算法参数:设置区域增强型多目标烟花算法的烟花种群POP大小为N、最大评价次数为Evamax、可用车数量K、决策变量维数为n、目标个数为m、建立外部档案archive,并将烟花种群放入外部档案,设置评价次数计数器Eva=0;
S3,生成初始烟花种群,并计算两个优化目标值:采用整数编码,随机生成N个个体,每个个体表示车辆前往客户点送货的顺序:X={x1,x2,…,xn}
其中,xi(i=1,2,…,n)表示被服务客户点的标号计算每个个体的目标向量;
S4,采用部分映射爆炸算子产生爆炸火花种群EPOP:每个烟花根据4种不同的爆炸半径通过部分映射交叉操作产生8个爆炸火花:S5,调整子回路任务的混合变异算子对烟花种群进行变异操作生成变异火花种群GPOP:
将每个烟花按以下两种变异方式对子回路任务进行调整:一种是改变配送中心位置的子回路长度变异算子,另一种是交换烟花编码中随机两点的子回路负载变异算子,生成变异火花种群GPOP;
S6,目标驱动的启发式扩展搜索:将EPOP∪GPOP中的非支配解加入NDS,分别利用各优化目标包含的启发信息,对当前爆炸火花和变异火花中的非支配解集进行目标驱动的启发式扩展搜索,得到扩展搜索火花群体SPOP;
S7,更新烟花种群和外部档案:根据Pareto支配概念,使用NDS和SPOP更新烟花种群POP,根据ε支配概念,使用NDS和SPOP更新外部档案archive,若超过外部档案的最大规模Lmax,则从archive中依次删除拥挤距离最小的个体,在archive和POP中分别随机选择N/2的个体组成下一代烟花群体;若archive中个体数量小于N/2,则用POP中的个体补充;在选出的烟花种群中随机选择一个个体,将与其相似度高于80%的个体进行随机长度的循环移位操作;
S8,选择策略:
通过协同选择策略选择烟花种群;
S9,终止准则判断:
若Eva>Evamax则终止迭代,输出可行解集;否则,Eva相应增加,转步骤S4。
2.根据权利要求1所述的一种基于多目标烟花算法的物流车辆低碳路线规划方法,其特征在于,步骤S1中,所述读取问题输入的信息,定义优化目标,设定约束条件的过程包括以下步骤:
设客户的平面坐标信息{(Ax1,Ay1),(Ax2,Ay2),…,(Axn,Ayn)},问题的规模表示访问客户的数量n,则不同客户间距离为欧式距离计算公式,其定义为:其中,dij表示客户i与客户j之间的距离;
定义优化目标一为物流车辆在规划路线中的碳排放量,其定义为:定义优化目标二为子回路最长耗时,其定义为:其中,目标一为最小化所有车辆的总碳排放量,目标二为最小化子回路最长耗时;计算某路段碳排放量时同时考虑行驶距离dij、速度vij、自重w、载重lij和路面状况对车辆耗油量的影响,通过燃油排放参数FE与耗油量的乘积获得车辆在该路段行驶产生的碳排放量;a为车辆行驶加速度;g为重力加速度常量;θij为从客户i到客户这一路段的路面坡度;Cr为滚动阻力系数;Cd为牵引力系数;A为车辆正面表面积;ρ表示空气密度;dij表示客户i与客户j之间的距离;
定义约束条件包括以下五个:
(1)每个客户必须被服务且仅被服务一次,即:(2)表示每个客户点被服务时,一定会有一辆车从某个地点行驶到该客户点,并从该客户点离开,即:
(3)子回路消除约束,保证每辆车的行驶路线中没有子回路,即:(4)车辆容量约束,即:
(5)配送中心出发的车辆数小于或等于可用车辆数,即:
3.根据权利要求1所述的一种基于多目标烟花算法的物流车辆低碳路线规划方法,其特征在于,步骤S4中,所述采用部分映射爆炸算子产生爆炸火花的实现步骤如下:S41,先将烟花种群中每个烟花的两个目标值分别进行归一化;
S42,两目标归一化后的结果相乘,得到N个乘积;
S43,根据第i(i=1,2,…,N)个乘积在N个乘积中所占的比例来计算第i个烟花需要变化的编号个数,其计算公式如下:其中,fs(Xi)、fsmax和fsmin分别表示第i个烟花的第s个目标值,所有烟花在第s个目标上的最大值和最小值;M(Xi)为各目标归一化后结果的乘积;Mmax和Mmin为N个烟花对应乘积中的最大值和最小值;Ai表示第i个烟花的爆炸半径,[·]表示四舍五入取整操作;
S44,令每个烟花产生4种爆炸半径不同的爆炸火花,其爆炸半径分别为:ri1=Ai,
S45,每个爆炸火花的爆炸半径确定后,对每个烟花,将编码中的配送中心0删除,得到一串客户的访问序列;随机选取4个其它烟花的客户访问序列,分别与当前烟花进行部分映射交叉操作,ri1,ri2,ri3,ri4分别为每次交叉所选取的片段长度;
S46,部分映射交叉操作中,随机选取一个起始点,根据爆炸半径得到两个交换片段,即对应编号的映射关系;
S47,交换两个片段的位置,得到新序列P′1和P′2;将P′1和P′2中非交换序列与交换片段重复的序号进行映射,直到序列中无重复序号,得到最终爆炸火花的客户访问序列S1和S2;
S48,将序列S1和S2按X1和X2的配送中心位置进行解码,生成新的爆炸火花E1和E2。
4.根据权利要求1所述的一种基于多目标烟花算法的物流车辆低碳路线规划方法,其特征在于,步骤S5中,所述采用调整子回路任务的混合变异算子的实现步骤如下:S51,确定需要变异的个体X;
S52,对个体X进行子回路长度变异算子,将烟花个体的编码中除序列首尾的其它位置的“0”随机插入客户访问序列中;
S53,对个体X进行子回路负载变异算子,并随机选择烟花编码中的两个编号进行互换。
5.根据权利要求1所述的一种基于多目标烟花算法的物流车辆低碳路线规划方法,其特征在于,步骤S6中,所述采用目标驱动的启发式扩展搜索的实现步骤如下:S61,确定需要进行操作个体X,并对个体X进行解码,得到车辆路径;
S62,确定需要启发式扩展搜索的的子回路Rk;
S63,以配送中心作为起始客户S,选择子回路Rk中的客户S’作为下一服务客户点,使得由S’和S行成的路径碳排放量最小;
S64,在Rk中删除S,将S’作为首个客户S选择子回路Rk中的客户S’作为下一服务客户点,使得由S’和S行成的路径碳排放量最小,重复执行S64,直至服务完所有客户,生成新路径Rk’,替换个体X的路径Rk,得到新解XNEW1;
S65,确定个体X中需要启发式扩展搜索的的子回路Rp;
S66,以配送中心作为起始客户S,选择子回路Rp中的客户S’作为下一服务客户点,使得由S’和S行成的路径耗时最短;
S67,在Rp中删除S,将S’作为首个客户S选择子回路Rp中的客户S’作为下一服务客户点,使得由S’和S行成的路径耗时最短,重复执行S67,直至服务完所有客户,生成新路径Rp’,替换个体X的路径Rp,得到新解XNEW2。