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 this https URL

通过多分辨率和对称性保持，我们提出了一种新的数据驱动方法来解决旅行推销员问题和车辆路径问题。实验证明，我们的模型超过了现有的基准线，并证明了对称性保持和多分辨率对于解决组合问题的重要性。