深度混合型邻域搜索模型求解CVRP问题

作     者：杨笑笑 陈智斌 Yang Xiaoxiao;Chen Zhibin

作者机构：昆明理工大学理学院昆明650000 

基　　金：国家自然科学基金(11761042 12361065) 

出 版 物：《南京大学学报（自然科学版）》 (Journal of Nanjing University（Natural Science）)

年 卷 期：2023年第59卷第6期

页      码：1023-1033页

摘      要：邻域搜索算法的关键是邻域结构的选择,但每次迭代搜索的时间较长,缺少在解空间内自主搜索的能力.利用深度强化学习(DRL)模型对邻域搜索算法进行改进,设计了一个新的深度混合型邻域搜索(DHNS)模型来求解带容量的车辆路径问题(CVRP).首先,利用贪婪算法为DRL模型提供初始解;其次,采用指针网络以及Transformer混合编码,利用不同网络的优势,深层次地提取节点特征信息;最后,将修复算子的修复过程转至DHNS模型,自动完成邻域搜索修复解的过程,扩大解空间的自主搜索能力.同时,针对混合编码中复杂传输机制以及解码输出误导性信息的问题,进一步在编码和解码过程中添加AOA(Attention on Attention)机制.AOA负责筛选有价值的信息,过滤不相关或误导性信息,有效刻画了注意力结果和查询之间的相关性,并对节点间的关系进行建模.实验结果表明,DHNS模型在100规模CVRP的优化效果上,优于现有DRL模型和部分传统算法.采用CVRPlib数据集中的算例对该算法的效能进行验证,结果表明,采用DHNS模型能够极大地提升路径问题的优化效能.

主 题 词：深度混合型邻域搜索模型 深度强化学习 混合模型 AOA机制 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 081104[081104] 08[工学] 070105[070105] 0835[0835] 0701[理学-数学类] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13232/j.cnki.jnju.2023.06.012

馆 藏 号：203124908...