Plane Thermoelastic Waves in Infinite Half-Space Caused Decision Making: Applications in Management and Engineering ISSN: 2560-6018 eISSN: 2620-0104 DOI: https://doi.org/10.31181/dmame0323062022s * Sujit Das. E-mail addresses: mukherjerjee.anupam.bnk@gmail.com (A. Mukherjee), partha4187@gmail.com (P.S. Barma), joy77deep@yahoo.co.in (J. Dutta), sujit.das@nitw.ac.in (S. Das), dpamucar@gmail.com (D. Pamucar) IMPRECISE COVERING RING STAR PROBLEM Anupam Mukherjee1, Partha Sarathi Barma2, Joydeep Dutta3, Sujit Das4,*, and Dragan Pamucar5 1 School of Applied Science and Humanities, Haldia Institute of Technology, Haldia, India 2 Center for Distance and Online Education, University of Burdwan, Burdwan, India 3 Department of Computer Science Kazi Nazrul University, Asansol, India 4 National Institute of Technology Warangal, India 5 Department of Logistics, University of Defence in Belgrade, Belgrade, Serbia Received: 11 March 2022; Accepted: 3 June 2022; Available online: 23 June 2022. Original scientific paper Abstract: In this paper, we formulate and solve an Imprecise Covering Ring Star Problem (ICRSP), a generalization of the Ring Star Problem (RSP). For a given network, the objective of this problem is to find a subset of nodes that forms a cycle, and other nodes are left-out nodes. This problem minimizes the total routing cost due to the cycle itself and assignment costs from the left-out nodes assigned to their nearest concentrators (i.e., nodes on the cycle). No assigned node exceeds a predetermined covering distance from its concentrator. The covering distance and the routing and assignment costs are considered fuzzy in the proposed ICRSP. A Modified Genetic Algorithm (MGA) has been developed and used to solve this model for different confidence levels depending on the corresponding imprecise parameters, reducing it to a deterministic form with fuzzy possibility and necessity approaches. Some comparisons with TSP benchmark problems are presented to justify the algorithm's performance. As individual cases, some practical ICRSPs are also solved and presented numerically. Key words: Covering Salesman Problem, Genetic Algorithm, Median Cycle Problem, Ring Star Problem. 1. Introduction 1.1. Literature Review Labbé et al. (1999) proposed a branch-and-cut technique based on some polyhedral properties to solve the model. Kedad-Sidhoum (2010) gave a chain-based formulation of RSP and proposed a branch-and-cut algorithm to obtain its results. An Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 2 integer programming approach to the same problem was formulated by Simonetti et al. (2011) and solved it by their branch-and-cut method. A Greedy Randomized Adaptive Search procedure for RSP was developed by Dias et al. (2006). Calvete et al. (2013) proposed an evolutionary method based on selection, crossover, and mutation for the same problem considering the installation cost. All the above authors examined their algorithms for RSP over the benchmark instances of TSPLIB for Travelling Salesman Problem (TSP). Labbé et al. (2004) studied a similar problem called the Median Cycle Problem, where the objective is to find a cycle with minimum routing cost from a subset of vertices in a network subject to an upper bound of assignment cost of the unvisited nodes. A variable neighborhood Tabu-search method was proposed by Moreno P´erez et al. (2003) for the median cycle problem. Capacitated m-ring star problem was introduced by Baldacci et al. (2007) where the goal is to find m rings with bounded capacity, which pass through a common depot and some other nodes, and all unvisited nodes are assigned to the visited nodes. The authors used a branch-and-cut algorithm for the model. Later, Naji- Azimi et al. (2012) proposed a heuristic method for the same model which consists of an integer linear programming based improvement on a variable neighborhood search. Introducing the multiple depot concept in the same model, Baldacci et al. (2010) further generalized it. Sundar et al. (2017) studied a polyhedral analysis and proposed an exact algorithm to solve the multiple-depot ring-star problem. Later, Baldacci et al. (2017) discussed pricing strategies of capacitated RSPs using dynamic programming approaches. Covering Salesman Problem (CSP) is similar to RSP, which minimizes the total traveling cost of a cycle through a subset of nodes from a network. The nodes out of the tour are within a predetermined distance from the visited nodes. This model was first introduced by Current & Schilling (1989) and solved with their proposed simple heuristics COVTOUR. Later, Golden et al. (2012) defined some variants of CSP and proposed two local search algorithms LS1 and LS2, which he used on the data sets initiated from TSPLIB. Salari et al. (2012) introduced an integer programming-based local search process for CSP. Recently, a hybrid algorithm consisting of dynamic programming and ant colony optimization (ACO) was developed by Salari et al. (2015). Mukherjee et al. (2019, 2021) have worked on ring star and ring tree problems considering an extra layer of rings. This second layer consists of secondary sub-depots. The authors have used their single and multi-objective discrete versions of the antlion optimizer. Barma et al. (2021) proposed a multi-objective ring-star vehicle routing problem with perishable items. The authors have considered an m-ring star network to speed up the routing process. This problem has been solved using a non-dominated sorting-based GA and strength Pareto evolutionary algorithm. 1.2. The Proposed Problem This paper introduces the concept of an Imprecise Covering Ring Star Problem (ICRSP). For a given network, a subset of nodes is to be selected to minimize the routing cost of the cycle through the selected nodes, added by the assignment cost of the unvisited nodes to their nearest concentrators. Also, the distance of each unvisited node to its nearest concentrator does not exceed a predetermined covering distance (Figure 1). Here, the routing cost, assignment costs and the covering distance are considered fuzzy and the shortest distance of one node to another node is considered crisp. A smooth formulation is given with possibility and necessity approaches for this model, which is reduced to deterministic forms in both cases. We have developed and used a modified genetic algorithm (MGA) where each binary chromosome implies a Imprecise Covering Ring Star Problem 3 subset of nodes of the given network. We assign the ith position of the chromosome as 1 if it is on the cycle and 0 otherwise. The MGA consists of probabilistic selection (Mukherjee et al., 2017), random crossover with proposed bi-part mating pool strategy, 4 types of mutations, i.e., exchange, inverse, reduction and augmentation mutations. The fitness function of each chromosome is the sum of the routing and assignment costs of the network. First, the MGA is compared with some of the best- known RSP results (Calvete et al., 2013) to justify the performance of the algorithm. After comparing the RSP results with the most renowned for some instances, a numerical experiment is performed to illustrate our ICRSP model. For the proposed ICRSP model, results with different confidence levels of routing cost, assignment costs and covering distance are presented in this paper. As individual cases, some practical ICRSPs are presented numerically. 1.3. Motivation In the case of Disaster Management, the routing costs from one node to another and assignment costs at nodes vary depending upon the type of the used conveyance, road condition, and climate condition at the time of journey, etc. Similarly, in the case of telecommunication, also, these costs are not permanently fixed. In- stead, these costs may be vague in a practical sense. Again, in the above- mentioned practical problems, the covering distance of left out nodes from the corresponding connecting nodes is not fixed, like fixed ‘l’ distance units. Instead, the covering distances are considered “near about ‘l’ distance units”. It can be little more than ‘l’ or slightly less than ‘l.’ The practical considerations motivated us to take up the present investigation. Fig 1. The Proposed ICRSP 1.4. Novelty Thus, the new features/concepts on RSP introduced in the present paper are: • The impreciseness of routing and assignment costs are considered. • The covering distance at each nearest concentrator from the left-out nodes is imprecise. • The proposed fuzzy optimization problem is transformed into a deterministic one using possibility and necessity measures. • A Modified Genetic Algorithm (MGA) with a bi-part mating pool crossover strategy is proposed to solve NP-hard problems like ICRSP. Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 4 The rest of the paper has been organized as follows. Section 2 recalls some mathematical preliminaries. Section 3 describes the mathematical formulation of the proposed problem. The solution procedure is presented in Section 4. Sections 5 and 6 include the numerical illustration and the discussion based on it, respectively. Some particular ICRSP is projected in section 7. Lastly, section 8 concludes the paper. 2. Mathematical Preliminaries 2.1. Fuzzy Possibility and Necessity Approach Let �̃� and �̃� be two fuzzy numbers 𝜇�̃�(𝑥) and 𝜇�̃�(𝑥) are their membership functions respectively. Then according to Zadeh (1994), pos(ã* b̃) = sup{min(μã(x),μb̃(y)),x,y ∈ R,x*y} (1) where pos stands for possibility, and 𝑛𝑒𝑠(𝑎∗ �̃�) = 1 − 𝑝𝑜𝑠(𝑎∗ �̃�̅̅̅̅̅̅̅) (2) where nes stands for necessity. If �̃�, �̃� ∈ ℜ and �̃� = 𝑓(�̃�, �̃�) where 𝑓:ℜ×ℜ → ℜ, then 𝜇𝑐̃ of c̃ is defined as For each 𝑧 ∈ ℜ, 𝜇𝑐̃(𝑧) = sup {min (𝜇�̃�(𝑥),𝜇�̃�(𝑦))} (3) 𝑥,𝑦 ∈ ℜ,𝑧 = 𝑓(𝑥,𝑦) The following lemmas can easily be derived (Zadeh et al., 1994) from the above given definitions. Lemma 1 If �̃� = (𝑎1,𝑎2,𝑎3) be a TFN with 0 < 𝑎1 and 𝑏 is a crisp number then 𝑃𝑜𝑠(�̃� < 𝑏) ≥ 𝛽 iff 𝑏−𝑎1 𝑎2−𝑎1 ≥ 𝛽 Lemma 2 If �̃� = (𝑎1,𝑎2,𝑎3) be a TFN with 0 < 𝑎1 and 𝑏 is a crisp number then 𝑛𝑒𝑠(�̃� < 𝑏) ≥ 𝛽 iff 𝑎3−𝑏 𝑎3−𝑎2 ≤ 1− 𝛽 Lemma 3 If �̃� be a TFN with 0 < 𝑎1 and 𝑏 be a crisp number then 𝑝𝑜𝑠(�̃� > 𝑏) ≥ 𝜂 iff 𝑎3−𝑏 𝑎3−𝑎2 ≥ 𝜂 Lemma 4 If �̃� be a TFN with 0 < 𝑎1 and 𝑏 be a crisp number then 𝑛𝑒𝑠(�̃� > 𝑏) ≥ 𝜂 iff 𝑏−𝑎1 𝑎2−𝑎1 ≤ 1− 𝜂 where β and η are predefined confidence levels. 3. Model Formulation 3.1. Ring Star Problem 𝑁 = {𝑥1,𝑥2,𝑥3,…,𝑥𝑛} being a set of nodes which defines the complete network, find a complete cycle (𝑥1,𝑥𝛼1,𝑥𝛼2,𝑥𝛼3,…,𝑥𝛼𝑚},𝑥1), where {𝑥1}⋃𝑥𝛼𝑖 𝑚 𝑖=1 = 𝑁′ ⊆ 𝑁,𝑚 ≤ 𝑛 −1 which minimizes the sum of the routing cost of the cycle through 𝑁′ and the Imprecise Covering Ring Star Problem 5 assignment costs of the vertices out of the cycle to their nearest concentrators on the cycle, where the node 𝑥1 is considered as depot. Hence the objective is to minimize 𝑐(𝑥1,𝑥𝛼1)+∑ 𝑐(𝑥𝛼𝑖,𝑥𝛼𝑖+1)+𝑐(𝑥𝛼𝑚,𝑥1) 𝑚−1 𝑖=1 +∑ 𝑑(𝑥𝑗,𝑦𝑘)𝑥𝑗∈ 𝑁′ 𝑦𝑘∈ 𝑁∖ 𝑁′ 𝑑𝑒𝑔(𝑦𝑘)=1 (4) where 𝑥1 ≠ 𝑥𝛼𝑖 and 𝑥𝛼𝑖 ≠ 𝑥𝛼𝑗 for 𝑖 ≠ 𝑗;∀𝑖, 𝑗 = 1,2,3,…,𝑚, 𝑐(𝑖, 𝑗) = routing cost from node 𝑖 to node 𝑗, 𝑑(𝑖,𝑗) = assignment cost of node 𝑗 to node 𝑖. 3.2. Imprecise Covering Ring Star Problem In this case, the objective is to minimize �̃�(𝑥1,𝑥𝛼1)+∑ �̃�(𝑥𝛼𝑖,𝑥𝛼𝑖+1)+ �̃�(𝑥𝛼𝑚,𝑥1) 𝑚−1 𝑖=1 +∑ �̃�(𝑥𝑗,𝑦𝑘)𝑥𝑗∈ 𝑁′ 𝑦𝑘∈ 𝑁∖ 𝑁′ 𝑑𝑒𝑔(𝑦𝑘)=1 (5) subject to 𝑥𝑗 ∈ �̅� (𝑥1,Δ1̃)∪�̅�(𝑥𝛼𝑖,Δ𝛼𝑖 ̃) ∀ 𝑗 ∈ 𝑁 and for some 𝑖 (6) where 𝑥1 ≠ 𝑥𝛼𝑖 and 𝑥𝛼𝑖 ≠ 𝑥𝛼𝑗 for 𝑖 ≠ 𝑗;∀𝑖, 𝑗 = 1,2,3,…,𝑚, �̃�(𝑖, 𝑗) = fuzzy routing cost from node 𝑖 to node 𝑗, �̃�(𝑖, 𝑗) = fuzzy assignment cost of node 𝑗 to node 𝑖, �̅�(𝑎,𝑟) = closed disc with centre 𝑎 and radius 𝑟, Δ�̃� = fuzzy covering distance at node 𝑖. Considering the aforesaid costs and the covering distance as triangular fuzzy number (TFN), the problem can be rewritten as: 3.2.1. Possibility Approach (Optimistic) Determine a complete cycle (𝑥1,𝑥𝛼1,𝑥𝛼2,𝑥𝛼3,…,𝑥𝛼𝑚,𝑥1) to minimize 𝐹1 +𝐹2 (7) subject to 𝑃𝑜𝑠(�̃�(𝑥1,𝑥𝛼1)+∑ �̃�(𝑥𝛼𝑖,𝑥𝛼𝑖+1) 𝑚−1 𝑖=1 +�̃�(𝑥𝛼𝑚,𝑥1) < 𝐹1) ≥ 𝛽1 (8) 𝑃𝑜𝑠 ( ∑ �̃�(𝑥𝑗,𝑦𝑘)𝑥𝑗∈ 𝑁′ 𝑦𝑘∈ 𝑁∖ 𝑁′ 𝑑𝑒𝑔(𝑦𝑘)=1 < 𝐹2 ) ≥ 𝛾1 (9) 𝑃𝑜𝑠(𝛿(𝑥𝑗,𝑥1) ≤ Δ1̃) ≥ 𝜂1 and 𝑃𝑜𝑠(𝛿(𝑥𝑗,𝑥𝛼𝑖) ≤ Δ𝛼𝑖 ̃) ≥ 𝜂1 (10) ∀𝑗 ∈ 𝑁 and for some 𝛼𝑖, where 𝛽1,𝛾1 and 𝜂1 are confidence levels for routing cost, assignment costs and covering distance and 𝛿(𝑥𝑖,𝑥𝑗) is the shortest distance between 𝑥𝑖 and 𝑥𝑗. The above equations (7)-(10) can be rewritten as: Determine a complete cycle (𝑥1,𝑥𝛼1,𝑥𝛼2,𝑥𝛼3,…,𝑥𝛼𝑚,𝑥1) to minimize 𝐹1 +𝐹2 (11) subject to 𝑃𝑜𝑠(𝐶 ̃ < 𝐹1) ≥ 𝛽1 (12) where, Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 6 𝐶 ̃ = �̃�(𝑥1,𝑥𝛼1)+ ∑ �̃�(𝑥𝛼𝑖,𝑥𝛼𝑖+1) 𝑚−1 𝑖=1 +�̃�(𝑥𝛼𝑚,𝑥1), 𝑃𝑜𝑠(𝐷 ̃ < 𝐹2) ≥ 𝛾1 (13) and, �̃� = ∑ �̃�(𝑥𝑗,𝑦𝑘) 𝑥𝑗∈ 𝑁′ 𝑦𝑘∈ 𝑁∖ 𝑁′ 𝑑𝑒𝑔(𝑦𝑘)=1 𝑃𝑜𝑠(𝛿(𝑥𝑗,𝑥1) ≤ Δ1̃) ≥ 𝜂1 and 𝑃𝑜𝑠(𝛿(𝑥𝑗,𝑥𝛼𝑖) ≤ Δ𝛼𝑖 ̃) ≥ 𝜂1 (14) ∀𝑗 ∈ 𝑁 and for some 𝛼𝑖. Considering all imprecise costs and covering distances as triangular fuzzy numbers, namely, 𝐶 ̃ = (𝐶1,𝐶2,𝐶3),�̃� = (𝐷1,𝐷2,𝐷3), Δ̃𝑘 = ((Δ𝛼𝑘)1 ,(Δ𝛼𝑘)2 ,(Δ𝛼𝑘)3 ) and following lemmas 1 and 3, the equations (11) to (14) can be transformed to: Determine a complete cycle (𝑥1,𝑥𝛼1,𝑥𝛼2,𝑥𝛼3,𝑥𝛼𝑚,𝑥1) to minimize 𝐹1 +𝐹2 (15) subject to 𝐹1−𝐶1 𝐶2−𝐶1 ≥ 𝛽1 (16) 𝐹2−𝐷1 𝐷2−𝐷1 ≥ 𝛾1 (17) (Δ𝛼𝑖 ) 3 −𝛿(𝑥𝑗,𝑥𝛼𝑖 ) (Δ𝛼𝑖 ) 3 −(Δ𝛼𝑖 ) 2 ≥ 𝜂1 (18) ∀𝑗 ∈ 𝑁 and for some 𝛼𝑖. The above equations (15)-(18) can be rewritten as: Determine a complete cycle (𝑥1,𝑥𝛼1,𝑥𝛼2,𝑥𝛼3,𝑥𝛼𝑚,𝑥1) to minimize 𝐶1 +𝛽1(𝐶2 −𝐶1)+𝐷1 +𝛾1(𝐷2 −𝐷1) (19) subject to (Δ𝛼𝑖)3 −𝜂1 {(Δ𝛼𝑖)3 −(Δ𝛼𝑖)2 } ≥ 𝛿(𝑥𝑗,𝑥𝛼𝑖) (20) ∀𝑗 ∈ 𝑁 and for some 𝛼𝑖. 3.2.2. Necessity Approach (Pessimistic) For necessity approach, following the 2 and 4, the equations (5), (6) can be transformed to: Determine a complete cycle (𝑥1,𝑥𝛼1,𝑥𝛼2,𝑥𝛼3,𝑥𝛼𝑚,𝑥1) to minimize 𝐹1 +𝐹2 (21) subject to Imprecise Covering Ring Star Problem 7 𝐶3−𝐹1 𝐶3−𝐶2 < 1−𝛽1 (22) 𝐷3−𝐹2 𝐷3−𝐷2 < 1−𝛾1 (23) 𝛿(𝑥𝑗,𝑥𝛼𝑖 )−(Δ𝛼𝑖 ) 1 (Δ𝛼𝑖 ) 2 −(Δ𝛼𝑖 ) 1 < 1 −𝜂1 (24) ∀𝑗 ∈ 𝑁 and for some 𝛼𝑖, where 𝛽2, 𝛾2 and 𝜂2 are confidence levels for cycle cost, assignment costs and covering distance. The above equations (21)-(24) can be rewritten as: Determine a complete cycle (𝑥1,𝑥𝛼1,𝑥𝛼2,𝑥𝛼3,𝑥𝛼𝑚,𝑥1) to minimize 𝐶2 +𝛽2(𝐶3 −𝐶2)+𝐷2 +𝛾2(𝐷3 −𝐷2) (25) subject to (Δ𝛼𝑖)2 −𝜂1 {(Δ𝛼𝑖)2 −(Δ𝛼𝑖)1 } ≥ 𝛿(𝑥𝑗,𝑥𝛼𝑖) (26) ∀𝑗 ∈ 𝑁 and for some 𝛼𝑖. 4. Solution Procedure using MGA 4.1. Description In the MGA for ICRSP, each chromosome is represented as a binary string (Calvete et al., 2013) equal to the total number of nodes contained in the network. The 𝑖𝑡ℎ element of the array is 1 if the corresponding node is on the cycle and it is 0 otherwise. As we fix the first node considering as the depot, so the first element of the string is always 1. For the other strings, we randomly generate 0’s and 1’s and fill each of the chromosomes of the total populations. This process is called the initialization procedure. Probabilistic selection (Mukherjee et al., 2017) is an efficient selection procedure which selects the chromosomes in each generation on the basis of the fitness function fitness(chromosome) = TSP(chromosome) +Assignment(chromosome). It is tested by Mukherjee et al. (2017) that the probabilistic selection technique is more efficient than ordinary roulette-wheel selection in most cases. After performing the selection procedure, the new population is archived to a set S1 with the considered population size m. Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 8 Fig 2. Representation of a chromosome, random crossover and inverse mutation We propose a bi-part strategic-based mating pool selection procedure to obtain offspring. At first, mating pools are selected based on the probability of crossover pc = 0.7 and sorted according to their fitness in descending order. Let the selected number of parents be 2q. After sorting, the parents are divided into two groups, each of which contains q chromosomes. Hence, the random crossover technique is performed between ith and (q +i)th parents, where 1 ≤ i ≤ q,, i.e., each corresponding parent between two groups. The proposed bi-part mating pool strategy is represented in Figure 3. In the next step, four types of mutations have been used to maintain diversity and have a better chance of finding near optimality. These are inverse mutation (Mukherjee et al., 2017) (with probability of mutation pm = 0.2) along with exchange mutation, reduction and augmentation local searches (Calvete et al., 2013) (with pm = 0.5). A mutated chromosome can replace the corresponding previous one if it has a better fitness value. For TSP evaluation in the fitness function, we use the 2-opt procedure keeping in mind the total time-consuming factor due to the impreciseness of the model, and the cost is calculated depending on confidence level β. Another cost, i.e., assignment cost in the fitness function, can easily be evaluated considering the corresponding confidence level γ of impreciseness. After crossover and mutations, the new population is archived in another set S2 with size m. Among the total 2m chromosomes of S1∪ S2, the best m chromosomes are selected without repetition and sent to the next generation. Each chromosome is considered feasible at each generation if it satisfies the covering distance constraint depending on the confidence level η of covering distance. The representation of a chromosome, random crossover, and inverse mutation are shown in Figure 2. Imprecise Covering Ring Star Problem 9 4.2. Algorithm in details 4.2.1. Initialization Input: number of nodes n, population size (pop-size) Output: a set of pop-size chromosomes each having n bits 1. 𝑓𝑜𝑟(𝑖 = 1 to 𝑝𝑜𝑝-𝑠𝑖𝑧𝑒){ 2. 𝑐ℎ𝑟𝑜𝑚𝑒[𝑖][1] = 1; 3. 𝑓𝑜𝑟(𝑗 = 2 𝑡𝑜 𝑛){ 𝑡 = 𝑟𝑎𝑛𝑑( )%2; 𝑖𝑓 (𝑡 = 1){ 𝑐ℎ𝑟𝑜𝑚𝑒[𝑖][𝑗] = 1; } 𝑒𝑙𝑠𝑒 𝑐ℎ𝑟𝑜𝑚𝑒[𝑖][𝑗] = 0; } } 4.2.2. Probabilistic Selection This is a more efficient selection procedure used previously by the authors Mukherjee et al. (2017). This technique was first tested on some TSP benchmark problems and justified its better efficiency and hence used in MGA. 4.2.3. Random Crossover Input: total number of nodes 𝑛, 𝑝𝑎𝑟𝑒𝑛𝑡1, 𝑝𝑎𝑟𝑒𝑛𝑡2, fitness function 𝑓 Output: 𝑐ℎ𝑖𝑙𝑑1, 𝑐ℎ𝑖𝑙𝑑2 1. 𝑐ℎ𝑖𝑙𝑑1[1] = 𝑐ℎ𝑖𝑙𝑑2[1] = 1; 2. 𝑓𝑜𝑟 (𝑖 = 2 𝑡𝑜 𝑛){ 𝑠 = 𝑟𝑎𝑛𝑑( )%2; 𝑖𝑓(𝑠 = 1){ 𝑐ℎ𝑖𝑙𝑑1[𝑖] = 𝑝𝑎𝑟𝑒𝑛𝑡1[𝑖]; } 𝑒𝑙𝑠𝑒{ 𝑐ℎ𝑖𝑙𝑑1[𝑖] = 𝑝𝑎𝑟𝑒𝑛𝑡2[𝑖]; } } 3. . 𝑓𝑜𝑟 (𝑖 = 2 𝑡𝑜 𝑛){ 𝑡 = 𝑟𝑎𝑛𝑑( )%2; 𝑖𝑓(𝑡 = 1){ 𝑐ℎ𝑖𝑙𝑑2[𝑖] = 𝑝𝑎𝑟𝑒𝑛𝑡2[𝑖]; } 𝑒𝑙𝑠𝑒{ 𝑐ℎ𝑖𝑙𝑑2[𝑖] = 𝑝𝑎𝑟𝑒𝑛𝑡1[𝑖]; } } Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 10 Fig 3. Graphical representation of Bi-part mating pool strategic crossover 4.2.4. Inverse Mutation Inverse mutation (Mukherjee et al. 2017) is a well-known mutation technique that works faster than conventional random mutation (Mukherjee et al. 2017). Exchange, reduction (vertex removal) and augmentation (vertex addition) mutations are three local search techniques that have been implemented inspired by the authors Calvete et al. (2013) and Salari et al. (2015). 4.2.5. Procedure MGA Input: Maximum number of generation (𝑚𝑎𝑥-𝑔𝑒𝑛), 𝑝𝑜𝑝-𝑠𝑖𝑧𝑒, number of nodes 𝑛, cost matrix, distance matrix crossover probability 𝑝𝑐, mutation probability 𝑝𝑚, probability of crossover 𝑝𝑠 Output: Minimum ICRSP cost 1. Procedure_Initialization Imprecise Covering Ring Star Problem 11 2. Set gen← 1, 𝑔𝑙𝑜𝑏-𝑏𝑒𝑠𝑡 = 𝑙𝑜𝑐-𝑏𝑒𝑠𝑡 = 𝑀𝐴𝑋-𝐼𝑁𝑇 3. Procedure_Probabilistic selection based on 𝑝𝑠 4. Archive the population to the set 𝑆1 (size 𝑚) 5. for(i=1 to 𝑝𝑜𝑝-𝑠𝑖𝑧𝑒){ if(rand[0,1] < pc) { 𝑖𝑡ℎ is selected for crossover } } 6. Procedure_random crossover with bi-part strategy among the mating pools 7. 𝑓𝑜𝑟(𝑖 = 1 to 𝑝𝑜𝑝-𝑠𝑖𝑧𝑒){ 𝑖𝑓(𝑟𝑎𝑛𝑑[0,1] < 𝑝𝑚){ 𝑠𝑒𝑙𝑒𝑐𝑡 𝑖𝑡ℎ chromosome for mutation } } 8. Procedure_inverse, exchange, augmentation and reduction mutations according to their 𝑝𝑚 9. Archive the new population to another set 𝑆2 (𝑠𝑖𝑧𝑒 𝑚) 10. Select best 𝑚 chromosomes from the set 𝑆1 ∪ 𝑆2 11.𝑓𝑜𝑟(𝑖 = 1 to 𝑝𝑜𝑝-𝑠𝑖𝑧𝑒){ 𝑖𝑓(𝑓[𝑖] < 𝑙𝑜𝑐-𝑏𝑒𝑠𝑡 and covering constraint satisfied){ 𝑙𝑜𝑐-𝑏𝑒𝑠𝑡 = 𝑐𝑜𝑠𝑡[𝑖] } } 12. 𝑔𝑒𝑛 ← 𝑔𝑒𝑛 +1 13. 𝑖𝑓(𝑙𝑜𝑐-𝑏𝑒𝑠𝑡 < 𝑔𝑙𝑜𝑏 −𝑏𝑒𝑠𝑡){ 𝑔𝑙𝑜𝑏-𝑏𝑒𝑠𝑡 ← 𝑙𝑜𝑐-𝑏𝑒𝑠𝑡 } 14. 𝑖𝑓(𝑔𝑒𝑛 < 𝑚𝑎𝑥𝑔𝑒𝑛){ 𝑔𝑜𝑡𝑜 𝑠𝑡𝑒𝑝 3 𝑒𝑙𝑠𝑒 Goto step 15 } 15. end The MGA program is operated until the termination condition is reached. We terminate the program if it yields the same solution in consecutive 50 generations. 5. Numerical Experiments 5.1. Verification with earlier RSP results To justify the performance of the developed MGA, we developed it in C programming language and tested it on a PC with Intel CORE i3. We choose some TSP benchmark problems and compare them with the RSP results obtained by Calvete et al.'s BBEA (Calvete et al., 2013) which has been the most efficient algorithm to outperform all other RSP algorithms, are given in Table 1. The routing costs 𝑐𝑖𝑗 and the assignment cost 𝑑𝑖𝑗 in the objective function being as follows: 𝑐𝑖𝑗 = 𝛼 𝐼𝑖𝑗,𝑑𝑖𝑗 = (10−𝛼)𝐼𝑖𝑗 Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 12 where, 𝐼𝑖𝑗 is the travelling costs from node 𝑖 to node 𝑗 in TSP instances and 𝛼 = 3,5,7,9. The different values of 𝛼 consider the different distribution of weights on rings and stars. More precisely, when 𝛼 = 3, the optimal solution should include all the nodes in the ring, as the star nodes assume (10 − 3) = 7 weightage. Similarly, when 𝛼 = 9, most vertices should be out of the ring. Here, for the TSP part in the fitness function, we use the same TSP solver algorithms as used by Calvete et al. (2013) and Salari et al. (2015) in their work on CSP, i.e., 2-𝑜𝑝𝑡, 3-𝑜𝑝𝑡, and the Lin-Kernighan method (Helsgaun, 2000) in the required cases. 5.2. Experiment with Proposed Models To illustrate our proposed model, we consider 100 nodes and randomly generate a 100 ×100 fuzzy cost matrix whose elements are TFNs in the form (𝑎1,𝑎2,𝑎3) with 30 ≤ 𝑎1 ≤ 120 and 𝑎2 = 𝑎1 +1 + 𝑟𝑎𝑛𝑑()%3, 𝑎3 = 𝑎2 + 1+ 𝑟𝑎𝑛𝑑()%3 and a 100 × 100 distance matrix with lower bound 22.5 and upper bound 90. For these fuzzy costs, the proposed imprecise model is reduced to deterministic ones (19,20) and (25,26) using the possibility and the necessity approaches respectively and solved by proposed MGA. In Table 2, some results for different parametric values of 𝛽 and 𝛾 along with no covering distance restrictions and with a crisp covering a distance of 70 distance units are presented using both the proposed MGA and BBEA (Calvete et al., 2013). The 𝛽 and 𝛾 are the confidence levels of routing and related assignment costs, respectively. We have compared the results obtained by the proposed MGA of our ICRSP model only with BBEA (Calvete et al., 2013) since it is the best among all the existing RSP methods. To apply BBEA in our ICRSP model, we developed it into an equivalent imprecise form and then compared it with our proposed MGA. In Table 3, we present some results using MGA for different values of 𝛽, 𝛾, and 𝜂 with a fuzzy covering distance (65,70,76), where 𝜂 is the confidence level of the covering distance. In the results with uncertain data, the fitness function is simply the sum of two costs-- the routing and assignment costs. Also, the 2-𝑜𝑝𝑡 procedure for solving TSPs is used in the program, as the program gets more intricate than the crisp case. Table 1 Verification of RSP results: Proposed MGA and BBEA (Calvete et al. 2013) Instance α Best known cost using BBEA Best cost by MGA among 25 different runs Time (s) eil51 3 1278 1278 0.76 eil51 5 1995 1995 1.92 eil51 7 2113 2113 2.01 eil51 9 1244 1244 2.27 berlin52 3 22,626 22,626 0.68 berlin52 5 36,115 36,115 1.91 berlin52 7 37,376 37,376 2.04 berlin52 9 20,361 20,361 2.15 brazil58 3 76,185 76,185 1.94 brazil58 5 115,045 115,045 2.54 brazil58 7 126,807 126,807 1.86 brazil58 9 83,690 83,690 1.77 st70 3 2025 2025 1.22 st70 5 3110 3110 2.41 st70 7 3402 3402 2.64 st70 9 2610 2610 2.88 Imprecise Covering Ring Star Problem 13 Instance α Best known cost using BBEA Best cost by MGA among 25 different runs Time (s) eil76 3 1614 1614 2.72 eil76 5 2460 2460 3.21 eil76 7 2504 2504 2.87 eil76 9 1710 1710 2.46 pr76 3 324,477 324,477 2.82 pr76 5 500,395 500,395 3.56 pr76 7 555,845 555,845 3.74 pr76 9 424,359 424,359 3.96 rat99 3 3633 3633 4.11 rat99 5 5885 5885 4.27 rat99 7 6436 6436 4.82 rat99 9 5150 5150 4.88 kroA100 3 63,846 63,846 4.74 kroA100 5 100,785 100,785 4.28 kroA100 7 115,388 115,388 5.07 kroA100 9 94,265 94,265 4.62 Table 2 Numerical results of proposed ICRSP using proposed MGA and BBEA (Calvete et al. 2013) with crisp covering distance Appro ach β γ optimal cost without covering distance optimal cost with covering distance = 70 distance units Proposed MGA Time (s) BBEA Time Proposed MGA Time (s) BBEA Time (s) Pos 0.6 0.6 3416.39 6.16 = 7.31 3427.1 7.07 = 7.24 0.7 3402.6 5.41 = 6.87 3432.1 6.18 = 7.47 0.8 3504.59 5.22 = 6.43 3509.8 6.94 = 7.85 0.9 3423.1 4.82 = 5.79 3491.29 6.15 = 6.27 0.95 3383.09 5.27 3381.6* 7.92 3512.04 5.08 = 6.11 0.7 0.6 3399 5.59 = 5.74 3484.40 5.87 = 5.44 0.7 3399.89 4.23 = 6.08 3563.5 7.31 = 8.18 0.8 3443 5.52 = 5.97 3477.20* 6.80 3486.29 7.12 0.9 3435.34 7.98 = 7.76 3486.19 7.82 = 8.32 0.95 3428.65 5.69 = 7.11 3471.09 7.54 = 7.92 0.8 0.6 3497.20 6.76 = 7.83 3672.8 6.94 = 8.11 0.7 3506* 5.09 3517.89 6.87 3597.5 7.19 = 6.93 0.8 3511.39* 6.82 3519.1 5.38 3622.39 5.88 = 6.23 0.9 3442 5.19 = 7.86 3489.19 8.14 = 7.91 0.95 3424.1* 6.61 3430.29 7.11 3481.84* 7.56 3493 8.14 0.9 0.6 3454.69 7.25 = 6.57 3608.40 8.39 = 7.83 0.7 3434.90* 6.67 3452.6 7.18 3605.19* 8.14 3611.5 7.66 0.8 3446.6 5.17 = 7.22 3606.3 7.85 = 8.11 0.9 3464.59* 7.08 3467.2 5.47 3633.9* 8.17 3637.29 8.42 0.95 3456.94* 4.29 3462.1 6.22 3632.54* 5.49 3643.5 7.55 0.95 0.6 3445.94 5.28 = 7.45 3606.35 7.74 3604.49* 9.22 0.7 3497.04 6.94 = 7.88 3707.5* 8.21 3711.1 6.16 Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 14 Appro ach β γ optimal cost without covering distance optimal cost with covering distance = 70 distance units 0.8 3463.8* 6.67 3472.59 8.04 3686 5.86 = 6.22 0.9 3482.04 7.11 = 7.74 3720.20 7.66 = 7.89 0.95 3457.44 5.82 = 6.25 3628.84* 5.84 3634.5 5.17 Nec 0.6 0.6 3664.20 7.26 = 8.14 3693.20 7.84 = 9.24 0.7 3634.6 6.51 = 5.22 3762.40 7.08 = 8.28 0.8 3637.8 7.12 = 9.37 3730.20* 8.02 3736.10 8.10 0.9 3630.70* 4.22 3642.20 6.28 3690.20 7.53 = 9.14 0.95 3547 5.72 = 7.29 3793.35 8.96 = 10.22 0.7 0.6 3750.6 5.65 = 6.24 3845 7.37 = 9.72 0.7 3606.8 6.58 = 7.55 3798.39 6.49 = 7.62 0.8 3579.89* 7.11 3586.6 6.86 3729.39 8.84 = 11.46 0.9 3721.5 6.62 = 8.11 4056.5 7.48 = 8.44 0.95 3674.69* 11.41 3686.8 6.73 4047.14 8.82 = 9.22 0.8 0.6 3653 6.71 = 8.43 3753.39 7.66 = 8.92 0.7 3501.6 5.16 = 6.74 3664.70 8.28 3658.1* 9.24 0.8 3581.8 7.62 = 6.22 3692.39 6.65 = 8.36 0.9 3633.1 11.85 = 9.52 3788.70 10.24 = 13.45 0.95 3622.85* 6.33 3645.6 7.42 3771.8 8.21 = 8.48 0.9 0.6 3822.69 7.33 = 6.46 3878.59 7.96 = 9.24 0.7 3786.19 8.94 = 10.41 3877.19 9.85 = 11.21 0.8 3785.19 7.16 = 8.64 3880.19 8.34 = 9.72 0.9 3797.20* 6.82 3801.19 8.52 3879.59 7.36 3878.19* 10.08 0.95 3711.1 5.89 = 6.74 3793.44 8.58 = 9.55 0.95 0.6 3812.20 7.65 = 9.52 3853* 9.86 3862.59 11.73 0.7 3555.3 6.82 = 7.58 3842.79 8.65 = 7.52 0.8 3667.20* 8.57 3674.49 6.28 3882.39 9.11 = 11.80 0.9 3648.8 11.15 = 14.53 3843.6 9.64 = 12.54 0.95 3642.6 9.25 = 10.55 3719.54 13.96 = 12.74 Table 3 Numerical results of proposed ICRSP using proposed MGA and BBEA (Calvete et al. 2013) with Fuzzy covering distance η β γ optimal cost with covering distance (65, 70, 76) Possibility-approach Time (s) optimal cost with covering distance (65, 70, 76) Necessity-approach Time (s) 0.7 0.8 0.8 3449.5998 7.61 4018.6 8.51 0.9 3471.6999 7.40 4133.3999 10.02 0.95 3468.75 6.45 4188.1 9.29 0.9 0.8 3559.6 8.27 4110.3999 11.68 0.9 3587.1 7.19 4114.3999 7.26 0.95 3556.6999 8.22 4139.2998 9.12 0.95 0.8 3642.2001 9.67 4137 10.34 0.9 3665.6501 6.28 4116.2 10.11 0.95 3572.6499 9.03 4003.0541 8.41 0.8 0.8 0.8 3562.6 7.59 4063 9.82 0.9 3548.6 8.95 4133.3999 8.76 0.95 3453.75 8.27 4188.1 8.14 0.9 0.8 3585.2001 9.17 4110.3999 10.27 0.9 3608 7.72 4114.3999 8.46 0.95 3537.5998 8.18 4139.2998 9.82 Imprecise Covering Ring Star Problem 15 η β γ optimal cost with covering distance (65, 70, 76) Possibility-approach Time (s) optimal cost with covering distance (65, 70, 76) Necessity-approach Time (s) 0.95 0.8 3582.0998 7.08 4112.2001 6.94 0.9 3582.0998 9.58 4116.2001 7.49 0.95 3533.6 9.77 4141.1 7.73 0.9 0.8 0.8 3562.6 8.65 4070.3999 8.02 0.9 3655.1999 9.19 4101.1 9.87 0.95 3484.75 8.74 4188.1 7.15 0.9 0.8 3563.1 7.67 4032 7.42 0.9 3624.5 9.91 4137.2001 9.37 0.95 3533.5998 8.71 4137.2998 9.91 0.95 0.8 3601.1499 9.45 3712.3999 9.29 0.9 3728.3498 9.43 3842.9501 8.77 0.95 3693.3 11.52 4188.9501 12.82 0.95 0.8 0.8 3589.4501 8.38 3970.8 8.89 0.9 3691.1999 9.16 4137.2001 8.74 0.95 3453.75 9.78 4146.2998 9.26 0.9 0.8 3589 8.82 3974.7001 9.71 0.9 3565.1 10.22 3782.3999 11.33 0.95 3537.3999 9.11 4188.1 5.86 0.95 0.8 3582.0998 7.18 3834.35 7.54 0.9 3605.6 9.74 3714.3999 8.71 0.95 3613.25 9.52 4141.1 10.96 Table 4 Some numerical results of particular ICRSP using MGA where the nodes 4,21,44,67,82 and 91 are always present on the route η β γ optimal cost with covering distance (65, 70, 76) Possibility-approach Time (s) optimal cost with covering distance (65, 70, 76) Necessity-approach Time (s) 0.95 0.8 0.8 3704.6999 8.74 4029.3999 8.48 0.9 3780.1 10.85 4157.25 9.82 0.95 3577.6 9.11 4164.35 8.37 0.9 0.8 3704.1999 9.28 4187.2001 11.41 0.9 3691.25 9.71 3994.1 8.58 0.95 3676.2998 8.91 4266.25 9.92 0.95 0.8 3714.1999 7.55 3952.3999 11.87 0.9 3689.1 8.93 3811.1999 8.52 0.95 3722.3999 8.46 4173.1 9.89 6. Discussion In Table 1, the best result of the considered benchmark problems among 25 different runs of the proposed MGA is the same as the results given by Calvete et al. (2013), where the parameter α and the objective function are considered the same as mentioned by the above authors. Table 2 presents near-optimal costs without and with a crisp covering distance separately, both in the possibility and the necessity approaches, using BBEA and proposed MGA. The route's cost with a covering distance is higher than that without the same restriction, which is as per our expectation. In most cases, the optimal solution is best at β=0.7 when γ is fixed. From the whole table, we notice that MGA performs better than BBEA in many results for different confidence levels, though sometimes it takes slightly more time than BBEA to result in a better solution. From Table 3, it is clear that the increase in the magnitude of η (confidence level of imprecise covering distance) increases the optimal cost for any fixed β and γ. In all cases, the possibility approach gives better optimal solutions than the necessity approach, which is as per expectations. Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 16 7. Conclusion An Imprecise Covering Ring Star Problem (ICRSP) is proposed and solved by a proposed modified genetic algorithm (MGA). The routing costs and the assignment costs are considered imprecise values. Also, an imprecise covering distance constraint is introduced, which is very significant in real-life cases and has not been discussed in the ring star problems by earlier researchers. Each type of cost is considered a fuzzy variable, and the ICRSP model is reduced to a deterministic form in both fuzzy possibility and necessity approaches. In our proposed MGA, we use probabilistic selection, which selects the best chromosomes from children and offspring sets at each generation. Bi-part mating pool strategy-based crossover keeps better diversity and good fitness values when making offsprings than the ordinary parent selection. At each iteration, the best population is collected from the union of populations before crossover and after mutation and sent to the next iteration, which speeds up the procedure. In most cases, our proposed MGA algorithm takes lesser time than BBEA to solve ICRSPs. Also, in many cases, MGA yields better results than BBEA, though sometimes it may take slightly more runtime, resulting in a better solution. This problem can also be formulated in different imprecise environments such as rough, random, fuzzy-random, fuzzy-rough, etc. It also can be extended to a multi- objective ICRSP by considering other objective functions, such as maximizing flow rate or minimizing the congestion rate in the case of telecommunication networks. Moreover, the proposed MGA can be used for optimization problems in other areas such as inventory control, transportation, supply chain, etc. The MGA can also be extended to the multi-objective MGA with better strategies. Author Contributions: Conceptualization, A. Mukherjee; methodology, A. Mukherjee; validation, A. Mukherjee; formal analysis, P. S. Barma; investigation, S. Das; resources, J. Dutta; writing—original draft preparation, A. Mukherjee; writing— review and editing, S. Das; visualization, S. Das; supervision, D. Pamučar; The author has read and agreed to the published version of the manuscript. Funding: This research received no external funding. Conflicts of Interest: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. References Baldacci. R., Dell’Amico. M. & González. J.S., (2007) The capacitated m-ring star problem, Operations Research 55 (6) 1147-1162. Baldacci. R. & Dell’Amico. (2010) M., Heuristic algorithms for the multi-depot ring star problem, European Journal of Operational Research 203 (1) 270-281. Baldacci. R., Hill. A., Hoshino. E.A. & Lim. A., (2017) Pricing Strategies for Capacitated Ring-Star Problems based on Dynamic Programming Algorithms, European Journal of Operational Research, 262 (3) 879-893. Barma, P.S., Dutta, J., Mukherjee, A., Kar, S., (2021) A Multi-Objective Ring Star Vehicle Routing Problem for Perishable Items, Journal of Ambient Intelligence and Humanized Computing, (13) 2355-2380. Imprecise Covering Ring Star Problem 17 Calvete, H.I., Galé, C., & J.A. Iranzo, (2013) An efficient evolutionary algorithm for the ring star problem. European Journal of Operational Research 231 22–33. Chakraborty, D., Jana, D. K., & Roy, T. K., (2015) A new approach to solve multi- objective multi-choice multi-item Atanassov's intuitionistic Fuzzy Transportation Problem using chance operator. Journal of Intelligence and Fuzzy Systems 28(2), 843- 865. Current, J.R., & Schilling, D.A., (1989), The covering salesman problem. Transportation Science, 23(3) 208-213. Dias, T.C.S., de Sousa Filho, G.F., Macambira, E.M., Cabral, L.A.F., & Fampa, M.H.C., (2006) An efficient heuristic for the ring star problem, in: C. Alvarez, M. Serna (Eds.), Experimental Algorithms, Lecture Notes in Computer Science, Springer Verlag, pp. 24- 35 (No. 4007). Golden, B.L., Naji-Azimi, Z., Raghavan, S., Salari, M., & Toth, P. (2012), The generalized covering salesman problem. INFORMS Journal on Computing, 24(4), 34-553. Helsgaun, K., (2000) Effective implementation of the Lin-Kerninghan traveling salesman heuristic, European Journal of Operational Research 126 106–130. Kedad-Sidhoum, S. & Nguyen, V.H., (2010) An exact algorithm for solving the ring star problem, Optimization 59 (1) 125-140. Kundu, P., Kar, M. B., Kar, S., Pal, T. & Maiti, M., (2015) A solid transportation model with product blending and parameters as rough variables, Soft Computing, , 1-10. Labbé, M., Laporte, G., Rodríguez Martín, I., & Salazar González, J.J., (1999) The median cycle problem, Working paper, CRT-99-29, Université de Montréal. Labbé , M. Laporte, G., Rodríguez Martín, I., & Salazar González, J.J., (2004) The ring star problem: Polyhedral analysis and exact algorithm, Networks 43 (3) 177-189. Lan, G. & DePuy, G. W., (2006) On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the Set Covering Problem, Computers & Industrial Engineering 51, 362-374. Liu, Y. H., (2010) Different initial solution generators in genetic algorithms for solving the probabilistic travelling salesman problem, Applied Mathematics and Computation, 216, 125-137. Moreno J.A., Moreno Pérez, PJ.A., Moreno Vega, J.M., & Rodríguez Martín, I., (2003) Variable neighborhood tabu search and its application to the median cycle problem, European Journal of Operational Research 151 (2) 365-378. Mukherjee, A., Panigrahi, G., & Kar, S., (2019) Constrained covering solid travelling salesman problems in uncertain environment, J Ambient Intell Human Comput. 10, 125-141. Mukherjee, A., Barma, P.S., Dutta, J., Panigrahi, G., Kar, S., & Maiti, M., (2019) A Modified Discrete Antlion Optimizer for the Ring Star Problem with Secondary Sub-depots, Neural Computing and Applications 32, 8143-8156. Mukherjee, A., Barma, P.S., Dutta, J., Panigrahi, G., Kar, S., & Maiti, M., (2021) A Multi- objective Antlion Optimizer for the Ring Tree Problem with Secondary Sub-depots, Operational Research, https://doi.org/10.1007/s12351-021-00623-8 https://doi.org/10.1007/s12351-021-00623-8 Mukherjee et al./Decis. Mak. Appl. Manag. Eng. (2022) 18 Naji-Azimi, Z., Salari, Toth, P., (2012) An integer linear programming based heuristic for the capacitated m-ring-star problem, European Journal of Operational Research 217 (1), 17-25. Pramanik, S., Jana, D. K., Maiti, M., (2015) A fixed charge multi-objective solid transportation problem in random fuzzy environment, Journal of Intelligent and Fuzzy Systems, 28, 2643-2654. Salari, M., & Naji-Azimi, Z., (2012) An integer programming-based local search for the covering salesman problem, Computers & Operations Research, 39, 2594-2602. Salari, M., Reihaneh, M., & Sabbagh, M.S., (2015) Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem, Computers & Industrial Engineering 83, 244-251. Simonetti, L., Frota, Y., & de Souza C.C., (2011) The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm, Discrete Applied Mathematics 159 (16) 1901-1914. Sundar, K. & Rathinam, S. (2017) Multiple depot ring star problem: a polyhedral study and an exact algorithm, J Glob Optim 67: 527. https://doi.org/10.1007/s10898-016- 0431-7 TSPLIB : http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp Zadeh, L.A., (1994) Fuzzy logic and soft computing: Issues, contentions and perspectives, In Proceedings of IIZUKA94 Third international conference on fuzzy logic, neural nets and soft computing (Vols. 1-2). Iizuka, Japan Zhao, F., Sun, J., Li, S., & Liu., W, (2009) A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery, International Journal of Automation and Computing, 06(1), 97-102. © 2022 by the authors. Submitted for possible open access publication under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/). https://doi.org/10.1007/s10898-016-0431-7 https://doi.org/10.1007/s10898-016-0431-7 http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp