METODE TRAVELING SALESMAN UNTUK MENENTUKAN LINTASAN TERPENDEK PADA DAERAH-DAERAH YANG TERIDENTIFIKASI BAHAYA Oleh : Aisyah Lestari 1206 100 016
Dosen Pembimbing: Subchan, Ph.D 19710513 199702 1 001
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2010
AGENDA PENDAHULUAN TINJAUAN PUSTAKA METODE PENELITIAN PEMBAHASAN DAN HASIL KESIMPULAN DAN SARAN DAFTAR PUSTAKA
PENDAHULUAN LATAR BELAKANG
Pada suatu daerah atau negara yang sedang dalam keadaan kurang aman penentuan lintasan terpendek menjadi hal yang cukup penting
RUMUSAN MASALAH
BATASAN MASALAH
Traveling Salesman Problem
TUJUAN DAN MANFAAT
Branch and bound
Nearest neighbor
PENDAHULUAN LATAR BELAKANG
1
RUMUSAN MASALAH
BATASAN MASALAH
TUJUAN DAN MANFAAT
Bagaimana menentukan lintasan terpendek menggunakan metode Traveleng Salesman Problem (TSP) pada daerah-daerah yang diidentifikasi terdapat bahaya sehingga dapat meminimalkan kecelakan atau hal buruk yang mungkin terjadi.
2 Bagaimana mensimulasikan lintasan terpendeknya dengan menggunakan software MATLAB.
PENDAHULUAN LATAR BELAKANG
RUMUSAN MASALAH
BATASAN MASALAH
TUJUAN DAN MANFAAT
Daerah yang akan didatangi sudah diidentifikasi. Setiap daerah dikunjungi satu kali. Daerah yang akan dikunjungi berada di darat. Tidak ada bahaya yang diprioritaskan. Diasumsikan seluruh daerah terhubung satu sama lain dengan jarak antara 2 daerah memiliki nilai yang sama meskipun dengan arah yang berbeda. Misal jarak daerah A ke daerah B sama dengan jarak daerah B ke daerah A. Simulasi dilakukan dengan menggunakan software MATLAB.
PENDAHULUAN LATAR BELAKANG
RUMUSAN MASALAH
BATASAN MASALAH
TUJUAN DAN MANFAAT
TUJUAN : menentukan lintasan terpendek dari daerah-daerah berbahaya yang akan dikunjungi sehingga dapat meminimalkan bahaya yang mungkin terjadi pada daerah tersebut.
MANFAAT : memberikan informasi tentang traveling salesman problem dan diharapkan dapat digunakan dalam aplikasi kehidupan seharihari baik oleh warga sipil maupun militer yang memerlukan efisiensi waktu dan biaya.
TINJAUAN PUSTAKA 1
Traveling Salesman Problem
TSP dikenal sebagai suatu permasalah optimasi yang bersifat klasik dan Non-Deterministic Polynomial-time Complete (NPC), dimana tidak ada penyelesaian yang paling optimal selain mencoba seluruh kemungkinan penyelesaian yang ada. Permasalahan ini melibatkan seorang traveling salesman yang harus melakukan kunjungan sekali pada semua kota dalam sebuah lintasan sebelum dia kembali ke titik awal, sehingga perjalanannya dikatakan sempurna. Definisi dari Traveling Saleman Problem yaitu diberikan n buah kota dan Cij yang merupakan jarak antara kota i dan kota j, seseorang ingin membuat suatu lintasan tertutup dengan mengunjungi setiap kota satu kali. Tujuannya adalah memilih lintasan tertutup yang total jaraknya paling minimum diantara pilihan dari semua kemungkinan lintasan.
Berikut ini adalah bentuk modelnya :
dengan : n = jumlah kota / lokasi / pelanggan yang akan dikunjungi (n tidak termasuk tempat asal (base), yang diindekkan dengan i = 0). Cij = biaya / jarak traveling dari kota i ke kota j A = sepasang arc / edge (i,j) yang ada. Note bahwa (i,j) yang dimaksud adalah arc yang ada dari node i ke node j. Variable :
2
Metode branch and bound
Langkah-langkah untuk menyelesaikan Metode Branch and Bound: Misalkan : 1. G = (V,E) adalah graf lengkap TSP. 2. |V|= n = jumlah simpul dalam graf G. Simpul-simpul diberi nomor 1,2,…,n. 3. Cij = bobot sisi (i,j). 4. Perjalanan berawal dan berakhir di simpul 1. 5. S adalah ruang penyelesaian, yang dalam hal ini S = {()} S = { (1, π ,1) | π adalah permutasi (2,3,.....,n) }. 6. |S|= (n-1)! = banyaknya kemungkinan penyelesaian. Penyelesaian TSP dinyatakan sebagai X = (1, x1, x2, ..., xn – 1, 1) yang dalam hal ini xo= xn = 1 (simpul asal = simpul akhir = 1).
3
Metode nearest neighbor
Pada metode ini, pemilihan lintasan akan dimulai pada lintasan yang memiliki nilai jarak paling minimum setiap melalui kota, kemudian akan memilih kota selanjutnya yang belum dikunjungi dan memiliki jarak yang paling minimum. Langkah-langkah untuk menyelesaikan Metode Nearest Neighbor : 1. Buat peta aliran yang menggambarkan letak-letak daerah yang akan dituju beserta jarak antar daerah. 2. Proses pengerjaan dengan melihat daerah dengan jarak terpendek. Setiap mencapai satu daerah, algoritma ini akan memilih daerah selanjutnya yang belum dikunjungi dan memiliki jarak yang paling minimum. 3. Perhitungan nilai optimal dengan menjumlah jarak dari awal sampai akhir perjalanan.
METODE PENELITIAN
1. Studi Pendahuluan 2. Pengambilan dan Pengumpulan Data 3. Penyelesaian traveling salesman problem dengan metode branch and bound menggunakan software QS (Quantitative System) 4. Penyelesaian traveling salesman problem dengan metode nearest neighbor 5. Simulasi dengan MATLAB 6. Penarikan kesimpulan
PEMBAHASAN DAN HASIL 1
Pengumpulan Data
Data yang dikumpulkan adalah merupakan data koordinat yang diperoleh dari Google Earth serta jarak antar daerah yang akan dikunjungi. Dalam tugas akhir ini diambil 3 contoh kota yang akan dihitung lintasan terpendeknya. Dimana pada tiap kota sudah ditentukan daerah-daerah yang terdapat bahaya. Table 1 Jarak antar daerah pada kota Surabaya (km) Keterangan : 1 2 3 4 5 6 7 1 = Gubeng 1 0 0.689 1.312 1.755 3.381 4.46 3.624 2 = Airlangga 2 0.689 0 0.989 1.846 2.733 3.771 2.975 3 = Kertajaya 3 1.312 0.989 0 1.103 2.334 3.683 3.305 4 = Ngagel 4 1.755 1.846 1.103 0 3.191 4.662 4.403 5 = Klampis Ngasem 5 3.381 2.733 2.334 3.191 0 1.567 2.169 6 = Gebang Putih 6 4.46 3.771 3.683 4.662 1.567 0 1.571 7 = Mulyorejo 7 3.624 2.975 3.305 4.403 2.169 1.571 0
Table 2 Jarak antar daerah pada kota Jakarta (km) 1
2
3
4
5
7
8
9
1
0
2.385
4.215
2.378
7.953
5.154
3.118
3.964
2
2.385
0
1.936
4.523
5.627
3.897
4.422
4.089
3
4.215
1.936
0
6.071
3.738
2.929
5.446
4.356
4
2.378
4.523
6.071
0
9.725
5.948
1.893
3.774
5
7.953
5.627
3.738
9.725
0
4.788
8.812
7.229
6
5.154
3.897
2.929
5.948
4.788
0
4.502
2.599
7
3.118
4.422
5.446
1.893
8.812
4.502
0
2.032
8
3.964
4.089
4.356
3.774
7.229
2.599
2.032
0
Keterangan : 1 = Tanah Abang 2 = Menteng 3 = Pegangsaan 4 = Gelora Bung Karno 5 = Rawmangun 6 = Tebet 7 = Senayan 8 = Jakarta Selatan
Table 3 Jarak antar daerah pada kota Bandung (km) 1
2
3
4
5
6
7
8
9
1
0
1.994
7.702
1.533
6.513
6.785
2.727
4.996
6.019
2
1.994
0
6.458
2.489
5.325
5.765
3.396
4.847
4.381
3
7.702
6.458
0
8.838
1.193
1.219
6.099
4.106
2.576
4
1.533
2.489
8.838
0
7.67
8.027
4.261
6.477
6.866
5
6.513
5.325
1.193
7.67
0
0.709
4.955
3.159
1.934
6
6.785
5.765
1.219
8.027
0.709
0
4.968
2.889
2.642
7
2.727
3.396
6.099
4.261
4.955
4.968
0
2.502
5.304
8
4.996
4.847
4.106
6.477
3.159
2.889
2.502
0
4.345
9
6.019
4.381
2.576
6.866
1.934
2.642
5.304
4.345
0
Keterangan : 1 = Antapani 2 = Cicaheum 3 = Ciroyom 4 = Arcamanik 5 = Kebon Jeruk 6 = Cibadak 7 = Binong 8 = Ancol 9 = Taman Sari
2
Pengolahan Data
2.1 Jalur Reguler Yang dimaksudkan jalur reguler disini adalah jalur yang ditempuh secara berururtan dari daerah awal (daerah nomor 1) menuju daerah selanjutnya sampai ke daerah terakhir (kembali ke daerah awal). Berdasarkan tabel 1 – 3 hasil dari perhitungan jalur reguler untuk tiap kota adalah sebagai berikut : Kota Surabaya = 1 – 2 – 3 – 4 – 5 – 6 – 7 = 12,734 km Kota Jakarta = 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 = 35,393 km Kota Bandung = 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 = 43,503 km
2.2 Dengan metode branch and bound menggunakan software QS (Quantitative System) Pengolahan jarak yang dilakukan adalah menggunakan Software QS (Quantitative System). Berikut adalah hasil yang diperoleh untuk tiap kota : Surabaya
Jakarta
Bandung
2.3 Dengan metode nearest neighbor Pengolahan jarak yang dilakukan adalah menggunakan metode Nearest Neighbor. Berikut adalah hasil yang diperoleh untuk tiap kota :
Surabaya S 1
T
J
S
T
J
S
T
J
S
T
J
S
T
J
S
T
J
S
T
J
2
0.689
2
3
0.989
3
4
1.103
4
5
3.191
5
6
1.567
6
7
1.571
7
1
3.624
3
1.312
4
1.846
5
2.334
6
4.662
7
2.169
4
1.755
5
2.733
6
3.683
7
4.403
5
3.381
6
3.771
7
3.305
6
4.46
7
2.975
7
3.624
Dari hasil perhitungan diatas didapat lintasan terpendeknya adalah 1 – 2 – 3 – 4 – 5 – 6 – 7 – 1 dengan total jarak tempuh sebesar 12,734 km.
Jakarta S
T
J
S
T
J
S
T
J
S
T
J
S
T
J
S
T
J
S
T
J
S
T
J
1
2
2.385
4
2
4.523
7
2
4.422
8
2
4.089
6
2
3.897
3
2
1.936
2
5
5.627
5
1
7.953
3
4.215
3
6.071
3
5.446
3
4.356
3
2.929
5
3.738
4
2.378
5
9.725
5
8.812
5
7.229
5
4.788
5
7.953
6
5.948
6
4.502
6
2.599
6
5.154
7
1.893
8
2.032
7
3.118
8
3.774
8
3.964
Dari hasil perhitungan diatas didapat lintasan terpendeknya adalah 1 – 4 – 7 – 8 – 6 – 3 – 2 – 5 – 1 dengan total jarak tempuh sebesar 27,347 km.
Bandung S
T
1
2
J
S
T
J
S T
J
S T
J
S
T
J
S T
J
S
T
J
S
T
J
S
T
J
1.994 4 2
2.489
2 3
6.458
7 3
6.099
8
3
4.106
6 3
1.219
5
3
1.193
3
9
2.576
9
1
6.019
3
7.702
3
8.838
5
5.325
5
4.955
5
3.159
5
0.709
9
1.934
4
1.533
5
7.67
6
5.765
6
4.968
6
2.889
9
2.642
5
6.513
6
8.027
7
3.396
8
2.502
9
4.345
6
6.785
7
4.261
8
4.847
9
5.304
7
2.727
8
6.477
9
4.381
8
4.996
9
6.866
9
6.019
Dari hasil perhitungan diatas didapat lintasan terpendeknya adalah 1 – 4 – 2 – 7 – 8 – 6 – 5 – 3 – 9 – 1 dengan total jarak tempuh 23,306 km.
Keterangan : S = start (mulai perjalanan) T = tujuan J = jarak antara masing-masing daerah
Rekapitulasi hasil perhitungan jalur yang dilalui
3
Dari hasil perhitungan traveling salesman dengan metode branch and bound dan metode nearest neighbor pada pembahasan diatas dapat dibuat tabel rekapitulasinya agar dapat dilihat perbandingannya. Tabel Rekapitulasi Hasil Perhitungan Jalur yang Dilalui Perhitungan jalur (km) Kota Reguler
Branch and bound
Nearest neighbor
Reguler - BB
Reguler - NN
Surabaya
12,734
11,994
12,734
0,740
0,000
Jakarta
35,393
21,749
27,347
13,644
8,046
Bandung
43,503
20,867
23,306
22,636
20,197
Tabel Pesentase Efisiensi Penghematan Jarak Kota
Penghematan jarak (km)
Branch and bound
Nearest neighbor
Surabaya
5,811 %
0%
Jakarta
38,549 %
22,733 %
Bandung
52,033 %
46,426 %
4
Simulasi dengan MATLAB
Setelah dilakukan perhitungan dengan metode branch and bound menggunakan software QS (Quantitative System) dan metode nearest neighbor, pada tahap ini dilakukan simulasi dengan menggunakan software MATLAB 7.4 sehingga dapat diketahui gambar lintasan terpendeknya. Form antar muka simulasi dibangun oleh Graphic User Interface (GUI) yang sudah tersedia dalam perangkat lunak MATLAB 7.4.
Gambar form awal simulasi lintasan terpendek
Hasil simulasi untuk kota Surabaya
Hasil simulasi untuk kota Jakarta
Hasil simulasi untuk kota Bandung
KESIMPULAN Kesimpulan yang diperoleh dari hasil dan pembahasan adalah : 1. Jarak terpendek yang diperoleh setelah melakukan perhitungan dengan metode branch and bound dan metode nearest neighbor untuk masing-masing lintasan adalah : Kota
Metode branch and bound
Metode nearest neighbor
Surabaya
11,994 km
12,734 km
Jakarta
21,749 km
27,347 km
Bandung
20,867 km
23,306 km
2. Penghematan jarak yang diperoleh dari masing-masing metode adalah : Penghematan jarak (km) Kota
3.
Reguler - BB
Reguler - NN
Surabaya
0,740
0,000
Jakarta
13,644
8,046
Bandung
22,636
20,197
Metode branch and bound lebih baik dalam menyelesaikan permasalahan traveling salesman dibandingkan dengan metode nearest neighbor.
SARAN Pada Tugas Akhir ini metode yang digunakan untuk penyelesaian traveling salesman problem adalah metode branch and bound dan metode nearest neighbor. Dimana kemungkinan hasil yang didapat kurang optimal. Diharapkan pada penelitian selanjutnya dapat menggunakan metode yang lebih optimal untuk menyelesaikan traveling salesman problem.
DAFTAR PUSTAKA Amin, Rahma Aulia. Dkk, 2006. Traveling Salesman Problem, Bandung: Institut Teknologi Bandung. <www.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik30.pdf > Biggs, N. L., dkk. 1976. Graph Theory 1736-1936. New York : Clarendon Press, Oxford University. Munir, Rinaldi. 2006. Bahan Kuliah: Algoritma Branch and Bound, Bandung: Institut Teknologi Bandung. Sarker, A. R., dan Newton C. 2007. Optimization Modeling: A Practical Aproach. Taylor & Francis Group, LLC. Wahyudi, Agus. 2002. Studi Komparatif Antara Algoritma Genetika dan Simulated Annealing untuk Menyelesaikan Traveling Salesman Problem. Tugas Akhir, Matematika, Institut Teknologi Sepuluh Nopember, Surabaya. Zuhdi, Mohd. 2009. Kuliah2: Sistem Koordinat. <www.angelfire.com/mo/zuhdi/Kuliah2.pdf> www.wikipedia.org/wiki/Google_earth diakses 13 Mei 2010 pukul 14.23 WIB www.divshare.com/download/3088474-054 diakses 13 Mei 2010 pukul 13.02 WIB
