Danny Waite Undergraduate Dissertation 2016/17

Using A Bio-Inspired Algorithm to Solve Multiple Travelling Salesman Problems with Online Mapping Integration

Supervised by D.Walker

Abstract

The primary objective of this dissertation is to provide a Bio-Inspired Solution to the Multiple Travelling Salesman Problem (mTPS), with the secondary objective of allowing a user to input geographical locations. This resulting in the output of an optimal route, visiting each location once, and only once, returning to the depot node at specified intervals. This report outlines several Bio-Inspired Techniques that can be used to solve the TSP and mTSP, resulting in the decision to use an evolutionary technique; Genetic Algorithms, based on merits and external factors.

Following this an in depth discussion of the requirements, design and implementation of a Python based implementation is conducted, with the conclusion being multiple selection and optimisation techniques being implemented. Tournament Selection with various tournament sizes and Roulette Wheel Selection with different levels of elitism imposed were compared, with it being found that Roulette Wheel Selection with high levels of Elitism imposed produces superior results for the uniform depot visit frequency mTSP. Various parameters were also experimented with, and the impact of a Sub-Tour Optimisation technique being evaluated, with the result of this being a drastic increase in fitness.

As a result of this project, a Python programme that is capable of solving the mTSP, whilst interacting with Google Maps has been produced, which provides near optimal results on most test cases.