王 原 陈 名 邢立宁 吴亚辉 马武彬 赵 宏

1(国防科技大学系统工程学院 长沙 410073) 2(湖南安全技术职业学院 长沙 410151)

组合优化问题(combinatorial optimization problem, COP)的求解一直是运筹学领域的一个重要研究方向.典型组合优化问题如旅行商问题(travelling salesman problem, TSP)、车辆路径问题(vehicle routing problem, VRP)、作业车间调度问题(job shop scheduling problem, JSSP)等通常均属于NP-Hard问题.因此，针对组合优化问题设计高效的求解算法一直是该领域的重要研究方向.

目前针对组合优化问题的求解方法一般被分为2种类型：近似算法(approximation algorithm)以及精确算法(exact algorithm).这2类方法面临2个问题的挑战[1-2]：1) 精确算法求解的时间消耗随着问题规模的扩大急遽上升，针对较大规模问题无法在可接受时间内取得最优解；2) 设计有效的启发式算法需要大量针对性的领域知识以及大量的试错(trial-and-error).因此，如何针对组合优化问题设计有效的求解算法，仍然面临重重困难.

近年来，一批深度强化学习方法在组合优化问题的新应用的提出给本问题的解决带来新的思路[3].得益于端到端学习(end-to-end learning)模型[4]的提出，深度强化学习方法能够通过在同一问题分布的不同实例上的训练来提取有关问题实例的深层特征，并基于问题特征对问题实例进行求解.深度强化学习方法在求解组合优化问题时具有如下2个特征：

1) 深度强化学习能够通过训练的方式搜索问题分布的特征并进行求解模型的自完善，且该过程不需要模型设计者掌握问题相关的领域知识；

2) 模型训练结束后，深度强化学习在求解时，能够以O(n)的时间复杂度求解问题实例.