  Travelling Salesperson Problems (TSPs) and Vehicle Routing Problems (VRPs)
have achieved reasonable improvement in accuracy and computation time with the
adaptation of Machine Learning (ML) methods. However, none of the previous
works completely respects the symmetries arising from TSPs and VRPs including
rotation, translation, permutation, and scaling. In this work, we introduce the
first-ever completely equivariant model and training to solve combinatorial
problems. Furthermore, it is essential to capture the multiscale structure
(i.e. from local to global information) of the input graph, especially for the
cases of large and long-range graphs, while previous methods are limited to
extracting only local information that can lead to a local or sub-optimal
solution. To tackle the above limitation, we propose a Multiresolution scheme
in combination with Equivariant Graph Attention network (mEGAT) architecture,
which can learn the optimal route based on low-level and high-level graph
resolutions in an efficient way. In particular, our approach constructs a
hierarchy of coarse-graining graphs from the input graph, in which we try to
solve the routing problems on simple low-level graphs first, then utilize that
knowledge for the more complex high-level graphs. Experimentally, we have shown
that our model outperforms existing baselines and proved that symmetry
preservation and multiresolution are important recipes for solving
combinatorial problems in a data-driven manner. Our source code is publicly
available at https://github.com/HySonLab/Multires-NP-hard
