TSP ejection chains. (English) Zbl 0883.90120
Summary: We identify ejection chain methods for the traveling salesman problem based on a special reference structure for generating constructions related to alternating paths. Computational tests show that the method performs very effectively, obtaining generally better solutions than improved versions of the Lin-Kernighan method within the same time frame. Our approach, which currently has a simple tabu-search guidance component at a local level, also has the potential to be combined in more advanced ways with metaheuristics such as genetic algorithms, simulated annealing and tabu-search.
MSC:
| 90C35 | Programming involving graphs or networks |
Software:
Tabu searchReferences:
| [1] | Applegate, D.; Bixby, R.; Chvatál, V.; Cook, W., Finding cuts in the TSP, (Preliminary Report, At&T Bell Labs (1994), Rice University, Rutgers University and Bellcore) |
| [2] | Berge, C., Theory of Graphs and its Applications (1962), Methuen: Methuen London · Zbl 0097.38903 |
| [3] | Dorndorf, U.; Pesch, E., Fast clustering algorithms, ORSA J. Comput., 6, 141-153 (1994) · Zbl 0820.90114 |
| [4] | Gendreau, M.; Hertz, A.; Laporte, G., New insertion and postoptimization procedures for the traveling salesman problem, Oper. Res., 40, 1086-1094 (1992) · Zbl 0767.90087 |
| [5] | Glover, F., Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem (1991), Graduate School of Business, University of Colorado: Graduate School of Business, University of Colorado Boulder |
| [6] | Glover, F., Ejection chains, reference structures and alternating path methods for the traveling salesman problem (1992), Graduate School of Business, University of Colorado: Graduate School of Business, University of Colorado Boulder |
| [7] | Glover, F.; Pesch, E., Ejection chains and graph-related applications (1995), Graduate School of Business, University of Colorado: Graduate School of Business, University of Colorado Boulder |
| [8] | Johnson, D. S., Local optimization and the traveling salesman problem, (Proceedings of the 17th Colloquim on Automata, Languages, and Programming (1990), Springer: Springer Berlin), 446-461 · Zbl 0766.90079 |
| [9] | Kelly, J. P.; Laguna, M.; Glover, F., A study of diversification strategies for the quadratic assignment problem, Comput. Oper. Res., 21, 885-893 (1994) · Zbl 0814.90060 |
| [10] | Kolen, A.; Pesch, E., Genetic local search in combinatorial optimization, Discrete Appl. Math., 48, 273-284 (1994) · Zbl 0794.90047 |
| [11] | Laguna, M.; Kelly, J.; Gonzales-Velarde, J. L.; Glover, F., Tabu search for the multilevel generalized assignment problem, (European J. Oper. Res. (1991), Graduate School of Business, University of Colorado: Graduate School of Business, University of Colorado Boulder), to appear |
| [12] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The traveling salesman problem (1985), Wiley: Wiley Chichester · Zbl 0563.90075 |
| [13] | Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling salesman problem, Oper. Res., 21, 498-516 (1973) · Zbl 0256.90038 |
| [14] | Mak, K.-T.; Morton, A. J., A modified Lin-Kernighan traveling-salesman heuristic, Oper. Res. Lett., 13, 127-132 (1993) · Zbl 0779.90076 |
| [15] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060 |
| [16] | Pesch, E., Learning in Automated Manufacturing (1994), Physica: Physica Heidelberg |
| [17] | Rego, C.; Roucairol, C., An efficient implementation of ejection chain procedures for the vehicle routing problem, (Research Report RR-94/44 (1994), PRISM Laboratory, University of Versailles) |
| [18] | Reinelt, G., The Traveling Salesman (1994), Springer: Springer Berlin · Zbl 0825.90720 |
| [19] | Stewart, W. R.; Kelly, J. P.; Laguna, M., Solving vehicle routing problems using generalized assignments and tabu search (1994), Graduate School of Business, University of Colorado: Graduate School of Business, University of Colorado Boulder |
| [20] | Ulder, N.; Aarts, E. H.L.; Bandelt, H.-J.; van Laarhoven, P. J.M.; Pesch, E., Genetic local search algorithms for the traveling salesman problem, Lecture Notes in Computer Science, Vol. 496, 109-116 (1991) |
| [21] | Xu, J.; Kelly, J. P., A robust network flow-based tabu search approach for the vehicle routing problem (1995), Graduate School of Business, University of Colorado: Graduate School of Business, University of Colorado Boulder |
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.
