广泛研究和使用旅行推销员问题等图形问题，如旅行推销员问题，或发现最小的施泰纳树在数据工程和计算机科学中使用。通常，在现实世界应用中，图表的特征往往会随着时间的推移而变化，因此，找到问题的解决方案变得具有挑战性。许多图表问题的动态版本是运输，电信和社交网络中普遍世界问题的关键。近年来，利用深度学习技术来寻找NP-Hard图组合问题的启发式解决方案，因为这些学习的启发式可以有效地找到近最佳解决方案。但是，大多数现有的学习启发式方法都关注静态图问题。动态性质使NP-Hard图表问题更具挑战性，并且现有方法无法找到合理的解决方案。在本文中，我们提出了一种名为Cabl时间关注的新型建筑，并利用加固学习（GTA-RL）来学习基于图形的动态组合优化问题的启发式解决方案。 GTA-RL架构包括能够嵌入组合问题实例的时间特征的编码器和能够动态地关注嵌入功能的解码器，以找到给定组合问题实例的解决方案。然后，我们将架构扩展到学习HeuRistics的组合优化问题的实时版本，其中问题的所有输入特征是未知的，而是实时学习。我们针对几种最先进的基于学习的算法和最佳求解器的实验结果表明，我们的方法在动态和效率方面，在有效性和最佳求解器方面优于基于最先进的学习方法。实时图组合优化。

钢筋学习最近在许多组合优化问题中显示了学习质量解决方案的承诺。特别地，基于注意的编码器 - 解码器模型在各种路由问题上显示出高效率，包括旅行推销员问题（TSP）。不幸的是，它们对具有无人机（TSP-D）的TSP表现不佳，需要在协调中路由车辆的异构队列 - 卡车和无人机。在TSP-D中，这两个车辆正在串联移动，并且可能需要在用于其他车辆的节点上等待加入。不那么关注的基于关注的解码器无法在车辆之间进行这种协调。我们提出了一种注意力编码器-LSTM解码器混合模型，其中解码器的隐藏状态可以代表所做的动作序列。我们经验证明，这种混合模型可提高基于纯粹的关注的模型，用于解决方案质量和计算效率。我们对MIN-MAX电容车辆路由问题（MMCVRP）的实验还确认混合模型更适合于多车辆的协调路由而不是基于注意的模型。

The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.

深度强化学习（DRL）赋予了各种人工智能领域，包括模式识别，机器人技术，推荐系统和游戏。同样，图神经网络（GNN）也证明了它们在图形结构数据的监督学习方面的出色表现。最近，GNN与DRL用于图形结构环境的融合引起了很多关注。本文对这些混合动力作品进行了全面评论。这些作品可以分为两类：（1）算法增强，其中DRL和GNN相互补充以获得更好的实用性； （2）特定于应用程序的增强，其中DRL和GNN相互支持。这种融合有效地解决了工程和生命科学方面的各种复杂问题。基于审查，我们进一步分析了融合这两个领域的适用性和好处，尤其是在提高通用性和降低计算复杂性方面。最后，集成DRL和GNN的关键挑战以及潜在的未来研究方向被突出显示，这将引起更广泛的机器学习社区的关注。

组合优化是运营研究和计算机科学领域的一个公认领域。直到最近，它的方法一直集中在孤立地解决问题实例，而忽略了它们通常源于实践中的相关数据分布。但是，近年来，人们对使用机器学习，尤其是图形神经网络（GNN）的兴趣激增，作为组合任务的关键构件，直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入，因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾，旨在优化和机器学习研究人员。

近年来，近年来，加强学习与图形神经网络（GNN）架构相结合，可以学会解决硬组合优化问题：给定原始输入数据和评估者指导过程，这个想法是自动学习策略返回可行和高质量的输出。最近的工作表明了有希望的结果，但后者主要在旅行推销员问题（TSP）和类似的抽象变体上进行评估，例如分割输送车辆路由问题（SDVRP）。在本文中，我们分析了如何以及最近的神经架构如何应用于实际重要性的图表问题。因此，我们将这些架构系统上“将这些架构转移到电力和信道分配问题（PCAP），其具有实际相关性，例如无线网络中的无线电资源分配。我们的实验结果表明现有的架构（I）仍然无法捕获图形结构特征，并且（II）不适合图表上的动作更改图形属性的问题。在一个积极的票据上，我们表明，增强了距离编码问题的结构表示是迈向学习多用途自主求解器的仍然雄心勃勃的目标的有希望的一步。

最近的研究表明，神经组合优化（NCO）在许多组合优化问题（如路由）中具有优于传统算法的优点，但是对于涉及相互条件的动作空间的包装，诸如打包的更加复杂的优化任务的效率较低。在本文中，我们提出了一种经常性的条件查询学习（RCQL）方法来解决2D和3D包装问题。我们首先通过经常性编码器嵌入状态，然后采用先前操作的条件查询注意。条件查询机制填充了学习步骤之间的信息差距，将问题塑造为Markov决策过程。从复发中受益，单个RCQL模型能够处理不同尺寸的包装问题。实验结果表明，RCQL可以有效地学习用于离线和在线条带包装问题（SPP）的强烈启发式，优于空间利用率范围广泛的基线。 RCQL与最先进的方法相比，在离线2D 40盒案例中将平均箱间隙比率降低1.83％，3.84％。同时，我们的方法还实现了5.64％的空间利用率，对于1000件物品的空间利用率比现有技术更高。

事件处理是动态和响应互联网（物联网）的基石。该领域的最近方法基于代表性状态转移（REST）原则，其允许将事件处理任务放置在遵循相同原理的任何设备上。但是，任务应在边缘设备之间正确分布，以确保公平资源利用率和保证无缝执行。本文调查了深入学习的使用，以公平分配任务。提出了一种基于关注的神经网络模型，在不同场景下产生有效的负载平衡解决方案。所提出的模型基于变压器和指针网络架构，并通过Advantage演员批评批评学习算法训练。该模型旨在缩放到事件处理任务的数量和边缘设备的数量，不需要重新调整甚至再刷新。广泛的实验结果表明，拟议的模型在许多关键绩效指标中优于传统的启发式。通用设计和所获得的结果表明，所提出的模型可能适用于几个其他负载平衡问题变化，这使得该提案是由于其可扩展性和效率而在现实世界场景中使用的有吸引力的选择。

Influence Maximization (IM) is a classical combinatorial optimization problem, which can be widely used in mobile networks, social computing, and recommendation systems. It aims at selecting a small number of users such that maximizing the influence spread across the online social network. Because of its potential commercial and academic value, there are a lot of researchers focusing on studying the IM problem from different perspectives. The main challenge comes from the NP-hardness of the IM problem and \#P-hardness of estimating the influence spread, thus traditional algorithms for overcoming them can be categorized into two classes: heuristic algorithms and approximation algorithms. However, there is no theoretical guarantee for heuristic algorithms, and the theoretical design is close to the limit. Therefore, it is almost impossible to further optimize and improve their performance. With the rapid development of artificial intelligence, the technology based on Machine Learning (ML) has achieved remarkable achievements in many fields. In view of this, in recent years, a number of new methods have emerged to solve combinatorial optimization problems by using ML-based techniques. These methods have the advantages of fast solving speed and strong generalization ability to unknown graphs, which provide a brand-new direction for solving combinatorial optimization problems. Therefore, we abandon the traditional algorithms based on iterative search and review the recent development of ML-based methods, especially Deep Reinforcement Learning, to solve the IM problem and other variants in social networks. We focus on summarizing the relevant background knowledge, basic principles, common methods, and applied research. Finally, the challenges that need to be solved urgently in future IM research are pointed out.

机器学习（ML）方法已成为解决车辆路由问题的有用工具，可以与流行的启发式方法或独立模型结合使用。但是，当解决不同大小或不同分布的问题时，当前的方法的概括不佳。结果，车辆路由中的ML见证了一个扩展阶段，为特定问题实例创建了新方法，这些方法在较大的问题大小上变得不可行。本文旨在通过理解和改善当前现有模型，即Kool等人的注意模型来鼓励该领域的整合。我们确定了VRP概括的两个差异类别。第一个是基于问题本身固有的差异，第二个与限制模型概括能力的建筑弱点有关。我们的贡献变成了三倍：我们首先通过适应Kool等人来靶向模型差异。方法及其基于alpha-entmax激活的稀疏动态注意力的损耗函数。然后，我们通过使用混合实例训练方法来靶向固有的差异，该方法已被证明在某些情况下超过了单个实例培训。最后，我们介绍了推理水平数据增强的框架，该框架通过利用模型缺乏旋转和扩张变化的不变性来提高性能。

用于图形组合优化问题的神经网络溶剂的端到端培训，例如旅行销售人员问题（TSP）最近看到了感兴趣的激增，但在几百节节点的图表中保持棘手和效率低下。虽然最先进的学习驱动的方法对于TSP在培训的古典索引时与古典求解器密切相关，但它们无法通过实际尺度的实际情况概括到更大的情况。这项工作提出了一个端到端的神经组合优化流水线，统一几个卷纸，以确定促进比在训练中看到的实例的概括的归纳偏差，模型架构和学习算法。我们的受控实验提供了第一个原则上调查这种零拍摄的概括，揭示了超越训练数据的推断需要重新思考从网络层和学习范例到评估协议的神经组合优化流水线。此外，我们分析了深入学习的最近进步，通过管道的镜头路由问题，并提供新的方向，以刺激未来的研究。

在本文中，我们介绍了有关典型乘车共享系统中决策优化问题的强化学习方法的全面，深入的调查。涵盖了有关乘车匹配，车辆重新定位，乘车，路由和动态定价主题的论文。在过去的几年中，大多数文献都出现了，并且要继续解决一些核心挑战：模型复杂性，代理协调和多个杠杆的联合优化。因此，我们还引入了流行的数据集和开放式仿真环境，以促进进一步的研发。随后，我们讨论了有关该重要领域的强化学习研究的许多挑战和机会。

雇用无人驾驶航空公司（无人机）吸引了日益增长的兴趣，并成为互联网（物联网）网络中的数据收集技术的最先进技术。在本文中，目的是最大限度地减少UAV-IOT系统的总能耗，我们制定了联合设计了UAV的轨迹和选择IOT网络中的群集头作为受约束的组合优化问题的问题，该问题被归类为NP-努力解决。我们提出了一种新的深度加强学习（DRL），其具有顺序模型策略，可以通过无监督方式有效地学习由UAV的轨迹设计来实现由序列到序列神经网络表示的策略。通过广泛的模拟，所获得的结果表明，与其他基线算法相比，所提出的DRL方法可以找到无人机的轨迹，这些轨迹需要更少的能量消耗，并实现近乎最佳性能。此外，仿真结果表明，我们所提出的DRL算法的训练模型具有出色的概括能力，对更大的问题尺寸而没有必要恢复模型。

实际应用程序中的车辆路由问题（VRP）通常会带有各种限制，因此为精确的解决方案方法或启发式搜索方法带来了其他计算挑战。从样本数据中学习启发式移动模式的最新想法已变得越来越有希望减少解决方案发展成本。但是，使用基于学习的方法来解决更多类型的受限VRP仍然是一个挑战。困难在于在寻找最佳解决方案时控制约束违规。为了克服这一挑战，我们提出了一种基于加强学习的方法，通过纳入Lagrangian放松技术并使用受限的策略优化来解决软件限制的VRP。我们将该方法应用于三种常见类型的VRP，旅行推销员问题与时间窗口（TSPTW），电容性VRP（CVRP）和带有时间窗口（CVRPTW）的电容VRP，以显示所提出方法的普遍性。在与现有的基于RL的方法和开源启发式求解器进行比较之后，我们展示了其在旅行距离，违规距离和推理速度方面良好平衡的解决方案方面的竞争性能。

多个旅行推销员问题（MTSP）是众多现实世界应用的众所周知的NP硬性问题。特别是，这项工作涉及Minmax MTSP，其目的是最大程度地减少所有代理商之间的最大巡回演出长度。许多机器人部署需要经常重新计算潜在的大型MTSP实例，从而使计算时间和解决方案质量的自然权衡非常重要。但是，由于其计算复杂性，精确和启发式算法随着城市数量的增加而效率低下。在最新的深入学习学习（DRL）方面的鼓励下，这项工作将MTSP作为一项合作任务，并引入了Dan，Dan是一种分散的基于注意力的神经方法，旨在解决这一关键权衡。在丹中，代理商通过预测彼此的未来决策来学习完全分散的政策，以合作构建巡回演出。我们的模型依赖于变压器体系结构，并使用具有参数共享的多代理RL进行了训练，从而为代理和城市的数量提供了自然的可扩展性。我们对小型至大规模MTSP实例的实验结果（$ 50至$ 1000 $的城市，$ 5 $至20美元的代理商）表明，Dan能够匹配或超越最先进的求解器，同时保持计划时间较低。特别是，在相同的计算时间预算的情况下，DAN在大规模实例（超过100个城市，超过5个代理商）上优于所有基于常规和DRL的基线，并展示了增强的代理协作。一段视频解释了我们的方法并介绍了我们的结果，请参见\ url {https://youtu.be/xi3clsdslvs}。

最近，变压器已成为解决车辆路由问题（VRP）的盛行深度建筑。但是，它在学习VRP的学习改进模型方面的有效性较小，因为其位置编码（PE）方法不适合表示VRP解决方案。本文介绍了一种新颖的双重协作变压器（DACT），以分别学习节点和位置特征的嵌入，而不是像现有的那样将它们融合在一起，以避免潜在的噪音和不相容的相关性。此外，位置特征通过新型的循环位置编码（CPE）方法嵌入，以使变压器有效捕获VRP溶液（即环状序列）的圆形性和对称性。我们使用近端政策优化训练DACT，并设计一种课程学习策略，以提高样本效率。我们应用DACT来解决旅行推销员问题（TSP）和电容的车辆路由问题（CVRP）。结果表明，我们的DACT优于现有的基于变压器的改进模型，并且在合成和基准实例上分别在不同问题大小上表现出更好的概括性能。

This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.

Steiner树问题（STP）在图中旨在在连接给定的顶点集的图表中找到一个最小权重的树。它是一种经典的NP - 硬组合优化问题，具有许多现实世界应用（例如，VLSI芯片设计，运输网络规划和无线传感器网络）。为STP开发了许多精确和近似算法，但它们分别遭受高计算复杂性和弱案例解决方案保证。还开发了启发式算法。但是，它们中的每一个都需要应用域知识来设计，并且仅适用于特定方案。最近报道的观察结果，同一NP-COLLECLIAL问题的情况可能保持相同或相似的组合结构，但主要在其数据中不同，我们调查将机器学习技术应用于STP的可行性和益处。为此，我们基于新型图形神经网络和深增强学习设计了一种新型模型瓦坎。 Vulcan的核心是一种新颖的紧凑型图形嵌入，将高瞻度图形结构数据（即路径改变信息）转换为低维矢量表示。鉴于STP实例，Vulcan使用此嵌入来对其路径相关的信息进行编码，并基于双层Q网络（DDQN）将编码的图形发送到深度加强学习组件，以找到解决方案。除了STP之外，Vulcan还可以通过将解决方案（例如，SAT，MVC和X3C）来减少到STP来找到解决方案。我们使用现实世界和合成数据集进行广泛的实验，展示了vulcan的原型，并展示了它的功效和效率。

SNCF, the French public train company, is experimenting to develop new types of transportation services by tackling vehicle routing problems. While many deep learning models have been used to tackle efficiently vehicle routing problems, it is difficult to take into account time related constraints. In this paper, we solve the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and the Capacitated Pickup and Delivery Problem with Time Windows (CPDPTW) with a constructive iterative Deep Learning algorithm. We use an Attention Encoder-Decoder structure and design a novel insertion heuristic for the feasibility check of the CPDPTW. Our models yields results that are better than best known learning solutions on the CVRPTW. We show the feasibility of deep learning techniques for solving the CPDPTW but witness the limitations of our iterative approach in terms of computational complexity.

这篇简短的评论旨在使读者熟悉与计划，调度和学习有关的最新作品。首先，我们研究最先进的计划算法。我们简要介绍神经网络。然后，我们更详细地探索图形神经网络，这是一种适合处理图形结构输入的神经网络的最新变体。我们简要描述了强化学习算法和迄今为止设计的一些方法的概念。接下来，我们研究了一些成功的方法，结合了用于路径规划的神经网络。最后，我们专注于不确定性的时间计划问题。