METODE TRAVELING SALESMAN UNTUK MENENTUKAN LINTASAN TERPENDEK PADA DAERAH-DAERAH YANG TERIDENTIFIKASI BAHAYA Nama Mahasiswa NRP Jurusan Dosen Pembimbing
: Aisyah Lestari : 1206 100 016 : Matematika : Subchan, Ph.D
Abstrak Pada suatu daerah atau negara yang sedang dalam keadaan kurang aman penentuan lintasan terpendek menjadi hal yang cukup penting untuk diperhitungkan karena dapat digunakan untuk meminimalkan bahaya atau hal buruk yang mungkin akan terjadi. Traveling salesman problem merupakan metode yang dapat digunakan untuk mencari lintasan terpendek dengan mengunjungi setiap daerah tepat satu kali. Pada tugas akhir ini dibahas tentang penyelesaian traveling salesman problem dengan metode branch and bound dan metode nearest neighbor. Hasil yang diperoleh adalah dengan metode branch and bound didapat penghematan jarak sebesar 0,74 km untuk kota Surabaya, 13,644 km untuk kota Jakarta, dan 22,636 km untuk kota Bandung. Sedangkan dengan metode nearest neighbor didapat penghematan jarak sebesar 0 km untuk kota Surabaya, 8,046 km untuk kota Jakarta, dan 20,197 km untuk kota Bandung. Sehingga dari kedua metode tersebut didapat bahwa metode branch and bound lebih baik dalam meyelesaikan permasalahan traveling salesman. Kata kunci : traveling salesman, lintasan terpendek, branch and bound, nearest neighbor. 1. Pendahuluan Perkembangan ilmu pengetahuan semakin pesat, hal ini ditunjukan dengan semakin banyaknya teknologi baru yang berkembang. Salah satunya adalah teknologi yang berkaitan dengan keamanan. Sebagai contoh, kendaraan Nir awak yang saat ini banyak digunakan untuk militer. Selain itu, muncul teknologi untuk mengembangkan senjata mutakhir. Akan tetapi perkembangan teknologi tersebut tidak berjalan sebanding dengan perkembangan keamanan itu sendiri. Misal pada suatu daerah atau negara yang sedang dalam keadaan kurang aman atau sedang dalam keadaan berperang, untuk mencapai beberapa tempat yang dituju dengan lintasan terpendek menjadi hal yang cukup penting diperhatikan karena dapat meminimalkan bahaya atau hal buruk yang mungkin akan terjadi. Metode Travelling Salesman Problem (TSP) adalah metode yang dapat digunakan untuk menentukan lintasan terpendek dengan mengunjungi setiap daerah yang ada hanya satu kali. Pada tugas akhir ini dibahas tentang cara menentukan lintasan terpendek dengan menggunakan metode traveling salesman problem dengan metode Branch and Bound menggunakan software QS
(Quantitative System) dan metode Nearest Neighbor. Sebelum melakukan proses TSP, terlebih dahulu perlu dilakukan pengidentifikasian daerah-daerah yang terdapat ancaman tersebut dengan memanfaatkan “Google Earth” untuk menentukan daerah tujuan dan jarak antar daerah satu dengan daerah lainnya. Untuk penyelesaian Traveling Salesman Problem dalam tugas akhir ini digunakan dua metode dikarenakan supaya dapat dilihat perbandingan hasil dari kedua metode tersebut, sehingga nantinya akan dapat dilihat metode yang paling baik. 2. Traveling Salesman Problem (TSP) Permasalahan tentang Traveling Salesman Problem dikemukakan pada tahun 1800 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Penyngton. Gambar dibawah ini adalah foto dari permainan Icosian Hamilton yang membutuhkan pemain untuk menyelesaikan perjalanan dari 20 titik menggunakan hanya jalur-jalur tertentu.
1
Dengan batas :
Gambar 1 Foto dari permainan Icosian Hamilton
Bentuk umum dari TSP pertama dipelajari oleh para matematikawan mulai tahun 1930. Diawali oleh Karl Menger di Viena dan Harvard. Setelah itu permasalahan TSP dipublikasikan oleh Hassler Whitney dan Merrill Flood di Princeton. Selanjutnya dengan permasalahan ini, TSP dibuat menjadi permasalahan yang terkenal dan popular untuk dipakai sebagai model produksi, transportasi dan komunikasi (Amin, Rahma Aulia. Dkk, 2006). TSP dikenal sebagai suatu permasalah optimasi yang bersifat klasik dan NonDeterministic 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 :
Parameter : 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 :
3. 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) (Munir Rinaldi, 2006). 4. Metode Nearest Neighbor Pada metode ini, pemilihan lintasan akan dimulai pada lintasan yang memiliki nilai jarak paling minimum setiap melalui kota, kemudian
2
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 letakletak daerah yang terdapat bahaya 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.
3
1.312
0.989
0
1.103
2.334
3.683
3.305
4
1.755
1.846
1.103
0
3.191
4.662
4.403
5
3.381
2.733
2.334
3.191
0
1.567
2.169
6
4.46
3.771
3.683
4.662
1.567
0
1.571
7
3.624
2.975
3.305
4.403
2.169
1.571
0
Keterangan : 1 = Gubeng 2 = Airlangga 3 = Kertajaya 4 = Ngagel 5 = Klampis Ngasem 6 = Gebang Putih 7 = Mulyorejo
5. Metode Penelitian
Table 2 Jarak antar daerah pada kota Jakarta (km)
Berikut adalah langkah-langkah yang dilakukan dalam penelitian agar proses pengerjaan dapat terstruktur dengan baik : a. Studi pendahuluan b. Pengambilan dan pengumpulan data. Data yang dimaksudkan dalam tugas akhir ini adalah gambar yang merupakan representasi dari posisi dan jumlah kotakota dalam TSP yang akan diselesaikan. Selain itu juga data koordinat posisi tiaptiap kota yang berupa longitude dan latitude. Pengambilan data tersebut memanfaatkan software Google earth. c. Penyelesaian traveling salesman problem dengan metode branch and bound menggunakan software QS (Quantitative System). d. Penyelesaian traveling salesman problem dengan metode nearest neighbor. e. Simulasi dengan MATLAB. f. Ppenarikan kesimpulan.
1
2
3
4
5
6
7
8
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
6. Pembahasan dan Hasil 6.1 Pengumpulan Data Table 1 Jarak antar daerah pada kota Surabaya (km) 1
2
3
4
5
6
7
1
0
0.689
1.312
1.755
2
0.689
0
0.989
1.846
3.381
4.46
3.624
2.733
3.771
2.975
3
Table 3 Jarak antar daerah pada kota Bandung (km)
1. Surabaya
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 6.2 Pengolahan Data 6.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 : 1. Kota Surabaya = 1 – 2 – 3 – 4 – 5 – 6 – 7 = 12,734 km 2. Kota Jakarta = 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 = 35,393 km 3. Kota Bandung = 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 = 43,503 km 6.2.2
Pengolahan Data dengan Metode Branch and Bound Menggunakan Software QS Pengolahan jarak yang dilakukan adalah menggunakan Software QS (Quantitative System). Berikut adalah hasil yang diperoleh untuk tiap kota :
Modules-1 Modules-2 Input Data Solution Options Help – ASTS --------Traveling Salesman Solution for surabaya ------06-15-2010 22:06:46 Page: 1 1 ==> 4 ==> 3 ==> 5 ==> 6 ==> 7 ==> 2 ==> 1 Minimized OBJ = 11.994 # Iterations = 43 CPU seconds = 963.2891 < OK > < Hardcopy > < Cancel > Gambar 2 Hasil perhitungan QS untuk kota Surabaya
Lintasan terpendek yang diperoleh adalah 1 – 4 – 3 – 5 – 6 – 7 – 2 – 1 dengan total jarak tempuh sebesar 11,994 km. 2. Jakarta Modules-1 Modules-2 Input Data Solution Options Help – ASTS --------- Traveling Salesman Solution for Jakarta-------06-16-2010 01:19:32 Page: 1 1 ==> 2 ==> 3 ==> 5 ==> 6 ==> 8 ==> 7 ==> 4 ==> 1 Minimized OBJ = 21.749 # Iterations = 3 CPU seconds = 46.19043 < OK > < Hardcopy > < Cancel > Gambar 3 Hasil perhitungan QS untuk kota Jakarta
Lintasan terpendek yang diperoleh adalah 1 – 2 – 3 – 5 – 6 – 8 – 7 – 4 – 1 dengan total jarak tempuh sebesar 21,749 km. 3. Bandung Modules-1 Modules-2 Input Data Solution Options Help – ASTS -------Traveling Salesman Solution for bandung--------06-16-2010 09:29:53 Page: 1
1 ==> 7 ==> 8 ==> 6 ==> 3 ==> 5 ==> 9 ==> 2 ==> 4 ==> 1 Minimized OBJ = 20.867 # Iterations = 47 CPU seconds = 355.0898 < OK > < Hardcopy > < Cancel > Gambar 4 Hasil perhitungan QS untuk kota bandung
4
Lintasan terpendek yang diperoleh adalah 1 – 7 – 8 – 6 – 3 – 5 – 9 – 2 – 4 – 1 dengan total jarak tempuh sebesar 20,867 km.
S T 1 2 3 4 5 6 7
6.2.3 Pengolahan Data dengan Metode Nearest Neighbor Pengolahan jarak yang dilakukan adalah menggunakan metode Nearest Neighbor. Berikut adalah hasil yang diperoleh untuk tiap kota : 1. Surabaya Table 4 Hasil Perhitungan Nearest Neighbor untuk Surabaya (km) J S T J S T J S T J 0.689 2 3 0.989 3 4 1.103 4 5 3.191 1.312 4 1.846 5 2.334 6 4.662 1.755 5 2.733 6 3.683 7 4.403 3.381 6 3.771 7 3.305 4.46 7 2.975 3.624 Lanjutan Tabel 4 S T J S T J 5 6 1.567 6 7 1.571 7 2.169
S 7
4
2.378
5
9.725
5
8.812
5
7.229
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
Lanjutan Tabel 5 S T J S T J S T J S T J 6 2 3.897 3 2 1.936 2 5 5.627 5 1 7.953 3 2.929 5 3.738 5 4.788
Keterangan : S = start (mulai perjalanan) T = tujuan J = jarak antara masing-masing daerah
T J 1 3.624
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. 3. Bandung Table 6 Hasil Perhitungan Nearest Neighbor untuk Bandung (km)
Keterangan : S = start (mulai perjalanan) T = tujuan J = jarak antara masing-masing daerah Dari hasil perhitungan diatas didapat lintasan terpendeknya adalah 1 – 2 – 3 – 4 – 5 – 6 – 7 – 1 dengan total jarak tempuh sebesar 12,734 km. 2. Jakarta Table 5 Hasil Perhitungan Nearest Neighbor untuk Jakarta (km) S 1
T 2 3
J 2.385 4.215
S 4
T 2 3
J 4.523 6.071
S 7
T 2 3
J 4.422 5.446
S 8
T 2 3
S
T
J
S
T
J
S
T
J
S
T
J
S
T
J
1
2
1.994
4
2
2.489
2
3
6.458
7
3
6.099
8
3
4.106
3
7.702
3
8.838
5
5.325
5
4.955
5
3.159
4
1.533
5
7.67
6
5.765
6
4.968
6
2.889
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
Lanjutan Tabel 6
J 4.089 4.356
S
T
J
S
T
J
S
T
J
S
T
J
6
3
1.219
5
3
1.193
3
9
2.576
9
1
6.019
5
0.709
9
1.934
5
9
2.642
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.
Keterangan : S = start (mulai perjalanan) T = tujuan J = jarak antara masing-masing daerah 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. 6.3 Rekapitulasi Hasil Perhitungan Jalur yang Dilalui Tabel 7 Rekapitulasi Hasil Perhitungan Jalur yang Dilalui Perhitungan jalur (km) Kota Reguler Surabaya Jakarta Bandung
12,734 35,393 43,503
Branch and bound 11,994 21,749 20,867
Penghematan jarak (km)
Nearest neighbor
Reguler - BB
Reguler - NN
12,734 27,347 23,306
0,740 13,644 22,636
0,000 8,046 20,197
Tabel 8 Pesentase Efisiensi Penghematan Jarak Kota Surabaya Jakarta Bandung Keterangan : % Efisiensi =
Branch and bound 5,811 % 38,549 % 52,033 %
Nearest neighbor 0% 22,733 % 46,426 %
Berikut ini adalah masing-masing tools yang digunakan pada gambar form yang ditunjukan pada Gambar 5. Tabel 9 Tools yang Digunakan pada Simulasi Nama Tools
Jenis
Banyak kota yang akan dilalui
Edit text
Browse
push button
Run
Push button
Reset
push button
Exit
Push button
Status Program
Edit text
x 100%
(untuk metode branch and bound) % Efisiensi =
Gambar 5 Form awal simulasi lintasan terpendek
x 100%
(untuk metode nearest neighbor) 7. Simulasi dengan MATLAB Setelah dilakukan perhitungan dengan metode branch and bound menggunakan
Keterangan Digunakan sebagai tempat input nilai jumlah daerah yang akan dilalui oleh user Digunakan untuk mencari peta area yang akan digunakan user Digunakan untuk memanggil fungsi menjalankan program Digunakan untuk mengatur kembali ke pengaturan awal Digunakan untuk menutup simulasi Digunakan untuk melihat status program
Berikut ini adalah hasil simulasi lintasan terpendek untuk masing-masing kota :
6
Gambar 6 Gambar lintasan terpendek untuk kota Surabaya Pada Gambar 6 dapat dilihat bahwa lintasan terpendek untuk kota Surabaya ditunjukkan dengan garis yang berwarna merah. Sehingga didapat lintasan terpendeknya adalah dari gubeng (1) – ngagel (4) – kertajaya (3) – klampis ngasem (5) – gebang putih (6) – mulyorejo (7) – airlangga (2) – gubeng (1). Sedangan garis-garis putih disekitarnya menunjukan iterasi.
Gambar 8 Gambar lintasan terpendek untuk kota Bandung Pada Gambar 8 dapat dilihat bahwa lintasan terpendek untuk kota Bandung ditunjukkan dengan garis yang berwarna merah. Sehingga didapat lintasan terpendeknya adalah dari antapani (1) – binong (7) – ancol (8) – cibadak (6) – coroyom (3) – kebon jeruk (5) – taman sari (9) – cicaheum (2) – arcamanik (4) – antapani (1). Sedangan garis-garis putih disekitarnya menunjukan iterasi.
8. Kesimpulan dan saran 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 : Gambar 7 Gambar lintasan terpendek untuk kota Jakarta Pada Gambar 7 dapat dilihat bahwa lintasan terpendek untuk kota Jakarta ditunjukkan dengan garis yang berwarna merah. Sehingga didapat lintasan terpendeknya adalah dari tanah abang (1) – menteng (2) – pegangsaan (3) – rawmangun (5) – tebet (6) – Jakarta selatan (8) – senayan (7) – gelora bung karno (4) – tanah abang (1). Sedangan garis-garis putih disekitarnya menunjukkan iterasi.
Kota Surabaya Jakarta Bandung
Metode branch and bound 11,994 km 21,749 km 20,867 km
Metode nearest neighbor 12,734 km 27,347 km 23,306 km
2. Penghematan jarak yang diperoleh dari masing-masing metode adalah : Penghematan jarak (km) Reguler - BB Reguler - NN Surabaya 0,740 0,000 Jakarta 13,644 8,046 Bandung 22,636 20,197 Kota
7
3. Dari hasil diatas dapat disimpulkan bahwa metode branch and bound lebih baik dibandingkan dengan metode nearest neighbor.
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
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. 9. 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 17361936. 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/Kuliah 2.pdf>
8
