ABSTRAK
Masalah penambahan rute penerbangan merupakan masalah dalam memilih rute-rute terbaik untuk ditambahkan ke dalam suatu jaringan penerbangan yang sudah ada. Tujuan dari penambahan rute tersebut adalah untuk memperbaiki robustness dari jaringan yang sudah ada. Salah satu metode pengukuran yang paling baik untuk mengukur robustness suatu jaringan adalah konektivitas aljabar. Semakin tinggi konektivitas aljabar suatu jaringan berarti semakin robust jaringan tersebut. Oleh karena itu, rute-rute terbaik yang dipilih adalah rute-rute yang saat ditambahkan menghasilkan konektivitas aljabar yang paling tinggi. Pada skripsi ini, masalah penambahan rute penerbangan diselesaikan menggunakan metode Tabu Search. Selain itu, sensitivitas metode Tabu Search terhadap perbedaan solusi awal juga dianalisa dengan melakukan percobaan.

---

ABSTRACT
Flight routes addition problem is a problem of choosing the best routes to be added to an existing air transportation network. The purpose of the addition is to improve the network?s robustness. One of the best metric to measure robustness of a network is algebraic connectivity. Higher algebraic connectivity means more robust network. Therefore, the best routes to be added are the routes that will yield the highest algebraic connectivity when they were added to the network. In this ?skripsi?, the flight routes addition is solved using Tabu Search method. Furthermore, the sensitivity of Tabu Search method towards different initial solutions is analysed by conducting several trials.