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


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.


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


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:

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:

BPS – Statistik Indonesia (2019), "Land Transportation Statistics, Statistik Transportasi Darat", available at :

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:

Jadczak, R. (2014), "Traveling Salesman Problem: Approach to Optimality", De Gruyter Open, Vol. XV, Issue 2, P. 157–159. DOI:

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 :

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:

Victoria Transport Policy Institute (2020), "Transportation Cost and Benefit Analysis II – Literature Review", availalble at : (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: (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:

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:

Black, A. P. (2019), "Lecture 6: Exhaustive Serach Algorithms. Department of Compuer Science", Portland State University, available at :

Droste, I. (2017), "Algorithms for the Traveling Salesman Problem", Thesis, Universiteit Utrecht. Facuteit Betawetenschappen. Netherland, available at:

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 :

Karaboga, D., Basturk, B. (2008), "On the Performance of Artificial Bee Colony Algorithm", Applied Soft Computing, No. 8, P. 687–697. DOI:

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:

Gendreau, M. (2002), An Introduction to Tabu Search, Universite de Montreal, Montreal, Canada. Available at:

Eglese, R. W. (1990), "Simulated Annealing: A Tool for Operational Research", European Journal of Operational Research, No. 46, P. 271–281. DOI:

De Weck, O. (2010), "Lecture 10: Simulated Annealing: A Basic Introduction", MIT OpenCourseWare, available at :

Zhu, Y. W. (-), "Brute Force", University of Seattle, available at:

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:

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 :

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:

Boussaid, I., Lepagnot, J., Siarry, P. (2013), "A Survey On Optimization Metaheuristics", Information Sciences, No. 237, P. 82–117. DOI:

Misevicius, A. (2004), "Using Iterated Tabu Search for the Traveling Salesman Problem", Informacines Technologijos Ir Valdymas, No. 3 (32), P. 29–40, available at :

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:

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 :

Abstract views: 13
PDF Downloads: 22
How to Cite