Abstract
A collaborative optimization algorithm under a control framework is developed for the asymmetric traveling salesman problem (ATSP). The collaborative approach is not just a simple combination of two methods, but a deep collaboration in a manner like the feedback control. A notable feature of the approach is to make use of the collaboration to reduce the search space while maintaining the optimality. Compared with the previous work of the reduction procedure by Carpaneto, Dell’Amico et al. (1995) we designed a tighter and more generalized reduction procedure to make the collaborative method more powerful. Computational experiments on benchmark problems are given to exemplify the approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blum, C., Dorigo, M.: The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 34(2), 1161–1172 (2004)
Carpaneto, G., Dell’Amico, M., et al.: Exact solution of large-scale, asymmetric traveling salesman problems. ACM Trans. Math. Softw. 21(4), 394–409 (1995)
Choi, I.-C., Kim, S.-I., et al.: A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem. Comput. Oper. Res. 30(5), 773–786 (2003)
Choi, J., Realff, M.J., et al.: An algorithmic framework for improving heuristic solutions Part I. A deterministic discount coupon traveling salesman problem Computers & Chemical Engineering 28(1): 1285-1296 (2004). Computers & Chemical Engineering 28(1), 1285–1296 (2004)
Dell’Amico, M., Toth, P.: Algorithms and codes for dense assignment problems: the state of the art. Discrete Applied Mathematics 100(1-2), 17–48 (2000)
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1(1), 53–66 (1997)
Fiechter, C.N.: A parallel tabu search algorithm for large traveling salesman problems. Discrete Appl. Math. 51(3), 243–267 (1994)
Fischetti, M., Toth, P.: A Polyhedral Approach to the Asymmetric Traveling Salesman Problem. Management Science 43(11), 1520–1536 (1997)
Glover, F., Gutin, G., et al.: Construction heuristics for the asymmetric TSP. European Journal of Operational Research 129(3), 555–568 (2001)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989)
John, D.L.: An improved solution to the traveling salesman problem with thousands of nodes. Commun. ACM 27(12), 1227–1236 (1984)
Jourdan, L., Basseur, M., et al.: Hybridizing exact methods and metaheuristics: A taxonomy. European Journal of Operational Research 199(3), 620–629 (2009)
Karp, R.M.: A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem. SIAM Journal on Computing 8(4), 561–573 (1979)
Laarhoven, P.J.v., Aarts, E.H.: Simulated Annealing: Theory and Applications. Mathematics and Its Applications. Springer, Heidelberg (1987)
Marco, D., Christian, B.: Ant colony optimization theory: a survey. Theor. Comput. Sci. 344(2-3), 243–278 (2005)
Miller, D.L., Pekny, J.F.: Exact Solution of Large Asymmetric Traveling Salesman Problems. Science 251(4995), 754–761 (1991)
Pan, C., Yang, G.K.: A method of solving a large-scale rolling batch scheduling problem in steel production using a variant of column generation. Comput. Ind. Eng. 56(1), 165–178 (2009)
Tang, L.X., Liu, J.Y., et al.: A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research 124(2), 267–282 (2000)
Turkensteen, M., Ghosh, D., et al.: Tolerance-based Branch and Bound algorithms for the ATSP. European Journal of Operational Research 189(3), 775–788 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bai, J., Zhu, J., Yang, GK., Pan, CC. (2011). Collaborative Optimization under a Control Framework for ATSP. In: Tan, Y., Shi, Y., Chai, Y., Wang, G. (eds) Advances in Swarm Intelligence. ICSI 2011. Lecture Notes in Computer Science, vol 6728. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21515-5_42
Download citation
DOI: https://doi.org/10.1007/978-3-642-21515-5_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21514-8
Online ISBN: 978-3-642-21515-5
eBook Packages: Computer ScienceComputer Science (R0)