(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111609467.2 (22)申请日 2021.12.24 (71)申请人 江南大学 地址 214122 江苏省无锡市滨湖区蠡湖大 道1800号 (72)发明人 方伟　接中冰　陆恒杨　孙俊　 吴小俊　 (74)专利代理 机构 哈尔滨市阳光惠远知识产权 代理有限公司 2321 1 代理人 张勇 (51)Int.Cl. G06Q 10/04(2012.01) G06N 3/08(2006.01) G06Q 10/08(2012.01) (54)发明名称 一种基于覆盖旅行商问题求解的路径规划 方法 (57)摘要 本发明公开了一种基于覆盖旅行商问题求 解的路径规划方法， 属于人工智 能的强化学习、 深度学习和组合优化领域。 所述方法通过利用深 度神经网络自动挖掘实例特征的特点提出了新 的模型来求解CSP问题， 解决了传统方法需要过 多的领域知识进行求解的缺点， 并极大地提高了 求解速度。 针对现有深度神经网络求解质量低的 问题， 采用了数据增强的方式扩充样本数量， 利 用多起点技术多次求解减少了预测误差， 并提出 了针对CSP问题的Mask策略对解的构造进行约 束。 结合简单局部搜索算法进行改进， 进一步地 提高了求解质量。 与现有的DNN求解方法相比显 著缩小了最优间隙， 与启发式算法相比取得了超 过20倍的速度提升， 更适合在实时性要求高的场 景中使用。 权利要求书3页 说明书11页 附图4页 CN 114330867 A 2022.04.12 CN 114330867 A 1.一种基于覆盖 旅行商问题求 解的路径规划方法， 其特 征在于， 所述方法包括： 步骤一： 获取 所要规划的路径需要覆盖的N个地 点的坐标； 步骤二： 对步骤一获取到的N个地 点的坐标进行 数据预处 理及数据扩充； 步骤三： 对步骤二预处理及扩充后的坐标数据进行特征编码， 并将每个地点的二维坐 标特征映射为高纬度的向量表示， 得到全局图信息； 步骤四： 采用多起点的方法从扩充后的坐标数据中选取多个地点作为起点， 分别输入 到解码器中进 行解码， 利用全局图信息和当前时刻访问的地点信息来进 行预测下一时刻访 问的地点， 并通过Mask策略来对解序列的构造进行约束， 直至已访问的地点能够对所有的 地点进行覆盖或访问， 得到相应的解； 在得到的多个解中选取路径最短的解作为初步规划 的路径； 步骤五： 对步骤四得到的初步规划的路径采用局部搜索算法对其中的部分地点进行替 换和删除操作进一 步优化， 优化后的路径作为 最终规划的路径。 2.根据权利要求1所述的方法， 其特 征在于， 所述 步骤二包括： 采用最大最小标准 化来对N个地 点坐标进行缩放： 其中， (a′， b′)表示任一地点xi的二维平面坐标， (a， b)表示缩放后的坐标， i＝{1， ...， N}； max(a′)， min(a′)分别表示N个地点的二维平面坐标在x轴坐标上的最大最小数值， max (b′)， min(b′)表示N个地点的二维平面 坐标在y轴坐标 上的最大最小数值； 对缩放后的坐标进行如下变换以实现数据扩充： f(a， b)＝(a， b) f(a， b)＝(b， a) f(a， b)＝(1 ‑a， b) f(a， b)＝(1 ‑b， a) f(a， b)＝(a， 1 ‑b) f(a， b)＝(b， 1 ‑a) f(a， b)＝(1 ‑a， 1‑b) f(a， b)＝(1 ‑b， 1‑a) f表示对应的变换函数。 3.根据权利要求2所述的方法， 其特 征在于， 所述 步骤三包括： 使用标准Transformer模型的编码器对输入的地 点坐标进行 特征编码； 通过一个线性投影层将输入的地 点坐标特征投射到高维空间： 其中， W、 b是 可学习的参数； 得到N个地 点的初始嵌入：权　利　要　求　书 1/3 页 2 CN 114330867 A 2其中， H(0)表示N个地点的初始嵌入的集 合， 其中的元 素分别表示各个地 点的初始嵌入； 通过L层的注意力层， 得到每个地点的顶点嵌入 并通过对所 有地点的顶点嵌入求平均得到表示代 表全局图信息的图嵌入hg： 其中， 表示第i个地点经过L层的注意力层后得到的顶点嵌入； 每层注意力层由多头 注意力层和前馈层构成， 并通过残差连接和批次归一 化确保深层网络训练的稳定性。 4.根据权利要求3所述的方法， 其特 征在于， 所述 步骤四包括： 在t＝1时刻， 选取m个地 点分别作为 起点， m的取值范围在[0 ‑N]之间； 然后在t≥2时刻， 利用t ‑1时刻构造的解序列信息， 预测t时刻要访问的地 点； 首先构造上 下文嵌入： 其中 表示所选 定的起点的嵌入， 表示在t‑1时刻选定的地点嵌入； 将上下文嵌入作为 解码器的输入， 用于预测t时刻要访问的顶点； 所述解码器中通过注意力机制及softmax运算输出预测每个顶点的概率； 针对已经访 问过的顶 点和已经访问过的顶点可覆盖的顶 点， 利用mask操作将其被预测将要访问的概率 置为0， 使其不会再被访问； 重复这一过程， 直至获取到的解序列已经能够将所有的顶点进 行覆盖和访问； 得到m个解； 通过下式分别求出m个解分别对应的路径的长度length( π )， 选取路径长度最短的解， 作为初步 规划的路径； 其中， π表示由k个地点所构成 的解序列； 表示对应的解中所选中的第一个地点， 表示对应的解中所选中的第k个地点， k≤N； 表示解中的第一个地点与解中第k个地点 的距离。 5.根据权利要求4所述的方法， 其特征在于， 所述步骤四中通过注意力机制及softmax 运算输出预测每个顶点的概 率， 包括： pi＝softmax(uc(i)) 其中 其中， C表示用于调整tanh函数输出区间的常数； qc表示对上 下文嵌入hc通过可学习的参数 进行线性变换：权　利　要　求　书 2/3 页 3 CN 114330867 A 3