关键词:
深度强化学习
车辆路径问题
注意力模型
分层优化
摘要:
针对带容量约束的车辆路径问题(capacitated vehicle routing problem,CVRP),提出一种利用层次结构对容量约束进行解耦的方法,将复杂的CVRP拆分为约束规划和路径规划,并分别进行深度强化学习(deep reinforcement learning,DRL)优化求解。首先,上层基于注意力模型和采样机制对配送任务进行分配,规划出满足容量约束的子回路集。其次,下层采用预训练的无约束的注意力机制模型,对子回路集进行路径规划。最后,通过Reinforce算法反馈训练和迭代优化上层的网络参数。实验结果表明,该方法对不同规模的CVRP和异构CVRP任务具有泛化性,性能优于最先进的DRL方法;并且与其他启发式方法相比,在批量运算任务中,求解速度提升10倍以上,且保持具有竞争力的解。