1.本发明涉及一种物流配送、电子商务、智能优化、计算机应用领域，尤其涉及的是一种车辆路径优化方法。
背景技术：2.车辆路径问题作为物流运输中抽象化出来的一类重要问题，其理论研究对解决现代物流行业中一些棘手的问题具有积极的作用，对推动物流行业快速发展具有重大意义，有利于增加物流企业的核心竞争力，可以给企业以及国家带来巨大的经济效益。车辆路径问题具有许多不同的衍生问题，例如带时间窗的车辆路径问题、同时取送货的车辆路径问题、多仓库车辆路径问题、开放式车辆路径问题，这些约束使得车辆路径问题更加复杂而且求解起来更加困难。很多方法被提出来用于求解车辆路径问题，其主要归结为两类：精确算法和启发式算法。如今提出的精确算法种类较多，有分枝定界法、分枝定价法，动态规划算法等，但精确算法存在面对问题规模较大时需要进行大量的计算工作的缺点。因此启发式算法更频繁的用于求解大规模车辆路径问题。启发式算法是解决大规模车辆路径问题的最佳方案之一。这些算法被大致分为三类：构造型启发式算法、改进型启发式算法和元启发式算法。构造型启发式算法基于基本的贪婪思想或其他具体策略，为所求最优化问题的实例构造可行解的算法。改进型启发式算法求解结果的优劣很大程度上取决于初始解，因此该算法在求解过程中易陷入局部最优；元启发式策略通常是一个通用的启发式策略，他们通常不借助于某种问题的特有条件，从而能够运用于更广泛的方面。这类算法逐渐被广泛的应用与求解大规模组合优化问题，除了经典的遗传算法，主要还包括差分进化算法、蚁群算法、蜂群算法、粒子群算法等。但对启发式算法的设计，设计者往往需要同时具备计算机算法设计基础以及所需解决问题领域的专业知识，缺乏通用性。超启发算法因其具有较强的通用性、高效性的特点，因而被广泛的应用于求解组合优化问题。强化学习作为一个强大的决策工具，已经引起了广泛的关注。在车辆路径问题中，已经应用了许多元启发式算法，但是如何开发更有效的算法来获得更好的解决方案仍在研究中。
技术实现要素：3.本发明要克服现有技术的上述缺点，提供一种基于强化学习中策略梯度算法的超启发式算法的车辆路径优化方法，以充分利用各种元启发式算法的优势。
4.本发明解决其技术问题所采用的技术方案是：
5.一种基于策略梯度的超启发算法的车辆路径优化方法，包括以下步骤：
6.步骤1分析车辆路径问题，采用augerat’s instances数据集，车辆路径问题的成本矩阵的元素是欧几里得距离；
7.假定配送中心设为i＝0，客户点设为l(i＝1,2,3,
…
,l)，最多车辆数设为k(k＝1,2,3,
…
k)，每辆车具有相同载重量为q，每个客户点需求量设为di(i＝1,2,3,
…
,l)，客户i到客户j的距离设为c
ij
，优化的目标是行驶距离最短，一个完整的解包含了全部路径的集
合；
8.步骤2输入系统所需的各种参数。设定actor和critic神经网络的结构并初始化权重参数。
9.步骤3通过k-means聚类算法初始化生成种群规模为npop的初始种群pop(pi＝p1,p2,p3,...,p
np
)，由初始种群根据目标函数计算种群中每个个体的适应度值f(fi＝f1,f2,f3,...,f
np
)。随机挑选种群中的一个个体pi及其适应度值fi，初始化pb＝pi，fb＝fi，其中pb代表最优解个体，fb代表最优适应度值，设llh数量为na，action取值为(1,2,3,
…
,na)整数，动作选择概率p＝0.8，训练最大步数d
max
＝800，状态值state＝{f，diff}，其中f当代种群中最优个相较上一代最优个体改进的程度，diff是指种群在经过action更新后两代之间的差异度。通过式(1)和式(2)计算state:
[0010][0011][0012]
步骤4随机生成一个[0，1]之间的数字，如果rand≤p,则随机从na个底层算子中挑选一个作为对种群进行处理的动作a；反之，如果rand》p，则将state输入actor网络输出一个动作a。使用上面得到的动作对种群pop中的个体进行处理，产生新的个体ind，适应度值fit，判断，如果fit《fit’(上一代个体的适应度值)，则说明此时解的适应度值更好，则保存解及解的适应度值；如果fit≥fit’，则采用自适应接受准则判别，若概率p》rand，则同样保留好解，同时更新状态，反之，则舍去该解，此时state
t
＝state，fit’＝fit’。在得到的新种群中挑选适应度值前二的个体，另外随机挑选一个个体，根据挑选出的三个个体的适应度值计算三者的立即回报值reward，此时的状态state为“下一状态”，将上述三者的信息记录到experience pool[s，a，r，s
t
]中，其中s为采用动作a处理之前个体ind的状态state，a为采取的动作a，r代表述计算中得到的立即回报值reward，具体由式(3)计算，其中为当前种群个体适应度值得均值，为上一代种群个体的适应度均值。
[0013]st
代表采用动作a处理后个体ind的状态state。如果经验池内的状态转移数据达到上限，则采取先进先出的原则更新经验池。令state＝state
t
(上一代种群的状态度值)，fit’＝fit，g(迭代代数)＝g+1。
[0014][0015]
步骤5判断mod(g，dmax)是否等于0，如果不等于0，判断解是否连续一定的代数未改进，如果是，随机选择一个变异算子作为动作a，并使用该动作a对种群进行操作处理，反之进入步骤4；如果等于0，则从experience pool中抽取n条状态转移数据[s，a，r，s
t
]，actor网络根据s
t
向critic网络提供a
t
，同时critic网络根据(s，a)与(s
t
,a
t
)得到q(s，a)与q(s
t
，a
t
)，计算td偏差，critic网络根据td偏差，按照相应公式进行权重参数的更新，actor网络根据critic网络提供的q(s
t
,a
t
)，按照相应公式进行权重参数更新，actor和critic神经网络权重参数的更新主要根据公式(4)和(5)所示：
[0016]
ω
t+1
＝ω
t
+α[r
t
+γq(s
t+1
,a
t+1
)-q(s
t
,a
t
)]
ꢀꢀ
(4)
[0017][0018]
式中，ω，θ分别为critic网络和actor网络权重参数；α为critic网络学习率，β为actor网络学习率；t下标代表上代对应值，t+1代表此代更新后的值。
[0019]
步骤6判断g是否大于最大迭代次数gmax或者解在设定的代数内未改进，如果上述两条件都未达到,，判断解是否连续一定的代数未改进，如果是，随机选择一个变异算子作为动作a，并使用该动作a对种群进行操作处理，反之进入步骤4，反之则输出最优解，完成任务。
[0020]
进一步，步骤2中，生成初始种群组的过程如下：
[0021]
2.1)以配送中心为起点，对于第k辆车的配送路径，随机分配客户点到该条路径中，判断车辆的载重约束，若未超出标准载重量，则继续随机分配客户点，反之则生成第k+1条路径；重复循环，当所有客户点都被分配到相应配送路径中，则一个初始种群个体生成；
[0022]
2.2)多次进行上述操作，生成设定数量个体的种群，选取种群中配送路径最短的个体，即该配送路径中配送车辆数为k，将k设为聚类块数；
[0023]
2.3)将每个车辆配送的客户点中距离配送中心距离最近的客户点作为基准，其余客户点按照与基准客户点的距离远近划分为k个聚类块；
[0024]
2.4)随机排列k个聚类块，根据车辆载重量约束，按照聚类块排列顺序，从相应聚类块中随机挑选客户点分配到配送路径中，若k块中客户点未能满足某条配送路径车辆载重，则向k+1聚类块中随机挑选客户点，直至达到车辆载重约束，反之则选用新的配送车辆，当所有客户点都被分配到相应配送路径中，由此产生一个初始解个体。
[0025]
本发明的有益效果主要表现在：在研究有容量车辆路径问题时，求解标准算例set a,set e和set p，能取得较好准确性和稳定性。在优化过程中算法的高层策略能够分析并学习算法各底层算子在搜索过程中的历史性能，使得算法能够在迭代过程中选择有竞争力的算子来执行当代的搜索，有助于控制算法收敛速度；解的接受准则的运用，有助于算法跳出局部最优解的能力，优化算法的搜索过程。此外，针对不同的问题，设计新的底层算子可以将算法高层策略应用到新的问题领域。
附图说明
[0026]
图1是本发明方法的流程图。
具体实施方式
[0027]
下面结合附图对本发明作进一步描述。
[0028]
参照图1，一种基于策略梯度的超启发算法的车辆路径优化方法，包括以下步骤：
[0029]
步骤1车辆路径问题分析，采用augerat’s instances数据集，车辆路径问题的成本矩阵的元素是欧几里得距离；
[0030]
有容量车辆路径问题可以描述为以下形式：图g＝(v,e)代表一个无向图，其中v＝{0,1,
…
,n}代表n+1个顶点的集合，e表示弧的集合。顶点0和vc＝v\{0}分别表示仓库和需要配送的客户点。每一条弧(i,j)∈e＝{(i,j):i,j∈v,i《j}上有相应的权c
ij
。c
ij
对称的，
即每一个客户点i∈vc有一个非负的需求qi，并且仓库的需求设为0，客户需求在后续的配送服务中必须得到满足。为了满足客户的需求，车队由m辆相同的车辆组成，每辆车最大载重量为q。每一个客户的需求都小于车辆的载重量，即，qi≤q，i∈vc。有容量车辆路径问题要解决的是一个等待配送服务的客户集合vc，vc中的客户点均有且仅有一辆配送车辆向其提供服务。车队中的车辆从配送中心出发,经过一系列服务后，最终回到配送中心。
[0031]
表1
[0032][0033]
表2
[0034][0035]
具体实验中使用的参数如表1和表2所示。
[0036]
步骤2初始化，第g＝0代，通过k-means聚类算法初始化生成种群规模为npop的初始种群pop(pi＝p1,p2,p3,...,p
np
)，由初始种群根据目标函数计算种群中每个个体的适应度值f(fi＝f1,f2,f3,...,f
np
)。随机挑选种群中的一个个体pi及其适应度值fi，初始化pb＝pi，fb＝fi，其中pb代表最优解个体，fb代表最优适应度值，设llh数量为na，action取值为(1,2,3,
…
,na)整数，状态值state＝{f，diff}。
[0037]
生成初始种群组步骤：
[0038]
2.1)以配送中心为起点，对于第k辆车的配送路径，随机分配客户点到该条路径中，判断车辆的载重约束，若未超出标准载重量，则继续随机分配客户点，反之则生成第k+1条路径；重复循环，当所有客户点都被分配到相应配送路径中，则一个初始种群个体生成；
[0039]
2.2)多次进行上述操作，生成设定数量个体的种群，选取种群中配送路径最短的个体，即该配送路径中配送车辆数为k，将k设为聚类块数；
[0040]
2.3)将每个车辆配送的客户点中距离配送中心距离最近的客户点作为基准，其余客户点按照与基准客户点的距离远近划分为k个聚类块；
[0041]
2.4)随机排列k个聚类块，根据车辆载重量约束，按照聚类块排列顺序，从相应聚类块中随机挑选客户点分配到配送路径中，若k块中客户点未能满足某条配送路径车辆载重，则向k+1聚类块中随机挑选客户点，直至达到车辆载重约束，反之则选用新的配送车辆，当所有客户点都被分配到相应配送路径中，由此产生一个初始解个体。
[0042]
步骤4随机生成一个[0，1]之间的数字，如果rand≤p,则随机从na个底层算子中挑选一个作为对种群进行处理的动作a；反之，如果rand》p，则将state输入actor网络输出一个动作a。使用上面得到的动作对种群pop中的个体进行处理，产生新的个体ind，适应度值fit，判断，如果fit《fit’(上一代个体的适应度值)，则说明此时解的适应度值更好，则保存解及解的适应度值；如果fit≥fit’，则采用自适应接受准则判别，若概率p》rand，则同样保留好解，同时更新状态，反之，则舍去该解，此时state
t
＝state，fit’＝fit’。在得到的新种群中挑选适应度值前二的个体，另外随机挑选一个个体，根据挑选出的三个个体的适应度值计算三者的立即回报值reward，此时的状态state为“下一状态”，将上述三者的信息记录到experience pool[s，a，r，s
t
]中，其中s为采用动作a处理之前个体ind的状态state，a为采取的动作a，r代表述计算中得到的立即回报值reward，s
t
代表采用动作a处理后个体ind的状态state。如果经验池内的状态转移数据达到上限，则采取先进先出的原则更新经验池。令state＝state
t
(上一代种群的状态度值)，fit’＝fit，g(迭代代数)＝g+1。动作a有具体为以下三大类算子：局部优化算子、变异算子和破坏与重构算子，局部优化算子能够高效地改进当前解的质量，使得算法能够快速的收敛，但局部优化算子在对解改进到一定程度时容易陷入局部最优解，并且不容易从该局部最优解出跳出来，影响收敛精度。而变异算子则往往能对在搜索过程中对解产生一些微小的扰动，增加在搜索过程的随机性与多样性，以防止陷入局部最优解，但无法保证得到高质量解。破坏与重构算子功能与变异算子类似。算子具体类型和功能如表3所示：
[0043]
表3
[0044][0045]
步骤5判断mod(g，dmax)是否等于0，如果不等于0，判断解是否连续一定的代数未改进，如果是，随机选择一个变异算子作为动作a，并使用该动作a对种群进行操作处理，反之进入步骤4；如果等于0，则从experience pool中抽取n条状态转移数据[s，a，r，s
t
]，actor网络根据s
t
向critic网络提供a
t
，同时critic网络根据(s，a)与(s
t
,a
t
)得到q(s，a)与q(s
t
，a
t
)，计算td偏差，critic网络根据td偏差，按照相应公式进行权重参数的更新，actor网络根据critic网络提供的q(s
t
,a
t
)，按照相应公式进行权重参数更新。
[0046]
步骤6判断g是否大于最大迭代次数gmax或者解在设定的代数内未改进，如果上述两条件都未达到,，判断解是否连续一定的代数未改进，如果是，随机选择一个变异算子作为动作a，并使用该动作a对种群进行操作处理，反之进入步骤4，反之则输出最优解，完成任务。
[0047]
本发明在有容量车辆路径问题上算法具有较强的搜索能力和稳定性，除了可以用于求解车辆路径问题，还可以通过改变底层算子的设计应用于其他的组合优化问题。补充说明，以上实施例仅用于说明本发明的技术方案，并非对其限制。本领域的技术人员应当理解本发明的技术特征，可对前述技术方案进行修改，或者等同替换其中的部分技术特征，但不能使其技术方案的本质脱离本发明的实施例技术方案的精神和范围。
技术特征：1.一种基于策略梯度的超启发算法的车辆路径优化方法，其特征在于，所述方法包括以下步骤：步骤1分析车辆路径问题，采用augerat’s instances数据集，车辆路径问题的成本矩阵的元素是欧几里得距离；假定配送中心设为i＝0，客户点设为l(i＝1,2,3,
…
,l)，最多车辆数设为k(k＝1,2,3,
…
k)，每辆车具有相同载重量为q，每个客户点需求量设为d
i
(i＝1,2,3,
…
,l)，客户i到客户j的距离设为c
ij
，优化的目标是行驶距离最短，一个完整的解包含了全部路径的集合；步骤2输入系统所需的各种参数；设定actor和critic神经网络的结构并初始化权重参数；步骤3通过k-means聚类算法初始化生成种群规模为npop的初始种群pop(p
i
＝p1,p2,p3,...,p
np
)，由初始种群根据目标函数计算种群中每个个体的适应度值f(f
i
＝f1,f2,f3,...,f
np
)；随机挑选种群中的一个个体p
i
及其适应度值f
i
，初始化p
b
＝p
i
，f
b
＝f
i
，其中p
b
代表最优解个体，f
b
代表最优适应度值，设llh数量为n
a
，action取值为(1,2,3,
…
,n
a
)整数，动作选择概率p＝0.8，训练最大步数d
max
＝800，状态值state＝{f，diff}，其中f当代种群中最优个相较上一代最优个体改进的程度，diff是指种群在经过action更新后两代之间的差异度；通过式(1)和式(2)计算state:异度；通过式(1)和式(2)计算state:步骤4随机生成一个[0，1]之间的数字，如果rand≤p,则随机从n
a
个底层算子中挑选一个作为对种群进行处理的动作a；反之，如果rand>p，则将state输入actor网络输出一个动作a；使用上面得到的动作对种群pop中的个体进行处理，产生新的个体ind，适应度值fit，判断，如果fit<fit’(上一代个体的适应度值)，则说明此时解的适应度值更好，则保存解及解的适应度值；如果fit≥fit’，则采用自适应接受准则判别，若概率p>rand，则同样保留好解，同时更新状态，反之，则舍去该解，此时state
t
＝state，fit’＝fit’；在得到的新种群中挑选适应度值前二的个体，另外随机挑选一个个体，根据挑选出的三个个体的适应度值计算三者的立即回报值reward，此时的状态state为“下一状态”，将上述三者的信息记录到experience pool[s，a，r，s
t
]中，其中s为采用动作a处理之前个体ind的状态state，a为采取的动作a，r代表述计算中得到的立即回报值reward，具体由式(3)计算，其中为当前种群个体适应度值得均值，为上一代种群个体的适应度均值；s
t
代表采用动作a处理后个体ind的状态state；如果经验池内的状态转移数据达到上限，则采取先进先出的原则更新经验池；令state＝state
t
(上一代种群的状态度值)，fit’＝fit，g(迭代代数)＝g+1；步骤5判断mod(g，dmax)是否等于0，如果不等于0，判断解是否连续一定的代数未改进，如果是，随机选择一个变异算子作为动作a，并使用该动作a对种群进行操作处理，反之进入
步骤4；如果等于0，则从experience pool中抽取n条状态转移数据[s，a，r，s
t
]，actor网络根据s
t
向critic网络提供a
t
，同时critic网络根据(s，a)与(s
t
,a
t
)得到q(s，a)与q(s
t
，a
t
)，计算td偏差，critic网络根据td偏差，按照相应公式进行权重参数的更新，actor网络根据critic网络提供的q(s
t
,a
t
)，按照相应公式进行权重参数更新，actor和critic神经网络权重参数的更新主要根据公式(4)和(5)所示：ω
t+1
＝ω
t
+α[r
t
+γq(s
t+1
,a
t+1
)-q(s
t
,a
t
)]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)式中，ω，θ分别为critic网络和actor网络权重参数；α为critic网络学习率，β为actor网络学习率；t下标代表上代对应值，t+1代表此代更新后的值；步骤6判断g是否大于最大迭代次数gmax或者解在设定的代数内未改进，如果上述两条件都未达到，判断解是否连续一定的代数未改进，如果是，随机选择一个变异算子作为动作a，并使用该动作a对种群进行操作处理，反之进入步骤4，反之则输出最优解，完成任务。2.如权利要求1所述的一种基于策略梯度的超启发算法的车辆路径优化方法，其特征在于，所述步骤2中，生成初始种群组的过程如下：2.1)以配送中心为起点，对于第k辆车的配送路径，随机分配客户点到该条路径中，判断车辆的载重约束，若未超出标准载重量，则继续随机分配客户点，反之则生成第k+1条路径；重复循环，当所有客户点都被分配到相应配送路径中，则一个初始种群个体生成；2.2)多次进行上述操作，生成设定数量个体的种群，选取种群中配送路径最短的个体，即该配送路径中配送车辆数为k，将k设为聚类块数；2.3)将每个车辆配送的客户点中距离配送中心距离最近的客户点作为基准，其余客户点按照与基准客户点的距离远近划分为k个聚类块；2.4)随机排列k个聚类块，根据车辆载重量约束，按照聚类块排列顺序，从相应聚类块中随机挑选客户点分配到配送路径中，若k块中客户点未能满足某条配送路径车辆载重，则向k+1聚类块中随机挑选客户点，直至达到车辆载重约束，反之则选用新的配送车辆，当所有客户点都被分配到相应配送路径中，由此产生一个初始解个体。
技术总结一种基于策略梯度的超启发算法的车辆路径优化方法，包括车辆路径问题的研究背景意义及技术，包括：步骤1有容量车辆路径问题分析；步骤2参数初始化；步骤3初始化种群；步骤4通过算子选择机制选择算子对种群进行操作，并计算相关信息并存储于经验池中；步骤5判断算法迭代的次数，若达到预设步距，则进入步骤6学习，反之，则进入步骤4；步骤6从经验池中选择状态转移数据对策略梯度算法中的神经网络进行训练；步骤7判断是否达到算法终止运行条件，若是，则输出最优解；反之则返回主循环。本发明提供了一种高层选择策略为策略梯度的超启发算法的车辆路径优化方法。法的车辆路径优化方法。法的车辆路径优化方法。
技术研发人员：张景玲 余孟凡 孙钰粟
受保护的技术使用者：浙江工业大学
技术研发日：2022.06.17
技术公布日：2022/11/1
