  Traditional solvers for tackling combinatorial optimization (CO) problems are
usually designed by human experts. Recently, there has been a surge of interest
in utilizing deep learning, especially deep reinforcement learning, to
automatically learn effective solvers for CO. The resultant new paradigm is
termed neural combinatorial optimization (NCO). However, the advantages and
disadvantages of NCO relative to other approaches have not been empirically or
theoretically well studied. This work presents a comprehensive comparative
study of NCO solvers and alternative solvers. Specifically, taking the
traveling salesman problem as the testbed problem, the performance of the
solvers is assessed in five aspects, i.e., effectiveness, efficiency,
stability, scalability, and generalization ability. Our results show that the
solvers learned by NCO approaches, in general, still fall short of traditional
solvers in nearly all these aspects. A potential benefit of NCO solvers would
be their superior time and energy efficiency for small-size problem instances
when sufficient training instances are available. Hopefully, this work would
help with a better understanding of the strengths and weaknesses of NCO and
provide a comprehensive evaluation protocol for further benchmarking NCO
approaches in comparison to other approaches.
