1.一种基于启发式粒子群算法的物流车辆低碳路线规划方法,其特征在于,包括以下步骤:
S1,读取路线规划信息,定义优化目标,设定约束条件:所述路线规划信息包括物流车辆需要访问的客户点数量T、客户具体坐标以及客户所需的物品重量;所述优化目标为所规划路线中车辆的碳排放量最少;
S2,初始化基于启发信息的改进粒子群算法参数:设置改进粒子群算法进化种群规模为N、最大迭代次数为G、邻域搜索最大规模Y、逆转变异选择概率Pr、优先卸货客户点比例α、相似度阈值K设置迭代计数器t=0;
S3,生成初始候选种群,并计算适应度:采用整数编码,随机生成N个个体,每个个体表示物流车辆前往客户点送货的顺序:X={x1,x2,L,xT}
其中,xi(i=1,2,L,T)表示被服务客户点的标号;计算每个个体的目标值f(X):其中,dij表示客户i与客户j之间的距离,ε(Mij)表示客户点之间载重与碳排放系数的函数关系:
则个体的适应度为F(X):
选出种群中的全局极值和每个个体的个体极值;
S4,采用个体多元变异策略对所有个体进行变异:S5,贪婪交叉:
变异后的个体分别与个体极值,全局极值依次贪婪交叉产生新个体,若新生成个体的适应度值更优,则接受新个体,否则,不接受新个体;
S6,更新个体极值和全局极值:根据优胜劣汰的规则在每次迭代中更新个体极值和全局极值;
S7,基于优先卸货的启发信息对个体极值进行局部搜索:首先,从配送中心出发,依次选择距离前一点最近的客户优先服务,直至替代原个体极值的前α*T位,然后,用缺少客户依次替代重复客户,在剩下的(1‑α)*T位中随机产生两个变异点,并在这两点之间进行逆转变异,产生新的个体极值;
S8,基于种群的相似度对全局极值进行精细化搜索:将2‑opt算子作用在全局极值上,接着判断种群中每个个体与全局极值的相似程度,若最小的相似度大于给定的阈值K,则利用点插法对全局极值进一步搜索,t=t+1;
S9,终止准则判断:
若t>G则终止迭代,输出适应度最优的个体,该个体为规划好的访问客户的顺序,否则t=t+1,转步骤S4。
2.根据权利要求1所述的基于启发式粒子群算法的物流车辆低碳路线规划方法,其特征在于,步骤S1中,所述读取路线规划信息,定义优化目标,设定约束条件的过程包括以下步骤:
设客户的平面坐标信息{(Ax1,Ay1),(Ax2,Ay2),…,(AxT,AyT)},问题的规模表示访问客户的数量T,则不同客户间距离为欧式距离计算公式,其定义为:其中,dij表示客户i与客户j之间的距离;
定义优化目标主体为物流车辆在规划路线中的碳排放量,其定义为:其中,ε(Mij)表示客户点之间载重与碳排放系数的函数关系。
定义约束条件包括以下三个:
(1)每个客户必须被服务且仅被服务一次,即:(2)物流车辆从配送中心出发,最终回到该配送中心,即:(3)物流车不得超载,且各客户节点总的需求量不能超过装载量,即:其中,mi(i=2,3,…,n)表示除仓库点之外每个客户点的需求量,M1表示物流车在从仓库出发时的装载量,M0表示物流车的最大装载量限制。
3.根据权利要求1所述的基于启发式粒子群算法的物流车辆低碳路线规划方法,其特征在于,步骤S4中,变异方式采取交换变异、逆转变异以及插入变异,并为三种变异方式赋予选择概率,基于轮盘赌策略为个体选择变异方式;
采用个体多元变异策略对所有个体进行变异的实现步骤如下:S41,根据输入的逆转变异概率Pr,计算交换变异和插入变异的概率Ps和Pi,其中,S42,基于轮盘赌方式选择变异方式的序号;
S43,如果选择变异方式1,则对个体进行交换变异;
S44,如果选择变异方式2,那么对个体进行逆转变异;
S45,如果选择变异方式3,则对个体进行插入变异;
S46,输出变异后的新个体。
4.根据权利要求1所述的基于启发式粒子群算法的物流车辆低碳路线规划方法,其特征在于,步骤S5中,所述贪婪交叉算子的实现步骤为:S51,确定需要交叉的个体X、个体极值Xpbest以及全局极值Xgbest;
S52,以仓库点作为起始客户S,选择客户S在Xpbest中的左侧客户SLp和右侧客户SRp,在X中左侧客户SLX和右侧客户SRX作为下个访问的候选客户;
S53,在候选客户集{SLp,SRp,SLX,SRX}中,选择距离客户S’,使得由S’和S行成的路径碳排放量最小;
S54,如果客户S’∈{SLp,SLX},执行S55,否则执行S56;
S55,在X和Xpbest中删除S,将S’作为首个客户S,仅从S左侧客户{SLp,SLX}中选择新的S’作为下一服务客户点,使得S’与S形成的路径碳排放量最小,重复执行S55,直至服务完所有客户,即生成新解Xnew;
S56,在X和Xpbest中删除S,将S’作为首个客户S,仅从S右侧客户{SRp,SRX}中选择新的S’作为下一服务客户点,使得S’与S形成的路径碳排放量最小,重复执行S55,直至服务完所有客户,即生成新解Xnew;
S57,将新解Xnew与全局极值Xgbest再一次进行贪婪交叉,生成新解。
5.根据权利要求1所述的基于启发式粒子群算法的物流车辆低碳路线规划方法,其特征在于,步骤S7中,所述对个体极值局部搜索的具体实现步骤如下:S71,确定个体极值Xpbest、优先服务客户点比例α以及客户规模T;
S72,从配送中心出发,依次选择距离前一点最近的客户点优先服务,直至确定好前α*T个客户点,并用它们替代原个体极值的前α*T位;
S73,确定当前个体极值回路中的缺少客户和重复客户,并用缺少客户依次替代重复客户;
S74,在剩下的(1‑α)*T位中随机产生两个变异点,并在这两点之间进行逆转变异,产生新的个体极值。
6.根据权利要求1述的基于启发式粒子群算法的物流车辆低碳路线规划方法,其特征在于,步骤S8中,所述考虑种群同化程度的全局极值精细化搜索,具体实现步骤为:S81,确定全局极值Xgbest、问题规模T和相似度阈值K;
S82,将2‑opt算子作用在全局极值上,通过随机交换两条边的方式,能够有效打开在回路中的交叉路线;
S83,接着判断种群中每个个体与全局极值的相似程度;
S84,若最小的相似度大于给定的阈值K,则利用点插法对全局极值进一步搜索,通过移动某一点的位置,改变三条边,有助于寻找在无交叉情况下的最优解决方案;
S85,输出通过精细化搜索后的全局极值。