A novel hybrid algorithm for generalized traveling salesman problems in different environments

Vietnam Journal of Computer Science

Indadul Khan¹  Manas Kumar Maiti² 

[1] Department of Computer Science, Chandrakona Vidyasagar Mahavidyalaya;Department of Mathematics, Mahishadal Raj College;

关键词: Traveling salesmen problem;    Genetic algorithm;    Particle swarm optimization;    Swap sequence;    Swap operation;    K-Opt;   

DOI  :  10.1007/s40595-017-0099-z

来源: DOAJ

【 摘 要 】

Abstract A swap sequence-based particle swarm optimization (SSPSO) technique and genetic algorithm (GA) are used in tandem to develop a hybrid algorithm to solve generalized traveling salesman problem. Local search algorithm K-Opt is occasionally used to move any stagnant solution. Here, SSPSO is used to find the sequence of groups of a solution in which a tour to be made and cities from different groups of the sequence are selected using GA. The K-Opt algorithm (for $$K=3$$ K=3 ) is used periodically for a predefined number of iterations to improve the quality of the solutions. The algorithm is capable of solving the problem in crisp as well as in imprecise environment. For this purpose, a general fitness evaluation rule for the solutions is proposed. The efficiency of the algorithm is tested in crisp environment using different size benchmark problems available in TSPLIB. In crisp environment, the algorithm gives 100% success rate for problems up to considerably large sizes. Imprecise problems are generated from crisp problems randomly using a rule and are solved using the proposed approach. The obtained results are discussed. Moreover it is observed that the proposed algorithm finds multiple optimal paths, when they exist, both for the crisp problems and their fuzzy variations.

【 授权许可】

Unknown