Dr Neil Urquhart N.Urquhart@napier.ac.uk
Lecturer
Solving Real-World Routing Problems using Evolutionary Algorithms and Multi-Agent-Systems.
Urquhart, Neil B.
Authors
Abstract
This thesis investigates the solving of routing problems using Evolutionary Algorithms (EAs). Routing problems are known to be hard and may possess complex search spaces. Evolutionary algorithms are potentially powerful tools for finding solutions within complex search spaces.
The problem investigated is the routing of deliveries to households within an urban environment; the most common instance of this problem is that of daily postal deliveries. A representation known as Street Based Routing (SBR) is presented. This is a problem representation that makes use of the real world groupings of streets and houses. This representation is an indirect problem representation
designed specifically for use with EAs. The SBR representation is incorporated within an EA and used to construct delivery routes around a variety of problem
instances. The EA based system is compared against a Travelling Salesman Problem (TSP) solver, and the results are presented. The EA based system produces
routes that are on average slightly longer than those produced by the TSP solver.
Real world problems may often involve the construction of a network of delivery routes that are subject to multiple hard and soft constraints. A Multi Agent System (MAS) based framework for building delivery networks is presented that
makes use of the SBR based EA presented earlier. Each agent within the system uses an EA to construct a single route. Agents may exchange work (via auctions
or by directly negotiated exchanges) allowing the optimisation of their route. It is demonstrated that this approach has much potential and is capable of constructing
delivery networks meeting set constraints, over a range of problem instances and constraint values.
Thesis Type | Thesis |
---|---|
Deposit Date | Jul 9, 2009 |
Peer Reviewed | Not Peer Reviewed |
Keywords | Computing; Evolutionary algorithms; Routing problems; Multiple Agent System; |
Public URL | http://researchrepository.napier.ac.uk/id/eprint/2748 |
Contract Date | Jul 9, 2009 |
Award Date | Feb 23, 2003 |
Files
Porteous251893.pdf
(36.6 Mb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc/4.0/
You might also like
State assignment for sequential circuits using multi-objective genetic algorithm
(2011)
Journal Article
Manipulation and optimization techniques for Boolean logic
(2010)
Journal Article
Optimization of MPRM functions using tabular techniques and genetic algorithms.
(2008)
Journal Article
Agent motion planning with GAs enhanced by memory models.
(2001)
Journal Article
Demo paper: AGADE - Scalability of ontology based agent simulations
(2016)
Presentation / Conference Contribution
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search