1.一种求解车辆路径优化问题的神经组合优化方法,其特征在于,包括:步骤S1:对CVRP问题进行描述,引入热力图来反映节点之间的关联关系,并采用图神经网络来参数化热力图;
其中对CVRP问题进行描述,具体包括:
多条路线的起始点和终点都为depot节点,将这个节点标号记为0,坐标为(x引入热力图来反映节点之间的关联关系,具体包括:对于一个包含1个仓库和n个客户的CVRP问题实例,总计1+n个节点,其热力图表示为:采用图神经网络来参数化热力图,具体包括:在输入层,得到节点位置V
在图卷积层,假设
其中
最后,在全连接层将边特征
步骤S2:基于参数化的热力图来确定客户与车辆的匹配,构建包括状态、动作、奖励和策略的客户匹配框架,具体包括:状态:t时刻状态表示为t时刻前已安排的部分客户匹配结果π动作:t时刻执行的动作是从未访问节点集合中选择一个客户节点,作为第r辆车下一个待配送节点,即动作表示为奖励:采用路径长度的相反数表示累计奖励;对CVRP问题实例ρ来说,执行某个特定匹配结果的累计回报表示为各辆车的行驶路径累计和的相反数,即策略:针对特定问题实例ρ,在满足约束条件Θ下,根据热力图其中
解码:根据基于
步骤S3:采用强化学习方法对神经网络模型进行训练,以所有车辆的行驶路径长度最小化为优化目标,得到训练好的神经网络模型;
其中采用强化学习方法对神经网络模型进行训练,具体包括:采用强化学习方法对神经网络模型进行训练,该方法从随机策略开始,并在训练实例上跟踪搜索过程中的采样效果进行反向传播,以此来迭代优化神经网络参数;使用的策略梯度函数如下:其中
式中,b(ρ)是基线奖励,等于历史解集中的平均路径长度,f步骤S4:利用训练好的神经网络模型,求解车辆的最优配送路径。
2.根据权利要求1所述的求解车辆路径优化问题的神经组合优化方法,其特征在于,步骤S3中,以所有车辆的行驶路径长度最小化为优化目标,其函数表达式如下:其中
3.一种求解车辆路径优化问题的神经组合优化系统,其特征在于,用于实现权利要求1至2所述的求解车辆路径优化问题的神经组合优化方法,所述系统包括:热力图处理模块,用于对CVRP问题进行描述,引入热力图来反映节点之间的关联关系,并采用图神经网络来参数化热力图;
框架构建模块,用于参数化的热力图来确定客户与车辆的匹配,构建包括状态、动作、奖励和策略的客户匹配框架;
模型训练模块,用于采用强化学习方法对神经网络模型进行训练,以所有车辆的行驶路径长度最小化为优化目标,得到训练好的神经网络模型;
求解模块,用于利用训练好的神经网络模型,求解车辆的最优配送路径。
4.一种电子装置,其特征在于,所述电子装置包括处理器、存储器和总线系统,所述处理器和存储器通过该总线系统相连,所述存储器用于存储指令,所述处理器用于执行存储器存储的指令,以实现权利要求1至2任意一项所述的求解车辆路径优化问题的神经组合优化方法。
5.一种计算机存储介质,其特征在于,所述计算机存储介质存储有计算机软件产品,所述计算机软件产品包括的若干指令,用以使得一台计算机设备执行权利要求1至2任意一项所述的求解车辆路径优化问题的神经组合优化方法。