International Journal of Neutrosophic Science

Journal DOI

https://doi.org/10.54216/IJNS

Submit Your Paper

2690-6805ISSN (Online) 2692-6148ISSN (Print)

Volume 19 , Issue 3 , PP: 40-46, 2022 | Cite this article as | XML | Html | PDF | Full Length Article

The Neutrosophic Traveling Salesman problem with Neutrosophic EdgeWeight: Formulation and A Genetic Algorithm

Arindam Dey 1 * , Ranjan Kumar 2 , Said Broumi 3

  • 1 School of Computer Science and Engineering (SCOPE), VIT-AP University , Amravati, India - (arindam84nit@gmail.com)
  • 2 Department of Mathematics, VIT-AP University , Amravati, India - (ranjank.nit52@gmail.com)
  • 3 Laboratory of Information Processing, Faculty of Science Ben M’Sik, University Hassan II, Casablanca, MOROCCO - (broumisaid78@gmail.com)
  • Doi: https://doi.org/10.54216/IJNS.190304

    Received: June 06, 2022 Accepted: November 12, 2022
    Abstract

    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.

    Keywords :

    Neutrosophic Edge Weight , Formulation , Genetic Algorithm , Traveling Salesman problem

    References

    [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.

    Cite This Article As :
    Dey, Arindam. , Kumar, Ranjan. , Broumi, Said. The Neutrosophic Traveling Salesman problem with Neutrosophic EdgeWeight: Formulation and A Genetic Algorithm. International Journal of Neutrosophic Science, vol. , no. , 2022, pp. 40-46. DOI: https://doi.org/10.54216/IJNS.190304
    Dey, A. Kumar, R. Broumi, S. (2022). The Neutrosophic Traveling Salesman problem with Neutrosophic EdgeWeight: Formulation and A Genetic Algorithm. International Journal of Neutrosophic Science, (), 40-46. DOI: https://doi.org/10.54216/IJNS.190304
    Dey, Arindam. Kumar, Ranjan. Broumi, Said. The Neutrosophic Traveling Salesman problem with Neutrosophic EdgeWeight: Formulation and A Genetic Algorithm. International Journal of Neutrosophic Science , no. (2022): 40-46. DOI: https://doi.org/10.54216/IJNS.190304
    Dey, A. , Kumar, R. , Broumi, S. (2022) . The Neutrosophic Traveling Salesman problem with Neutrosophic EdgeWeight: Formulation and A Genetic Algorithm. International Journal of Neutrosophic Science , () , 40-46 . DOI: https://doi.org/10.54216/IJNS.190304
    Dey A. , Kumar R. , Broumi S. [2022]. The Neutrosophic Traveling Salesman problem with Neutrosophic EdgeWeight: Formulation and A Genetic Algorithm. International Journal of Neutrosophic Science. (): 40-46. DOI: https://doi.org/10.54216/IJNS.190304
    Dey, A. Kumar, R. Broumi, S. "The Neutrosophic Traveling Salesman problem with Neutrosophic EdgeWeight: Formulation and A Genetic Algorithm," International Journal of Neutrosophic Science, vol. , no. , pp. 40-46, 2022. DOI: https://doi.org/10.54216/IJNS.190304