【阿姆斯特丹博士论文】组合空间的学习与优化:专注于车辆路径的深度学习，172页pdf

在本文中，我们开发了使用机器学习来解决组合优化问题的方法，重点是车辆路径问题。本文由两部分组成。在第一部分(第3章和第4章)中，我们开发了使用机器学习模型来解决不同变体的车辆路径问题的实用方法。由于这些模型表示组合空间上的概率分布，在第二部分(第5章和第6章)中，我们将重点从这些模型中采样并优化它们的参数。具体来说，在第3章中，我们使用强化学习来训练注意力模型，该模型代表一种构造启发式，以解决不同变体的路由问题。在第4章中，我们将介绍深度策略动态规划，它使用另一个学习到的模型来指导受限动态规划算法，以提高路由问题的性能和处理复杂约束(如时间窗口)的能力。鉴于组合问题的确定性，第一部分中模型中的重复样本是没有信息量的，因此第二部分侧重于从这些模型中进行无替换的采样。在第5章中，提出了Gumbel-top-k采样，作为一种从组合域的结构化模型中无替换地提取样本的有效方法，并说明了路由问题以外的一般适用性。在第6章中，我们推导了基于这些无替换样本的统计梯度估计器，该估计器可用于改进第3章中基于梯度的模型训练过程。