A Study of Route Planning Algorithms for Travelling Salesman Problem

Travelling Salesman Problem (TSP) is a non-trivial NP-hard routing problem. Given a set of cities and distance between each pair of cities a salesman must find out the shortest tour that covers all the cities exactly once and returns to the starting city. For a large-scale graph it is time-consuming to generate all possible edges. Therefore it is challenging for real-life applications to generate the shortest tour in real-time. Additionally consider an example of a salesman visiting many points of interest (POIs) then the salesman must visit those POIs during opening hours to make sure the total time taken for completing the tour is the minimum. The wait-time at a POI and the Real-time traffic movement between two consecutive POIs must also be considered to evaluate journey time between the POIs. In summary a real-time algorithm for TSP is necessary which can generate the tour for many POIs considering real-time traffic flow opening hours busy hours wait-time etc. An android application has also been developed to find out optimal tours using multiple algorithms. A promising result is obtained by the Hilbert Space-Filling Curve algorithm.