# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 4 Computational Experiments
### Evaluation of the Heuristic's Performance  
The KSSP_LL_Heap method was evaluated against Y, NC, and SB algorithms based on computational time and solution quality. The experiment was conducted with the randomly selected 50 OD pairs for the single destination case and from the origins of the 50 pairs to all destinations in the network for the multi-destination case (KSSP-OA problem). The reported results for each case represent the average over all instances when \(k\) was fixed at 100, 500, 1000, 1500, and 2000. Existing algorithms perform well for a single destination but struggle to scale effectively to multiple destinations. Figure 3 shows the average computational time taken by the algorithms to find KSSP for all destinations. Compared to the single destination case, for the benchmark algorithms, the run times increased by 386 times, 946 times, 3262 times, 3936 times, and 6325 times on average for the Anaheim, Barcelona, Rome, Hessen, and Austin networks, respectively. In contrast, it was only 1.35 times, 1.63 times, 1.76 times, 1.74 times, and 2.64 times for KSSP_LL_Heap. Figure 2: Computational performance of the heuristic with different data structure combinations. (**a**) Anaheim network. (**b**) Barcelona network. (**c**) Rome network. (**d**) Hessen network. (**e**) Austin network. Figure 3: The computational time of KSSP algorithms from a single origin to multiple destinations. (**a**) Anaheim network. (**b**) Barcelona network. (**c**) Rome network. Note: Y and NC algorithms exceeded the running time threshold from \(k=500\) and \(k=1500\), respectively. (**d**) Hessen network. Note: Y, NC, and SB algorithms exceeded the running time threshold from \(k=100\), \(k=1000\), and \(k=100\), respectively. (**e**) Austin network. Note: Y, NC, and SB algorithms exceeded the running time threshold from \(k=100\), \(k=500\), and \(k=1000\), respectively. For multiple destinations, it is clear from Figure 3 that KSSP_LL_Heap outperforms other algorithms in terms of computational time. KSSP_LL_Heap provides a speedup of 29 to 1416 times across the networks and gets better as the network size grows. While the heuristic does not guarantee an optimal solution, it offers a significant computational advantage at the expense of a slight compromise in solution quality. Figure 4 shows that the quality of the heuristic solution is only marginally worse than the optimal solution across networks and the number of paths found. Moreover, for a given \(k\), the solution accuracy is mostly higher for larger networks. The average deviation in the \(k\)th path cost is at most 0.167% of the actual \(k\)th path cost. It is also observed that the solution quality improves when the number of paths to be found increases. This finding suggests that one could almost always find the optimal solution with the heuristic by setting \(k\) to be larger than needed while still having the computational benefits. To further understand this tradeoff between speed and accuracy, an experiment was conducted where the number of labels created (\(k^{\prime}\)) was set to be higher than \(k\) (the number of simple paths required). Figure 5 illustrates the speed-accuracy tradeoff as a function of \(k^{\prime}\) when \(k\) is 100. It is seen that the deviation in the \(k\)th path cost could be driven towards zero by increasing the number of labels for each node by a certain percentage of \(k\). In all cases, the deviations are in the order of 0.004 to 0.147% (i.e., 99.853 to 99.996% accurate). Across all networks, we observed a consistent trend: as \(k^{\prime}\) increased, the accuracy improved, while the computational time increased marginally. This trend is particularly evident in the Barcelona network (Figure 5b), where a 15% increase in the number of labels led to a threefold improvement in accuracy. Figure 4: Solution quality of the KSSP_LL_Heap heuristic from a single origin to multiple destinations. Figure 5: _Cont_. Similarly, the other networks (Figure 5a-e) saw a twofold accuracy boost with a 20-25% increase in the number of labels used.