# A Deep Reinforcement Learning-Based Decision-Making Approach for Routing Problems
## 4 Experiments
### Comparison Analysis  
The detailed descriptions of baseline methods are listed as follows:  
1. Concorde [14]: A mature exact solver tailored for TSPs, which has been applied to scenes like vehicle routing, gene mapping, and so on. 2. Gurobi [28]: A most powerful commercial optimizer that models routing problems as mathematical programming and attains excellent solutions. 3. LKH-3 [29]: The practical decision-making technique that achieves state-of-the-art performance in a variety of routing problems. 4. Google OR Tools (v9.11) [30]: A fast and portable software specialized for combinatorial optimization problems. 5. GA [31]: The genetic algorithm which utilizes crossover and mutation operations to search for optimal solutions based on natural selection. 6. SA [32]: The simulated annealing approach that involves heating and controlled cooling strategies to approximate the global optimum in TSPs and CVRPs. 7. ACO [33]: The ant colony optimization that uses artificial ants to explore the entire environment via pheromone-based communication, thereby ultimately finding satisfactory routing results. 8. AM [22]: A milestone DRL-based method that, for the first time, introduces a transformer-based encoder-decoder framework to tackle different kinds of routing problems. 9. [PERSON] et al. [24]: A DRL-based approach that learns improvement heuristics to handle routing problems. Figure 3: The training procedure of our DRL-DM. The training set comprises both synthetic datasets and real-world benchmarks with diverse node distributions, including uniform, explosion, and implosion patterns. As illustrated in the training pipeline, the encoder (depicted in the gray box) is designed to extract underlying structural features from the input nodes. The decoder (shown in the light green box) then iteratively utilizes these encoded representations to determine the next node to visit, thereby constructing feasible routing solutions in a sequential manner. 10. DACT [25]: The improvement-based DRL model which exploits the circularity attribute inherent in traversal routes and designs a dual-aspect attention mechanism to find optimal solutions. 11. Neural-2-Opt [34]: The DRL-based model that learns to select 2-opt operators for local search and exhibits near-optimal results with relatively fast solving speed. 12. POMO [23]: A state-of-the-art DRL-based approach that learns parallel policies with multiple optima and achieves superior performance in various routing problems. 13. NeuRewritter [35]: A neural-based method that learns an elaborated policy to iteratively rewrite local components of the current route and improves it until convergence. Tables 1 and 2 illustrate the routing performance between baseline methods and our approach to TSPs and CVRPs. From an overall perspective, our DRL-DM consistently outperforms other heuristic and learning-based methods by a clear margin. Its advantage becomes more pronounced especially when the problem sizes gradually increase. This achievement convincingly demonstrates the effectiveness and efficiency of the proposed model in tackling practical large-scale problems in real-life scenarios. For TSPs, the optimal results are calculated based on the exact solver Concorde [14] with sufficient solving time. As shown in Table 1, it can be observed that DRL-DM outstrips the milestone DRL-based method, AM [22], by a gap reduction of 0.52%, 1.57%, and 2.06% in TSP20, TSP50, and TSP100, respectively. When compared with heuristic methods, the advantage becomes more significant. For example, in TSP100, the optimality gap of our approach is 3.22%, 2.96%, and 2.83% lower than that of GA [31], SA [32], and ACO [33] separately. Regarding the state-of-the-art POMO [23], our proposed approach achieves shorter route lengths while maintaining the same magnitude of running time on TSPs with various scales. These accomplishments reveal the superiority of our well-designed GT block and dynamic-aware context embedding.