Volume 19 , Issue 3 , PP: 40-46, 2022 | Cite this article as | XML | Html | PDF | Full Length Article
Arindam Dey 1 * , Ranjan Kumar 2 , Said Broumi 3
Doi: https://doi.org/10.54216/IJNS.190304
The traveling salesman problem (TSP) is an important and well known classical combinatorial network optimization
problem in operation research, where the TSP finds a shortest possible route through a set of n nodes
such that each and every node are visited exactly one time except for the starting node. In this problem, the
arc lengths are generally considered to represent the traveling time or travelling cost rather than geographical
distance. It is not possible to predict the exact arc length because the traveling time or traveling cost fluctuated
with payload, weather, traffic conditions and so on. neutrosophic set theory provides a new tool to handle the
uncertainties in TSP. In this paper, we concentrate on TSP on a network in which neutrosophic set, Instead of
real number is assigned to edge as edge weight. We propose a mathematical model for a TSP with neutrosophic
arc lengths. We present the utility of neutrosophic sets as arc length for TSP. An algorithmic method based
on Genetic Algorithm (GA) is proposed for solving this problem. We have designed a new heuristic crossover
and heuristic mutation our proposed GA. We have used a numerical example to illustrate the effectiveness of
our proposed algorithm.
Neutrosophic Edge Weight , Formulation , Genetic Algorithm , Traveling Salesman problem
[1] R. Bellman, “Dynamic programming treatment of the travelling salesman problem,” Journal of the ACM
(JACM), vol. 9, no. 1, pp. 61–63, 1962.
[2] M. Dorigo and L. M. Gambardella, “Ant colonies for the travelling salesman problem,” Biosystems,
vol. 43, no. 2, pp. 73–81, 1997.
[3] A. Langevin, F. Soumis, and J. Desrosiers, “Classification of travelling salesman problem formulations,”
Operations Research Letters, vol. 9, no. 2, pp. 127–132, 1990.
[4] X. Chen and S. Liu, “Adjacent vertex distinguishing proper edge colorings of bicyclic graphs,” IAENG
International Journal of Applied Mathematics, vol. 48, no. 4, pp. 401–411, 2018.
[5] L. A. Zadeh, “The concept of a linguistic variable and its application to approximate reasoning—i,”
Information sciences, vol. 8, no. 3, pp. 199–249, 1975.
[6] C. Changdar, G. Mahapatra, and R. K. Pal, “An efficient genetic algorithm for multi-objective solid
travelling salesman problem under fuzziness,” Swarm and Evolutionary Computation, vol. 15, pp. 27–
37, 2014.
[7] S. Maity, A. Roy, and M. Maiti, “A modified genetic algorithm for solving uncertain constrained solid
travelling salesman problems,” Computers & Industrial Engineering, vol. 83, pp. 273–296, 2015.
[8] J. Ries, P. Beullens, and D. Salt, “Instance-specific multi-objective parameter tuning based on fuzzy
logic,” European Journal of Operational Research, vol. 218, no. 2, pp. 305–315, 2012.
[9] J. Wang, “A novel firefly algorithm for portfolio optimization problem,” IAENG International Journal of
Applied Mathematics, vol. 49, no. 1, pp. 45–50, 2019.
[10] A. E. Eiben, J. K. Van Der Hauw, and J. I. van Hemert, “Graph coloring with adaptive evolutionary
algorithms,” Journal of Heuristics, vol. 4, no. 1, pp. 25–46, 1998.
[11] L. V. Snyder and M. S. Daskin, “A random-key genetic algorithm for the generalized traveling salesman
problem,” European journal of operational research, vol. 174, no. 1, pp. 38–53, 2006.
[12] C. Moon, J. Kim, G. Choi, and Y. Seo, “An efficient genetic algorithm for the traveling salesman problem
with precedence constraints,” European Journal of Operational Research, vol. 140, no. 3, pp. 606–617,
2002.
[13] I.-C. Choi, S.-I. Kim, and H.-S. Kim, “A genetic algorithm with a mixed region search for the asymmetric
traveling salesman problem,” Computers & Operations Research, vol. 30, no. 5, pp. 773–786, 2003.
[14] Z. H. Ahmed, “Genetic algorithm for the traveling salesman problem using sequential constructive
crossover operator,” International Journal of Biometrics & Bioinformatics (IJBB), vol. 3, no. 6, p. 96,
2010.
[15] J. Majumdar and A. K. Bhunia, “Genetic algorithm for asymmetric traveling salesman problem with
imprecise travel times,” Journal of Computational and Applied Mathematics, vol. 235, no. 9, pp. 3063–
3078, 2011.
[16] S. Chatterjee, C. Carrera, and L. A. Lynch, “Genetic algorithms and traveling salesman problems,” European
journal of operational research, vol. 93, no. 3, pp. 490–510, 1996.
[17] F. Smarandache, “Invisible paradox,” Neutrosophy/Neutrosophic Probability, Set, and Logic”, Am. Res.
Press, Rehoboth, pp. 22–23, 1998.
[18] H. Wang, F. Smarandache, Y. Zhang, and R. Sunderraman, “Single valued neutrosophic sets,” Review of
the Air Force Academy, no. 1, p. 10, 2010.
[19] H. Garg et al., “An improved score function for ranking neutrosophic sets and its application to decisionmaking
process,” International Journal for Uncertainty Quantification, vol. 6, no. 5, 2016.
