In graph theory, the robustness of a network measures its resilience (in terms of connectivity) to either removal of network nodes or edges. Using algebraic connectivity is one of the best way to measure the robustness of a network. The higher algebraic connectivity means more robust network. The goal of this work is to improve the robustness of an existing air transportation network. It can be accomplished by adding edges (routes) to the network. However, due to limited budget and aircraft, the routes to be added have to be chosen carefully. The best routes to be added are the routes that will yield the highest algebraic connectivity when they were added to the network. This problem of choosing the best routes to be added is called flight routes addition. In this paper, the flight routes addition is solved using Tabu Search method with the algebraic connectivity component to choose two new lines to strengthening the robustness of the flight routes. We only consider the robustness and do not.