一种基于深度强化学习的动态路径优化问题求解方法

摘要

本发明公开了一种基于深度强化学习的动态路径优化问题求解方法，包括以下步骤：S1：动态路径优化问题定义；S2：构建深度强化学习框架，所述深度强化学习框架包括四个组成部分，分别为状态、智能体、动作和奖励，所述状态包括所有顾客及所有点对之间预计所需要的通行时间，所述智能体在不同状态下进行决策，得到对应的动作，所述动作为下一位访问的顾客，所述奖励为从仓库点出发，访问所有顾客后回到仓库点所需要的时间；S3：利用深度强化学习框架得出优化后的路径。本发明利用了深度强化学习算法，将动态路径优化问题的动态环境嵌入到模型中，使得模型能感知到环境的动态变化，从而使其在极短时间内得到一个较优的解。

说明书

技术领域

本发明涉及运筹学领域中的车辆调度领域，更具体地，涉及一种基于深度强化学习的动态路径优化问题求解方法。

背景技术

路径优化问题是传统的NP-complete组合优化问题，在物流调度行业中有着广泛的应用。根据现实生活中实际约束的不同，又有多种不同的变种，如车辆路径问题，提货送货问题等等。路径优化问题的一个经典变种：动态路径优化问题。

动态路径优化问题定义在有向完全图G＝(V，E)上，其中V代表点集，包含了1个仓库点(0号点)、c位需要服务的顾客(用集合C表示)和n-c-1个可能需要服务的顾客的地点；E代表边集。动态路径优化问题是一个非对称性问题，即问题不保证边集E中方向相反的边(i，j)与(j，i)长度相等。销售员需要在一天的开始(t＝0)从仓库点出发，然后访问集合C中所有的顾客恰好一次(销售员在访问顾客后需立即出发前往下一个目的地)，最后回到仓库点。任意两点i，j之间所需要的通行时间，和当前时间t相关。即销售员若在t＝t

公开日为2018年05月18日，中国专利CN108053059A公开了一种运用基于重用策略的智能群体算法优化动态路径优化问题的方法。传统的路径优化问题需要在一个静态的搜索空间中找到一条代价最小的哈密顿回路。但实际上，现实世界中一些可以以路径优化问题为模型的应用并不都是静态的。它们的问题模型中的城市集合和权重矩阵是动态变化的。在动态环境中，上一次环境中搜索结果可以被新环境下的群体重用并得以学习。目前解决动态路径优化问题的主要解法以启发式算法为主，如遗传算法、蚁群算法等。启发式算法的优点在于能得到较优的解，而缺点在于所需运行时间过长。不适合用于求解动态路径优化问题这类在线问题。

用于求解路径优化问题的主要算法可以分为三类。第一类是精确算法，精确算法如分支定界法，分支切割法，列生成法等。这类算法的思路是遍历所有解空间，并将不可能是最优解的空间舍弃。精确算法能找到问题的最优解，却需要耗费极大量的搜索时间。第二类是启发式算法，如邻域搜索法、模拟退火、遗传算法等等。启发式算法。启发式算法一般首先需要一个或一组最优解，之后迭代对这些解进行优化。第三类是构造算法如最近邻法，最近插入法，最远插入法等。构造算法根据问题特点，直接得到一个解，不需要对解进行优化。构造算法的运行速度快，而一般来说解的质量较低。

发明内容

本发明提供一种基于深度强化学习的动态路径优化问题求解方法，快速高质量的获得问题的最优解。

为解决上述技术问题，本发明的技术方案如下：

一种基于深度强化学习的动态路径优化问题求解方法，包括以下步骤：

S1：动态路径优化问题定义：在有向完全图G＝(V，E)上，其中V代表点集，包含了1个仓库点、c位需要服务的顾客，用集合C表示，和n-c-1个可能需要服务的顾客的地点；E代表边集，由于动态路径优化问题是一个非对称性问题，即不保证边集E中方向相反的边长度相等，求从仓库点出发，然后访问集合C中所有的顾客恰好一次，最后回到仓库点的最小时间；

S2：构建深度强化学习框架，所述深度强化学习框架包括四个组成部分，分别为状态、智能体、动作和奖励，所述状态包括所有顾客及所有点对之间预计所需要的通行时间，所述智能体在不同状态下进行决策，得到对应的动作，所述动作为下一位访问的顾客，所述奖励为从仓库点出发，访问所有顾客后回到仓库点所需要的时间；

S3：利用深度强化学习框架得出优化后的路径。

上述方案中，深度强化学习算法可以看作一种构造算法。深度强化学习框架包含了四个组成部分：状态(state)、智能体(agent)、动作(action)和奖励(reward)。状态指当前问题的状态。比如，在路径优化问题中，经典的Held-Karp算法将问题的状态定义为每位顾客的访问情况以及上一位访问的顾客。智能体一般是一个深度神经网络，能根据各种不同的状态得到对应的动作。典型用于求解路径优化问题的深度神经网络包括指针网络、图神经网络、注意力模型等。在动态路径优化问题中，动作指下一位访问的顾客，而奖励可以设置为销售员花费的总时间的相反数。奖励主要作用是用于评价动作的优劣以训练模型。典型用于训练模型的强化学习算法包括策略梯度法、Q学习法、行动者-评分者算法、深度确定性策略梯度法等。

优选地，步骤S2中所述状态包括静态部分和动态部分，其中，静态部分包括每一位顾客的编号及在各时间片上每两个点之间预计所需的通行时间，顾客的编号为每个顾客在数据集中出现次序，这两组在决策过程中不会变化的量；动态部分随着销售员访问顾客过程中的时间变化而变化，包括在某一特定时刻，每两个点之间预计所需通行时间，以及每个点是否被访问。

优选地，由于在动态路径优化问题中，状态的空间很大，所以必须使用表达能力强的模型在各时间片上每两个点之间预计所需的通行时间y

优选地，每个点的访问情况v

优选地，由于在动态路径优化问题中，状态的空间很大，所以必须使用表达能力强的模型，所述智能体采用一个编码解码结构的注意力模型，由编码器和解码器组成，所述编码器将所述状态的静态部分编码至每个顾客的特征向量上，解码器将所述状态的动态部分编码至中间向量，再将每位顾客的特征向量及中间向量解码到每位顾客被选为下一位访问顾客的概率p

优选地，所述编码器由多个全连接神经网络和一个多层自注意力网络组成，所述解码器由多个全连接神经网络和一个单层自注意力网络组成。

优选地，所述智能体选择完下一位访问的顾客j后，当前时刻t需要加上当前路径实际花费的通行时间f

优选地，更新当前时刻的同时，状态的动态部分也随之被改变：重新获得当前时刻的预计通行时间，并将访问状况中已经服务顾客对应的访问情况设置为0，此时，解码器将根据新的状态进行下一轮的解码。

在动态路径优化问题中动作指下一位访问顾客，对于每一个算例，智能体中的编码器将状态的静态部分编码到特征向量，解码器根据特征向量及状态的动态部分输出c个动作(c为顾客总数)，这c个动作组成整个算例的解。销售员从仓库出发，依次访问这c位顾客后回到仓库。

优选地，所述将奖励设置为所花费的实际总时间，在智能体的解码器中保存了到达每一位顾客的实际时间t

优选地，在训练的过程中，采用了Adam优化器根据损失函数更新模型，在Adam优化器中，初始学习率设置为10

与现有技术相比，本发明技术方案的有益效果是：

本发明利用了深度强化学习算法，将动态路径优化问题的动态环境嵌入到模型中，使得模型能感知到环境的动态变化，从而使其在极短时间内得到一个较优的解。

附图说明

图1为本发明的方法流程示意图。

图2为本发明的深度强化学习框架的示意图。

图3为实施例中提供的仓库及所有顾客的分布图。

图4为实施例中编码器结构示意图。

图5为实施例中解码器结构示意图。

图6为带基线的深度强化学习算法流程图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制；

为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；

对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。

下面结合附图和实施例对本发明的技术方案做进一步的说明。

实施例1

一种基于深度强化学习的动态路径优化问题求解方法，如图1，包括以下步骤：

S1：动态路径优化问题定义：在有向完全图G＝(V，E)上，其中V代表点集，包含了1个仓库点、c位需要服务的顾客，用集合C表示，和n-c-1个可能需要服务的顾客的地点；E代表边集，由于动态路径优化问题是一个非对称性问题，即不保证边集E中方向相反的边长度相等，求从仓库点出发，然后访问集合C中所有的顾客恰好一次，最后回到仓库点的最小时间；

S2：构建深度强化学习框架，如图2，所述深度强化学习框架包括四个组成部分，分别为状态、智能体、动作和奖励，所述状态包括所有顾客及所有点对之间预计所需要的通行时间，所述智能体在不同状态下进行决策，得到对应的动作，所述动作为下一位访问的顾客，所述奖励为从仓库点出发，访问所有顾客后回到仓库点所需要的时间；

S3：利用深度强化学习框架得出优化后的路径。

步骤S2中所述状态包括静态部分和动态部分，其中，静态部分包括每一位顾客的编号及在各时间片上每两个点之间预计所需的通行时间，顾客的编号为每个顾客在数据集中出现次序，动态部分包括在某一特定时刻，每两个点之间预计所需通行时间，以及每个点是否被访问。

在各时间片上每两个点之间预计所需的通行时间y

每个点的访问情况v

所述智能体采用一个编码解码结构的注意力模型，由编码器和解码器组成，所述编码器将所述状态的静态部分编码至每个顾客的特征向量上，解码器将所述状态的动态部分编码至中间向量，再将每位顾客的特征向量及中间向量解码到每位顾客被选为下一位访问顾客的概率p

如图4、图5所示，所述编码器由多个全连接神经网络和一个多层自注意力网络组成，所述解码器由多个全连接神经网络和一个单层自注意力网络组成。

所述智能体选择完下一位访问的顾客j后，当前时刻t需要加上当前路径实际花费的通行时间f

更新当前时刻的同时，状态的动态部分也随之被改变：重新获得当前时刻的预计通行时间，并将访问状况中已经服务顾客对应的访问情况设置为0，此时，解码器将根据新的状态进行下一轮的解码。

如图6，所述将奖励设置为所花费的实际总时间，在智能体的解码器中保存了到达每一位顾客的实际时间t

在训练的过程中，采用了Adam优化器根据损失函数更新模型，在Adam优化器中，初始学习率设置为10

在具体实施过程中，如图3，状态数据是由北京的一个真实数据集中提取的，仓库及所有顾客的分布图如图2所示。此数据集包含1个仓库和99位顾客的位置，在数据集中还包含了100000个算例。每个算例包含c位顾客的编号，代表当天需要服务的顾客。静态部分的状态包含每一位需要服务顾客的编号及在各时间片上每两个点之间预计所需的通行时间这两组在决策过程中不会变化的量。动态部分的状态随着销售员访问顾客过程中的时间变化而变化，包含在某一特定时刻，每两个点之间预计所需通行时间，以及每个点是否被访问这两组变量。其中，每一位顾客的编号x

编码器由多个全连接神经网络和一个多层自注意力网络组成，将每位顾客的编号x

为了测试模型，设计了三种对比算法：模拟退火法，贪心算法与动态规划法。这三种算法都是近似算法，而动态规划法在确定性的算例下(预测误差Φ为0)能得到精确解。共设计了两组对比实验分别测试了各算法的运行时间与各算例下的实际效果。在模型的测试过程中，预测误差Φ设置为不同的均值为0的随机变量。其实验结果如表1、表2所示。

表1

表2

相同或相似的标号对应相同或相似的部件；

附图中描述位置关系的用语仅用于示例性说明，不能理解为对本专利的限制；

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。