Learning to Iteratively Solve Routing Problems with Dual-Aspect\n Collaborative Transformer

Abstract

Recently, Transformer has become a prevailing deep architecture for solving\nvehicle routing problems (VRPs). However, it is less effective in learning\nimprovement models for VRP because its positional encoding (PE) method is not\nsuitable in representing VRP solutions. This paper presents a novel Dual-Aspect\nCollaborative Transformer (DACT) to learn embeddings for the node and\npositional features separately, instead of fusing them together as done in\nexisting ones, so as to avoid potential noises and incompatible correlations.\nMoreover, the positional features are embedded through a novel cyclic\npositional encoding (CPE) method to allow Transformer to effectively capture\nthe circularity and symmetry of VRP solutions (i.e., cyclic sequences). We\ntrain DACT using Proximal Policy Optimization and design a curriculum learning\nstrategy for better sample efficiency. We apply DACT to solve the traveling\nsalesman problem (TSP) and capacitated vehicle routing problem (CVRP). Results\nshow that our DACT outperforms existing Transformer based improvement models,\nand exhibits much better generalization performance across different problem\nsizes on synthetic and benchmark instances, respectively.\n