PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM

Keywords: traveling salesman problem, optimization method, exact method, approximate methods, gaps

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

Chandra Agung, Universitas Mercu Buana
Master of Engineering (Civil Engineering), Master of Management (Financial Management), Senior Lecturer, Department of Industrial Engineering
Natalia Christine, Universitas Katolik Indonesia Atma Jaya Jakarta
Master of Engineering (Industrial Engineering and Management), Senior Lecturer, Department of Industrial Engineering

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


Abstract views: 13
PDF Downloads: 22
Published
2021-03-28
How to Cite
Agung, C. and Christine, N. (2021) “PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM”, INNOVATIVE TECHNOLOGIES AND SCIENTIFIC SOLUTIONS FOR INDUSTRIES, (1 (15), pp. 69-75. doi: 10.30837/ITSSI.2021.15.069.
Section
MODERN ENTERPRISE MANAGEMENT TECHNOLOGIES