论文部分内容阅读
限量弧路由问题(capacitated arc routing problem,简称CARP)是一类有挑战性的复杂组合优化问题,在现实世界中有着广泛的应用,如市政服务、物流运输、城市垃圾回收、电力线路检查、自动引导车路径规划。在过去数十年的研究中,启发式算法被主要用来求解限量弧路由问题。然而,对于给定的一个待求解的限量弧路由问题样例,大多数启发式算法需要从零开始进行迭代搜索来寻找问题的解。这一过程往往非常耗时,因此现有的启发式算法难以被应用到一些需要实时求解的问题场景中。受近几年快速发展的深度学习研究的启发,本文提出了一种全新的范式来求解限量弧路由问题。预先通过大量的问题样例训练得到的深度神经网络模型作为神经求解器。在新的待求解的问题样例上,求解过程将转化为耗时很低的神经求解器的测试过程。对比启发式算法,神经求解器的目标是在允许小幅度损失解的质量的范围内,极大地提高求解速度。本文针对这一目标展开研究,提出了两个不同的CARP神经求解器。本文首先提出了一个基于序列到序列模型和采用监督学习进行训练的神经求解器。问题样例和启发式算法在对应样例上给出的解作为输入和标记值来构造产生每一个训练样本。通过图嵌入和预排序方法,每一个样本中的输入和标记值被构造为两个序列,限量弧路由问题的求解过程即被转化为一个序列到序列(sequence-to-sequence,简称seq2seq)的预测过程。该方法采用一个编码器-解码器模型(encoder-decoder)作为神经求解器来完成序列到序列的映射,并使用监督学习训练这个模型。通过监督学习,启发式算法在历史数据上的求解经验被转移到神经求解器内,在一定程度上保证了解的质量。鉴于有标记的数据在一些场景下难以获得,本文提出了一个基于集合到序列模型和采用强化学习进行训练的神经求解器。强化学习将最大化累积奖励作为训练目标,不需要额外准备有标记的数据。在该方法中,引入图卷积网络(graph convolutional network,简称GCN)模型和两个编码器-解码器模型将限量弧路由问题的求解过程转化为集合到序列(set-to-sequence)的过程。整个模型被参数化为一个生成有效解的策略。通过将执行策略得到的解对应的代价函数值映射为奖励信号,并使用经典的REINFORCE算法优化策略中的参数,神经求解器能够学习到有效地求解方法。实验结果验证了这两种方法在产生的解不明显差于启发式算法的情况下,求解速度可以得到显著的提升。