Computational Numerical Solution for Traveling Salesman Problem

Abstract

This paper examined and analysed the desire of Traveling Salesman Problem (TSP) to find the cheapest way of visiting all given set of cities and returning to the starting point.     We presented a unique decomposition approach model for TSP in which the requirements and features of practical application in communication network, road transportation and supply chains are put into consideration.  We used a Mathematical Modeling solution with the application of Ant Colony Search Algorithm (ACSA) approach for result computation.

In our approach, different Agents were created for difference purposes.   Information agent gathered information about best tour and detected the solution agent that arrived at a given point with information message containing details of where the solution agent has come from as well as best tour cost.  The place ant performs local pheromone decay on the relevant links.   This help to avoid random visit to irrelevant edges and allows the place ant to calculate the cost of tour of all place ants including the latest pheromone level on the links to each of the place ants. The solution agent uses available information to decide  which node to visit next and informs the place ant of  its decision to move to a given destination and update better tour  previously sampled while information about where to go next also obtained.       The place ant updates its pheromone value for that link using the equivalent of the algorithm for local pheromone update.    The cycle continues until solution agent arrives at its destination.

The main advantage of our approach is that it permits the use of mixed integer programming and combinatorial optimization techniques to compute real optimal routing path, solving the problem in practice by returning actual shortest route with its numerical value and not the best effort result as provided by some previous models and analytical methods.

The implementation was carried out using C# programming language.  Data used were generated and the performance evaluation of the model was carried out through simulation using Matlab 7.0.  The result shows that by considering all possible paths between a node as the source and another as the destination, all possible routes for a particular journey with shortest route in each case were generated.

Keywords: Ant Colony, Combinatorial Optimization, Mixed Integer Programming, Pheromone, Search Algorithm and Traveling Salesman.