Page 127 - IJOCTA-15-2

¨
E. Sonu¸c, E. Ozcan / IJOCTA, Vol.15, No.2, pp.311-329 (2025)
Table 10. Gap scores for MCP instances with different number of threads on PLAHC where L = 50

Instance 4 thds 8 thds 16 thds 32 thds
pw01 100.0 0.8504 1.4165 2.4978 4.0451
pw01 100.1 0.3383 0.9141 1.9694 3.3723
pw01 100.2 0.7859 1.3844 1.8209 2.9444
pw01 100.3 0.6918 0.8403 2.7949 4.4881
pw01 100.4 0.9725 2.3409 3.4036 4.7048
pw01 100.5 0.7386 1.7362 3.0773 4.4639
pw01 100.6 0.9070 1.2879 2.7347 4.6344
pw01 100.7 0.5868 1.1172 1.9012 3.4730
pw01 100.8 1.0618 1.7557 2.9228 4.2779
pw01 100.9 0.7247 1.0574 2.3277 3.5711
pw05 100.0 0.1966 0.5076 0.7485 1.0546
pw05 100.1 0.3924 0.5395 0.9475 1.2799
pw05 100.2 0.2920 0.4715 0.6291 0.9852
pw05 100.3 0.2924 0.5439 1.2520 1.6836
pw05 100.4 0.2896 0.3967 0.6994 1.0933
pw05 100.5 0.3791 0.5941 0.9728 1.4494
pw05 100.6 0.2601 0.4044 0.7469 1.1777
pw05 100.7 0.2501 0.3621 0.7743 1.2632
pw05 100.8 0.2143 0.5285 1.1676 1.5746
pw05 100.9 0.1824 0.5503 0.9063 1.3800
pw09 100.0 0.1877 0.4183 0.5067 0.7528
pw09 100.1 0.2253 0.2849 0.4593 0.6449
pw09 100.2 0.3605 0.4546 0.5861 0.7050
pw09 100.3 0.3048 0.4945 0.6178 0.8836
pw09 100.4 0.2573 0.4179 0.6527 0.8448
pw09 100.5 0.1490 0.2981 0.4126 0.5844
pw09 100.6 0.3268 0.5086 0.7036 0.9122
pw09 100.7 0.1701 0.3523 0.4716 0.5994
pw09 100.8 0.1962 0.3995 0.6001 0.7494
pw09 100.9 0.2473 0.4127 0.6094 0.8271
Avg.Gap 0.4277 0.7597 1.3305 2.0140

for the PLAHC algorithm applied to MCP in- std values. The results of oBABC were taken di-
stances. rectly from the the reference study. Note that
Figure 4 shows average speedups for MCP in- the termination criterion is a predetermined num-
stances. Similar to the UFLP experiments, the re- ber of function evaluations = 20,000 to fairly
sults show consistent performance improvements compare the performance of oBABC to ABPEA.
as the number of threads increases. Speedup val- The best average gap scores for each instance
ues increase from 2.93x with 4 threads to 11.01x are shown in bold. The performance compar-
with 32 threads, demonstrating significant im- ison between PLAHC and oBABC shows that
provement through parallelization. However, the PLAHC generally outperforms oBABC in most
observed scaling is non-linear, suggesting that the problem instances, especially in the pw01 series.
benefits of adding more threads yield less per- PLAHC consistently achieves lower gap scores,
formance. This can be seen in the decreasing with improvements in several instances such as
throughput or speedup per thread as the number pw01 100.5, pw05 100.1, and pw09 100.6. While
of threads increases. While 32 threads achieve the PLAHC typically has higher standard deviations,
highest speedup of 11.01x, it’s important to note indicating more diverse solutions, its superior av-
that earlier results show that 4-thread implemen- erage gap scores indicate a more effective explo-
tation often produces the best solution quality. ration of the solution space. The results highlight
This highlights a critical trade-off in parallel op- PLAHC’s effectiveness in solving MCP instances,
timization algorithms between speed and solution likely due to its parallel nature and late accep-
quality. tance strategy.
The comparative results of PLAHC (4-thread
with L = 100), and the state-of-the-art algo-
4.3. Runtime analysis
rithms on the MCP instances are reported in Ta-
ble 12. The performance evaluation of PLAHC To provide a comprehensive understanding of the
is conducted by comparing its average gap and computational efficiency of PLAHC, we analyzed
322