| 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.
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.
More InformationA hybrid ant colony optimisation technique for dynamic vehicle routing: https://link.springer.com/chapter/10.1007/978-3-540-24854-5_5 Paywalled. Related ArticlesAnts AI Challenge Winner Announced 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. 
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.
Comments
or email your comment to: comments@i-programmer.info |
||||||
| Last Updated ( Monday, 27 July 2020 ) |
