# Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems
## 4 Experiments  
### Experiment Settings  
We focus on three types of VRPs in our experiments: (1) TSP; (2) CVRP; and (3) OP. Generally, the objective of the TSP is to determine the shortest path that starts and ends at a depot while visiting all nodes exactly once. The CVRP, a generalized case of TSP, requires that each vehicle departs from a central depot, visits a set of customer nodes, and completes all delivery tasks within specified capacity constraints. In the OP, each node is associated with a prize value, and the goal is to construct a single path starting and ending at the depot, aiming to maximize the total prize collected while staying within the maximum routing length constraint. Furthermore, following adjustments to the input, masking rules, and decoder context vectors, the model is also capable of addressing other variants of VRP as well as more complex real-world routing challenges. For each problem, we follow [25,41] to conduct experiments with node sizes of \(\{20,50,100\}\). For each problem instance, the coordinates of the nodes are randomly generated within the region \([0,1]\times[0,1]\). The vehicle capacities of CVRP are set to \(\{30,40,50\}\) for problems with \(\{20,50,100\}\) nodes, while the demand at each customer node is assigned values from \(\{1,2,\ldots,9\}\). For OP, the maximum path length constraints for instances of different node sizes are set to \(\{2,3,4\}\), respectively. We train the models for 100 epochs, during which 1,280,000 instances are generated in real time with a batch size of 512 per epoch (we specifically generate 320,000 instances and use a batch size of 128 for CVRP50 and CVRP100). We use the rollout baseline as the baseline estimator and employ the Adam optimizer for model training. Additionally, we construct a test set consisting of 1000 instances, which follows the same distribution as the training data. Other relevant hyperparameter settings used in our framework are detailed in Table 1. All our experiments are conducted on an Intel Core i5-12600 KF CPU and an NVIDIA GeForce RTX 4060 GPU. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Parameters** & **Value** & **Parameter** & **Value** \\ \hline Node embedding dimension & 128 & Number of decoders \(K\) & 8 \\ Edge embedding dimension & 64 & Tanh clip \(C\) & 10 \\ Number of encoder layers \(L\) & 3 & Balance coefficient \(\lambda_{JS}\) & 0.01 \\ Number of attention heads \(H\) & 8 & Initial learning rate & \(10^{-4}\) \\ FFN dimension & 512 & Learning rate decay & 0.96 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Hyperparameter values. Figure 3: Training policy of our E-MTAM. For evaluation, we consider the average tour length, optimality gap, and running time to assess the performance of a method on a given problem. The optimality gap quantifies the difference between the obtained result and the best result:  
\[Gap^{l}=\frac{L_{mean}-L_{best}}{L_{best}}\times 100\% \tag{22}\]  
where \(L_{mean}\) denotes the average tour length across all test instances, while \(L_{best}\) represents the best-known result for the given problem. Similarly, we calculate the optimality gap of OP using the average collected prize \(P_{mean}\) and the maximum prize \(P_{best}\):  
\[Gap^{p}=\frac{P_{mean}-P_{best}}{P_{best}}\times 100\% \tag{23}\]  
We compare our proposed E-MTAM against a range of traditional and DRL-based approaches for solving VRPs. These baselines include the following:  
1. Concorde [29]: a specialized exact solver for solving TSP;
2. LKH [15]: a state-of-the-art heuristic optimization solver;
3. Gurobi [44]: a commercial optimization solver;
4. OR Tools [45]: an open source software suite developed by Google for solving optimization problems such as routing, scheduling, and linear programming;
5. ACO [46]: a heuristic algorithm inspired by the foraging behavior of ants, used to solve combinatorial optimization problems;
6.