General Variable Neighborhood Search (GVNS) is shown to be a powerful and robust methodology for solving travelling salesman and vehicle routing problems. However, its efficient implementation may play a significant role in solving large size instances. In this paper we suggest new GVNS heuristic for solving Travelling salesman problem with time windows. It uses different set of neighborhoods, new feasibility