A Genetic Algorithm with Best Combination Operator for the Traveling Salesman Problem

Muhammad Luthfi Shahab, Titin J. Ambarwati, Soetrisno Soetrisno, Mohammad Isa Irawan

Abstract


In this research, we propose a genetic algorithm with best combination operator (BC(x,y)O) for the traveling salesman problem. The idea of best combination operator is to find the best combination of some disjoint sub-solutions (also the reverse of sub-solutions) from some known solutions. We use BC(2,1)O together with a genetic algorithm. The proposed genetic algorithm uses the swap mutation operator and elitism replacement with filtration for faster computational time. We compare the performances of GA (genetic algorithm without BC(2,1)O), IABC(2,1)O (iterative approach of BC(2,1)O), and GABC(2,1)O (genetic algorithm with BC(2,1)O). We have tested GA, IABC(2,1)O, and GABC(2,1)O three times and pick the best solution on 50 problems from TSPLIB. From those 50 problems, the average of the accuracy from GA, IABC(2,1)O, and GABC(2,1)O are 65.12%, 94.21%, and 99.82% respectively.

Keywords


traveling salesman problem; best combination operator; genetic algorithm

Full Text:

PDF

References


M. L. Shahab, D. B. Utomo, and M. I. Irawan, “Decomposing and solving capacitated vehicle routing problem (cvrp) using two-step genetic algorithm (tsga),” Journal of Theoretical & Applied Information Technology, vol. 87, no. 3, 2016.

U. Hacizade and I. Kaya, “Ga based traveling salesman problem solution and its application to transport routes optimization,” IFACPapersOnLine, vol. 51, no. 30, pp. 620–625, 2018.

Muren, J. Wu, L. Zhou, Z. Du, and Y. Lv, “Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics,” Transportation Research Part E: Logistics and Transportation Review, vol. 126, pp. 87–102, 2019.

A. S. Elgesem, E. S. Skogen, X. Wang, and K. Fagerholt, “A traveling salesman problem with pickups and deliveries and stochastic travel times: An application from chemical shipping,” European Journal of Operational Research, vol. 269, no. 3, pp. 844–859, 2018.

A. Fischer, F. Fischer, G. J¨ager, J. Keilwagen, P. Molitor, and I. Grosse, “Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics,” Discrete Applied Mathematics, vol. 166, pp. 97–114, 2014.

D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, The traveling salesman problem: a computational study. Princeton university press, 2006.

M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems,” Journal of the Society for Industrial and Applied mathematics, vol. 10, no. 1, pp. 196–210, 1962.

S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations research, vol. 21, no. 2, pp. 498–516, 1973.

M. L. Shahab, “New heuristic algorithm for traveling salesman problem,” in Journal of Physics: Conference Series, vol. 1218, no. 1, 2019, p. 012038.

P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, and S. Dizdarevic, “Genetic algorithms for the travelling salesman problem: A review of representations and operators,” Artificial Intelligence Review, vol. 13, no. 2, pp. 129–170, 1999.

G. Reinelt, “Tspliba traveling salesman problem library,” ORSA Journal on Computing, vol. 3, no. 4, pp. 376–384, 1991.




DOI: http://dx.doi.org/10.12962/j24775401.v5i2.5830

Refbacks

  • There are currently no refbacks.



View My Stats


Creative Commons License
International Journal of Computing Science and Applied Mathematics by Pusat Publikasi Ilmiah LPPM, Institut Teknologi Sepuluh Nopember is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://iptek.its.ac.id/index.php/ijcsam.