The asymmetric travelling salesman problem (ATSP) is a generalised travelling salesman problem that the distances between a pair of cities may not be equal in opposite directions. This problem has a close relation with real-world problems in logistics and transportation. This paper aims to enhance performances of variable neighbourhood search (VNS) algorithm by introducing population-based approach (EVNS) and simulated annealing (SA) technique to the VNS algorithm. Benchmark ATSP instances available in TSP library (TSPLIB) are used to test the performances of the proposed algorithms. Experimental results show that the solution quality can be improved significantly when the population-based approach is applied and the worse solution is accepted with some probabilities which is a mechanism of SA technique. The proposed EVNS-SA algorithm has very good performances among the algorithms for solving ATSP available in literatures. Copyright © 2013 Inderscience Enterprises Ltd.