{"id":12349,"date":"2013-05-23T07:31:28","date_gmt":"2013-05-23T06:31:28","guid":{"rendered":"http:\/\/www.decidesoluciones.es\/colonia-de-hormigas-y-calculo-de-rutas-2\/"},"modified":"2020-03-27T13:20:36","modified_gmt":"2020-03-27T13:20:36","slug":"ant-colony-optimization-and-routing","status":"publish","type":"post","link":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/","title":{"rendered":"Ant Colony and Routing"},"content":{"rendered":"<p>As already mentioned in this <a title=\"Integer Linear Programming and Routing\" href=\"http:\/\/www.decidesoluciones.es\/en\/integer-linear-programming-and-routing\/\" target=\"_blank\" rel=\"noopener noreferrer\">blog<\/a>, integer linear programming is often not useful in the real world to find the optimal solution to routing problems.<\/p>\n<p>One of the most common metaheuristic techniques to solve this problem is known as Ant Colony Optimisation (ACO).<\/p>\n<p>The ant colony technique was introduced by Marco Dorigo in 1992, and it is based on ant behaviours when they leave the ant nest to look for food. Ants deposit pheromones wherever they go, so that whenever an ant leaves the nest looking for food, it has a higher probability of choosing trails covered by more ants earlier, in other words, trails with higher amounts of pheromones.<\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-953\" src=\"\" alt=\"\" width=\"482\" height=\"332\" \/><\/a><\/p>\n<p>The ant colony algorithm slightly modifies this behaviour, expecting each ant to calculate a complete route to deposit pheromones. This way, in each iteration of the algorithm, every ant will have to choose which unvisited node will be visited next, based on its position and the amount of pheromones deposited in the trails. Thus, the probability of an ant \u201ck\u201d choosing trail \u201cxy\u201d is:<\/p>\n<p><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-951\" src=\"\" alt=\"\" width=\"226\" height=\"55\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p>Where \u03c4(xy) is the amount of pheromone deposited in trail xy , \u03b7(xy) represents the appropriateness of choosing trail xy (generally defined as 1\/distance(xy)), \u03b1 represents a parameter that gives weight to the amount of pheromones deposited in each trail and \u03b2 represents the influence parameter of \u03b7(xy) .<\/p>\n<p>As shown with this metaheuristic technique, the convergence and advantage of the solution found is the parameter function to be chosen by the user which, in general, can be different for each problem.<\/p>\n<p>Once each ant has completed a route, that is, it has found a feasible solution, the amount of pheromones in each trail is update<\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-952\" src=\"\" alt=\"\" width=\"252\" height=\"59\" \/><\/a>Where \u03c4(xy) is the amount of pheromones deposited in trail xy, \u03c1 is a parameter showing pheromone evaporation in each trail and \u0394\u03c4(xy) represents pheromones deposited by each ant in the trails they have covered. Typically, the pheromones deposited by each ant in each trail is Q\/L(k) if they have transited the trail and 0 otherwise, where Q is a constant and L(k) represents the total space covered by the ant in its circuit.<\/p>\n<p>There are several differentiating characteristics of the algorithm, such as the number of ants or the number and position of the ant nests. Also common are extensions of the case presented:<\/p>\n<p><span style=\"color: #ff6633;\"><strong>Elitist Ant System (EAS):<\/strong><\/span> In each pheromone deposit, the total best solution found to date also deposits pheromones along its path.<br \/>\n<strong><span style=\"color: #ff6633;\">Max-Min Ant System (MMAS):<\/span><\/strong> There is a range in the amount of pheromone to be deposited [\u03c4min,\u03c4max], and only the best solution obtained in each iteration deposits pheromones. All the trails start with pheromone initialized to \u03c4max, and when it has evaporated and reaches the value \u03c4min, it is reinitialized to \u03c4max.<br \/>\n<strong><span style=\"color: #ff6633;\">Rank-based Ant System (ASrank):<\/span><\/strong> Solutions are classified by advantage, and the amount of pheromone deposited is proportional to that value, so that the ants that have found a better solution deposit a greater amount of pheromone in their trails.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>As already mentioned in this blog, integer linear programming is often not useful in the real world to find the optimal solution to routing problems.One of the most common metaheuristic techniques to solve this problem is known as Ant Colony Optimisation (ACO).<\/p>\n","protected":false},"author":11,"featured_media":24870,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[262],"tags":[],"class_list":["post-12349","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized","category-262","description-off"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.6 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Ant Colony and Routing - Decide<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Ant Colony and Routing - Decide\" \/>\n<meta property=\"og:description\" content=\"As already mentioned in this blog, integer linear programming is often not useful in the real world to find the optimal solution to routing problems.One of the most common metaheuristic techniques to solve this problem is known as Ant Colony Optimisation (ACO).\" \/>\n<meta property=\"og:url\" content=\"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/\" \/>\n<meta property=\"og:site_name\" content=\"Decide\" \/>\n<meta property=\"article:published_time\" content=\"2013-05-23T06:31:28+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-03-27T13:20:36+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/05\/colonia-hormigas_7534-56.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"626\" \/>\n\t<meta property=\"og:image:height\" content=\"447\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Daniel Herrero Giner\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@canaldecide\" \/>\n<meta name=\"twitter:site\" content=\"@canaldecide\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Daniel Herrero Giner\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/\"},\"author\":{\"name\":\"Daniel Herrero Giner\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#\\\/schema\\\/person\\\/aab1e32b3835b23bd112dbbe72a2a22c\"},\"headline\":\"Ant Colony and Routing\",\"datePublished\":\"2013-05-23T06:31:28+00:00\",\"dateModified\":\"2020-03-27T13:20:36+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/\"},\"wordCount\":502,\"image\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/decidesoluciones.es\\\/wp-content\\\/uploads\\\/2013\\\/05\\\/colonia-hormigas_7534-56.jpg\",\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/\",\"url\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/\",\"name\":\"Ant Colony and Routing - Decide\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/decidesoluciones.es\\\/wp-content\\\/uploads\\\/2013\\\/05\\\/colonia-hormigas_7534-56.jpg\",\"datePublished\":\"2013-05-23T06:31:28+00:00\",\"dateModified\":\"2020-03-27T13:20:36+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#\\\/schema\\\/person\\\/aab1e32b3835b23bd112dbbe72a2a22c\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/#primaryimage\",\"url\":\"https:\\\/\\\/decidesoluciones.es\\\/wp-content\\\/uploads\\\/2013\\\/05\\\/colonia-hormigas_7534-56.jpg\",\"contentUrl\":\"https:\\\/\\\/decidesoluciones.es\\\/wp-content\\\/uploads\\\/2013\\\/05\\\/colonia-hormigas_7534-56.jpg\",\"width\":626,\"height\":447,\"caption\":\"Colonia de Hormigas Y C\u00e1lculo de Rutas\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/ant-colony-optimization-and-routing\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Portada\",\"item\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/decide-2\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Ant Colony and Routing\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#website\",\"url\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/\",\"name\":\"Decide\",\"description\":\"Advanced Analytics. Smart Decisions\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#\\\/schema\\\/person\\\/aab1e32b3835b23bd112dbbe72a2a22c\",\"name\":\"Daniel Herrero Giner\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/2d528afe1ec8105be28735adc4227e384bbd4d5269fac945a44f4d7cd2e56531?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/2d528afe1ec8105be28735adc4227e384bbd4d5269fac945a44f4d7cd2e56531?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/2d528afe1ec8105be28735adc4227e384bbd4d5269fac945a44f4d7cd2e56531?s=96&d=mm&r=g\",\"caption\":\"Daniel Herrero Giner\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Ant Colony and Routing - Decide","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/","og_locale":"en_US","og_type":"article","og_title":"Ant Colony and Routing - Decide","og_description":"As already mentioned in this blog, integer linear programming is often not useful in the real world to find the optimal solution to routing problems.One of the most common metaheuristic techniques to solve this problem is known as Ant Colony Optimisation (ACO).","og_url":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/","og_site_name":"Decide","article_published_time":"2013-05-23T06:31:28+00:00","article_modified_time":"2020-03-27T13:20:36+00:00","og_image":[{"width":626,"height":447,"url":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/05\/colonia-hormigas_7534-56.jpg","type":"image\/jpeg"}],"author":"Daniel Herrero Giner","twitter_card":"summary_large_image","twitter_creator":"@canaldecide","twitter_site":"@canaldecide","twitter_misc":{"Written by":"Daniel Herrero Giner","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/#article","isPartOf":{"@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/"},"author":{"name":"Daniel Herrero Giner","@id":"https:\/\/decidesoluciones.es\/en\/#\/schema\/person\/aab1e32b3835b23bd112dbbe72a2a22c"},"headline":"Ant Colony and Routing","datePublished":"2013-05-23T06:31:28+00:00","dateModified":"2020-03-27T13:20:36+00:00","mainEntityOfPage":{"@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/"},"wordCount":502,"image":{"@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/#primaryimage"},"thumbnailUrl":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/05\/colonia-hormigas_7534-56.jpg","inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/","url":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/","name":"Ant Colony and Routing - Decide","isPartOf":{"@id":"https:\/\/decidesoluciones.es\/en\/#website"},"primaryImageOfPage":{"@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/#primaryimage"},"image":{"@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/#primaryimage"},"thumbnailUrl":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/05\/colonia-hormigas_7534-56.jpg","datePublished":"2013-05-23T06:31:28+00:00","dateModified":"2020-03-27T13:20:36+00:00","author":{"@id":"https:\/\/decidesoluciones.es\/en\/#\/schema\/person\/aab1e32b3835b23bd112dbbe72a2a22c"},"breadcrumb":{"@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/#primaryimage","url":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/05\/colonia-hormigas_7534-56.jpg","contentUrl":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/05\/colonia-hormigas_7534-56.jpg","width":626,"height":447,"caption":"Colonia de Hormigas Y C\u00e1lculo de Rutas"},{"@type":"BreadcrumbList","@id":"https:\/\/decidesoluciones.es\/en\/ant-colony-optimization-and-routing\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Portada","item":"https:\/\/decidesoluciones.es\/en\/decide-2\/"},{"@type":"ListItem","position":2,"name":"Ant Colony and Routing"}]},{"@type":"WebSite","@id":"https:\/\/decidesoluciones.es\/en\/#website","url":"https:\/\/decidesoluciones.es\/en\/","name":"Decide","description":"Advanced Analytics. Smart Decisions","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/decidesoluciones.es\/en\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/decidesoluciones.es\/en\/#\/schema\/person\/aab1e32b3835b23bd112dbbe72a2a22c","name":"Daniel Herrero Giner","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/2d528afe1ec8105be28735adc4227e384bbd4d5269fac945a44f4d7cd2e56531?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/2d528afe1ec8105be28735adc4227e384bbd4d5269fac945a44f4d7cd2e56531?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/2d528afe1ec8105be28735adc4227e384bbd4d5269fac945a44f4d7cd2e56531?s=96&d=mm&r=g","caption":"Daniel Herrero Giner"}}]}},"_links":{"self":[{"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/posts\/12349","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/users\/11"}],"replies":[{"embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/comments?post=12349"}],"version-history":[{"count":2,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/posts\/12349\/revisions"}],"predecessor-version":[{"id":21431,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/posts\/12349\/revisions\/21431"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/media\/24870"}],"wp:attachment":[{"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/media?parent=12349"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/categories?post=12349"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/tags?post=12349"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}