A Solving Route Optimization of Airplane Travel Problem Use Artificial Bee Colony Algorithm

I Gusti Agung Premananda, Ahmad Muklason, Rizal Risnanda

Abstract


The Traveling Salesman Problem (TSP) is very popular in combinatoric optimization. The TSP problem is finding the optimal route from several cities where the distance between cities is known, and a salesman must visit each city exactly once and return to the origin city. The goal is to find a route with a minimum total distance. This problem is known as a non-deterministic polynomial hard (NP-hard) problem, which means the computation time to find a solution increases exponentially with the size of the problem. NP-Hard problems can be solved by using heuristic methods where the solution obtained is good enough (does not guarantee the most optimal solution) in a reasonable time. One of the most recent variants of TSP problem is finding the cheapest flight routes to several cities, which is part of the Traveling Salesman Challenge 2.0 (TSC 2.0) 2018 competition . This paper reports our study of implementing an artificial bee colony (ABC) algorithm for the TSC 2.0 problem. ABC algorithm is chosen based on its superiority over other algorithms in several optimization problems. The algorithm is implemented in a hyper-heuristic form. Several combinations of swap operators are used to find the best combination result. The experimental result shows that the ABC algorithm can solve the TSC 2.0 problem with a fairly good performance by producing a savings cost of 54.6% from the initial solution and 26% compared to the Genetic Algorithm.

Keywords


Traveling salesman problem; artificial bee colony; traveling salesman challenge 2.0.

Full Text:

PDF

References


M. A. H. Akhand, S. I. Ayon, S. A. Shahriyar, N. Siddique, and H. Adeli, “Discrete Spider Monkey Optimization for Travelling Salesman Problem,†Appl. Soft Comput. J., vol. 86, 2020, doi: 10.1016/j.asoc.2019.105887.

G. Campuzano, C. Obreque, and M. M. Aguayo, “Accelerating the Miller–Tucker–Zemlin model for the asymmetric traveling salesman problem,†Expert Syst. Appl., vol. 148, 2020, doi: 10.1016/j.eswa.2020.113229.

E. Baş and E. Ülker, “Dıscrete socıal spıder algorıthm for the travelıng salesman problem,†Artif. Intell. Rev., vol. 54, no. 2, 2021, doi: 10.1007/s10462-020-09869-8.

Komarudin and S. F. Parhusip, “Composite algorithm based on Clarke – Wright and local search for the traveling salesman problem,†2019. doi: 10.1145/3364335.3364388.

M. A. Al-Furhud and Z. Hussain, “Genetic Algorithms for the Multiple Travelling Salesman Problem,†Int. J. Adv. Comput. Sci. Appl., vol. 11, no. 7, 2020, doi: 10.14569/IJACSA.2020.0110768.

A. C. Cinar, S. Korkmaz, and M. S. Kiran, “A discrete tree-seed algorithm for solving symmetric traveling salesman problem,†Eng. Sci. Technol. an Int. J., vol. 23, no. 4, pp. 879–890, Aug. 2020, doi: 10.1016/j.jestch.2019.11.005.

J. Kaur and A. Pal, “An analysis of different metaheuristic approaches for solving travelling salesman problems,†Adv. Math. Sci. J., vol. 9, no. 8, 2020, doi: 10.37418/amsj.9.8.29.

M. Mosayebi, M. Sodhi, and T. A. Wettergren, “The Traveling Salesman Problem with Job-times (TSPJ),†Comput. Oper. Res., vol. 129, 2021, doi: 10.1016/j.cor.2021.105226.

N. Rokbani et al., “Bi-heuristic ant colony optimization-based approaches for traveling salesman problem,†Soft Comput., vol. 25, no. 5, 2021, doi: 10.1007/s00500-020-05406-5.

M. A. Tawhid and P. Savsani, “Discrete Sine-Cosine Algorithm (DSCA) with Local Search for Solving Traveling Salesman Problem,†Arab. J. Sci. Eng., vol. 44, no. 4, 2019, doi: 10.1007/s13369-018-3617-0.

Z. Daoqing and J. Mingyan, “Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem,†J. Syst. Eng. Electron., vol. 31, no. 4, 2020, doi: 10.23919/JSEE.2020.000050.

S. K. R. Kanna, K. Sivakumar, and N. Lingaraj, “Development of Deer Hunting linked Earthworm Optimization Algorithm for solving large scale Traveling Salesman Problem,†Knowledge-Based Syst., vol. 227, 2021, doi: 10.1016/j.knosys.2021.107199.

I. G. A. Premananda and A. Muklason, “Complex University Timetabling Using Iterative Forward Search Algorithm and Great Deluge Algorithm,†Khazanah Inform. J. Ilmu Komput. dan Inform., vol. 7, no. 2, 2021.

C. Jiang, Z. Wan, and Z. Peng, “A new efficient hybrid algorithm for large scale multiple traveling salesman problems,†Expert Syst. Appl., vol. 139, 2020, doi: 10.1016/j.eswa.2019.112867.

R. S. de Moraes and E. P. de Freitas, “Experimental analysis of heuristic solutions for the moving target traveling salesman problem applied to a moving targets monitoring system,†Expert Syst. Appl., vol. 136, 2019, doi: 10.1016/j.eswa.2019.04.023.

Q. M. Ha, Y. Deville, Q. D. Pham, and M. H. Hà , “A hybrid genetic algorithm for the traveling salesman problem with drone,†J. Heuristics, vol. 26, no. 2, 2020, doi: 10.1007/s10732-019-09431-y.

J. C. de Freitas and P. H. V. Penna, “A variable neighborhood search for flying sidekick traveling salesman problem,†Int. Trans. Oper. Res., vol. 27, no. 1, pp. 267–290, 2020, doi: 10.1111/itor.12671.

W. Gao, “New ant colony optimization algorithm for the traveling salesman problem,†Int. J. Comput. Intell. Syst., vol. 13, no. 1, 2020, doi: 10.2991/ijcis.d.200117.001.

T. Huang, Y. J. Gong, S. Kwong, H. Wang, and J. Zhang, “A Niching Memetic Algorithm for Multi-Solution Traveling Salesman Problem,†IEEE Trans. Evol. Comput., vol. 24, no. 3, 2020, doi: 10.1109/TEVC.2019.2936440.

I. M. Ali, D. Essam, and K. Kasmarik, “A novel design of differential evolution for solving discrete traveling salesman problems,†Swarm Evol. Comput., vol. 52, 2020, doi: 10.1016/j.swevo.2019.100607.

I. Khan and M. K. Maiti, “A swap sequence based Artificial Bee Colony algorithm for Traveling Salesman Problem,†Swarm Evol. Comput., vol. 44, 2019, doi: 10.1016/j.swevo.2018.05.006.

D. Karaboga and B. Gorkemli, “Solving Traveling Salesman Problem by Using Combinatorial Artificial Bee Colony Algorithms,†Int. J. Artif. Intell. Tools, vol. 28, no. 1, 2019, doi: 10.1142/S0218213019500040.

M. R. Batchanaboyina and N. R. Devarakonda, “Handling optimization problem, and the scope of varied artificial bee colony (ABC) algorithms: A contemporary research,†Int. J. Innov. Technol. Explor. Eng., vol. 8, no. 6 Special Issue 4, 2019, doi: 10.35940/ijitee.F1125.0486S419.

F. Xu et al., “A new global best guided artificial bee colony algorithm with application in robot path planning,†Appl. Soft Comput. J., vol. 88, 2020, doi: 10.1016/j.asoc.2019.106037.

Y. Li, W. Huang, R. Wu, and K. Guo, “An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem,†Appl. Soft Comput. J., vol. 95, 2020, doi: 10.1016/j.asoc.2020.106544.

S. S. Choong, L. P. Wong, and C. P. Lim, “An artificial bee colony algorithm with a Modified Choice Function for the traveling salesman problem,†Swarm Evol. Comput., vol. 44, 2019, doi: 10.1016/j.swevo.2018.08.004.

V. Pandiri and A. Singh, “An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem,†Appl. Soft Comput. J., vol. 78, 2019, doi: 10.1016/j.asoc.2019.03.001.

A. M. H. Al-Ibrahim, “Solving Travelling Salesman Problem (TSP) by Hybrid Genetic Algorithm (HGA),†Int. J. Adv. Comput. Sci. Appl., vol. 11, no. 6, 2020, doi: 10.14569/IJACSA.2020.0110649.

A. Riazi, “Genetic algorithm and a double-chromosome implementation to the traveling salesman problem,†SN Appl. Sci., vol. 1, no. 11, 2019, doi: 10.1007/s42452-019-1469-1.

Kiwi, “Travelling Salesman Challenge 2.0,†2019. https://travellingsalesman.kiwi.com

K. Hussain, M. N. Mohd Salleh, S. Cheng, Y. Shi, and R. Naseem, “Artificial bee colony algorithm: A component-wise analysis using diversity measurement,†J. King Saud Univ. - Comput. Inf. Sci., vol. 32, no. 7, 2020, doi: 10.1016/j.jksuci.2018.09.017.

H. C. Tsai, “Artificial bee colony directive for continuous optimization,†Appl. Soft Comput. J., vol. 87, 2020, doi: 10.1016/j.asoc.2019.105982.

M. A. Awadallah, M. A. Al-Betar, A. L. Bolaji, I. A. Doush, A. I. Hammouri, and M. Mafarja, “Island artificial bee colony for global optimization,†Soft Comput., vol. 24, no. 17, 2020, doi: 10.1007/s00500-020-04760-8.

W. li Xiang, Y. zhen Li, R. chun He, and M. qing An, “Artificial bee colony algorithm with a pure crossover operation for binary optimization,†Comput. Ind. Eng., vol. 152, 2021, doi: 10.1016/j.cie.2020.107011.

Y. Deng, H. Xu, and J. Wu, “Optimization of blockchain investment portfolio under artificial bee colony algorithm,†J. Comput. Appl. Math., vol. 385, 2021, doi: 10.1016/j.cam.2020.113199.




DOI: http://dx.doi.org/10.18517/ijaseit.12.6.16746

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development