Article Preview
Top1. Introduction
The Travelling Salesman Problem (TSP) is one of the fundamental combinatorial problems. It looks for finding the optimal cycle between n cities, where all cities are visited only once except the starting city which is the last visited one. However, in real-life, the parameters of the industrial problems are in an uncertain environment due to different reasons and the most suitable presentation of these parameters will be as intuitionistic fuzzy sets instead of fixed real numbers. The concept of fuzzy sets was introduced by (Zadeh, 1965), while the theory of intuitionistic fuzzy sets was presented by (Atanassov, 1986).
In the intuitionistic fuzzy TSP, the aim is to find an optimal cycle between all cities with intuitionistic fuzzy distance (or cost, time, etc.). In the classical TSP, the indicates the distance of travelling from city i to city j. However, in the fuzzy TSP the distance will be denoted by and for the intuitionistic TSP the distance will be represented by .
The mathematical formulation of the intuitionistic fuzzy TSP is depicted in Eq. 1, where xij is the decision variable equal to 1 if city i is connected to city j and 0 otherwise.
Minimize:
(1)In literature, several papers solved the TSP under intuitionisitc domain. In (Prabakaran and Ganesan, 2018), the Hungarian method is used to solve the TSP with intuitionistic triangular fuzzy numbers. In (Prabha and Jeyalakshmi, 2020), the exerting reduced matrix technique is applied to find the shortest cyclic route for a mixed TSP (or type-3, where all parameters in the TSP matrix are crisp, fuzzy and intuitionistic numbers). In (Traneva and Traneva, 2020) the TSP under interval-valued intuitionistic fuzzy numbers is introduced then solved using hungarian method. In (Almahasneh and Kóczy, 2020) the TSP with intuitionistic fuzzy time dependent numbers is optimized. In (Anuradha and Kavitha, 2018), a sensitivity analysis method is presented to search the minimum Hamiltonian cycle for the intuitionistic fuzzy TSP.
In this paper, the TSP in intuitionistic triangular fuzzy environment is consider and the recently invented heuristic Dhouib-Matrix-TSP1 (DM-TSP1) is proposed to solve it. In fact, the DM-TSP1 heuristic is characterized by its rapidity to generate the optimal or a good initial basic solution after only n interactions (Dhouib, 2021a).
This paper presents the first application of the DM-TSP1 to vagueness environment where the distances between cities in the TSP are presented as intuitionistic triangular fuzzy set. The reminder of this paper is organized as follows. In section 2, a literature review is presented. In section 3, the fuzzy and intuitionistic terminologies are detailed. In section 4, the DM-TSP1 optimization heuristic is enhanced with Annie Varghese and Sunny Kuriakose ranking function (Varghese and Kuriakose, 2012) and with a range metric to select cities. In section 5, the efficiency of the enriched heuristic in the intuitionistic approach is proved through illustrative examples. Finally, the conclusion is given in section 6.