vii
DAFTAR ISI LEMBAR PENGESAHAN……………………………………….……......…......i ABSTRACT……………………………………….……………….………..........ii ABSTRAKSI…………………………………………………….........................iii KATA PENGANTAR……………………………………….……….…….........iv DAFTAR ISI……………………………………………………………….........vii DAFTAR GAMBAR...……………………………………………………..….....x DAFTAR TABEL ……....………………………………………………….......xii DAFTAR RUMUS …………………………………………………….............xiii DAFTAR LAMPIRAN…………………………………………………….......xiv BAB I PENDAHULUAN ................................................................................... I.1
1.1
Latar Belakang Masalah .............................................................................. I.1
1.2
Rumusan Masalah ........................................................................................ I.2
1.3
Maksud dan Tujuan Penelitian .................................................................... I.2
1.4
Batasan Masalah .......................................................................................... I.2
1.5
Sistematika Penulisan .................................................................................. I.3
BAB II LANDASAN TEORI .......................................................................... II.1 2.1
Traveling Salesmen Problem ...................................................................... II.1
2.2
Metode Heuristik ........................................................................................ II.2
2.3
Hierarchical clustering ............................................................................... II.6
2.4
2.3.1
Agglomerative Hierarchical Clustering ....................................... II.8
2.3.2
Metode Single Linkage ................................................................. II.8
2.3.3
Metode Complete linkage ............................................................. II.8
MATLAB ................................................................................................... II.9
BAB III METODE PENELITIAN ................................................................ III.1 3.1
Definition of Research Problem ................................................................III.2
vii
viii
3.2
Data Definition ..........................................................................................III.2
3.3
Data Preparation and Pre pocessing ........................................................III.2
3.4
Heuristic Deveplopment ............................................................................III.3
3.5
Testing And Validation ..............................................................................III.3
3.6
Result Analysis ...........................................................................................III.3
3.7
Result Output .............................................................................................III.3
BAB IV PERANCANGAN ............................................................................. IV.1 4.1
Perancangan Program ............................................................................... IV.1
4.2
Hierarchical clustering............................................................................. IV.3
4.3
4.2.1
Agglomerative Hierarchical Clustering ..................................... IV.4
4.2.2
Metode Single Linkage ............................................................... IV.5
4.2.3
Metode Complete linkage ......................................................... IV.12
4.2.4
TSP dengan Metode Heuristik.................................................. IV.19
Perancangan Antarmuka ......................................................................... IV.22
BAB V IMPLEMENTASI DAN ANALISIS .................................................. V.1 5.1
5.2
5.3
Implementasi Program Simulasi ................................................................. V.1 5.1.1
Perangkat Keras ............................................................................ V.1
5.1.2
Perangkat Lunak ........................................................................... V.1
5.1.3
Implementasi Antar Muka ............................................................ V.2
Analisis Hasil Simulasi ............................................................................... V.4 5.2.1
Tour Distance ............................................................................... V.4
5.2.2
Running Time.............................................................................. V.11
5.2.3
Jumlah Klaster ............................................................................ V.14
Testing Dan Validasi ................................................................................ V.16
............................................................................................................................ V.21 viii
ix
BAB VI KESIMPULAN DAN SARAN......................................................... VI.1 6.1
Kesimpulan ............................................................................................... VI.1
6.2
Saran ......................................................................................................... VI.2
DAFTAR PUSTAKA LAMPIRAN
ix
x
DAFTAR GAMBAR
Gambar II-1 Ilustrasi Clarke and Wright Tour Extension .................................. II.5 Gambar II-2 Dendrogram..................................................................................... II.7 Gambar III-1 General Research Methodology ................................................... III.1 Gambar IV-1 flowchart program ....................................................................... IV.1 Gambar IV-2 Dendogram Single Linkage untuk jarak antara 10 objek .......... IV.12 Gambar IV-3 Dendrogram Complete linkage Untuk Jarak 10 Objek.............. IV.19 Gambar IV-10 Prototype Antar Muka ............................................................. IV.23 Gambar V-1 Antarmuka.......................................................................................V.2 Gambar V-2 Random50 A ...................................................................................V.5 Gambar V-3 TSP Tanpa Klastering Random50 A ...............................................V.5 Gambar V-4 Klaster Single Linkage Random 50 A ............................................V.6 Gambar V-5 Klaster Complete linkage Random50 A .........................................V.6 Gambar V-6 Solusi TSP Dengan Complete linkage Random50 A .....................V.7 Gambar V-7 Solusi TSP Dengan Single Linkage Random50 A..........................V.7 Gambar V-8 Perbandingan Tour distance random 50..........................................V.8 Gambar V-9 Perbandingan Tour Distance Kasus TSPlib ..................................V.10 Gambar V-10 Perbandingan Tour Distance Kasus Random..............................V.10 Gambar V-11 Perbandingan Running time ........................................................V.12 Gambar V-12 Perbandingan Running time random250.xls ...............................V.13 Gambar V-13 Perbandingan Running time Random 50 ....................................V.13 Gambar V-14 Perbandingan Jumlah Klaster......................................................V.15 Gambar V-15 Rata-Rata Jumlah Titik Per Klaster ............................................V.16 Gambar V-16 Java50.tsp ....................................................................................V.17 Gambar V-17 TSP Java50.tsp Tanpa Klaster ....................................................V.17 Gambar V-18 Single Klaster Java50.tsp ............................................................V.18 Gambar V-19 Complete Linkage Java50.tsp .....................................................V.18 Gambar V-20 Solusi TSP Dengan Single Linkage Java50.tsp ..........................V.19 Gambar V-21 Solusi TSP Complete Linkage Pada Java50.tsp..........................V.19
x
xi
Gambar V-22 Tour Distance Java50.tsp ............................................................V.21 Gambar V-23 Running Time Java50.tsp............................................................V.21
xi
xii
DAFTAR TABEL
Tabel IV-1 hasil subtour data yang telah di klastering .................................... IV.21 Tabel IV-2 Proses penghitungan penyisipan titik pada subtour....................... IV.22 Tabel V-1 Perbandingan Hasil Tour Distance Pada Random 50 titik .................V.8 Tabel V-2 Perbandingan Tour Distance ...............................................................V.9 Tabel V-3 Perbandingan Running Time ............................................................V.11 Tabel V-4 Jumlah Klaster Terbaik Solusi TSP ..................................................V.14 Tabel V-5 Perbandingan Single Linkage dan Complete Linkage Java50.tsp ....V.20
xii
xiii
DAFTAR RUMUS Rumus 2.1 Persamaan Cheapest insertion ...........................................................II-3 Rumus 2.2 Persamaan Priciest insertion .............................................................II-3 Rumus 2.3 Persamaan Nearest insertion .............................................................II-3 Rumus 2.4 Persamaan Nearest insertion 2 ..........................................................II-4 Rumus 2.5 Persamaan Farthest Insertion ............................................................II-4 Rumus 2.6 Persamaan Farthest Insertion 2 .........................................................II-4 Rumus 2.7 Persamaan Nearest addition ..............................................................II-4 Rumus 2.8 Persamaan Nearest addition 2 ...........................................................II-4 Rumus 2.9 Persamaan Clarke dan Wright ...........................................................II-5 Rumus 2.10 Persamaan Clarke dan Wright 2 ......................................................II-5 Rumus 2.11 Persamaan Singe linkage .................................................................II-7 Rumus 2.12 Persamaan Complete Linkage ..........................................................II-8 Rumus 4.1 Persamaan Standarisasi Data ........................................................... IV-4 Rumus 4.2 Persamaan Jarak Euclidean ............................................................. IV-5 Rumus 4.3 Persamaan Perbaikan Solusi Travelling Salesmen Problem ......... IV-11
xiii
xiv
DAFTAR LAMPIRAN
Lampiran A
: Kartu Bimbingan Tugas Akhir
Lampiran B
: Tabel Koordinat Kota
Lampiran C
: Tabel Hasil Simulasi
Lampiran D
: Listing Program
xiv
