Ants Show The Way To Manage Vehicles
Written by Alex Armstrong   
Monday, 27 July 2020

Before you start fantasizing about ants sitting round a table planning how to route vehicles I'd better tell you that its ant algorithms that are being charged with the task, not the real thing. Of course, these are still ant-inspired so the title is accurate.

ant2020

To be honest this is one of those "I'm not quite sure what to think" items. A research team at Aston University (UK) have tried to reduce emissions and time by optimizing delivery vehicle routing in cities and they have been successful with a claimed 50% reduction in emissions.

The novel part of the approach is the use of ant optimization. This is one of many biologically inspired algorithms that we often don't completely understand. I suppose you can see all ant, or any other swarm-based, algorithms as being descended from the full genetic algorithm - i.e. simulated evolution. Only in this case the simulation is real. The swarms evolve over time, allowing evolution to weed out methods that don't work and keeping methods that do.

The algorithm in this case, a meta-heuristic, is Ant Colony Optimization (ACO). In a pure ACO the ants blunder about and occasionally find food. By leaving pheromone trails, the ants slowly converge on a best route to find the best food. The characteristics of the algorithm depend on how quickly the simulated pheromone evaporates, forcing new routes to be explored. For example, the travelling salesman problem, which is similar to the routing problem, can be solved by allowing ants to explore the network, choosing cities with a probability that decreases with distance and picking routes the have high pheromone deposits. Having completed a journey, the ant then backtracks and deposits more pheromone - more if the journey was short and less if it was long. The pheromone evaporates at a steady rate.

The actual algorithm used is roughly to use ACO to route within small sub-networks and then using these to build a complete route. The way that the pheromone is deposited is also changed - just the first edge visited by each ant. If this is vague, or I have got it wrong, then blame the fact that the paper is behind a paywall - a shameful way to profit and restrict access to research paid for with public money.

The research is very noble and we would all agree that improving air quality is a good thing, but using electric vehicles for such deliveries would be even better than a 20% reduction of emissions. The publicity for the research makes a big deal out of the success, but says nothing about what more classical methods of optimization might achieve. 

ant2020

More Information

A hybrid ant colony optimisation technique for dynamic vehicle routing: https://link.springer.com/chapter/10.1007/978-3-540-24854-5_5 Paywalled.

Related Articles

Ants AI Challenge Winner Announced

Take the AI Ants Challenge

Kilobots Work Together

Artificial Ants       

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.

 

Banner


js1024 - How Much Awesomeness Can You Pack In Just 1K?
06/08/2020

js1024 is the continuation of the legendary js1k JavaScript golfing competition which ended last year and like its predecessor is planned to be an annual contest. The winners of the first one  ha [ ... ]



Fukuoka Ruby Award 2021 Prestigious Ruby Prize
20/07/2020

While most Rubyists are probably familiar with the Fukuoka Ruby Award there may be multi-linguists who could be tempted to join in a competition that asks you to use Ruby, possibly in conjunction [ ... ]


More News

 

graphics

 



 

Comments




or email your comment to: comments@i-programmer.info

More Information

 

Related Articles

 

 

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.

 

Banner


js1024 - How Much Awesomeness Can You Pack In Just 1K?
06/08/2020

js1024 is the continuation of the legendary js1k JavaScript golfing competition which ended last year and like its predecessor is planned to be an annual contest. The winners of the first one  ha [ ... ]



Fukuoka Ruby Award 2021 Prestigious Ruby Prize
20/07/2020

While most Rubyists are probably familiar with the Fukuoka Ruby Award there may be multi-linguists who could be tempted to join in a competition that asks you to use Ruby, possibly in conjunction [ ... ]


More News

 

graphics

 



 

Comments




or email your comment to: comments@i-programmer.info

Last Updated ( Monday, 27 July 2020 )