Your Cart

Your cart is empty

Home  >  Volume 35

Using Tabu Search Technique for Solving Travel Salesman by P. E. Amiolemhen and J. K. Okpowo (149-154)
Sale price: $5.00
Quantity:

Abstract

The travelling salesman problem (TSP) is a classical problem in discrete or combinatorial optimization and belongs to the NP-complete classes, which means that it may require an infeasible processing time to be solved by an exhaustive search method, and therefore less expensive heuristics in respect to the processing time are commonly used in order to obtain satisfactory solutions in short running time. 

This paper address the optimization of a Traveling Salesman Problem using the Tabu search heuristic, also implementing Tabu Search using Visual basic.Net programming language to optimize the Traveling Salesman problem. 

To test the performance of the proposed method, a Six-City symmetric TSP Problem is solved using the data collected for the city-city distances. The implementation of the proposed algorithm was done using the Visual Basic.Net programming language and the experimental results show that the proposed algorithm provides better compromise between CPU time and effectiveness among some recent algorithms for the TSP.

Keywords:Tabu Search; Travel salesman problem; Optimal tour distance

Nomenclature

dij Distance value between cities

TS Tabu Search

TSP-   Travelling salesman problem

aTSP Asymmetric travelling salesman problem

mTSP multi-travelling salesman problem

sTSP Symmetric travelling salesman problem

N^* (x) Neighbor solutions of x

n Number of nodes (cities)

xij Decision variable that indicates whether the path from city i to city jis 

x Current solution

x’ Improve current solution

x* Best solution

x_ij Cost of traveling route from city I to city j

z(x) summation of distance of solution x

z(x’) Summation of distance of  improved solution x

 z(x*) Summation of distance of best solution

Close
Loading...