# A Deep Reinforcement Learning-Based Decision-Making Approach for Routing Problems
## 1 Introduction  
Routing problems constitute a fundamental class of combinatorial optimization challenges that have been extensively explored in operations research and computer science [1]. Broadly, these problems seek to determine the shortest feasible tour for serving geographically distributed customer nodes while satisfying a set of problem-specific constraints. A range of well-known problems, such as the traveling salesman problem (TSP) [2] and the capacitated vehicle routing problem (CVRP) [3], have attracted significant attention due to their broad applicability in domains including robot route planning [4], express logistic management [5], transportation control [6], and so forth. Traditional approaches to routing can be broadly categorized into exact and heuristic algorithms. Exact algorithms, like branch-and-price-and-cut [7], provide theoreticalguarantees of finding optimal solutions, but are computationally prohibitive for large-scale problems due to their exponential complexity. In comparison, heuristic algorithms, such as ant colony optimization [8], employ manually designed rules to navigate the solution space, striking a balance between solution quality and computational efficiency. Nevertheless, these heuristic methods are highly dependent on extensive domain expertise, limiting their adaptability to complex real-world applications. In recent times, with the promising advancements of neural networks and reinforcement learning in various domains [9; 10], there has been a growing interest in leveraging deep reinforcement learning (DRL) techniques to tackle a variety of routing problems [11; 12; 13]. DRL-based approaches formulate the routing issue as a sequential decision-making process and exploit the parallel computing capabilities of graphics processing units (GPUs) to enhance search efficiency. Notably, DRL models are able to identify latent patterns from large-scale instances and autonomously learn effective decision-making strategies, enabling the construction of high-quality routes within reasonable time frames. Despite their notable success, DRL-based approaches face several limitations. First of all, most learning-based methods rely on classical transformer architectures to generate high-dimensional embeddings of customer nodes, yet these conventional designs fall short of capturing effective state representations. Second, existing methods employ simplistic context embeddings to encode environmental information, limiting their ability to accurately model real-time state transitions and graph variations. Third, current methods fail to account for the inherent symmetry and circularity of routing solutions, restricting their capacity to learn more efficient decision-making strategies from a fixed number of training instances. To address these challenges, we introduce a deep reinforcement learning-based decision-making (DRL-DM) framework, which leverages an encoder-decoder architecture to solve complex routing problems. In the encoding phase, we integrate a batch normalization fronting mechanism and a gate-like threshold block to enhance feature extraction and representation, producing more informative node embeddings for decision-making. As shown in Figure 1, in the decoding phase, we design a dynamic-aware context embedding that captures time-varying environmental information. This refined embedding constructs multiple relational structures, incorporating embeddings of visited and unvisited nodes, as well as the starting and ending points, thereby enabling a more accurate representation of state transitions. To further optimize policy learning, we account for the inherent symmetry and circularity of routing solutions by introducing multiple starting nodes per instance. This design facilitates policy optimization across multiple trajectories, promoting broader exploration of the solution space while leveraging the same set of instances.