INSPIRING FUTURES

Solving Real-World Routing Problems using Evolutionary Algorithms and Multi-Agent-Systems.

Urquhart, Neil B (2003) Solving Real-World Routing Problems using Evolutionary Algorithms and Multi-Agent-Systems. PhD thesis, Napier University.

[img]
Preview
PDF
Available under License Creative Commons Attribution Non-commercial.

Download (34MB) | Preview

    Abstract/Description

    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.

    Item Type: Thesis (PhD)
    Uncontrolled Keywords: Computing; Evolutionary algorithms; Routing problems; Multiple Agent System;
    University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Computing
    Dewey Decimal Subjects: 000 Computer science, information & general works > 000 Computer science, knowledge & systems > 006 Special Computer Methods
    600 Technology > 650 Management & public relations > 658 General management
    Library of Congress Subjects: H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management
    Q Science > QA Mathematics > QA76 Computer software
    Item ID: 2748
    Depositing User: Dr. David A. Cumming
    Date Deposited: 09 Jul 2009 16:53
    Last Modified: 12 Jan 2011 04:50
    URI: http://researchrepository.napier.ac.uk/id/eprint/2748

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...

    Edinburgh Napier University is a registered Scottish charity. Registration number SC018373