This paper presents a heuristic method to find out a good tour for the asymmetric traveling salesman problem. At first, the proposed approach uses the normalized cost matrix to construct a tour by choosing the cities in such a way that it avoids having to go to very high cost (distance or time) cities later on. In order to improve further the size of this tour, it uses a developed tour improvement method. To evaluate its performance, the cost normalization algorithm for the solution of the linear assignment problem as well as the proposed method have been coded in C++ and many problems with up to 500 cities have been tested. The solved problems include a number of asymmetric random problems and all the benchmark asymmetric traveling salesman problems. The results indicate that the method returns a very good tour on all tested problems.
)