PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM
DOI:
https://doi.org/10.30837/ITSSI.2021.15.069Keywords:
traveling salesman problem, optimization method, exact method, approximate methods, gapsAbstract
The subject of this research is distance and time of several city tour problems which known as traveling salesman problem (tsp). The goal is to find out the gaps of distance and time between two types of optimization methods in traveling salesman problem: exact and approximate. Exact method yields optimal solution but spends more time when the number of cities is increasing and approximate method yields near optimal solution even optimal but spends less time than exact methods. The task in this study is to identify and formulate each algorithm for each method, then to run each algorithm with the same input and to get the research output: total distance, and the last to compare both methods: advantage and limitation. Methods used are Brute Force (BF) and Branch and Bound (B&B) algorithms which are categorized as exact methods are compared with Artificial Bee Colony (ABC), Tabu Search (TS) and Simulated Annealing (SA) algorithms which are categorized as approximate methods or known as a heuristics method. These three approximate methods are chosen because they are effective algorithms, easy to implement and provide good solutions for combinatorial optimization problems. Exact and approximate algorithms are tested in several sizes of city tour problems: 6, 9, 10, 16, 17, 25, 42, and 58 cities. 17, 42 and 58 cities are derived from tsplib: a library of sample instances for tsp; and others are taken from big cities in Java (West, Central, East) island. All of the algorithms are run by MATLAB program. The results show that exact method is better in time performance for problem size less than 25 cities and both exact and approximate methods yield optimal solution. For problem sizes that have more than 25 cities, approximate method – Artificial Bee Colony (ABC) yields better time which is approximately 37% less than exact and deviates 0.0197% for distance from exact method. The conclusion is to apply exact method for problem size that is less than 25 cities and approximate method for problem size that is more than 25 cities. The gap of time will be increasing between two methods when sample size becomes larger.
References
Dimitrijevic, V., Saric, Z. (1997), "An Efficient Transformation of The Generalized Traveling Salesman Problem into The Traveling Salesman Problem on Diagraphs", Information Sciences, Vol. 102, Issues 1-4, P. 105–110. DOI: https://doi.org/10.1016/S0020-0255(96)00084-9
Baniasadi, P., Foumani, M., Miles, K. S., Ejov, V. (2020), "A Transformation Technique for The Clustered Generalized Traveling Salesman Problem with Applications to Logistics", European Journal of Operational Research, Vol. 285, Issue 2, P. 444–457. DOI: https://doi.org/10.1016/j.ejor
BPS – Statistik Indonesia (2019), "Land Transportation Statistics, Statistik Transportasi Darat", available at : www.bps.go.id
Saud, S., Kodaz, H., Babaoglu, I. (2017), "Solving the Traveling Salesman Problem Using Optimization Algorithms", IAIT Conference Proceddings. The 9th International Conference on Advances in Information Technology, Vol. 2017. DOI: https://doi.org/10.18502/kss.v3i1.1394
Jadczak, R. (2014), "Traveling Salesman Problem: Approach to Optimality", De Gruyter Open, Vol. XV, Issue 2, P. 157–159. DOI: https://doi.org/10.2478/eam-2014-0024
Chandra, A., Setiawan, B. (2018), "Optimizing the Distribution Routes Using Vehicle Routing Problem (VRP) Method", Journal Manajemen Transportasi dan Logistik, Vol. 05, No. 2, available at : http://ejournal.stmt-trisakti.ac.id/index.php/jmtranslog
Query, J. A. (2015), "The Impact of Transportation Costs and Trade Barriers on International Trade Flows", Dissertation, Department of Economics, Graduate School of the University of Oregon, available at: https://scholarsbank.uoregon.edu
Victoria Transport Policy Institute (2020), "Transportation Cost and Benefit Analysis II – Literature Review", availalble at : www.vtpi.org/tca/tca02.pdf (last accessed: 19.02.2021).
Keya, K. T., Rahman, M. M., Rob, U., Bellows, B. (2014), "Distance, Transportation Cost and Mode of Transport in the Utilization of Facility – Based Maternity Service: Evidence for Rural Bangladesh", International Quarterly of Community Health Education. DOI: https://10.2190/IQ.35.1.d
Bernatz, G. (2009),"Apples, Bananas, Oranges: Using GIS to Determine Distance Travelled, Energy Use, and Emissions from Imported Fruit", Papers in Resource Analysis, Saint Mary’s University of Minnesota Central Service Press. Winona, MN, Vol. 11, P. 16, available: http://www.gis.smumn.edu (last accessed: 13.02.2021).
Chandra, A., Naro, A. (2020), "A Comparative Study of Capacitated Vehicle Routing Problem Heuristics Model", International Journal of Engineering and Emerging Technology, Vol. 5, No. 2, P. 94-100. DOI: https://doi.org/10.24843/IJEET.2020.v05.i02.p015
Talbi, E. G. (2009), Metaheuristics: From Design to Implementation, John Wiley and Sons, New Jersey.
Vatutin, E. (2017), "Comparisons of Decisions Quality of Heuristics Methods with Limited Depth First Search Techniques in the Graph Shortest Path Problem", De Gruyter Open, P. 428–434. DOI: https://doi.org/10.1515/eng-2017-0041
Black, A. P. (2019), "Lecture 6: Exhaustive Serach Algorithms. Department of Compuer Science", Portland State University, available at : https://web.cecs.pdx.edu
Droste, I. (2017), "Algorithms for the Traveling Salesman Problem", Thesis, Universiteit Utrecht. Facuteit Betawetenschappen. Netherland, available at: https://dspace.library.uu.nl
Balas, E., Toth, P. (1983), "Branch and Bound Methods fo the Traveling Salesman Problem", Management Science Research Report, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, No. MSRR 488, available at : https://apps.dtic.mil
Karaboga, D., Basturk, B. (2008), "On the Performance of Artificial Bee Colony Algorithm", Applied Soft Computing, No. 8, P. 687–697. DOI: https://doi.org/10.1016/j.asoc.2007.05.007
Teodorovic, D., Selmic, M., Davidovic, T. (2015), "Bee Colony Optimization Part II: The Application Survey", Yugoslav Journal of Operations Research, Vol. 25, No. 2, P. 185–219. DOI: https://doi.org/10.2298/YJOR131029020T
Gendreau, M. (2002), An Introduction to Tabu Search, Universite de Montreal, Montreal, Canada. Available at: http://www.ifi.uio.no/infheur/Bakgrunn/Intro_to_TS.Gendreau.htm
Eglese, R. W. (1990), "Simulated Annealing: A Tool for Operational Research", European Journal of Operational Research, No. 46, P. 271–281. DOI: https://doi.org/10/1016/0377-2217(90)90001-R
De Weck, O. (2010), "Lecture 10: Simulated Annealing: A Basic Introduction", MIT OpenCourseWare, available at : http://ocw.mit.edu
Zhu, Y. W. (-), "Brute Force", University of Seattle, available at: http://www.fac-staff.seattleu.edu
Morrison, D., Jacobson, S. H., Sauppe, J. J., Sewell, E. C. (2016), "Branch and Bound algorithms: A Survey of Recent Advances in Searching, Branching, and Pruning", Discrete Optimization, No. 19, P. 79–102. DOI: http://dx.doi.org/10.1016/j.disopt.2016.01.005
Onder, E., Ozdemir, M., Yildrim, B. F. (2013), "Combinatorial Optimization Using Artificial Bee Colony Algorithm and Particle Swarm Optimization Supported Genetic Algorithm", KAU IIBF Dergisi, No. 4 (6), P. 59–70, available at : https://ssrn.com
Kocer, H. E., Akca, M. R. (2014), "An Improved Artificial Bee Colony Algorithm with Local Search for Traveling Salesman Problem", Cybernetics and Systems: An International Journal, Vol. 45, No. 8, P. 635–649. DOI: https://doi.org/10.1080/01969722.2014.970396
Boussaid, I., Lepagnot, J., Siarry, P. (2013), "A Survey On Optimization Metaheuristics", Information Sciences, No. 237, P. 82–117. DOI: https://doi.org/10.1016/j.ins.2013.02.041
Misevicius, A. (2004), "Using Iterated Tabu Search for the Traveling Salesman Problem", Informacines Technologijos Ir Valdymas, No. 3 (32), P. 29–40, available at : https://itc.ktu.lt
Zhou, A. H., Zhu, L. P., Hu, B., Deng, S., Song, Y., Qiu, H., Pan, S. (2019), "Traveling-Salesman-Problem Based on Simulated Annealing and Gene-Expression Programming", Information, Vol. 10, No. 7. DOI: https://doi.org/10.3390/info10010007
Mataija, M., Segic, M. R., Jozic, F. (2016), "Solving the Traveling Salesman Problem Using the Branch and Bound Method", Zbomik Veleucilista u Rjeci, Vol. 4 No. 1, P. 259–270, available at : https://hrcak.srce.hr
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Our journal abides by the Creative Commons copyright rights and permissions for open access journals.
Authors who publish with this journal agree to the following terms:
Authors hold the copyright without restrictions and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-commercial and non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
Authors are permitted and encouraged to post their published work online (e.g., in institutional repositories or on their website) as it can lead to productive exchanges, as well as earlier and greater citation of published work.
