SMART: Solution Methods with Ants Running by Types
Ant algorithms are well-known metaheuristics which
have been widely used since two decades. In most of the literature,
an ant is a constructive heuristic able to build a solution from scratch.
However, other types of ant algorithms have recently emerged: the
discussion is thus not limited by the common framework of the
constructive ant algorithms. Generally, at each generation of an ant
algorithm, each ant builds a solution step by step by adding an
element to it. Each choice is based on the greedy force (also called the
visibility, the short term profit or the heuristic information) and the
trail system (central memory which collects historical information of
the search process). Usually, all the ants of the population have the
same characteristics and behaviors. In contrast in this paper, a new
type of ant metaheuristic is proposed, namely SMART (for Solution
Methods with Ants Running by Types). It relies on the use of different
population of ants, where each population has its own personality.
[1] N. Zufferey, “Metaheuristics: some Principles for an Efficient Design,”
Computer Technology and Applications, vol. 3 (6), pp. 446 – 462, 2012.
[2] M. Gendreau and J.-Y. Potvin, Handbook of Metaheuristics, ser.
International Series in Operations Research & Management Science.
Springer, 2010, vol. 146.
[3] M. Dorigo, “Optimization, learning and natural algorithms (in Italian),”
Ph.D. dissertation, Politecnico di Milano, Dipartimento di Elettronica,
Italy, 1992.
[4] C. Blum, “Ant colony optimization: Introduction and recent trends,”
Physics of Life Reviews, vol. 2(4), pp. 353–373, 2005.
[5] M. Dorigo, M. Birattari, and T. Stuetzle, “Ant colony optimization
– artificial ants as a computational intelligence technique,” IEEE
Computational Intelligence Magazine, vol. 1 (4), pp. 28–39, 2006.
[6] M. Dorigo and T. Stuetzle, Handbook of Metaheuristics. In F.
Glover and G. Kochenberger (Eds), 2003, vol. 57, ch. The Ant Colony
Optimization Metaheuristic: Algorithms, Applications, and Advances,
pp. 251–285.
[7] N. Zufferey, “Optimization by ant algorithms: Possible roles for an
individual ant,” Optimization Letters, vol. 6 (5), pp. 963 – 973, 2012.
[8] “Design and classification of ant metaheuristics,” in Proceedings of the
22nd Euromicro International Conference on Parallel, Distributed and
Network-Based Processing (PDP 2014), Turin, Italy, February 12 – 14
2014.
[9] L. Luyet, S. Varone, and N. Zufferey, “An Ant Algorithm for the Steiner
Tree Problem in Graphs,” Lecture Notes in Computer Science, vol. 4448,
pp. 42 – 51, 2007.
[10] N. Zufferey, J. Farres, and R. Glardon, “Ant metaheuristics with adapted
personalities for the vehicle routing problem,” in Proceedings of the
6th International Conference on Computational Logistics (ICCL 2015),
Delft, Nederland, September 23 – 25 2015.
[11] M. Plumettaz, D. Schindl, and N. Zufferey, “Ant local search and its
efficient adaptation to graph colouring,” Journal of the Operational
Research Society, vol. 61, pp. 819 – 826, 2010. [12] A. Hertz, D. Schindl, and N. Zufferey, “Lower bounding and tabu search
procedures for the frequency assignment problem with polarization
constraints,” 4OR, vol. 3 (2), pp. 139 – 161, 2005.
[13] J.-F. Cordeau, M. Gendreau, A. Hertz, G. Laporte, and J.-S. Sormany,
Logistics Systems: Design and Optimization. Springer, 2005, ch. New
Heuristics for the Vehicle Routing Problem, pp. 270–297.
[14] J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, and F. Semet,
“A Guide to Vehicle Routing Heuristics,” Journal of the Operational
Research Society, vol. 53 (5), pp. 512–522, 2002.
[15] J.-F. Cordeau and G. Laporte, Metaheuristic Optimization via Memory
and Evolution: Tabu Search and Scatter Search. Boston: Kluwer, 2004,
ch. Tabu search heuristics for the vehicle routing problem, pp. 145–163.
[16] M. Gendreau, G. Laporte, and J.-Y. Potvin, The Vehicle Routing
Problem. Philadelphia: SIAM Monographs on Discrete Mathematics
and Applications, 2002, ch. Metaheuristics for the VRP, pp. 129–154.
[17] B. L. Golden, E. A. Wasil, J. P. Kelly, and I.-M. Chao, Fleet Management
and Logistics. Boston: Kluwer, 1998, ch. Metaheuristics in vehicle
routing, pp. 33–56.
[18] G. Laporte and F. Semet, The Vehicle Routing Problem. Philadelphia:
SIAM Monographs on Discrete Mathematics and Applications, 2002,
ch. Classical heuristics for the capacitated VRP, pp. 109–128.
[19] S. Lin, “Computer solutions of the traveling salesman problem,” Bell
System Technical Journal, vol. 44, pp. 2245–2269, 1965.
[20] I. Or, “Traveling salesman-type combinatorial problems and their
relation to the logistics of regional blood banking,” Ph.D. dissertation,
Nortwester University, USA, 1976.
[21] N. Christofides, A. Mingozzi, and P. Toth, Combinatorial Optimization,
1979, ch. The vehicle routing problem, pp. 315 – 338.
[22] D. Mester and O. Braysy, “Active-guided evolution strategies for
large-scale capacitated vehicle routing problems,” Computers &
Operations Research, vol. 34 (10), pp. 2964 – 2975, 2007.
[1] N. Zufferey, “Metaheuristics: some Principles for an Efficient Design,”
Computer Technology and Applications, vol. 3 (6), pp. 446 – 462, 2012.
[2] M. Gendreau and J.-Y. Potvin, Handbook of Metaheuristics, ser.
International Series in Operations Research & Management Science.
Springer, 2010, vol. 146.
[3] M. Dorigo, “Optimization, learning and natural algorithms (in Italian),”
Ph.D. dissertation, Politecnico di Milano, Dipartimento di Elettronica,
Italy, 1992.
[4] C. Blum, “Ant colony optimization: Introduction and recent trends,”
Physics of Life Reviews, vol. 2(4), pp. 353–373, 2005.
[5] M. Dorigo, M. Birattari, and T. Stuetzle, “Ant colony optimization
– artificial ants as a computational intelligence technique,” IEEE
Computational Intelligence Magazine, vol. 1 (4), pp. 28–39, 2006.
[6] M. Dorigo and T. Stuetzle, Handbook of Metaheuristics. In F.
Glover and G. Kochenberger (Eds), 2003, vol. 57, ch. The Ant Colony
Optimization Metaheuristic: Algorithms, Applications, and Advances,
pp. 251–285.
[7] N. Zufferey, “Optimization by ant algorithms: Possible roles for an
individual ant,” Optimization Letters, vol. 6 (5), pp. 963 – 973, 2012.
[8] “Design and classification of ant metaheuristics,” in Proceedings of the
22nd Euromicro International Conference on Parallel, Distributed and
Network-Based Processing (PDP 2014), Turin, Italy, February 12 – 14
2014.
[9] L. Luyet, S. Varone, and N. Zufferey, “An Ant Algorithm for the Steiner
Tree Problem in Graphs,” Lecture Notes in Computer Science, vol. 4448,
pp. 42 – 51, 2007.
[10] N. Zufferey, J. Farres, and R. Glardon, “Ant metaheuristics with adapted
personalities for the vehicle routing problem,” in Proceedings of the
6th International Conference on Computational Logistics (ICCL 2015),
Delft, Nederland, September 23 – 25 2015.
[11] M. Plumettaz, D. Schindl, and N. Zufferey, “Ant local search and its
efficient adaptation to graph colouring,” Journal of the Operational
Research Society, vol. 61, pp. 819 – 826, 2010. [12] A. Hertz, D. Schindl, and N. Zufferey, “Lower bounding and tabu search
procedures for the frequency assignment problem with polarization
constraints,” 4OR, vol. 3 (2), pp. 139 – 161, 2005.
[13] J.-F. Cordeau, M. Gendreau, A. Hertz, G. Laporte, and J.-S. Sormany,
Logistics Systems: Design and Optimization. Springer, 2005, ch. New
Heuristics for the Vehicle Routing Problem, pp. 270–297.
[14] J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, and F. Semet,
“A Guide to Vehicle Routing Heuristics,” Journal of the Operational
Research Society, vol. 53 (5), pp. 512–522, 2002.
[15] J.-F. Cordeau and G. Laporte, Metaheuristic Optimization via Memory
and Evolution: Tabu Search and Scatter Search. Boston: Kluwer, 2004,
ch. Tabu search heuristics for the vehicle routing problem, pp. 145–163.
[16] M. Gendreau, G. Laporte, and J.-Y. Potvin, The Vehicle Routing
Problem. Philadelphia: SIAM Monographs on Discrete Mathematics
and Applications, 2002, ch. Metaheuristics for the VRP, pp. 129–154.
[17] B. L. Golden, E. A. Wasil, J. P. Kelly, and I.-M. Chao, Fleet Management
and Logistics. Boston: Kluwer, 1998, ch. Metaheuristics in vehicle
routing, pp. 33–56.
[18] G. Laporte and F. Semet, The Vehicle Routing Problem. Philadelphia:
SIAM Monographs on Discrete Mathematics and Applications, 2002,
ch. Classical heuristics for the capacitated VRP, pp. 109–128.
[19] S. Lin, “Computer solutions of the traveling salesman problem,” Bell
System Technical Journal, vol. 44, pp. 2245–2269, 1965.
[20] I. Or, “Traveling salesman-type combinatorial problems and their
relation to the logistics of regional blood banking,” Ph.D. dissertation,
Nortwester University, USA, 1976.
[21] N. Christofides, A. Mingozzi, and P. Toth, Combinatorial Optimization,
1979, ch. The vehicle routing problem, pp. 315 – 338.
[22] D. Mester and O. Braysy, “Active-guided evolution strategies for
large-scale capacitated vehicle routing problems,” Computers &
Operations Research, vol. 34 (10), pp. 2964 – 2975, 2007.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:71867", author = "Nicolas Zufferey", title = "SMART: Solution Methods with Ants Running by Types", abstract = "Ant algorithms are well-known metaheuristics which
have been widely used since two decades. In most of the literature,
an ant is a constructive heuristic able to build a solution from scratch.
However, other types of ant algorithms have recently emerged: the
discussion is thus not limited by the common framework of the
constructive ant algorithms. Generally, at each generation of an ant
algorithm, each ant builds a solution step by step by adding an
element to it. Each choice is based on the greedy force (also called the
visibility, the short term profit or the heuristic information) and the
trail system (central memory which collects historical information of
the search process). Usually, all the ants of the population have the
same characteristics and behaviors. In contrast in this paper, a new
type of ant metaheuristic is proposed, namely SMART (for Solution
Methods with Ants Running by Types). It relies on the use of different
population of ants, where each population has its own personality.", keywords = "Optimization, Metaheuristics, Ant Algorithms,
Evolutionary Procedures, Population-Based Methods.", volume = "10", number = "1", pages = "5-5", }
