带时间窗的旅行商问题(traveling salesman problem with time window, TSPTW)是旅行商问题的一个变种,在物资配送等方面有大量的应用。传统方法的求解时间较长且泛化性较差,为提高TSPTW的求解效率,将求解过程建模为马尔科夫决策过程,...带时间窗的旅行商问题(traveling salesman problem with time window, TSPTW)是旅行商问题的一个变种,在物资配送等方面有大量的应用。传统方法的求解时间较长且泛化性较差,为提高TSPTW的求解效率,将求解过程建模为马尔科夫决策过程,定义了状态、动作、奖励,提出了一种基于深度强化学习的Transformer加指针网络的组合模型,通过多头注意力对输入的特征进行编码,采用指针网络求出解的概率分布,所提深度学习网络通过强化学习算法进行训练。实验结果表明:所提方法对比传统的启发式求解算法,可以得到更高质量的解,相较于求解器和启发式算法,有超过数10倍的提升效果,且易于将模型拓展到不同规模的问题上。展开更多
文摘带时间窗的旅行商问题(traveling salesman problem with time window, TSPTW)是旅行商问题的一个变种,在物资配送等方面有大量的应用。传统方法的求解时间较长且泛化性较差,为提高TSPTW的求解效率,将求解过程建模为马尔科夫决策过程,定义了状态、动作、奖励,提出了一种基于深度强化学习的Transformer加指针网络的组合模型,通过多头注意力对输入的特征进行编码,采用指针网络求出解的概率分布,所提深度学习网络通过强化学习算法进行训练。实验结果表明:所提方法对比传统的启发式求解算法,可以得到更高质量的解,相较于求解器和启发式算法,有超过数10倍的提升效果,且易于将模型拓展到不同规模的问题上。
