Particle swarm optimization-based algorithms for TSP and generalized TSP. (English) Zbl 1187.90238
Summary: A novel particle swarm optimization (PSO)-based algorithm for the traveling salesman problem (TSP) is presented. An uncertain searching strategy and a crossover eliminated technique are used to accelerate the convergence speed. Compared with the existing algorithms for solving TSP using swarm intelligence, it has been shown that the size of the solved problems could be increased by using the proposed algorithm. Another PSO-based algorithm is proposed and applied to solve the generalized traveling salesman problem by employing the generalized chromosome. Two local search techniques are used to speed up the convergence. Numerical results show the effectiveness of the proposed algorithms.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
swap operatorSoftware:
TSPLIBReferences:
| [1] | Kennedy, J.; Eberhart, R. C., Particle swarm optimization, (Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia, vol. 4 (1995), IEEE Service Center: IEEE Service Center Piscataway, NJ), 1942-1948 |
| [2] | Angeline, P. J., Evolutionary optimization versus particle swarm optimization: philosophy and performance differences, Evolutionary Programming, 7, 601-610 (1998) |
| [3] | Clerc, M.; Kennedy, J., The particle swarm-explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 6, 58-73 (2002) |
| [4] | Trelea, I. C., The particle swarm optimization algorithm: convergence analysis and parameter selection, Information Processing Letters, 85, 317-325 (2003) · Zbl 1156.90463 |
| [5] | Chang, J. F.; Chu, S. C.; Roddick, J. F.; Pan, J. S., A parallel particle swarm optimization algorithm with communication strategies, Journal of Information Science and Engineering, 4, 21, 809-818 (2005) |
| [6] | J. Kennedy, R.C. Eberhart, Discrete binary version of the particle swarm algorithm, in: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, vol. 5, Orlando, Florida, USA, 1997, pp. 4104-4108; J. Kennedy, R.C. Eberhart, Discrete binary version of the particle swarm algorithm, in: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, vol. 5, Orlando, Florida, USA, 1997, pp. 4104-4108 |
| [7] | Clerc, M., (Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem New Optimization Techniques in Engineering (2004), Springer), 219-239 · Zbl 1139.90415 |
| [8] | Bellman, R. E., Dynamic programming treatment of the traveling salesman problem, Journal of the ACM, 9, 61-63 (1962) · Zbl 0106.14102 |
| [9] | Bellmore, M.; Nemhauser, G. L., The traveling salesman problem: a survey, Operations Research, 16, 538-558 (1968) · Zbl 0213.44604 |
| [10] | Goldberg, D. E., Messy genetic algorithms: motivation, analysis, and first results, Complex Systems, 3, 493-530 (1989) · Zbl 0727.68097 |
| [11] | Ausiello, G.; Demange, M.; Laura, L.; Paschos, V., Algorithms for the on-line quota traveling salesman problem, Information Process Letters, 92, 89-94 (2004) · Zbl 1178.90282 |
| [12] | Munakata, T.; Nakamura, Y., Temperature control for simulated annealing, Physical Review E, 64, 046127 (2001) |
| [13] | Fomin, F. V.; Lingas, A., Approximation algorithms for time-dependent orienteering, Information Process Letters, 83, 57-62 (2002) · Zbl 1043.90076 |
| [14] | Huang, L.; Zhou, C. G.; Wang, K. P., Hybrid ant colony algorithm for traveling salesman problem, Progress in Natural Science, 4, 13, 295-299 (2003) · Zbl 1155.90442 |
| [15] | Clerc, M., Discrete particle swarm optimization illustrated by the traveling salesman problem (2000) · Zbl 1139.90415 |
| [16] | Hendtlass, T., Preserving Diversity in Particle Swarm Optimization, (Lecture Notes in Computer Science, vol. 2718 (2003), Springer), 4104-4108 |
| [17] | Wang, K. P.; Huang, L.; Zhou, C. G.; Pang, W., Particle swarm optimization for traveling salesman problem, International Conference on Machine Learning and Cybernetics, 3, 1583-1585 (2003) |
| [18] | Henry-Labordere, A. L., The record balancing problem: a dynamic programming solution of a generalized traveling salesman problem, RIRO B, 2, 43-49 (1969) · Zbl 0187.14002 |
| [19] | Saskena, J. P., Mathematical model for scheduling clients through welfare agencies, CORS J., 8, 185-200 (1970) · Zbl 0211.52002 |
| [20] | Srivastava, S. S.; Kumar, S.; Garg, R. C.; Sen, P., Generalized traveling salesman problem through \(n\) sets of nodes, CORS J., 7, 97-101 (1969) · Zbl 0174.51305 |
| [21] | Lien, Y. N.; Ma, E.; Wah, B. W.-S., Transformation of the generalized traveling-salesman problem into the standard traveling-salesman problem, Information Sciences, 74, 177-189 (1993) · Zbl 0790.90073 |
| [22] | Fischetti, M.; Salazar, J. J.; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Operations Research, 45, 378-394 (1997) · Zbl 0893.90164 |
| [23] | Wu, C. G.; Liang, Y. C.; Lee, H. P.; Lu, C., A generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for machining, Physical Review E, 70 (2004), 016701-1-13 |
| [24] | Reinelt, G., TSPLIB—A traveling salesman problem library, ORSA Journal on Computing, 3, 4, 376-384 (1991) · Zbl 0775.90293 |
| [25] | Laporte, G.; Asef-vaziri, A.; Sriskandarajah, C., Some applications of the generalized traveling salesman problem, Journal of the Operational Research Society, 47, 1461-1467 (1996) · Zbl 0873.90104 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
