×

zbMATH — the first resource for mathematics

An interactive simulation and analysis software for solving TSP using ant colony optimization algorithms. (English) Zbl 1161.65334
Summary: The traveling salesman problem (TSP) is one of the extensively studied combinatorial optimization problems and tries to find the shortest route for salesperson which visits each given city precisely once. Ant colony optimization (ACO) algorithms have been used to solve many optimization problems in various fields of engineering. In this paper, a web-based simulation and analysis software (TSPAntSim) is developed for solving TSP using ACO algorithms with local search heuristics. Algorithms are tested on benchmark problems from TSPLIB and test results are presented. Importance of TSPAntSim providing also interactive visualization with real-time analysis support for researchers studying on optimization and people who have problems in form of TSP is discussed.

MSC:
65K05 Numerical mathematical programming methods
90C27 Combinatorial optimization
90B06 Transportation, logistics and supply chain management
90C15 Stochastic programming
Software:
TSPAntSim; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Kureichik, V. V.; Kureichik, V. M.: A genetic algorithm for finding a salesman’s route, J comput syst sci int 45, No. 1, 89-95 (2006) · Zbl 1260.90142
[2] Goldberg, D. E.: Genetic algorithms in search, optimization and machine learning, (1989) · Zbl 0721.68056
[3] Laarhoven, P. V.; Aarts, E. H. L.: Simulated annealing: theory and applications, (1987) · Zbl 0643.65028
[4] Fiechter, L.: A parallel tabu search algorithm for large traveling salesman problems, Dis appl math combinat operat res comput sci 51, 243-267 (1994) · Zbl 0938.68942 · doi:10.1016/0166-218X(92)00033-I
[5] Dorigo M, Maniezzo V, Colorni A. Positive feedback as a search strategy. Technical report, Dipartimento di Elettronica, Politecnico di Milano; 1991. · Zbl 0825.90549
[6] Dorigo, M.; Maniezzo, V.; Colorni, A.: The ant system: optimization by a colony of cooperating agents, IEEE trans syst man cyber part-B 26, 29-41 (1996)
[7] Dorigo, M.; Gambardella, L. M.: Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE trans evol comput 1, 53-66 (1997)
[8] Stützle, T.; Dorigo, M.: A short convergence proof for a class of ant colony optimization algorithms, IEEE trans evol comput 6, No. 4, 358-365 (2002)
[9] Jin, H. D.; Leung, K. S.; Wong, M. L.; Xu, Z. B.: An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem, IEEE trans syst man cyber part-B 33, No. 6, 877-887 (2003)
[10] Applegate, D.; Bixby, R.; Chvátal, V.; Cook, W.: On the solution of traveling salesman problems, Documenta math proc int cogr math 3, 645-656 (1998) · Zbl 0904.90165 · emis:journals/DMJDMV/xvol-icm/17/17.html
[11] Baraglia, R.; Hidalgo, J. I.; Perego, R.: A hybrid heuristic for the traveling salesman problem, IEEE trans evol comput 5, 613-622 (2001) · Zbl 0978.68567
[12] Padberg, M.; Rinaldi, G.: Optimization of a 532-city symmetric genetic traveling salesman problem by branch and cut, Oper res lett 6, No. 1, 1-7 (1987) · Zbl 0618.90082 · doi:10.1016/0167-6377(87)90002-2
[13] Kuan, S. N.; Ong, H. L.; Ng, K. M.: Solving the feeder bus network design problem by genetic algorithms and ant colony optimization, Adv eng software 37, No. 6, 351-359 (2006)
[14] Coelho, L. D. S.; Mariani, V. C.: Use of chaotic sequences in a biologically inspired algorithm for engineering design optimization, Expert syst appl 34, No. 3, 1905-1913 (2008)
[15] Foong, W. K.; Simpson, A. R.; Maier, H. R.: Ant colony optimization for power plant maintenance scheduling optimization – a five-station hydropower system, Ann oper res 159, No. 1, 433-450 (2008) · Zbl 1151.90406 · doi:10.1007/s10479-007-0277-y
[16] Shelokar, P. S.; Jayaraman, V. K.; Kulkarni, B. D.: An ant colony classifier system: application to some process engineering problems, Comput chem eng 28, No. 9, 1577-1584 (2004)
[17] Samrout, M.; Kouta, R.; Yalaoui, F.: Parameter’s setting of the ant colony algorithm applied in preventive maintenance optimization, J int manuf 18, No. 6, 663-677 (2007)
[18] Liao, Y. H.; Sun, C. T.: An educational genetic algorithms learning tool, IEEE trans education 44, 20 (2001)
[19] Collins, T. D.: Applying software visualization technology to support the use of evolutionary algorithms, J visual languages comput 14, 123-150 (2003)
[20] Kollat, J. B.; Reed, P.: A framework for visually interactive decision-making and design using evolutionary multi-objective optimization (VIDEO), Environ modell software 22, 1691-1704 (2007)
[21] Ringwood, J. V.; Galvin, G.: Computer-aided learning in artificial neural networks, IEEE trans education 45, 380-387 (2002)
[22] Manic M, Wilamowsky B, Malinowsky A. Internet based neural network simulation tool. In: Proceeding of the IECON’02, vol. 4; 2002. p. 2870 – 4.
[23] Ramı&acute, J. A.; Rez; Guimaraes, F. G.; Campelo, F.; Pereira, E. C.; Barros, P. H. L.; Takahashi, R. H. C.: Optimise: a computational environment for teaching optimization in electrical engineering, IEEE trans magn 40, 695-698 (2004)
[24] Reiners, T.; Vob, T.: Teaching meta-heuristics within virtual learning environments, Int trans oper res 11, 225-238 (2004) · Zbl 1069.90064 · doi:10.1111/j.1475-3995.2004.00454.x
[25] Foulloy, L.; Boukezzoula, R.; Galichet, S.: An educational tool for fuzzy control, IEEE trans fuzzy syst 14, 217-221 (2006)
[26] Effective Interactive AI Resources Workshop. IJCAI; 2001.
[27] Symposium on Improving Instruction of Introductory AI. AAAI; 1994.
[28] Dorigo M. Ottimizzazione, Apprendimento Automatico, ed Algoritmi Basati su Metafora Naturale. Ph.D. thesis, Politecnico di Milano; 1992.
[29] Dorigo, M.; Di Caro, G.: Ant colony optimization: a new meta-heuristic, Proceedings of the congress on evolutionary computation 2, 1470-1477 (1999)
[30] Dorigo M, Birattari M, Stützle T. Ant colony optimization: artificial ants as a computational intelligence technique. IEEE Comput Intell Mag; 2006. p. 28 – 38.
[31] Costa, Hertz A.: Ants can colour graphs, J oper res soc 48, 295-305 (1997) · Zbl 0890.90174
[32] Leguizamón G, Michalewicz Z. A new version of ant system for subset problems. In: Proceeding of the CEC’99; 1999. p. 1459 – 64.
[33] Solnon: Ant can solve constraint satisfaction problems, IEEE trans evol comput 6, 347-357 (2002)
[34] Campos, L. M. D.; Fernández-Luna, J. M.; Gámez, J. A.; Puetra, J. M.: Ant colony optimization for learning Bayesian network, Int J approx reasoning 31, 291-311 (2002) · Zbl 1033.68091 · doi:10.1016/S0888-613X(02)00091-9
[35] Lessing L, Dumitrescu I, Stützle T. A comparison between ACO algorithms for the set covering problem. In: Proceeding of the ANTS’2004, ser. LNCS 3172; 2004. p. 1 – 12.
[36] Reimann, M.; Doerner, K.; Hartl, R. F.: D-ants: saving based ants divide and conquer the vehicle routing problem, Comput oper res 31, 237-255 (2004) · Zbl 1061.90024 · doi:10.1016/S0305-0548(03)00014-5
[37] Korb O, Stützle T, Exner TE. Application of ant colony optimization to structure-based drug design. In: Proceeding of the ANTS 2006, ser. LNCS 4150; 2006. p. 247 – 58.
[38] Grassé, P. P.: La reconstruction dun id et LES coordinations interindividuelles chez bellicosimetes natalensis et cubitemes sp. La théorie de la stigmerie: essai d’inrprétation du comportement des termites constructeurs, Insectes sociaux 6, 41-81 (1959)
[39] Lin, S.: Computer solutions for the traveling salesman problem, Bell syst J 44, 2245-2269 (1965) · Zbl 0136.14705
[40] Lin, S.; Kernighan, B. W.: An effective heuristic algorithm for the travelling salesman problem, Oper res 21, 498-516 (1973) · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[41] Dorigo, M.; Gambardella, L. M.: Ant colonies for the traveling salesman problem, Bio syst 43, 73-81 (1997)
[42] Bullnheimer; Hartl, R. F.; Strauss, C.: A new ranked-based version of the ant system: a computational study, Central eur J oper res 7, 25-38 (1999) · Zbl 0941.90063
[43] Cordon O, Viana IF, Moreno L. New ACO model integrating evolutionary computation concepts: the best-worst ant system. In: Proceeding of the ANTS 2000, Brussels; 2000. p. 22 – 9.
[44] Stützle, T.; Hoos, H. H.: MAX – MIN ant system, Future generation comput syst 16, 889-914 (2000)
[45] Shtovba, S. D.: Ant algorithms: theory and applications, Program comput software 31, 167-178 (2005) · Zbl 1120.90051 · doi:10.1007/s11086-005-0029-1
[46] Bentley, J. L.: Fast algorithms for geometric traveling salesman problems, ORSA J comput 4, 387-411 (1992) · Zbl 0758.90071 · doi:10.1287/ijoc.4.4.387
[47] Johnson, D. S.; Mcgeoch, L. A.: The traveling salesman problem: a case study in local optimization, Local search in combinatorial optimization (1995)
[48] Bonabeau, E.; Dorigo, M.; Theraulaz, G.: Swarm intelligence from natural to artificial systems, (1999) · Zbl 1003.68123
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.