Using an evolutionary algorithm to discover low CO2 tours within a Travelling Salesman Problem

Urquhart, N., Scott, C., Hart, E. (2010). Using an evolutionary algorithm to discover low CO2 tours within a Travelling Salesman Problem. In: al., C. De Chio et (Ed.) Evo Applications 2010, Part II, LNCS 6025, () ( ed.). (pp. 421-430). : . Springer-Verlag.


ISBN:
ISSN:

Abstract

This paper examines the issues surrounding the effects of using vehicle emissions as the fitness criteria when solving routing problems using evolutionary techniques. The case-study examined is that of the Travelling Salesman Problem (TSP) based upon the road network within
the City of Edinburgh, Scotland. A low cost path finding algorithm (A*) is used to build paths through the street network between delivery points. The EA is used to discover tours that utilise paths with low emissions characteristics. Two methods of estimating CO2 emissions are examined;
one that utilises a fuel consumption model and applies it to an estimated drive cycle and one that applies a simplistic CO2 calculation model that focuses on average speeds over street sections. The results of these two metrics are compared with each other and with results obtained using a
traditional distance metric.
[Read More]

Authors

Emma Hart
Director of CEC
e.hart@napier.ac.uk
+44 131 455 2783
Neil Urquhart
Lecturer
n.urquhart@napier.ac.uk
+44 131 455 2655
Catherine Scott
Research Student
c.scott@napier.ac.uk
+44 131 455

Areas of Expertise

Bio-inspired Computing
The Bio-Inspired Algorithms group within the Centre for Algorithms, Visualisation and Evolving Systems is a large and thriving group with interests in nature-inspired computing that include Evolutionary Computing, Hyper-Heuristics, Artificial Immune Systems and Swarm Intelligence.
Software Systems
The institute's expertise in software engineering encompasses the entire development lifecycle, and we focus on developing the approaches and tools to improve the engineering process of both emerging and widely used software systems.

Associated Projects