GENETIC ALGORITHM-BASED EFFICIENT ROUTE PLANNING FOR TRAVELING SALESMAN PROBLEM

Andysah Putera Utama Siahaan

Abstract


Abstract:  This paper proposes a solution to the Traveling Salesman Problem (TSP) using a Genetic Algorithm (GA) approach. The GA is a technique that imitates natural evolution to produce and improve candidate solutions for the TSP. The proposed algorithm improves the efficiency of route planning by using a unique crossover and mutation operator that lowers the chances of getting stuck in local optima. The algorithm was tested on benchmark datasets, and the results showed that it performs better than others existing GA methods in terms of finding the shortest route with the least number of generations. This proposed algorithm has promising potential applications in logistics and transportation planning. The genetic algorithm can generate populations in order to find the minimum value, which may not be the global minimum, but it can still provide an optimal solution. By utilizing artificial intelligence, specifically in the context of the Traveling Salesman Problem, the distance traveled can be optimized.

Keywords: artificial intelligence, TSP, shortest path, optimum.


Full Text:

PDF

References


Borna, K., & Hashemi, V. H. (2014). An Improved Genetic Algorithm with a Local Optimization Strategy and an Extra Mutation Level for Solving Traveling Salesman Problem. International Journal of Computer Science, Engineering and Information Technology, 4(4), 47–53. https://doi.org/10.5121/ijcseit.2014.4405

Deng, Y., Liu, Y., & Zhou, D. (2015). An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP. Mathematical Problems in Engineering, 2015, 1–6. https://doi.org/10.1155/2015/212794

El Hassani, H., Benkachcha, S., & Benhra, J. (2015). New Genetic Operator (Jump Crossover) for the Traveling Salesman Problem. International Journal of Applied Metaheuristic Computing, 6(2), 33–44. https://doi.org/10.4018/IJAMC.2015040103

Gabriel, J. (2016). Artificial Intelligence: Artificial Intelligence for Humans. CreateSpace Independent Publishing.

Siahaan, A. P. U. (2016a). Genetic Algorithm in Hill Cipher Encryption. American International Journal of Research in Science, Technology, Engineering & Mathematics, 15(1), 84–89.

Siahaan, A. P. U. (2016b). Scheduling Courses using Genetic Algorithms. International Journal of Computer Applications, 153(3), 20–25.

Siahaan, A. P. U., Rusiadi, Kan, P. L. E., Azir, K. N. F. K., & Amir, A. (2018). Prim and Genetic Algorithms Performance in Determining Optimum Route on Graph. International Journal of Control and Automation, 11(6), 109–122. https://doi.org/10.14257/ijca.2018.11.6.11

Sutojo, T., Mulyanto, E., & Suhartono, V. (2011). Kecerdasan Buatan. Andi Offset.

Tabatabaee, H. (2015). Solving the Traveling Salesman Problem using Genetic Algorithms with the New Evaluation Function. Bulletin of Environment, Pharmacology and Life Sciences, 4(11), 124–131. https://pdfs.semanticscholar.org/1fdc/eab75bd110c594e9af2afbf399f901b04471.pdf

Zhao, J., Shi, R., Sai, L., Huang, X., & Su, Y. (2016). Comprehensive genetic algorithm for ab initio global optimisation of clusters. Molecular Simulation, 42(10), 809–819. https://doi.org/10.1080/08927022.2015.1121386

Zhou, A.-H., Zhu, L.-P., Hu, B., Deng, S., Song, Y., Qiu, H., & Pan, S. (2018). Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming. Information, 10(1), 7. https://doi.org/10.3390/info10010007.


Article Metrics

Abstract view : 118 times
PDF – 225 times

Refbacks

  • There are currently no refbacks.


Copyright (c) 2023 PROSIDING UNIVERSITAS DHARMAWANGSA

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Prosiding Universitas Dharmawangsa Terindex pada:

PROSIDING SEMINAR NASIONAL DAN INTERNASIONAL PUBLISHED BY :

UPT. Penerbitan dan Publikasi Ilmiah
UNIVERSITAS DHARMAWANGSA

Alamat : Jl. K. L. Yos Sudarso No. 224 Medan
Kontak : Tel. 061 6635682 - 6613783  Fax. 061 6615190
Surat Elektronik : ppi@dharmawangsa.ac.id

 

 Creative Commons License

Prosiding Seminar Nasional dan Internasional By Universitas Dharmawangsa is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Based on a work at https://proceeding.dharmawangsa.ac.id/index.php/PSND/index