• ISSN: 2148-2225 (online)

Ulaştırma ve Lojistik Kongreleri

alphanumeric journal

The Journal of Operations Research, Statistics, Econometrics and Management Information Systems

Analysis of the Computational Performance in Traveling Salesman Problem: An Application of the Grey Prediction Hybrid Black Hole Algorithm

Mehmet Fatih Demiral, Ph.D.


Abstract

Grey prediction evolution algorithm (GPEA) is a nature-inspired intelligent approach applied to global optimization and engineering problems in 2020. The performance of the GPEA is evaluated on benchmark functions, global optimization, and tested on six engineering-constrained design problems. The comparison shows the effectiveness and superiority of the GPEA. Although the pure GPEA is better than other algorithms in global optimization, and engineering problems, it shows poor performance in combinatorial optimization. In this work, GPEA hybridizes with the black hole algorithm and tabu search for the event horizon condition. Besides, the grey prediction hybrid black hole algorithm (GPHBH) is implemented with heuristics, such as 2-opt, 3-opt, and k-opt swap, and tries to improve with constructive heuristics, such as NN (nearest neighbor), and k-NN. All the algorithms have been tested under appropriate parameters in this work. The traveling salesman problem has been used as a benchmark problem so eight benchmark OR-Library datasets are experimented with. The experimental solutions are presented as best, average solutions, standard deviation, and CPU time for all datasets. As a result, GPHBH and its derived forms give alternative and acceptable solutions to combinatorial optimization in admissible CPU time.

Keywords: Grey Prediction Evolution Algorithm, Heuristics, Hybrid Black Hole Algorithm, Metaheuristics

Jel Classification: C60, C61, C63

Suggested citation

Demiral, M. F. (). Analysis of the Computational Performance in Traveling Salesman Problem: An Application of the Grey Prediction Hybrid Black Hole Algorithm. Alphanumeric Journal, 12(3), 281-292. https://doi.org/10.17093/alphanumeric.1506894

bibtex

References

  • Aladag, C. H., Hocaoglu, G., & Basaran, M. A. (2009). The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem. Expert Systems with Applications, 36(10), 12349–12356. https://doi.org/10.1016/j.eswa.2009.04.051
  • Arnaout, J. P. (2014). Worm optimization: A novel optimization algorithm. Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management., 2499–2505.
  • Deng, J. L. (1982). Control problems of grey systems. Systems & Control Letters, 1(5), 288–294. https://doi.org/10.1016/s0167-6911(82)80025-x
  • Elloumi, W., El Abed, H., Abraham, A., & Alimi, A. M. (2014). A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP. Applied Soft Computing, 25, 234–241. https://doi.org/10.1016/j.asoc.2014.09.031
  • Feng, X., Liu, Y., Yu, H., & Luo, F. (2019). Physarum-energy optimization algorithm. Soft Computing. https://doi.org/10.1007/s00500-017-2796-z
  • Halim, A. H., & Ismail, I. (2019). Combinatorial Optimization: Comparison of Heuristic Algorithms in Travelling Salesman Problem. Archives of Computational Methods in Engineering, 26(2), 367–380. https://doi.org/10.1007/s11831-017-9247-y
  • Hatamlou, A. (2013). Black hole: A new heuristic optimization approach for data clustering. Information Sciences, 222, 175–184. https://doi.org/10.1016/j.ins.2012.08.023
  • Hatamlou, A. (2018). Solving travelling salesman problem using black hole algorithm. Soft Computing, 22(24), 8167–8175. https://doi.org/10.1007/s00500-017-2760-y
  • Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
  • Hu, Z., Xu, X., Su, Q., Zhu, H., & Guo, J. (2020). Grey prediction evolution algorithm for global optimization. Applied Mathematical Modelling, 79, 145–160. https://doi.org/10.1016/j.apm.2019.10.026
  • Husseinzadeh Kashan, A. (2015). A new metaheuristic for optimization: Optics inspired optimization (OIO). Computers & Operations Research, 55, 99–125. https://doi.org/10.1016/j.cor.2014.10.011
  • Koza, J. R. (1992). Genetic programming. 1: On the programming of computers by means of natural selection (1st ed.). MIT Press.
  • Liu, S., & Lin, Y. (2011). Grey Systems. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-16158-2
  • Liu, S., Zeng, B., Liu, J., Xie, N., & Yang, Y. (2015). Four basic models of GM(1, 1) and their suitable sequences. Grey Systems: Theory and Application, 5(2), 141–156. https://doi.org/10.1108/gs-04-2015-0016
  • Peker, M., Şen, B., & Kumru, P. Y. (2013). An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering & Computer Sciences, 21, 2015–2036. https://doi.org/10.3906/elk-1109-44
  • Reinelt, G. (2013). Tsplib. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
  • Siddique, N., & Adeli, H. (2017). Nature-Inspired Chemical Reaction Optimisation Algorithms. Cognitive Computation, 9(4), 411–422. https://doi.org/10.1007/s12559-017-9485-1
  • Szeto, W., Wu, Y., & Ho, S. C. (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126–135. https://doi.org/10.1016/j.ejor.2011.06.006
  • Tien, T.-L. (2012). A research on the grey prediction model GM(1,n). Applied Mathematics and Computation, 218(9), 4903–4916. https://doi.org/10.1016/j.amc.2011.10.055
  • Xie, N.-m., & Liu, S.-f. (2009). Discrete grey forecasting model and its optimization. Applied Mathematical Modelling, 33(2), 1173–1186. https://doi.org/10.1016/j.apm.2008.01.011
  • Xu, X., Hu, Z., Su, Q., Li, Y., & Dai, J. (2020). Multivariable grey prediction evolution algorithm: A new metaheuristic. Applied Soft Computing, 89, 106086. https://doi.org/10.1016/j.asoc.2020.106086
  • Yildirim, A. E., & Karci, A. (2018). Applications of artificial atom algorithm to small-scale traveling salesman problems. Soft Computing, 22(22), 7619–7631. https://doi.org/10.1007/s00500-017-2735-z
  • Zheng, Y.-J. (2015). Water wave optimization: A new nature-inspired metaheuristic. Computers & Operations Research, 55, 1–11. https://doi.org/10.1016/j.cor.2014.10.008

Volume 12, Issue 3, 2024

2024.12.03.OR.04

alphanumeric journal

Volume 12, Issue 3, 2024

Pages 281-292

Received: June 28, 2024

Accepted: Sept. 24, 2024

Published: Dec. 31, 2024

Full Text [290.3 KB]

2024 Demiral, MF.

This is an Open Access article, licensed under Creative Commons Attribution-NonCommercial 4.0 International License.

Creative Commons Attribution licence

scan QR code to access this article from your mobile device

Contact Us

Faculty of Transportation and Logistics, Istanbul University
Beyazit Campus 34452 Fatih/Istanbul/TURKEY

Bahadır Fatih Yıldırım, Ph.D.
editor@alphanumericjournal.com
+ 90 (212) 440 00 00 - 13219

alphanumeric journal

alphanumeric journal has been publishing as "International Peer-Reviewed Journal" every six months since 2013. alphanumeric serves as a vehicle for researchers and practitioners in the field of quantitative methods, and is enabling a process of sharing in all fields related to the operations research, statistics, econometrics and management informations systems in order to enhance the quality on a globe scale.