# Graph-Driven Deep Reinforcement Learning for Vehicle Routing Problems with Pickup and Delivery
## 5 Experiments
### Comparison Analysis
#### 5.2.2 Comparison  
The comparison results among heuristic and DRL-based methods on the conventional and improved VRP-PDs are presented in Tables 2 and 3. We report the average tour length, optimality gap, and average computational time over test instances as evaluation metrics to verify the effectiveness of baseline methods. In particular, the optimality gap is calculated as the relative difference between the average tour length \(L_{aver}\) of the method and the best-known solution length \(L_{best}\) obtained by all comparative methods.  
\[Gap=\frac{L_{aver}-L_{best}}{L_{best}}\times 100\%. \tag{23}\]  
Regarding the conventional VRP-PD, CPLEX achieves the optimal tour length on small-scale problems with 20 nodes. However, as the problem scale increases gradually, the solution quality of CPLEX significantly drops with a limited computational time, especially when confronted with the problem with 150 nodes. In contrast, LKH, standing out as a powerful heuristic routing solver, exhibits the best performance among problems with four different scales, which provides the optimal baseline for gap calculation. In comparison with heuristic and DRL-based methods, GDRL attains the most competitive routing performance. Taking the conventional VRP-PD with 100 nodes as an example, GDRL achieves an average length of 17.94, reducing the length of 19.17, 17.22, 1.29, and 19.04 separately when compared with ACO, ALNS, POMO, and FER. For \(N=150\), the proposed approach obtains an optimality gap of 18.28%, outperforming the second-best model (i.e., POMO) by a reduction of 5.81%.  
As for the improved VRP-PD, CPLEX provides the best tour length on problems with 20, 50, and 100 nodes, while the proposed approach achieves the best results on the problem with 150 nodes. ALNS exhibits desirable results on sizes \(N=20\), 50, 100, and 150 among heuristic methods, but they are inferior to the proposed GDRL with longer traveling lengths of 4.02, 8.56, 17.22, and 17.59. In comparison with the second-best method POMO, GDRL achieves an average tour length of 4.68, 7.56, 11.36, and 13.06 on problems with 20, 50, 100, and 150 nodes, decreasing the optimality gap by 3.14%, 5.46%, 4.70%, and 15.39%, respectively. Regarding the solving speed, the proposed approach decreases the computational time by an order of magnitude in contrast with DRL-based AM (sampling) and FER while also achieving the most excellent routing performance on four problem sizes. In order to more intuitively demonstrate the superiority of our solution results, we visualize the detailed traversing routes of POMO and the proposed GDRL on two exemplary instances with 100 and 150 nodes, as shown in Figure 3. It can be observed  
\begin{table}
\begin{tabular}{l c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Method**} & \multicolumn{3}{c}{\(N\) = 20} & \multicolumn{3}{c}{\(N\) = 50} & \multicolumn{3}{c}{\(N\) = 100} & \multicolumn{3}{c}{\(N\) = 150} \\ \cline{2-13}  & **Length** & **Gap** & **Time (s)** & **Length** & **Gap** & **Time (s)** & **Length** & **Gap** & **Time (s)** & **Length** & **Gap** & **Time (s)** \\ \hline CPLEX [31] & 6.59 & 0.00\% & 8.04 & 14.50 & 38.36\% & 3600 & 26.19 & 66.92\% & 3600 & 38.07 & 89.12\% & 3600 \\ LKH [23] & 6.59 & 0.00\% & 0.07 & 10.48 & 0.00\% & 345.06 & 15.69 & 0.00\% & 3600 &  
that GDRL attains a shorter route and avoids inefficient pickups and deliveries. These achievements convincingly demonstrate the superiority of innovative designs for GDRL.