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.