A random-permutation based GA for generalized traveling salesman problem in imprecise environments
Tóm tắt
A random-permutation technique and the features of the genetic algorithm (GA) are combined together to develop a novel heuristic for solving generalized travelling salesman problem. Here, the random-permutation technique is used to find the sequence of clusters of a probable solution in which a complete tour to be commenced. The features of GA are used to select the cities from different clusters of the sequence. The algorithm has the ability to solve the problems in both the crisp as well as in the imprecise environments. A fuzzy membership-based selection process is proposed to select a solution for the mating pool. A general comparison rule of the solutions is proposed to rank the potential solutions of the population in imprecise environments. In the crisp environment, the efficiency of the proposed approach is tested against a set of different benchmark test problems from GTSPLIB having sizes up to 226 cities with 26 clusters. It is observed from the experimental results that the algorithm produces 100% accurate results for all the benchmark test problems under consideration. Imprecise test problems are generated from different benchmark crisp test problems of TSPLIB and are used to test the algorithm in the imprecise environments. It is also observed from the experimental results that the proposed approach finds multiple optimal paths (i.e, more than one path), if exists, for the problems in the crisp as well as in the imprecise environments.
Tài liệu tham khảo
Ardalan Z, Karimi S, Poursabzi O, Naderi B (2015) A novel imperialist competitive algorithm for generalized traveling salesman problems. Appl Soft Comput 26:546–555
Bontouxa B, Artigues C, Feilletc D (2010) A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem. Comput Oper Res 37:1844–1852
Changdar C, Maiti MK, Maiti M (2013) A constrained solid TSP in fuzzy environment: two heuristic approaches. Iran J Fuzzy Syst 10(1):1–28
Changdar C, Mahapatra GS, Pal R (2014) An efficient genetic algorithm for multi-objective solid traveling salesman problem under fuzziness. Swarm Evol Comput 15:27–37
Dimitrijević V, Šarić Z (1997) An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs. Inf Sci 102:1–4
Fischetti M, Salazar JJ, Toth P (1997) A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper Res 45:378–394
Goldberg DE (1989) Genetic algorithms: search, optimization and machine learning. Addison Wesley, Reading
Guchhait P, Maiti MK, Maitia M (2013) Inventory model of a deteriorating item with price and credit linked fuzzy demand: a fuzzy differential equation approach. Opsearch 51(3):321–353
Gutin G, Karapetyan D (2010) A memetic algorithm for the generalized traveling salesman problem. Nat Comput 9:47–60
Helsgaun K (2015) Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun algorithm. Math Program Comput 7(3):269–287
Henry-Labordere AL (1969) The record balancing problem: a dynamic programming solution of a generalized traveling salesman problem. RAIRO Oper Res B2:43–49
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor
Khanra A, Maiti MK, Maiti M (2015) Profit maximization of TSP with uncertain parameters through a hybrid algorithm. In: Proceedings of the 4th international conference on Frontiers in Intelligent Computing: Theory and Applications (FICTA), advances in intelligent systems and computing. Springer, p 404
Khanra A, Maiti MK, Maiti M (2016) A hybrid heuristic algorithm for single and multi-objective imprecise traveling salesman problems. J Intell Fuzzy Syst 30:1987–2001
Khan I, Maiti MK (2018) A novel hybrid algorithm for generalized traveling salesman problems in different environments. Vietnam J Comput Sci 1(5):27–43
Laporte G, Nobert Y (1983) Generalized traveling salesman through n sets of nodes: an integer programming approach. INFOR 21:61–75
Laporte G, Asef-Vaziri A, Sriskandarajah C (1996) Some applications of the generalized traveling salesman problem. J Oper Res Soc 47:1461–1467
Liu B (2002) Theory and practice of uncertain programming. Physica, Heidelberg
Maity AK (2011) One machine multiple-product problem with production-inventory system under fuzzy inequality constraint. Appl Soft Comput 11:1549–1555
Maiti AK, Maiti MK, Maiti M (2009) Inventory model with stochastic lead-time and price dependent demand incorporating advance payment. Appl Math Model 33:2433–2443
Michalewicz Z (1992) Genetic algorithms + data structure = evolution programs. Springer, Berlin
Mondal M, Maity AK, Maiti MK, Maiti M (2013) A production-repairing inventory model with fuzzy rough coefficients under inflation and time value of money. Appl Math Model 37:3200–3215
Mohon C (2000) Optimization in fuzzy-stochastic environment and its importance in present day industrial scenario. In: Proceedings on mathematics and its application in industry and business. Narosa Publishing House, India
Noon CE, Bean JC (1991) A Lagrangian based approach for the asymmetric generalized traveling salesman problem. Oper Res 39:623–632
Noon CE, Bean JC (1993) An efficient transformation of the generalized traveling salesman problem. INFOR Inf Syst Oper Res 31(1):39–44
Pramanik P, Maiti MK, Maiti M (2017) Three level partial trade credit with promotional cost sharing. Appl Soft Comput 58:553–575
Reinelt G (1991) TSPLIB—a traveling salesman problem library. ORSA J Comput 3:376–84
Renaud J, Boctor FF (1998) An efficient composite heuristic for the symmetric generalized traveling salesman problem. Eur J Oper Res 108(3):571–584
Ren X, Wang X, Wang Z, Wu T (2020) Parallel DNA algorithms of generalized traveling salesman problem-based bioinspired computing model. Int J Comput Intell Syst 14:228–237
Smith SL, Imeson F (2017) GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem. Comput Oper Res 87:1–19
Saskena JP (1970) Mathematical model of scheduling clients through welfare agencies. J Can Oper Res Soc 8:185–200
Shi XH, Lianga YC, Leeb HP, Lub C, Wanga QX (2007) Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf Process Lett 103:69–176
Srivastava SS, Kumar S, Garg RC, Sen P (1969) Generalized traveling salesman problem through n sets of nodes. CORS J 7:97–101
Snyder LV, Daskin MS (2006) A random-key genetic algorithm for the generalized traveling salesman problem. Eur J Oper Res 174:38–53
Wu CG, Liang YC, Lee HP, Lu C (2004) A generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for machining. Phys Rev E 70:016701
Yang J, Shi X, Marchese M, Liang Y (2008) An ant colony optimization method for generalized TSP problem. Prog Nat Sci 18:1417–1422
Zadeh L (1965) Fuzzy sets. Inf Control 8:338–356
Zhao X, Zhu XP (2010) Innovative genetic algorithm for solving GTSP. In: Second international conference on modeling, simulation and visualization methods. College of Computer Science and Engineering, Guangdong Institute of Science and Technology