nach oben

Erschienen in:

19.10.2022 | Application of soft computing

Application of proposed hybrid active genetic algorithm for optimization of traveling salesman problem

verfasst von: Rahul Jain, Kushal Pal Singh, Arvind Meena, Kun Bihari Rana, Makkhan Lal Meena, Govind Sharan Dangayach, Xiao-Zhi Gao

Erschienen in: Soft Computing | Ausgabe 8/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In the technological development era, the solution to various complex problems is uncertain, and more attention should be paid for changing certain conditions. Therefore, a precise solution to a complex problem is critical. The traveling salesman problem (TSP) is often fuse for an outbreak of a better solution. Inspired by the successful genetic algorithm (GA) applications, this study proposes a new approach to improve the convergence rate by incorporating a unique feature, namely 'sub-tour division'. The new method consists of multiple zones of TSPs (i.e., active and inactive), which are used to sort and group the critical region for finding the solutions. To illustrate the performance of the new approach, the traveling distance between various cities in India is considered as a problem. The simulation findings show that the new approach provides a more accurate and robust solution to a complex problem than alternative methods.

Vorheriger Artikel A flexible power point tracking algorithm based on adaptive lion swarm optimization for photovoltaic system

Nächster Artikel A practical study of active disturbance rejection control for rotary flexible joint robot manipulator

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abdoun O, Abouchabaka J (2012) A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem. Int J Comput Appl 31:49–57

Ahmed ZH (2014) The ordered clustered travelling salesman problem: A hybrid genetic algorithm. Sci World J Article ID. https://doi.org/10.1155/2014/258207CrossRef

Alipour MM, Razavi SN, Derakhshi MRF, Balafar MA (2018) A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem. Neural Comput Appl 30:2935–2951. https://doi.org/10.1007/s00521-017-2880-4CrossRef

Avsar B, Aliabadi DE (2015) Parallelized neural network system for solving Euclidean traveling salesman problem. Appl Soft Comput 34:862–873. https://doi.org/10.1016/j.asoc.2015.06.011CrossRef

Changdar C, Pal RK, Mahapatra GS (2017) A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment. Soft Comput 21:4661–4675. https://doi.org/10.1007/s00500-016-2075-4CrossRef

Chen SM, Chien CY (2011) Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Exp Syst Appl 38:14439–14450. https://doi.org/10.1016/j.eswa.2011.04.163CrossRef

Ding C, Cheng Y, He M (2007) Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs. Tsinghua Sci Technol 12:459–465. https://doi.org/10.1016/S1007-0214(07)70068-8MathSciNetCrossRefMATH

Feng X, Lau FC, Yu H (2013) A novel bio-inspired approach based on the behavior of mosquitoes. Inf Sci 233:87–108. https://doi.org/10.1016/j.ins.2012.12.053MathSciNetCrossRefMATH

Filip E, Otakar M (2011) The travelling salesman problem and its application in logistic practice. WSEAS Trans Bus Econ 8:163–173

Gülcü Ş, Mahi M, Baykan ÖK, Kodaz H (2018) A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem. Soft Comput 22:1669–1685. https://doi.org/10.1007/s00500-016-2432-3CrossRef

Gündüz M, Kiran MS, Özceylan E (2015) A hierarchic approach based on swarm intelligence to solve the traveling salesman problem. Turk J Elect Engg Comp Sci 23:103–117. https://doi.org/10.3906/elk-1210-147CrossRef

Hosseinabadi AR, Yazdanpanah M, Rostami AS (2012) A new search algorithm for solving symmetric traveling salesman problem based on gravity. World Appl Sci J 16:1387–1392

Hosseinabadi AR, Rostami NSH, Kardgar M, Mirkamali SS, Abraham A (2017) A new efficient approach for solving the capacitated vehicle routing problem using the gravitational emulation local search algorithm. Appl Math Model 49:663–679. https://doi.org/10.1016/j.apm.2017.02.042MathSciNetCrossRefMATH

Kaabi J, Harrath Y (2019) Permutation rules and genetic algorithm to solve the traveling salesman problem. Arab J Basic Appl Sci 26:283–291. https://doi.org/10.1080/25765299.2019.1615172CrossRef

Lin Y, Bian Z, Liu X (2016) Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing–tabu search algorithm to solve the symmetrical traveling salesman problem. Appl Soft Comput 49:937–952. https://doi.org/10.1016/j.asoc.2016.08.036CrossRef

Man KF, Tang KS, Kwong S (1996) Genetic algorithms: concepts and applications. IEEE Trans Ind Electron 43:519–534. https://doi.org/10.1109/41.538609CrossRef

Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J Comput 3:376–384. https://doi.org/10.1287/ijoc.3.4.376CrossRefMATH

Riazi A (2019) Genetic algorithm and a double-chromosome implementation to the traveling salesman problem. SN Appl Sci 1:1–7. https://doi.org/10.1007/s42452-019-1469-1CrossRef

Rostami AS, Mohanna F, Keshavarz H, Hosseinabadi AR (2015) Solving multiple traveling salesman problem using the gravitational emulation local search algorithm. Appl Math Inf Sci 9:699–709MathSciNet

Sena GA, Megherbi D, Isern G (2001) Implementation of a parallel genetic algorithm on a cluster of workstations: traveling salesman problem, a case study. Future Gener Comput Sys 17:477–488. https://doi.org/10.1016/S0167-739X(99)00134-XCrossRefMATH

Trigui S, Cheikhrouhou O, Koubaa A, Baroudi U, Youssef H (2017) FL-MTSP: a fuzzy logic approach to solve the multi-objective multiple traveling salesman problem for multi-robot systems. Soft Comput 21:7351–7362. https://doi.org/10.1007/s00500-016-2279-7CrossRef

Tsai HK, Yang JM, Tsai YF, Kao CY (2004) Some issues of designing genetic algorithms for traveling salesman problems. Soft Comput 8:689–697. https://doi.org/10.1007/s00500-003-0317-8CrossRefMATH

Tsai CW, Tseng SP, Chiang MC, Yang CS, Hong TP (2014) A high-performance genetic algorithm: using traveling salesman problem as a case. Sci World J. https://doi.org/10.1155/2014/178621CrossRef

Victer Paul P, Ganeshkumar C, Dhavachelvan P, Baskaran R (2020) A novel ODV crossover operator-based genetic algorithms for traveling salesman problem. Soft Comput 24:12855–12885. https://doi.org/10.1007/s00500-020-04712-2CrossRef

Wang ZG, Wong YS, Rahman M (2005) Development of a parallel optimization method based on genetic simulated annealing algorithm. Parallel Comput 31:839–857. https://doi.org/10.1016/j.parco.2005.03.006CrossRef

Xu X, Yuan H, Liptrott M, Trovati M (2018) Two phase heuristic algorithm for the multiple-travelling salesman problem. Soft Comput 22:6567–6581. https://doi.org/10.1007/s00500-017-2705-5CrossRef

Yong W (2015) Hybrid max–min ant system with four vertices and three lines inequality for traveling salesman problem. Soft Comput 19:585–596. https://doi.org/10.1007/s00500-014-1279-8CrossRef

Yusof R, Khalid M, Hui GT, Yusof SM, Othman MF (2011) Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm. Appl Soft Comput 11:5782–5792. https://doi.org/10.1016/j.asoc.2011.01.046CrossRef

Zhan SH, Lin J, Zhang ZJ, Zhong YW (2016) List-based simulated annealing algorithm for traveling salesman problem. Comput Intell Neurosci. https://doi.org/10.1155/2016/1712630CrossRef

Titel: Application of proposed hybrid active genetic algorithm for optimization of traveling salesman problem
verfasst von: Rahul Jain
Kushal Pal Singh
Arvind Meena
Kun Bihari Rana
Makkhan Lal Meena
Govind Sharan Dangayach
Xiao-Zhi Gao
Publikationsdatum: 19.10.2022
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 8/2023
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-022-07581-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 8/2023

SpanMTL: a span-based multi-table labeling for aspect-oriented fine-grained opinion extraction

Set-valued uncertain process: definition and some properties

An application of neutrosophic logic on an inventory model with two-level partial trade credit policy for time-dependent perishable products

An intelligent traffic detection approach for vehicles on highway using pattern recognition and deep learning

g-States on unital weak pseudo EMV-algebras

Metaheuristic techniques for the capacitated facility location problem with customer incompatibilities

Premium Partner