The neural combinatorial optimization (NCO) approach has shown great
potential for solving routing problems without the requirement of expert
knowledge. However, existing constructive NCO methods cannot directly solve
large-scale instances, which significantly limits their application prospects.
To address these crucial shortcomings, this work proposes a novel
Instance-Conditioned Adaptation Model (ICAM) for better large-scale
generalization of neural combinatorial optimization. In particular, we design a
powerful yet lightweight instance-conditioned adaptation module for the NCO
model to generate better solutions for instances across different scales. In
addition, we develop an efficient three-stage reinforcement learning-based
training scheme that enables the model to learn cross-scale features without
any labeled optimal solution. Experimental results show that our proposed
method is capable of obtaining excellent results with a very fast inference
time in solving Traveling Salesman Problems (TSPs) and Capacitated Vehicle
Routing Problems (CVRPs) across different scales. To the best of our knowledge,
our model achieves state-of-the-art performance among all RL-based constructive
methods for TSP and CVRP with up to 1,000 nodes.

大规模神经组合优化模型的实例条件适应模型 (ICAM) 和基于强化学习的训练方案可在不同规模下解决旅行商问题 (TSP) 并实现最佳性能。

基于实例的适应性算法用于大规模神经组合优化问题通用化

Instance-Conditioned Adaptation for Large-scale Generalization of Neural  Combinatorial Optimization

This paper addresses the Capacitated Arc Routing Problem (CARP) using an Ant
Colony Optimization scheme. Ant Colony schemes can compute solutions for medium
scale instances of VRP. The proposed Ant Colony is dedicated to large-scale
instances of CARP with more than 140 nodes and 190 arcs to service. The Ant
Colony scheme is coupled with a local search procedure and provides high
quality solutions. The benchmarks we carried out prove possible to obtain
solutions as profitable as CARPET ones can be obtained using such scheme when a
sufficient number of iterations is devoted to the ants. It competes with the
Genetic Algorithm of Lacomme et al. regarding solution quality but it is more
time consuming on large scale instances. The method has been intensively
benchmarked on the well-known instances of Eglese, DeArmon and the last ones of
Belenguer and Benavent. This research report is a step forward CARP resolution
by Ant Colony proving ant schemes can compete with Taboo search methods and
Genetic Algorithms

使用 Ant Colony Optimization 算法解决 Capacitated Arc Routing Problem，使用本地搜索算法进行优化，对大规模实例进行了基准测试，并证明了 Ant Colony 算法可以与 Taboo 搜索方法和遗传算法竞争。

针对 CARP 的首个蚁群竞争方案

First Competitive Ant Colony Scheme for the CARP

A hallmark of intelligence is the ability to deduce general principles from
examples, which are correct beyond the range of those observed. Generalized
Planning deals with finding such principles for a class of planning problems,
so that principles discovered using small instances of a domain can be used to
solve much larger instances of the same domain. In this work we study the use
of Deep Reinforcement Learning and Graph Neural Networks to learn such
generalized policies and demonstrate that they can generalize to instances that
are orders of magnitude larger than those they were trained on.

从小数据域中学习推导出可适用于远大于其所训练数据范围的领域的普遍性规则，本文研究了深度强化学习和图神经网络在学习这种广义策略的应用，并证明其具有普遍性。