PENYELESAIAN TRAVELING SALESMAN PROBLEM (TSP) MENGGUNAKAN ALGORITMA RECURSIVE BEST FIRST SEARCH (RBFS) Hari Santoso – 146060300111019
[email protected]
Prodi Sistem Komunikasi dan Infromatika Teknik Elektro Universitas Brawijaya ABSTRAK Travelling Salesman Problem (TSP) merupakan sebuah permasalahan optimasi yang dapat diterapkan pada berbagai kegiatan seperti routing. Masalah optimasi TSP terkenal dan telah menjadi standar untuk mencoba algoritma yang komputational. Pokok permasalahan dari TSP adalah seorang salesman harus mengunjungi sejumlah kota yang diketahui jaraknya satu dengan yang lainnya. Semua kota yang ada harus dikunjungi oleh salesman tersebut dan kota tersebut hanya boleh dikunjungi tepat satu kali. Permasalahannya adalah bagaimana salesman tersebut dapat mengatur rute perjalanannya sehingga jarak yang ditempuhnya merupakan rute yang optimum yaitu jarak minimum terbaik. Dalam makalah ini penyelesaian kasus TSP diselesaikan dengan algoritma Recursive Best First Search (RBFS). A. LATAR BELAKANG MASALAH Travelling Salesman Problem (TSP) merupakan permasalahan pedagang keliling dalam mencari lintasan terpendek dari semua kota yang dikunjunginya. Dengan syarat kota tersebut hanya boleh dikunjungi satu kali. Banyak permasalahan yang dapat direpresentasikan dalam bentuk Travelling Salesman Problem. Persoalan ini sendiri menggunakan representasi graf untuk memodelkan persolan yang diwakili sehingga lebih memudahkan penyelesaiannya. Diantaranya permasalahan yang dapat direpresentasikan dengan TSP ialah masalah transportasi, efisiensi pengiriman surat atau barang, perancangan pemasangan pipa saluran, proses pembuatan PCB (Printed Circuit Board) dan lain–lain. Ada beberapa algoritma dan metode yang bisa menyelesaikan TSP ini, antara lain: algoritma Brute Force dengan complete Enumeration, algoritma Branch and Bound, Greedy Heuristik. Dalam Algoritma Bruto Force, hal yang dilakukan ialah dengan cara mengenumerasi seluruh
kemungkinan rute yang akan ditempuh. Setelah itu, akan dibandingkan dari seluruh kemungkinan rute yang telah dienumerasi tersebut, rute mana yang memiliki lintasan/bobot yang paling minimum. Namun, jumlah enumerasi dari algoritma ini ialah (n-1)! Yang akan memerlukan waktu yang sangat lama untuk mendapatkan panjang lintasan paling minimum jika n bernilai sangat besar. Seperti Algoritma Brute Force yang mengenumerasi satu per satu kemungkinan jalur yang akan ditempuh, Algoritma Branch and bound ternyata tidak memiliki kompleksitas waktu yang lebih baik dimana algoritma ini juga memilki kompleksitas waktu (n-1)! Dan sangat membutuhkan waktu yang sangat lama untuk mendapatkan panjang lintasan paling minimum jika n bernilai sangat besar. Sedangkan pada greedy heuristik, pemilihan lintasan akan dimulai pada lintasan yang memilki nilai paling minimum, algoritma ini akan memilih kota selanjutnya yang belum dikunjungi yang mempunyai bobot paling minimum/kota terdekat sampai swmua kota tersebut dikunjungi dan kemudian kembali ke kota awal, tetapi hasil yang didapat bisa sangat jauh dari hasil optimal, semakin banyak kota yang dikunjungi semakin besar pula perbedaan yang dicapai. Algoritma Heuristik merupakan salah satu algoritma alternatif yang dapat digunakan sebab prosesnya cepat dan memberikan hasil yang diinginkan. Algoritma Heuristik adalah algoritma yang mencari solusi terbaik untuk kasus yang merupakan bagian atau irisan dari permasalahan total dengan harapan dapat menghasilkan solusi optimal untuk keseluruhan kasus melalui proses tambahan, yaitu mencari bobot minimum dengan menggunakan Recursive Best First Search (RBFS) sehingga menghasilkan routing dari graf yang memiliki nilai optimal. Permasalahan pada makalah ini bisa dilihat pada Gambar 1, yaitu mencari jarak terpendek terbaik yang bisa ditempuh oleh sales dan setiap kota hanya boleh dikunjungi satu kali.
Gambar 1. Peta jalur antar kota yang harus dilewati oleh sales B. RECURSIVE BEST-FIRST SEARCH (RBFS) Recursive Best-First Search merupakan algoritma pencarian terbimbing yang mirip dengan algoritma standar Best First Search yang bersifat linear. Desain algoritmanya juga mirip dengan Depth-First Search walaupun dengan model yang sangat berbeda. Cara kerja RBFS yaitu tetap memperhatikan jalur teratas, kalau misalkan pada tree, maka tree paling atas. Apabila ada jalur yang tidak sesuai, maka jalur teratas akan langsung mengubahnya. Pada saat operasi, setiap operasi yang akan dipilih adalah jalur yang terpendek, dan setiap ada jalur baru, maka jalur teratas akan diurutkan berdasarkan nilai cost yang terkecil. Hal tersebut akan dilakukan hingga titik akhir adalah jalur yang dituju dan cost yang ditemukan pada jalur terakhir ini lebih kecil dari jalur-jalur yang sudah dilewati sebelumnya. Berikut ini adalah algoritma untuk RBFS.
Gambar 2. Representasi jalur antar kota dalam kasus TSP Tabel 1. Tabel jarak antar kota (dalam km) Kota
Jkt
Bdg
Crb
Jkt
0
270
327
Bdg
270
0
120
373
Crb
327
120
0
210
305
373
210
0
109
60
305
109
0
97
60
97
0
Ygy Smg Srkt Sby Mlg
Ygy
Smg
Srkt
369 370
Sby
Mlg
369 370 0
94
94
0
C. PEMODELAN Gambar 2. merupakan representasi bentuk pohon dari peta jalur antar kota yang akan dicari solusinya. Garis putus-putus menunjukkan bahwa jalur yang bisa menjadi solusi adalah jalur yang melewati seluruh kota dan tepat satu kali untuk masing-masing kota. Sedangkan jarak antar kota berdasarkan jalur yang ada pata peta dapat dilihat pada tabel 1.
Berdasarkan pohon pada Gambar 2, maka proses pencarian RBFS akan dilakukan dengan cara membandingkan setiap simpul yang dilewati dan dicari simpul yang memiliki cost atau jarak yang paling kecil sesuai dengan algoritma pada RBFS. Proses perhitungan untuk menemukan jalur terpendek dengan metode RBFS akan dijelaskan secara singkat seperti pada Tabel 2.
Pada step pertama, hitung jalur asal dengan jalur yang mungkin untuk dilewati. Jalur yang mungkin hanya Bandung (270km) dan Cirebon (327km). Urutkan jarak tersebut berdasarkan yang terpendek. jarak yang terpendek akan dipilih untuk menghitung jarak selanjutnya, sedangkan jarak terpendek kedua akan dijadikan treshold atau patokan untuk dihitung apabila hasil dari jalur yang dibuka dari jarak terpendek lebih besar daripada jarak jalur kedua tersebut. Pada step awal, jarak minimal adalah Jakarta-Bandung, dan yang menjadi treshold adalah jarak JakartaCirebon.
Step kedua yang dibuka adalah jalur Jakarta-Bandung. Kemungkinan yang bisa dilewati adalah jalur Jakarta-Bandung-Cirebon (390km) dan Jakarta-Bandung-Yogyakarta (643). Selanjutnya jarak-jarak tersebut dibandingkan dan dipilih jalur terpendek. Jalur yang terpendek adalah JakartaCirebon dan jalur terpendek kedua adalah JakartaBandung-Cirebon. Sehingga jalur yang akan dibuka selanjutnya adalah jalur Jakarta-Cirebon dan yang menjadi treshold adalah jalur JakartaBandung-Cirebon. Begitu seterusnya hingga didapatkan jarak terpendek untuk menghubungkan semua kota.
Tabel 2. Step-step pencarian algoritma RBFS Step
Open
Jalur
Min
Treshhold
1
Jkt (0)
Jkt-Bdg (270)
Jkt-Bdg (270)
Jkt-Crb (327)
Jkt-Crb (327)
Jkt-Bdg-Crb (390)
Jkt-Bdg-Crb (390)
Jkt-Crb-Bdg (447)
Jkt-Crb-Bdg (447)
Jkt-Crb-Ygy (537)
Jkt-Crb (327) 2
Jkt-Bdg (270)
Jkt-Bdg-Crb (390) Jkt-Bdg-Ygy (643)
3
Jkt-Crb (327)
Jkt-Crb-Bdg (447) Jkt-Crb-Ygy (537) Jkt-Crb-Smg (632)
3
Jkt-Bdg-Crb (390)
Jkt-Bdg-Crb-Smg (695) Jkt-Bdg-Crb-Ygy (600)
4
Jkt-Crb-Bdg (447)
Jkt-Crb-Bdg-Ygy (820)
Jkt-Crb-Ygy (537)
Jkt-Bdg-Crb-Ygy (600)
…
…
…
…
…
D. IMPLEMENTASI METODE Model komputasi algoritma untuk menyelesaikan kasus TSP dengan RBFS yaitu dibuat dengan bahasa pemrograman PHP1. Hal yang pertama dilakukan adalah pemetaan kota dan jarak antar kota. Peta dibuat dalam bentuk array objek dimana untuk masing-masing kota berisi ID kota, Nama kota, jalur yang mungkin dilalui sekaligus jarak antara kota denga jalur tersebut. Pada Gambar 3. menunjukkan kota Jakarta dan kota Bandung. Kota jakarta memiliki id ‘jkt’ dan jalur yang mungkin dilalui adalah Jakarta-Bandung (bdg) dengan jarak 270 km dan Jakarta-Cirebon (crb) dengan jarak 327 km. Sedangkan kota Bandung, jalur yang mungkin dilewati adalah Bandung-Cirebon (crb) dengan jarak 120 km dan Bandung-Yogyakarta (ygy) dengan jarak 373 km.
1
http://lab.elangsakti.com/tsp/
Gambar 3. Representasi peta dalam bahasa pemrograman Dalam proses pencarian, peta tersebut ‘dibaca’ dengan fungsi possible() untuk mengetahui kemungkinan jalur yang akan dilalui dari suatu kota. Fungsi possible() tampak pada Gambar 4, inputnya adalah id kota, dan ouputnya adalah daftar kota yang mungkin dilalui. Pada kode
tersebut dilalukan perulangan pada peta dan mencari jalur yang mungkin untuk kota dengan id yang cocok.
usort() (lihat Gambar 6). Seletah diurutkan, makan jalur dengan cost terkecil akan dibuka (variabel $open) dan jalur terkecil kedua akan dijadikan treshold untuk perbandingan (variabel $back). Selanjutnya pembukaan jalur baru dilakukan pada bagian $this->route($open).
Gambar 4. Fungsi possible() Fungsi utama untuk RBFS ada pada fungsi route(). Fungsi route() membutuhkan input kota yang sedang dibuka (di-expand / open) dan menghasilkan jalur dengan cost yang minimal dan jalur yang akan dijadikan backup / treshold. Gambar 5. Merupakan potongan source code untuk fungsi route(). Pertama akan dicari jalur yang mungkin dilewati dengan pemanggilan fungsi possible(). Setelah itu daftar jalur yang akan dilewati akan dihitung satu-persatu dengan perulangan. Masingmasing jalur akan dihitung besar cost dari jalur awal yaitu pada variabel $tmp[lenmin].
Gambar 6. Potongan fungsi route untuk pengurutan data dan menentukan jalur yang akan dibuka Gambar 7. adalah hasil eksekusi program ketika dijalankan. Jika memilih jalur awal adalah Jakarta, maka sistem membutuhkan 107 kali perulangan dengan jalur terbaik Jakarta-CirebonSemarang-Surabaya-Malang-Surakarta-YogyakartaBandung-Jakarta dengan jarak yang ditempuh 2164 km atau sebaliknya. Step-step pencarian jalur yang lengkap bisa dilihat pada tabel 3.
Gambar 7. Hasil eksekusi program
Gambar 5. Potongan fungsi route() untuk menghitung path
Tabel 3. Step-step pencarian jalur terpendek dengan kota awal Jakarta Step
Setelah masing-masing cost dihitung, maka semua kemungkinan jalur yang ada akan diurutkan berdasarkan cost yang terkecil dengan fungsi
Rute
Cost
1
Jakarta-Bandung
270
2
Jakarta-Cirebon
327
3
Jakarta-Bandung-Cirebon
390
4
Jakarta-Cirebon-Bandung
447
52
Jakarta-Cirebon-Semarang-Yogyakarta-Bandung
1114
5
Jakarta-Cirebon-Yogyakarta
537
53
Jakarta-Cirebon-Yogyakarta-Surakarta
597
54
7
Jakarta-Bandung-Cirebon-Yogyakarta
600
55
8
Jakarta-Cirebon-Semarang
632
56
Jakarta-Bandung-Yogyakarta-Semarang-Surabaya Jakarta-Bandung-Cirebon-Yogyakarta-SurakartaSemarang-Surabaya Jakarta-Bandung-Cirebon-Yogyakarta-SurakartaMalang-Surabaya Jakarta-Cirebon-Yogyakarta-Surakarta-SemarangSurabaya-Malang
1117
6
9
1122 1124 1153
Jakarta-Bandung-Yogyakarta
643
57
Jakarta-Bandung-Cirebon-Semarang-Surabaya-Malang
1154
10
Jakarta-Cirebon-Yogyakarta-Semarang
646
58
Jakarta-Bandung-Cirebon-Yogyakarta-Surakarta
660
59
12
Jakarta-Cirebon-Yogyakarta-Surakarta-Semarang
694
60
13
Jakarta-Bandung-Cirebon-Semarang
695
61
14
Jakarta-Bandung-Yogyakarta-Surakarta
703
15
Jakarta-Bandung-Cirebon-Yogyakarta-Semarang
709
16
Jakarta-Cirebon-Semarang-Surakarta
729
17
Jakarta-Cirebon-Semarang-Yogyakarta
741
18
Jakarta-Cirebon-Yogyakarta-Semarang-Surakarta
743
19
752
20
Jakarta-Bandung-Yogyakarta-Semarang Jakarta-Bandung-Cirebon-Yogyakarta-SurakartaSemarang
21
Jakarta-Cirebon-Semarang-Surakarta-Yogyakarta
789
22
Jakarta-Bandung-Cirebon-Semarang-Surakarta
792
23
Jakarta-Bandung-Yogyakarta-Surakarta-Semarang
800
Jakarta-Bandung-Yogyakarta-Cirebon-Semarang Jakarta-Cirebon-Semarang-Surakarta-YogyakartaBandung Jakarta-Bandung-Cirebon-Semarang-SurakartaMalang Jakarta-Bandung-Yogyakarta-Surakarta-SemarangSurabaya Jakarta-Bandung-Yogyakarta-Surakarta-MalangSurabaya Jakarta-Bandung-Cirebon-Yogyakarta-SemarangSurabaya-Malang Jakarta-Cirebon-Semarang-Yogyakarta-SurakartaMalang Jakarta-Bandung-Cirebon-Yogyakarta-SemarangSurakarta-Malang Jakarta-Cirebon-Semarang-Surakarta-MalangSurabaya Jakarta-Cirebon-Yogyakarta-Semarang-SurakartaMalang-Surabaya Jakarta-Bandung-Yogyakarta-Semarang-SurabayaMalang Jakarta-Bandung-Cirebon-Yogyakarta-SurakartaSemarang-Surabaya-Malang Jakarta-Bandung-Yogyakarta-Semarang-SurakartaMalang Jakarta-Bandung-Cirebon-Semarang-YogyakartaSurakarta-Malang Jakarta-Cirebon-Bandung-Yogyakarta-SurakartaMalang Jakarta-Bandung-Yogyakarta-Cirebon-SemarangSurakarta Jakarta-Bandung-Cirebon-Semarang-SurakartaMalang-Surabaya Jakarta-Bandung-Yogyakarta-Surakarta-SemarangSurabaya-Malang Jakarta-Cirebon-Semarang-Yogyakarta-SurakartaMalang-Surabaya Jakarta-Bandung-Cirebon-Yogyakarta-SemarangSurakarta-Malang-Surabaya Jakarta-Cirebon-Bandung-Yogyakarta-SemarangSurabaya Jakarta-Bandung-Yogyakarta-Semarang-SurakartaMalang-Surabaya Jakarta-Bandung-Cirebon-Semarang-YogyakartaSurakarta-Malang-Surabaya Jakarta-Cirebon-Bandung-Yogyakarta-SurakartaSemarang-Surabaya Jakarta-Cirebon-Bandung-Yogyakarta-SurakartaMalang-Surabaya Jakarta-Cirebon-Bandung-Yogyakarta-SemarangSurabaya-Malang Jakarta-Cirebon-Bandung-Yogyakarta-SemarangSurakarta-Malang Jakarta-Cirebon-Yogyakarta-Surakarta-MalangSurabaya-Semarang Jakarta-Cirebon-Bandung-Yogyakarta-SurakartaSemarang-Surabaya-Malang Jakarta-Cirebon-Semarang-Surabaya-MalangSurakarta Jakarta-Cirebon-Yogyakarta-Semarang-SurabayaMalang-Surakarta Jakarta-Bandung-Cirebon-Yogyakarta-SurakartaMalang-Surabaya-Semarang Jakarta-Cirebon-Bandung-Yogyakarta-SemarangSurakarta-Malang-Surabaya Jakarta-Cirebon-Semarang-Surabaya-MalangSurakarta-Yogyakarta Jakarta-Bandung-Yogyakarta-Cirebon-SemarangSurabaya Jakarta-Bandung-Cirebon-Semarang-SurabayaMalang-Surakarta Jakarta-Bandung-Yogyakarta-Surakarta-MalangSurabaya-Semarang Jakarta-Bandung-Cirebon-Yogyakarta-SemarangSurabaya-Malang-Surakarta Jakarta-Bandung-Yogyakarta-Semarang-SurabayaMalang-Surakarta Jakarta-Bandung-Cirebon-Semarang-SurabayaMalang-Surakarta-Yogyakarta
1158
11
757
24
Jakarta-Cirebon-Semarang-Yogyakarta-Surakarta
801
25
804
26
Jakarta-Bandung-Cirebon-Semarang-Yogyakarta Jakarta-Bandung-Cirebon-Yogyakarta-SemarangSurakarta
27
Jakarta-Cirebon-Bandung-Yogyakarta
820
28
Jakarta-Bandung-Yogyakarta-Semarang-Surakarta Jakarta-Bandung-Cirebon-Semarang-SurakartaYogyakarta
849
853
31
Jakarta-Bandung-Yogyakarta-Cirebon Jakarta-Bandung-Cirebon-Semarang-YogyakartaSurakarta
32
Jakarta-Cirebon-Bandung-Yogyakarta-Surakarta
880
29 30
806
852
864
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
33
Jakarta-Cirebon-Yogyakarta-Bandung
910
80
34
Jakarta-Cirebon-Bandung-Yogyakarta-Semarang
929
81
35
967
82
36
Jakarta-Cirebon-Yogyakarta-Surakarta-Malang Jakarta-Cirebon-Bandung-Yogyakarta-SurakartaSemarang
977
83
37
Jakarta-Cirebon-Semarang-Surabaya
997
84
38
Jakarta-Cirebon-Yogyakarta-Semarang-Surabaya Jakarta-Cirebon-Bandung-Yogyakarta-SemarangSurakarta Jakarta-Bandung-Cirebon-Yogyakarta-SurakartaMalang
1011
85
1026
86
1030
87
Jakarta-Bandung-Yogyakarta-Semarang-Cirebon Jakarta-Cirebon-Yogyakarta-Surakarta-SemarangSurabaya
1057
88
1059
89
Jakarta-Bandung-Cirebon-Semarang-Surabaya Jakarta-Cirebon-Yogyakarta-Surakarta-MalangSurabaya
1060
90
1061
91
1073
92
46
Jakarta-Bandung-Yogyakarta-Surakarta-Malang Jakarta-Bandung-Cirebon-Yogyakarta-SemarangSurabaya
1074
93
47
Jakarta-Cirebon-Semarang-Surabaya-Malang
1091
94
48
Jakarta-Cirebon-Semarang-Surakarta-Malang Jakarta-Cirebon-Yogyakarta-Semarang-SurabayaMalang Jakarta-Bandung-Yogyakarta-Surakarta-SemarangCirebon Jakarta-Cirebon-Yogyakarta-Semarang-SurakartaMalang
1099
95
1105
96
1105
97
39 40 41 42 43 44 45
49 50 51
1113
1162 1162 1165 1167 1168 1171 1176 1193 1207 1211 1216 1219 1234 1250 1255 1256 1259 1265 1270 1294 1313 1328 1342 1344 1388 1396 1426 1436 1461 1475 1489 1490 1521 1523 1524 1532 1538 1581 1584
98 99 100 101 102 103 104 105 106 107
Jakarta-Bandung-Yogyakarta-Cirebon-SemarangSurabaya-Malang Jakarta-Bandung-Yogyakarta-Cirebon-SemarangSurakarta-Malang Jakarta-Cirebon-Bandung-Yogyakarta-SurakartaMalang-Surabaya-Semarang Jakarta-Bandung-Yogyakarta-Cirebon-SemarangSurakarta-Malang-Surabaya Jakarta-Cirebon-Bandung-Yogyakarta-SemarangSurabaya-Malang-Surakarta Jakarta-Bandung-Yogyakarta-Surakarta-MalangSurabaya-Semarang-Cirebon Jakarta-Cirebon-Semarang-Surabaya-MalangSurakarta-Yogyakarta-Bandung Jakarta-Bandung-Yogyakarta-Cirebon-SemarangSurabaya-Malang-Surakarta Jakarta-Bandung-Yogyakarta-Surakarta-MalangSurabaya-Semarang-Cirebon-Jakarta Jakarta-Cirebon-Semarang-Surabaya-MalangSurakarta-Yogyakarta-Bandung-Jakarta
1617 1625 1709 1719 1758 1837 1894 1987 2164 2164
E. KESIMPULAN Penggunaan RBFS dalam mencari rute terpendek terbaik untuk kasus ini dengan kota asala Jakarta adalah jalur :
Jakarta – Cirebon – Semarang – Surabaya – Malang – Surakarta – Yogyakarta – Bandung Jakarta atau jalur sebaliknya dengan pangjang rute adalah 2164 km. Sampel aplikasi bisa diakses di alamat http://lab.elangsakti.com/tsp/ .
F. REFERENSI Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48. Russell, S. J., Norvig, P, Artificial Intelligence: A Modern Approach, 2003.
