Comparative Solutions of Exact and Approximate Methods for Traveling Salesman Problem
DOI:
https://doi.org/10.21501/21454086.3804Keywords:
Rama y atado, eliminación basada en la optimización de la mosca de la fruta, algoritmo de átomo artificial, problema de vendedor ambulante.Abstract
There are two major optimization methods: Exact and Approximate methods. A well known exact method, Branch and Bound algorithm (B&B) and approximate methods, Elimination-based Fruit Fly Optimization Algorithm (EFOA) and Artificial Atom Algorithm (A3) are used for solving the Traveling Salesman Problem (TSP). For 56 destinations, the results of total distance, processing time, and the deviation between exact and approximate method will be compared where the distance between two destinations is a Euclidean distance and this study shows that the distance of B&B is 270 , EFOA is 270 and A3 is 288.38 which deviates 6.81%. For time processing aspect, B&B needs 12.5 days to process, EFOA needs 36.59 seconds, A3 needs 35.34 seconds. But for 29 destinations, exact method is more powerful than approximate method.
Downloads
References
M. Gierszewski, and A. Kozlak, “The Impact of Congestion on The Cost of Public Transport in Starogard Gdanski”, Transport Economics and Logistics, vol. 84, pp. 7-18, 2019. https://doi.org/10.26881/etil.2019.84.01
L. Kavka, I. Dockalikova, Z. Cujan, and G. Fedorko, “Technological and Economic Analysis in Interior Parts Manufacturing”, Advances in Science and Technology Research Journal, vol. 14, no. 3, pp. 204-212, 2020. https://doi.org/10.12913/22998624/122062
F. Jorgensen, and J. Preston, “The Relationship between Fare and Travel Distance”, Journal of Transport Economics and Policy, vol. 41, no. 3, pp. 451-468, 2007.
P. Rietveld, B. Zwart, B. van Wee, and T. van den Horn, “On the Relationship between Travel Time and Travel Distance of Commuters”, European Congress of the Regional Science Association. Zurich, 2016.
J. D. Little, K. G. Murty, and D. W. Sweeney, “An Algorithm for the Traveling Salesman Problem”, Operations Research vol. 11, no. 6, pp. 972-989, 1963. https://doi.org/10.1287/opre.11.6.972
S. Saud, H. Kodaz, and I. Babaoglu, “Solving the Traveling Salesman Problem Using Optimization Algorithms”, IAIT Conference Proceddings. The 9th International Conference on Advances in Information Technology, vol. 2017, pp. 17-32.
I. Droste, “Algorithms for the Traveling Salesman Problem”, Thesis, Universiteit Utrecht. Facuteit Betawetenschappen. Netherland, 2017.
Chandra, A., Setiawan, B.,”Optimizing the Distribution Routes Using Vehicle Routing Problem (VRP) Method,” Jurnal Manajemen Transportasi dan Logistik Vol.05 no.2, 2018. Available at: http://ejournal.stmt-trisakti.ac.id/index.php/jmtranslog.
V. Dimitrijevic, and Z. Saric, “An Efficient Transformation of The Generalized Traveling Salesman Problem into The Traveling Salesman Problem on Diagraphs,” Information Sciences, vol. 102, Issues 1-4, pp. 105-110, 1997. https://doi.org/10.1016/S0020-0255(96)00084-9
P. Baniasadi, M. Foumani, K. Smith-Miles, and V. Ejov, “A Transformation Technique for The Clustered Generalized Traveling Salesman Problem with Applications to Logistics”, European Journal of Operational Research, vol. 285, no. 2, pp. 444-457, 2020. https://doi.org/10.1016/j.ejor.2020.01.053
E. G. Talbi, Metaheuristics; From Design to Implementation, New Jersey: John Wiley and Sons, 2009.
S. Bandaru, and K. Deb, “Metaheuristics Techniques”, In: Sengupta, R.N., Gupta, A., Dutta, J., Decision Science: Theory and Practices”, CRM Press, Taylor and Francis Group, 2016.
G. Zhukova, M. Ulyanov, and M. Fomichev, “Exact Time Efficient Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem”. Business Informatics, vol. 3, no. 45, pp. 20-28, 2018. https://doi.org/10.17323/1998-0663.2018.3.20.28
A. E. Yildirim, and A. Karci, “Application of Traveling Salesman Problem for 81 Provinces in Turkey Using Artificial Atom Algorithm”, 7th International Conference on Advanced Technologies, 2018.
L. Huang, G. C. Wang, T. Bai, and Z. Wang, “An Improved Fruit Fly Optimization Algorithm for Solving the Traveling Salesman Problem”, Frontiers of Information Technology and Electronic Engineering, vol. 18, pp. 1525-1533, 2017. https://doi.org/10.1631/FITEE.1601364
G. Dukic, V. Cesnik, and T. Opetuk, “Order Picking Methods and Technologies for Greener Warehousing” Strojarstvo, vol. 52, no. 1, pp. 23-31, 2010.
A. Chandra, and B. Setiawan, “Minimasi Jalur Distribusi di PT. XYZ dengan Metode Improved Cluster First Route Second”, Jurnal Metris, vol. 20, pp. 11-16, 2019, Available: http://ojs.atmajaya.ac.id/index.php/metris/article/view/1449
E. Balas, and P. Toth, “Branch and Bound Methods fo the Traveling Salesman Problem”, Management Science Research Report no. MSRR 488, 1983.
M. Mataija, M. R. Segic, and F. Jozic, “Solving the Traveling Salesman Problem Using the Branch and Bound Method”, Zbomik Veleucilista u Rjeci, vol.4, no.1, pp. 259-270, 2016.
A. E. Yilidirim, and A. Karci, “Application of Artificial Atom Algorithm to Small Scale Traveling Salesman Problem”, Journal of Soft Computing, vol. 22, pp. 7619-7631, 2017. https://doi.org/10.1007/s00500-017-2735-z
H. Iscan, and M. Gunduz, “Parameter Analysis on Fruit Fly Optimization Algorithm”, Journal of Computer and Communications, vol. 2, no. 4, pp. 137-141, 2014. https://doi.org/10.4236/jcc.2014.24018
E. Duka, “Traveling Salesman Problem Solved by Branch and Bound Algorithm in Lindo Programming”, 2018.https://dx.doi.org/10.2139/ssrn.3152830
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Lámpsakos
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
In accordance with national and international copyrights, as well as publishing policies of "Fundación Universitaria Luis Amigó" and its Journal "Lámpsakos" (indexed with ISSN : 2145-4086), I (we ) hereby manifest:1. The desire to participate as writers and submit to the rules established by the magazine publishers.
2. The commitment not to withdraw the manuscript until the journal finishes the editing process of the ongoing issue.
3. That article is original and unpublished and has not been nominated or submitted together in another magazine; therefore, the rights of the article in evaluation have not been assigned in advance and they do not weigh any lien or limitation for use.
4. The absence of conflict of interest with commercial institution or association of any kind
5. The incorporation of the quotes and references from other authors, tending to avoid plagiarism. Accordingly, the author affirms that the paper being published do not violate copyright, intellectual property or privacy rights of third parties. Morover, if necessary there is a way of demonstrating the respective permits original copyright to the aspects or elements taken from other documents such as texts of more than 500 words, tables, graphs, among others. In the event of any claim or action by a third party regarding copyright on the article, the author (s) will assume full responsibility and come out in defense of the rights herein assigned. Therefore, for all purposes, the Journal "Lámpsakos" of the "Fundación Universitaria Luis Amigó" acts as a third party in good faith.
6. In the event of the publication of the article, the authors free of charge and on an exclusive basis the integrity of the economic rights and the right to print, reprint and reproduction in any form and medium, without any limitation as to territory is concerned, in favor of the Journal "Lámpsakos" of the "Fundación Universitaria Luis Amigó".
