Memetic algorithm based on improved inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem. (English) Zbl 1231.90327
Summary: An improved inver-over operator is proposed to solve the Euclidean traveling salesman problem (TSP) problem. The Improved inver-over operator is tested on 14 different TSP examples selected from TSPLIB. The application of the improved inver-over operator gives much more effective results regarding to the best and average error values than the basic inver-over operator. Then an effective memetic algorithm based on improved inver-over operator and Lin-Kernighan local search is implemented. To speed up the convergence capability of the presented algorithm, a restart technique is employed. We evaluate the proposed algorithm based on standard TSP test problems and show that the proposed algorithm performs better than other memetic algorithm in terms of solution quality and computational effort.
MSC:
| 90C27 | Combinatorial optimization |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
Euclidean traveling salesman problem; inver-over operator; Lin-Kernighan local search; memetic algorithmSoftware:
TSPLIBReferences:
| [1] | Arora, S., Polynomial-time approximation schemes for Euclidean TSP and other geometric problems, J. ACM, 45, 753-782 (1998) · Zbl 1064.90566 |
| [2] | Gutin, G.; Punnen, A. P., The Traveling Salesman Problem and its Variations (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0996.00026 |
| [3] | Helsgaun, K., An effective implementation of the Lin-Kernighan traveling salesman heuristic, European J. Oper. Res., 126, 106-130 (2000) · Zbl 0969.90073 |
| [4] | Jeong, C. S.; Kim, M. H., Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections, Parallel Comput., 17, 221-228 (1991) |
| [5] | Chen, Y.; Zhang, P., Optimized annealing of traveling salesman problem from the \(n\) th-nearest-neighbor distribution, Physica A, 371, 627-632 (2006) |
| [6] | Li, J. Q.; Pan, Q. K.; Liang, Y. C., An effective hybrid Tabu search algorithm for multi-objective flexible job shop scheduling problems, Comput. Ind. Eng., 59, 647-662 (2010) |
| [7] | Fiechter, C.-N., A parallel Tabu search algorithm for large traveling salesman problems, Discrete Appl. Math., 51, 243-267 (1994) · Zbl 0938.68942 |
| [8] | Li, J. Q.; Pan, Q. K.; Suganthan, P. N.; Chua, T. J., A hybrid Tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem, Int. J. Adv. Manuf. Technol. (2010) |
| [9] | Guo, T.; Michalewicz, Z., Inver-over operator for the TSP, (Baeck, T.; Eiben, A.; Schoenauer, M.; Schwefel, H., Proceedings of the 5th Parallel Problem Solving from Nature. Proceedings of the 5th Parallel Problem Solving from Nature, Lecture Notes in Computer Science (1998), Springer-Verlag: Springer-Verlag Amsterdam), 803-812 |
| [10] | Louis, S. J.; Li, G., Case injected genetic algorithms for traveling salesman problems, Inform. Sci., 122, 201-225 (2000) · Zbl 1147.90419 |
| [11] | Albayrak, M.; Allahverdi, N., Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms, Expert Syst. Appl., 38, 1313-1320 (2011) |
| [12] | Mladenović, N.; Hansen, P., Variable neighborhood search, Comput. Oper. Res., 24, 1097-1100 (1997) · Zbl 0889.90119 |
| [13] | Applegate, D.; Cook, W.; Rohe, A., Chained Lin-Kernighan for large traveling salesman problems, INFORMS J. Comput., 15, 82-92 (2003) · Zbl 1238.90125 |
| [14] | Leung, K. S.; Jin, H. D.; Xu, Z. B., An expanding self-organizing neural network for the travelling salesman problem, Neurocomputing, 62, 267-292 (2004) |
| [15] | Créput, J. C.; Koukam, A., A Memetic neural network for the Euclidean traveling salesman problem, Neurocomputing, 72, 1250-1264 (2009) |
| [16] | Dorigo, M.; Gambardella, L. M., Ant colonies for the traveling salesman problem, Biosystems, 43, 73-81 (1997) |
| [17] | Tsai, C. F.; Tsai, C. W.; Tseng, C. C., A new hybrid heuristic approach for solving large traveling salesman problem, Inform. Sci., 166, 67-81 (2004) · Zbl 1076.90063 |
| [18] | Shi, X. H.; Liang, Y. C.; Lee, H. P.; Lu, C.; Wang, Q. X., Particle swarm optimization-based algorithms for TSP and generalized TSP, Inform. Process. Lett., 103, 169-176 (2007) · Zbl 1187.90238 |
| [19] | Clerc, M., Discrete particle swarm optimization, illustrated by the traveling salesman problem, (Onwubolu, G. C.; Babu, B. V., New Optimization Techniques in Engineering (2004), Springer: Springer Heidelberg), 219-239 · Zbl 1139.90415 |
| [20] | Geem, Z.; Tseng, C.; Park, Y., Harmony search for generalized orienteering problem: best touring in China, (Springer Lecture Notes in Computer Science, vol. 3412 (2005)), 741-750 |
| [21] | Onwubolu, G. C., Optimizing CNC drilling machine operations: traveling salesman problem-differential evolution approach, (Onwubolu, G. C.; Babu, B. V., New Optimization Techniques in Engineering (2004), Springer: Springer Heidelberg), 537-565 · Zbl 1078.90525 |
| [22] | Marinakis, Y.; Marinaki, M.; Dounias, G., Honey bees mating optimization algorithm for the Euclidean traveling salesman problem, Inform. Sci. (2010) |
| [23] | Merz, P.; Freisleben, B., Memetic algorithms for the traveling salesman problem, Complex Systems, 13, 297-345 (2001) · Zbl 1167.90693 |
| [24] | Padberg, M. W.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33, 60-100 (1991) · Zbl 0734.90060 |
| [25] | Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res., 12, 568-581 (1964) |
| [26] | Rosenkrantz, D. J.; Stearns, R. E.; Lewis, P. M., An analysis of several heuristics for the traveling salesman problem, SIAM J. Comput., 6, 563-581 (1977) · Zbl 0364.90104 |
| [27] | Bentley, J. L., Fast algorithm for geometric traveling salesman problems, ORSA J. Comput., 4, 387-441 (1992) · Zbl 0758.90071 |
| [28] | Gendreau, M.; Hertz, A.; Laporte, G., New insertion and post optimization procedures for the traveling salesman problem, Oper. Res., 40, 1086-1094 (1992) · Zbl 0767.90087 |
| [29] | Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling salesman problem, Oper. Res., 21, 498-516 (1973) · Zbl 0256.90038 |
| [30] | P. Merz, Memetic algorithms for combinatorial optimization problems: fitness landscapes and effective search strategies, Ph.D. Thesis, Department of Electrical Engineering and Computer Science, University of Siegen, Germany, 2000.; P. Merz, Memetic algorithms for combinatorial optimization problems: fitness landscapes and effective search strategies, Ph.D. Thesis, Department of Electrical Engineering and Computer Science, University of Siegen, Germany, 2000. |
| [31] | Moscato, P.; Cotta, C., A gentle introduction to Memetic algorithms, (Glower, F.; Kochenberger, G., Handbook of Metaheuristics (1999), Academic Publishers: Academic Publishers Dordrecht), 1-56 |
| [32] | (Hart, W. E.; Krasnogor, N.; Smith, J. E., Recent Advances in Memetic Algorithms. Recent Advances in Memetic Algorithms, Studies in Fuzziness and Soft Computing, vol. 166 (2004), Springer: Springer Berlin) · Zbl 1060.68101 |
| [33] | P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: towards Memetic algorithms, Technical Report, Caltech Concurrent Computation Program, C3P Report 826, California Institute of Technology, 1989.; P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: towards Memetic algorithms, Technical Report, Caltech Concurrent Computation Program, C3P Report 826, California Institute of Technology, 1989. |
| [34] | Dawkins, R., The Selfish Gene (1976), Oxford University Press: Oxford University Press Oxford |
| [35] | Moscato, P., A gentle introduction to Memetic algorithms, (Glover, F. W.; Kochenberger, G. A., Handbook of Metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 105-144 · Zbl 1107.90459 |
| [36] | Moscato, P., Memetic algorithms, (Pardalos, P. M.; Resende, M. G.C., Handbook of Applied Optimization (2002), Oxford University Press: Oxford University Press New York), 157-165 · Zbl 0996.90001 |
| [37] | Chiang, T. C.; Fu, L. C., A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop, Int. J. Prod. Res., 46, 6913-6931 (2008) |
| [38] | Bontoux, B.; Artigues, C.; Feillet, D., A Memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem, Comput. Oper. Res., 37, 1844-1852 (2010) · Zbl 1188.90263 |
| [39] | Voudouris, C.; Tsang, E., Guided local search and its application to the traveling salesman problem, European J. Oper. Res., 113, 469-499 (1999) · Zbl 0937.90094 |
| [40] | Christofides, N.; Eilon, S., Algorithms for large-scale traveling salesman problems, Oper. Res. Q., 23, 511-518 (1972) · Zbl 0248.90039 |
| [41] | Reinelt, G., TSPLIB—a traveling salesman problem library, ORSA J. Comput., 3, 376-384 (1991) · Zbl 0775.90293 |
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.
