一种基于启发式粒子群算法的物流车辆低碳路线规划方法与流程

1.本发明涉及路径规划技术领域，具体而言涉及一种基于启发式粒子群算法的物流车辆低碳路线规划方法。


背景技术：

2.众所周知，二氧化碳(co2)是引起温室效应的主要因素，美国国家海洋和大气局 (noaa)称，在所有造成全球变暖的温室气体中，co2占63％。根据国际能源署(iea) 的数据，2019年全球碳排放量的增长约为330亿吨。除了发电供热，全球第二大二氧化碳排放量贡献者便是交通运输，其中交通运输产生的二氧化碳占全球二氧化碳排放量的 23％，而交通运输总碳排放量的主要来源是道路运输。目前，关于车辆道路运输的研究大多将总的行驶距离最短作为优化目标。然而，随着环境状况每日愈下，污染物排放和燃料消耗所造成的环境成本越来越受到重视，人们在交通运输领域也开始考虑“绿色物流”的践行。国家在“十四五规划纲要”中也提出了广泛形成绿色生产生活方式的要求和碳排放总量持续减少，生态环境持续改善的目标。为响应这一号召，近年来，本发明将道路运输问题与环境问题相结合，以降低能源消耗，减少co2排放，缓解温室效应。
3.路径规划问题属于np难题，随着问题规模的增加，精确算法无法在有效时间获得满足要求的解，为此，学者们提出了群智能优化算法。kennedy和eberhart于1995年提出的粒子群算法(pso)便是其中的典型代表。它通过初始化、适应度评价、速度和位置更新等阶段产生较优后代，实现进化迭代。与其余群智能算法相比，pso依靠粒子速度完成搜索，并且在迭代进化中只有最优粒子把信息传递给其他粒子，搜索速度更快。此外，pso具有记忆性、自我学习能力和社会学习能力，搜索精度更高。基于启发信息的粒子群算法是粒子群算法的改进版本，它将物流车辆运输的问题信息与粒子群算法的结构特点相融合，该算法基本步骤如下：采用整数编码的方式，随机生成初始种群，计算每个个体的适应度值，确定个体的个体极值和全局极值；采用个体多元变异策略对所有个体进行变异，变异后的粒子分别与个体极值，全局极值依次贪婪交叉产生新个体；更新个体极值和全局极值；基于优先卸货的启发信息对个体极值进行局部搜索：首先，从配送中心出发，依次选择距离前一点最近的客户优先卸货，直至替代原个体极值的前α*n位，用缺少客户依次替代重复客户，在剩下的(1
‑
α)*n位中随机产生两个变异点，并在这两点之间进行逆转变异，产生新的个体极值；基于种群的相似度对全局极值进行精细化搜索：将2
‑
opt算子作用在全局极值上，接着判断种群中每个个体与全局极值的相似程度。若最小的相似度大于给定的阈值k，则利用点插法对全局极值进一步搜索。传统粒子群算法求解物流车辆低碳路线规划未利用问题特征，搜索极为盲目，收敛速度较慢，且传统粒子群算法具有易陷入局部最优，求解精度低等不足，综上，提出一种收敛效率更高且具有较强跳出局部最优能力的路线规划方法极为必要。


技术实现要素：

4.本发明目的在于提供一种基于启发式粒子群算法的物流车辆低碳路线规划方法，
能够极大地提高算法的收敛速度，具有较强的跳出局部最优的能力，从而快速规划出一条高效的碳排放量最少的路线。
5.为达成上述目的，本发明提出一种基于启发式粒子群算法的物流车辆低碳路线规划方法，包括以下步骤：
6.s1，读取路线规划的信息，定义优化目标，设定约束条件：
7.所述路线规划信息包括物流车辆需要访问的客户点数量t和具体坐标信息以及客户所需的物品重量；所述优化目标为所规划路线中车辆的碳排放量最少；所述约束条件为每个客户必须被服务且仅被服务一次，车辆不得超载且各客户节点总的需求量不能超过装载量且车辆从物流配送中心出发最终回到该处；
8.s2，初始化基于启发信息的改进粒子群算法参数：
9.设置改进粒子群算法进化种群规模为n、最大迭代次数为g、邻域搜索最大规模y、逆转变异选择概率p
r
、优先卸货客户点比例α、相似度阈值k设置迭代计数器t＝0；
10.s3，生成初始候选种群，并计算适应度：
11.采用整数编码，随机生成n个个体，每个个体表示物流车辆前往客户点送货的顺序：
12.x＝{x1,x2,l,x
t
}
13.其中，x
i
(i＝1,2,l,t)表示被服务客户点的标号；计算每个个体的目标值f(x)：
[0014][0015][0016]
其中，d
ij
表示客户i与客户j之间的距离，ε(m
ij
)表示客户点之间载重与碳排放系数的函数关系：
[0017][0018]
则个体的适应度为f(x)：
[0019][0020]
即个体的适应度越大则个体质量越好；选出种群中的全局极值和每个个体的个体极值；
[0021]
s4，采用个体多元变异策略对所有个体进行变异：
[0022]
为保持个体“惯性”，采取三种变异方式，即交换变异、逆转变异以及插入变异，为三种变异方式赋予选择概率，基于轮盘赌策略为个体选择变异方式；
[0023]
s5，贪婪交叉：
[0024]
变异后的个体分别与个体极值，全局极值依次贪婪交叉产生新个体，若新生成个体适应度值更优，则接受新个体，否则，不接受新个体；
[0025]
s6，更新个体极值和全局极值：
[0026]
根据优胜劣汰的规则在每次迭代中更新个体极值和全局极值；
[0027]
s7，基于优先卸货的启发信息对个体极值进行局部搜索：
[0028]
首先，从配送中心出发，依次选择距离前一点最近的客户优先服务，直至替代原个体极值的前α*n位，用缺少客户依次替代重复客户，在剩下的(1
‑
α)*n位中随机产生两个变异点，并在这两点之间进行逆转变异，产生新的个体极值；
[0029]
s8，基于种群的相似度对全局极值进行精细化搜索：
[0030]
将2
‑
opt算子作用在全局极值上，接着判断种群中每个个体与全局极值的相似程度。若最小的相似度大于给定的阈值k，则利用点插法对全局极值进一步搜索，t＝t 1；
[0031]
s9，终止准则判断：
[0032]
若t>g则终止迭代，输出适应度最优的个体，该个体为规划好的访问客户的顺序，否则t＝t 1，转步骤s4。
[0033]
步骤s1中，所述读取问题输入的信息，定义优化目标，设定约束条件的过程包括以下步骤：
[0034]
设客户的平面坐标信息{(a
x1
,a
y1
),(a
x2
,a
y2
),
…
,(a
xt
,a
yt
)}，问题的规模表示访问客户的数量t，则不同客户间距离为欧式距离计算公式，其定义为：
[0035][0036]
其中，d
ij
表示客户i与客户j之间的距离；
[0037]
定义优化目标主体为物流车辆在规划路线中的碳排放量，其定义为：
[0038][0039][0040][0041]
其中，ε(m
ij
)表示客户点之间载重与碳排放系数的函数关系。
[0042]
定义约束条件包括以下三个：
[0043]
(1)每个客户必须被服务且仅被服务一次，即：
[0044][0045]
(2)物流车辆从配送中心出发，最终回到该配送中心，即：
[0046][0047]
(3)物流车不得超载，且各客户节点总的需求量不能超过装载量，即：
[0048][0049]
其中，m
i
(i＝2,3,
…
,n)表示除仓库点之外每个客户点的需求量，m1表示物流车在从仓库出发时的装载量，m0表示物流车的最大装载量限制。
[0050]
步骤s4中，所述采用个体多元变异策略对所有个体进行变异的实现步骤如下：
[0051]
s41，根据输入的逆转变异概率p
r
，计算交换变异和插入变异的概率p
s
和p
i
，其中，
[0052]
s42，基于轮盘赌方式选择变异方式的序号；
[0053]
s43，如果选择变异方式1，则对个体进行交换变异；
[0054]
s44，如果选择变异方式2，那么对个体进行逆转变异；
[0055]
s45，如果选择变异方式3，则对个体进行插入变异；
[0056]
s46，输出变异后的新个体。
[0057]
步骤s5中，所述贪婪交叉算子的实现步骤为：
[0058]
s51，确定需要交叉的个体x、个体极值x
pbest
以及全局极值x
gbest
；
[0059]
s52，以仓库点作为起始客户s，选择客户s在x
pbest
中的左侧客户s
lp
和右侧客户 s
rp
，在x中左侧客户s
lx
和右侧客户s
rx
作为下个访问的候选客户；
[0060]
s53，在候选客户集{s
lp
,s
rp
,s
lx
,s
rx
}中，选择距离客户s’，使得由s’和s行成的路径碳排放量最小；
[0061]
s54，如果客户s’∈{s
lp
,s
lx
}，执行s55，否则执行s56；
[0062]
s55，在x和x
pbest
中删除s，将s’作为首个客户s，仅从s左侧客户{s
lp
,s
lx
}中选择新的s’作为下一服务客户点，使得s’与s形成的路径碳排放量最小，重复执行s55，直至服务完所有客户，即生成新解x
new
；
[0063]
s56，在x和x
pbest
中删除s，将s’作为首个客户s，仅从s右侧客户{s
rp
,s
rx
}中选择新的s’作为下一服务客户点，使得s’与s形成的路径碳排放量最小，重复执行s55，直至服务完所有客户，即生成新解x
new
；
[0064]
s57，以x和x
pbest
的贪婪交叉为例，将新解x
new
与全局极值x
gbest
再一次进行贪婪交叉，生成新解。
[0065]
步骤s7中，所述对个体极值局部搜索的方向是根据问题的启发信息的，具体实现步骤如下：
[0066]
s71，确定个体极值x
pbest
、优先服务客户点比例α以及客户规模t；
[0067]
s72，从配送中心出发，依次选择距离前一点最近的客户点优先服务，直至确定好前α*t个客户点，并用它们替代原个体极值的前α*t位；
[0068]
s73，确定当前个体极值回路中的缺少客户和重复客户，并用缺少客户依次替代重复客户；
[0069]
s74，在剩下的(1
‑
α)*t位中随机产生两个变异点，并在这两点之间进行逆转变异，产生新的个体极值。
[0070]
步骤s8中，所述考虑种群同化程度的全局极值精细化搜索，具体实现为：
[0071]
s81，确定全局极值x
gbest
、问题规模t和相似度阈值k；
[0072]
s82，将2
‑
opt算子作用在全局极值上，通过随机交换两条边的方式，能够有效打开在回路中的交叉路线；
[0073]
s83，接着判断种群中每个个体与全局极值的相似程度；
[0074]
s84，若最小的相似度大于给定的阈值k，则利用点插法对全局极值进一步搜索，通过移动某一点的位置，改变三条边，有助于寻找在无交叉情况下的最优解决方案；
[0075]
s85，输出通过精细化搜索后的全局极值。
[0076]
本发明的技术方案，与现有技术相比，其显著的有益效果在于：
[0077]
(1)建立物流车辆低碳路线规划的数学模型，该模型能够在保持车辆运输总距离较小的情况下大幅度减少碳排放量。
[0078]
(2)本发明采用一种基于启发信息的改进粒子群算法实现低碳路线规划，利用物流车辆卸货的启发信息，引入增加种群多样性策略以及增强局部搜索等，促使该算法的性能优于传统的粒子群算法。
[0079]
(3)根据路线规划问题的启发信息，设计了一种新型离散个体生成算子，该算子对个体自身采用多元变异策略，保持个体的“惯性”，同时采用贪婪交叉策略实现个体与个体极值和全局极值之间信息的交互，以实现在迭代过程中的新个体生成，其中，交叉策略实现个体与个体极值以及全局极值之间的交互，贪婪思想促使新个体既能够吸收个体极值和全局极值的优良特征，又能保留个体本身的有效信息。
[0080]
(4)为了解决由于个体生成的贪婪性导致的种群早熟收敛问题，提出考虑优先卸货的个体极值局部搜索策略以提高种群跳出局部最优的能力。
[0081]
(5)为了提升种群整体的搜索质量，考虑同化程度的全局极值精细化搜索策略，该策略根据种群相似度及时调整信息交互源，不仅提高了搜索精度，也降低了种群的同化速率。
附图说明
[0082]
附图按比例绘制。附图中，在各个图中示出的每个相同或近似相同的组成部分可以用相同的标号表示。为了清晰起见，在每个图中，并非每个组成部分均被标记。现在，将通过例子并参考附图来描述本发明的各个方面的实例，其中：
[0083]
图1为本发明采用基于启发信息的改进粒子群算法的主体流程图。
[0084]
图2为采用本发明基于启发信息的改进粒子群算法求解实例得到的最佳路线图。
[0085]
图3为采用基本粒子群算法求解实施例得到的最佳路线规划图。
具体实施方式
[0086]
为了更了解本发明的技术内容，特举具体实例并配合所附图说明如下。
[0087]
选取客户规模为24的测试实例，有1辆车，需要服务24个客户，客户坐标(a
xi
,a
yi
)，客户需求量m
i
，如表1所示。
[0088]
表1
[0089]
编号1234567891011坐标(37,52)(49,49)(52,64)(20,26)(40,30)(21,47)(17,63)(31,62)(52,33)(51,21)(42,41)需求量0728131312374编号1213141516171819202122坐标(31,32)(5,25)(12,42)(36,16)(52,41)(27,23)(17,33)(13,13)(57,58)(62,42)(42,57)需求量20154818215578编号2324252627282930313233坐标(16,57)(8,52)(7,38)(27,68)(30,48)(43,67)(58,48)(58,27)(37,69)(38,46)(46,10)需求量2837722510463编号3435363738394041424344
坐标(61,33)(62,63)(63,69)(32,22)(45,35)(59,15)(5,6)(10,17)(21,10)(5,64)(30,15)需求量836791062239编号45464748495051
ꢀꢀꢀꢀ
坐标(39,10)(32,39)(25,32)(25,55)(48,28)(56,37)(30,40)
ꢀꢀꢀꢀ
需求量39310423
ꢀꢀꢀꢀ
[0090]
使用本发明提出的基于启发信息的改进粒子群算法求解实施例得到的最佳路线规划方案，主体流程如图1所示，具体步骤如下：
[0091]
(1)初始化。读取实例的路线规划输入信息，包括访问客户坐标信息(见表1)和问题规模t；给出优化目标的定义，并设定约束条件。
[0092]
优化目标“路径中产生的碳排放量”表示在物流车从配送中心出发服务完所有客户并回到配送中心的路径中车辆产生的碳排放量，它定义为：
[0093][0094][0095][0096]
其中，ε(m
ij
)表示碳排放系数与客户点间的载重量m
ij
的函数关系，d
ij
表示客户i与客户j之间的距离，而客户间距离采用欧式距离计算：
[0097][0098]
其中，a
xi
,和a
yi
表示客户的坐标信息，如表1所示。
[0099]
定义约束条件包括以下三个：
[0100]
(1)每个客户必须被服务且仅被服务一次，即：
[0101][0102]
(2)物流车辆从配送中心出发，最终回到该配送中心，即：
[0103][0104]
(3)物流车不得超载，且各客户节点总的需求量不能超过装载量，即：
[0105][0106]
其中，m
i
(i＝2,3,
…
,n)表示除仓库点之外每个客户点的需求量，m1表示物流车在从仓库出发时的装载量，m0表示物流车的最大装载量限制。
[0107]
(2)初始化基于启发信息的改进粒子群算法参数：
[0108]
设置基于启发信息的改进粒子群算法进化种群规模为n＝200、邻域解数量y＝10、逆转变异选择概率p
r
＝0.6、优先卸货客户
[0109]
点比例α＝0.2、相似度阈值k＝0.6、全局迭代次数g为500、设置迭代计数器t＝0。
[0110]
(3)生成初始候选种群，并计算适应度：
[0111]
采用整数编码，随机生成n个个体，每个个体表示物流车辆前往客户点送货的顺序：
[0112]
x＝{x1,x2,l,x
t
}
[0113]
其中，x
i
(i＝1,2,l,t)表示被服务客户点的标号；根据步骤(1)中已知优化目标为路径中产生的碳排放量，即碳排放量越少适应度越高，规划的路径越好，则个体适应度定义为：
[0114][0115]
确定个体的个体极值和全局极值。
[0116]
(4)采用个体多元变异策略对所有粒子进行变异：
[0117]
为保持个体“惯性”，采取三种变异方式，即交换变异、逆转变异以及插入变异，为三种变异方式赋予选择概率，基于轮盘赌策略为个体选择变异方式，实现步骤为：
[0118]
1.根据输入的逆转变异概率p
r
，计算交换变异和插入变异的概率p
s
和p
i
，其中，
[0119][0120]
2.基于轮盘赌方式选择变异方式的序号；
[0121]
3.如果选择变异方式1，则对个体进行交换变异；
[0122]
4.如果选择变异方式2，那么对个体进行逆转变异；
[0123]
5.如果选择变异方式3，则对个体进行插入变异；
[0124]
6.输出变异后的新个体。
[0125]
(5)贪婪交叉：
[0126]
变异后的个体分别与个体极值，全局极值依次贪婪交叉产生新个体，若新生成个体适应度值更优，则接受新个体，否则，不接受新个体。实现步骤如下：
[0127]
1.确定需要交叉的个体x、个体极值x
pbest
以及全局极值x
gbest
；
[0128]
2.在x和x
pbest
中删除s，将s’作为首个客户s，仅从s右侧客户{s
rp
,s
rx
}中选择以仓库点作为起始客户s，选择客户s在x
pbest
中的左侧客户s
lp
和右侧客户s
rp
，在x中左侧客户s
lx
和右侧客户s
rx
作为下个访问的候选客户；
[0129]
3.在候选客户集{s
lp
,s
rp
,s
lx
,s
rx
}中，选择距离客户s’，使得由s’和s行成的路径碳排放量最小；
[0130]
4.如果客户s’∈{s
lp
,s
lx
}，执行s55，否则执行s56；
[0131]
5.s55，在x和x
pbest
中删除s，将s’作为首个客户s，仅从s左侧客户{s
lp
,s
lx
} 中选择新的s’作为下一服务客户点，使得s’与s形成的路径碳排放量最小，重复执行s55，直至服务完所有客户，即生成新解x
new
；
[0132]
6.新的s’作为下一服务客户点，使得s’与s形成的路径碳排放量最小，重复执行 s55，直至服务完所有客户，即生成新解x
new
；
[0133]
7.以x和x
pbest
的贪婪交叉为例，将新解x
new
与全局极值x
gbest
z再一次进行贪婪交叉，生成新解。
[0134]
(6)更新个体极值和全局极值：
[0135]
根据优胜劣汰的规则在每次迭代中更新个体极值和全局极值；
[0136]
(7)基于优先卸货的启发信息对个体极值进行局部搜索：
[0137]
个体极值局部搜索的方向是根据问题的启发信息的，实现步骤如下：
[0138]
1.确定个体极值x
pbest
、优先服务客户点比例α以及客户规模t；
[0139]
2.从配送中心出发，依次选择距离前一点最近的客户点优先服务，直至确定好前α*t 个服务点，并用它们替代原个体极值的前α*t位；
[0140]
3.确定当前个体极值回路中的缺少客户和重复客户，并用缺少客户依次替代重复客户；
[0141]
4.在剩下的(1
‑
α)*t位中随机产生两个变异点，并在这两点之间进行逆转变异，产生新的个体极值。
[0142]
(8)考虑种群同化程度的全局极值精细化搜索，具体实现如下：
[0143]
1.确定全局极值x
gbest
、问题规模t和相似度阈值k；
[0144]
2.将2
‑
opt算子作用在全局极值上，通过随机交换两条边的方式，能够有效打开在回路中的交叉路线；
[0145]
3.接着判断种群中每个个体与全局极值的相似程度；
[0146]
4.若最小的相似度大于给定的阈值k，则利用点插法对全局极值进一步搜索，通过移动某一点的位置，改变三条边，有助于寻找在无交叉情况下的最优解决方案；
[0147]
5.输出通过精细化搜索后的全局极值。
[0148]
本发明的效果可以通过以下仿真实验进一步说明：
[0149]
1.实验条件：
[0150]
在intel(r)core(tm)i5
‑
5500u cpu@2.40ghz、内存8gb、windows 10系统上使用matlab 2017b进行仿真。
[0151]
2.实验内容：
[0152]
选取客户规模为24的测试实例，有1辆车，需要服务24个客户，客户坐标(a
xi
,a
yi
)，客户需求量m
i
，如表1所示.
[0153]
3.实验结果
[0154]
i.采用本发明与现有的以路线最短为优化目标的路线规划实验对比；
[0155]
ii.采用本发明采用的基于启发信息的改进粒子群算法与现有的基本粒子群算法分别对该问题进行求解。
[0156]
实验在实例中分别独立地运行30次。表2分别列出了两种目标的路线规划在30次运行中求得的碳排放量，行驶距离，表中还给出了与以最短距离为优化目标的车辆路线规划相比，以碳排放量为优化目标的车辆路线规划行驶距离或碳排放量的增加或减少百分比，
“↑”
表示增加，
“↓”
表示减少。表3给出了本发明采用的基于启发信息的粒子群算法和基本粒子群算法在30次运行中求得的最少碳排放量以及碳排量的平均值。
[0157]
由表2可见，与现有的以行驶距离为优化目标的路线规划相比，本发明运输距离仅增加了0.94，但是却减少了17.65％的碳排放量，表明，以低碳作为性能指标，能够在保持车辆行驶距离较小的同时大幅度减少碳排放量。
[0158]
由表3可见，与现有的基本粒子群算法相比，本发明能够搜索到适应度更优的个体，大幅度降低了车辆行驶路径中的碳排放量。
[0159]
表2
[0160][0161]
表3
[0162][0163]
图2为采用本发明基于启发信息的改进粒子群算法求解实例的路线规划图，图3为基本粒子群算法求解实例的路线规划图。从路径规划图可以看出每个客户的坐标，以及访问的路线。由图2可见，本发明基于启发信息的改进粒子群算法求解实例的最优规划路线中产生的碳排放量为1000.23，由图3可见，基本粒子群算法求解实例的最优规划路线中产生的碳排放量为1073.17。
[0164]
综上，本发明提出的基于启发式粒子群算法的物流车辆低碳路线规划方法，在以距离最短为优化目标的车辆路线规划基础上，建立了物流车辆低碳路线规划的数学模型。在基本粒子群算法的基础上，设计了多元变异和贪婪交叉等个体生成算子，提出考虑优先卸货的个体极值局部搜索策略和考虑种群同化程度的全局极值精细化搜索策略，克服了基本粒子群算法早熟收敛、易于陷入局部最优、局部搜索能力弱和求解精度不高等缺点，能够快速高效地实现物流车辆在送货过程中的低碳路线规划。
[0165]
在本公开中参照附图来描述本发明的各方面，附图中示出了许多说明的实例。本公开的实例不必定义在包括本发明的所有方面。应当理解，上面介绍的多种构思和实例，可以以很多方式中任意一种来实施，这是因为本发明所公开的构思和实例并不限于任何实施方式。另外，本发明公开的一些方面可以单独使用，或者与本发明公开的其他方面的任何适当组合来使用。
[0166]
虽然本发明已以较佳实施例揭露如上，然其并非用以限定本发明。本发明所属技术领域中具有通常知识者，在不脱离本发明的精神和范围内，当可作各种的更动与润饰。因此，本发明的保护范围当视权利要求书所界定者为准。

技术特征：
1.一种基于启发式粒子群算法的物流车辆低碳路线规划方法，其特征在于，包括以下步骤：s1，读取路线规划信息，定义优化目标，设定约束条件：所述路线规划信息包括物流车辆需要访问的客户点数量t、客户具体坐标以及客户所需的物品重量；所述优化目标为所规划路线中车辆的碳排放量最少；s2，初始化基于启发信息的改进粒子群算法参数：设置改进粒子群算法进化种群规模为n、最大迭代次数为g、邻域搜索最大规模y、逆转变异选择概率p
r
、优先卸货客户点比例α、相似度阈值k设置迭代计数器t＝0；s3，生成初始候选种群，并计算适应度：采用整数编码，随机生成n个个体，每个个体表示物流车辆前往客户点送货的顺序：x＝{x1,x2,l,x
t
}其中，x
i
(i＝1,2,l,t)表示被服务客户点的标号；计算每个个体的目标值f(x)：计算每个个体的目标值f(x)：其中，d
ij
表示客户i与客户j之间的距离，ε(m
ij
)表示客户点之间载重与碳排放系数的函数关系：则个体的适应度为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中，所述读取路线规划信息，定义优化目标，设定约束条件的过程包括以下步骤：设客户的平面坐标信息{(a
x1
,a
y1
),(a
x2
,a
y2
),
…
,(a
xt
,a
yt
)}，问题的规模表示访问客户的数量t，则不同客户间距离为欧式距离计算公式，其定义为：其中，d
ij
表示客户i与客户j之间的距离；定义优化目标主体为物流车辆在规划路线中的碳排放量，其定义为：其定义为：其定义为：其中，ε(m
ij
)表示客户点之间载重与碳排放系数的函数关系。定义约束条件包括以下三个：(1)每个客户必须被服务且仅被服务一次，即：(2)物流车辆从配送中心出发，最终回到该配送中心，即：(3)物流车不得超载，且各客户节点总的需求量不能超过装载量，即：其中，m
i
(i＝2,3,
…
,n)表示除仓库点之外每个客户点的需求量，m1表示物流车在从仓库出发时的装载量，m0表示物流车的最大装载量限制。3.根据权利要求1所述的基于启发式粒子群算法的物流车辆低碳路线规划方法，其特征在于，步骤s4中，变异方式采取交换变异、逆转变异以及插入变异，并为三种变异方式赋予选择概率，基于轮盘赌策略为个体选择变异方式；采用个体多元变异策略对所有个体进行变异的实现步骤如下：s41，根据输入的逆转变异概率p
r
，计算交换变异和插入变异的概率p
s
和p
i
，其中，s42，基于轮盘赌方式选择变异方式的序号；
s43，如果选择变异方式1，则对个体进行交换变异；s44，如果选择变异方式2，那么对个体进行逆转变异；s45，如果选择变异方式3，则对个体进行插入变异；s46，输出变异后的新个体。4.根据权利要求1所述的基于启发式粒子群算法的物流车辆低碳路线规划方法，其特征在于，步骤s5中，所述贪婪交叉算子的实现步骤为：s51，确定需要交叉的个体x、个体极值x
pbest
以及全局极值x
gbest
；s52，以仓库点作为起始客户s，选择客户s在x
pbest
中的左侧客户s
lp
和右侧客户s
rp
，在x中左侧客户s
lx
和右侧客户s
rx
作为下个访问的候选客户；s53，在候选客户集{s
lp
,s
rp
,s
lx
,s
rx
}中，选择距离客户s’，使得由s’和s行成的路径碳排放量最小；s54，如果客户s’∈{s
lp
,s
lx
}，执行s55，否则执行s56；s55，在x和x
pbest
中删除s，将s’作为首个客户s，仅从s左侧客户{s
lp
,s
lx
}中选择新的s’作为下一服务客户点，使得s’与s形成的路径碳排放量最小，重复执行s55，直至服务完所有客户，即生成新解x
new
；s56，在x和x
pbest
中删除s，将s’作为首个客户s，仅从s右侧客户{s
rp
,s
rx
}中选择新的s’作为下一服务客户点，使得s’与s形成的路径碳排放量最小，重复执行s55，直至服务完所有客户，即生成新解x
new
；s57，将新解x
new
与全局极值x
gbest
再一次进行贪婪交叉，生成新解。5.根据权利要求1所述的基于启发式粒子群算法的物流车辆低碳路线规划方法，其特征在于，步骤s7中，所述对个体极值局部搜索的具体实现步骤如下：s71，确定个体极值x
pbest
、优先服务客户点比例α以及客户规模t；s72，从配送中心出发，依次选择距离前一点最近的客户点优先服务，直至确定好前α*t个客户点，并用它们替代原个体极值的前α*t位；s73，确定当前个体极值回路中的缺少客户和重复客户，并用缺少客户依次替代重复客户；s74，在剩下的(1
‑
α)*t位中随机产生两个变异点，并在这两点之间进行逆转变异，产生新的个体极值。6.根据权利要求1述的基于启发式粒子群算法的物流车辆低碳路线规划方法，其特征在于，步骤s8中，所述考虑种群同化程度的全局极值精细化搜索，具体实现步骤为：s81，确定全局极值x
gbest
、问题规模t和相似度阈值k；s82，将2
‑
opt算子作用在全局极值上，通过随机交换两条边的方式，能够有效打开在回路中的交叉路线；s83，接着判断种群中每个个体与全局极值的相似程度；s84，若最小的相似度大于给定的阈值k，则利用点插法对全局极值进一步搜索，通过移动某一点的位置，改变三条边，有助于寻找在无交叉情况下的最优解决方案；s85，输出通过精细化搜索后的全局极值。
技术总结
本发明公开了一种基于启发式粒子群算法的物流车辆低碳路线规划方法，包括如下步骤：（1）问题信息读取，包括客户的位置坐标和需求重量等；（2）初始化算法参数；（3）计算种群中所有个体的适应度，确定个体极值和全局极值；（4）采用个体多元变异策略对所有个体进行变异；（5）变异后的个体分别与个体极值，全局极值依次交叉产生新个体；（6）更新个体极值和全局极值；（7）基于优先卸货的启发信息对个体极值进行局部搜索；（8）基于种群的相似度对全局极值进行精细化搜索；（9）判断是否达到终止条件，若达到，则终止迭代，输出适应度最优的个体，该个体即为货车的配送服务顺序。本发明具有搜索速度快，搜索能力强，规划路线碳排放量少的优点。规划路线碳排放量少的优点。规划路线碳排放量少的优点。


技术研发人员：申晓宁 潘红丽 陈庆洲 游璇
受保护的技术使用者：南京信息工程大学
技术研发日：2021.04.06
技术公布日：2021/6/29