  Deep reinforcement learning (DRL)-based combinatorial optimization (CO)
methods (i.e., DRL-NCO) have shown significant merit over the conventional CO
solvers as DRL-NCO is capable of learning CO solvers less relying on
problem-specific expert domain knowledge (heuristic method) and supervised
labeled data (supervised learning method). This paper presents a novel training
scheme, Sym-NCO, which is a regularizer-based training scheme that leverages
universal symmetricities in various CO problems and solutions. Leveraging
symmetricities such as rotational and reflectional invariance can greatly
improve the generalization capability of DRL-NCO because it allows the learned
solver to exploit the commonly shared symmetricities in the same CO problem
class. Our experimental results verify that our Sym-NCO greatly improves the
performance of DRL-NCO methods in four CO tasks, including the traveling
salesman problem (TSP), capacitated vehicle routing problem (CVRP), prize
collecting TSP (PCTSP), and orienteering problem (OP), without utilizing
problem-specific expert domain knowledge. Remarkably, Sym-NCO outperformed not
only the existing DRL-NCO methods but also a competitive conventional solver,
the iterative local search (ILS), in PCTSP at 240 faster speed. Our source code
is available at https://github.com/alstn12088/Sym-NCO.
