Jurnal Matematika Vol.
16 No.
2 Desember 2017
ISSN: 1412-5056 / 2598-8980
https://ejournal.
Diterima: 19/08/2017 Disetujui: 21/11/2017 Publikasi Online: 26/05/2018 Penyelesaian Travelling Salesman Problem (TSP) Menggunakan Algoritma Hill Climbing dan MATLAB Muhammad Irfan Fakultas Keguruan dan Ilmu Pendidikan.
Universitas Sarjanawiyata Tamansiswa irfan@ustjogja.
Abstrak.
Travelling Salesman Problem (TSP) adalah permasalahan dimana seorang salesman harus mengunjungi semua kota yang mana tiap kota hanya dikunjungi sekali, dan harus kembali ke kota Masalah utama yang dihadapi sebuah TSP adalah bagaimana mencari rute terpendek dari perjalanan seorang salesman dengan biaya minimum.
Penelitian ini bertujuan untuk mengetahui penyelesaian masalah TSP dengan menggunakan algoritma Hill Climbing baik Simple Hill Climbing (SHC) maupun Steepest-Ascent Hill Climbing (SAHC).
Berdasarkan hasil kajian teori yang dilakukan, dapat disimpulkan bahwa algoritma Hill Climbing dapat digunakan untuk menyelesaikan TSP.
Algoritma Hill Climbing dalam menyelesaikan masalah TSP yaitu: menentukan initial state, melakukan pengujian panjang lintasan, melakukan kombinasi penukaran dua kota, dan kemudian melakukan pengujian terhadap nilai heuristiknya.
Penyelesaian masalah TSP dengan menggunakan algoritma Hill Climbing masing-masing mempunyai karakteristik yang berbeda-beda.
Dalam menyelesaikan masalah TSP.
SHC memilih keadaan yang lebih baik tanpa melakukan pengujian dikombinasi pertukaran kota pada iterasi yang sama.
Sedangkan SAHC membandingkan keadaan yang lebih baik sebelum memilih keadaan tersebut sebagai new state.
Selanjutnya untuk membantu proses komputasi pada saat menyelesaikan TSP, dibuat sebuah program dengan model algoritma Hill Climbing menggunakan MATLAB.
Program yang terbentuk memberikan solusi berupa rute perjalanan yang disajikan dalam bentuk diagram.
Kata kunci: Algoritma.
Hill Climbing.
Travelling Salesman Problem Abstract.
(Completion of Traveling Salesman Problem (TSP) Using the Hill Climbing and MATLAB Algorithm.
Traveling Salesman Problem (TSP) is a problem where a salesman must visit all cities where each city is visited only once, and he/she must return to the hometown.
The main problem facing a TSP is how to find the shortest route of a sales trip with minimum cost.
This study aims to determine the solution of TSP problems using Hill Climbing algorithm both Simple Hill Climbing (SHC) and Steepest-Ascent Hill Climbing (SAHC).
Based on the result of the theoretical study, it can be concluded that Hill Climbing algorithm can be used to solve TSP.
Hill Climbing algorithm in solving TSP problem is: determining initial state, conducting track length test, performing combination of two city exchanges, and then testing the heuristic value.
TSP problem solving using Hill Climbing algorithm each have different characteristics.
In solving the TSP problem.
SHC chooses a better state, without performing tests in combination of city exchanges on the same iteration.
While SAHC compares the situation better before choosing the state as a new state.
Furthermore, to assist the computing process when completing the TSP then made a program model Hill Climbing algorithm using MATLAB language.
The program is formed to provide solutions in the form of travel routes presented in the form of diagrams.
Keywordsi: Algorithm.
Hill Climbing.
Travelling Salesman Problem Muhammad Irfan Pendahuluan Setiap hari manusia dihadapkan pada banyak permasalahan hidup yang semakin kompleks dan terkadang sering menjadi terbiasa dengan permasalahan tersebut, karena permasalahan tersebut selalu muncul di dalam setiap aktivitas.
Salah satu dari permasalahan tersebut adalah pencarian rute Sebagai contoh sebuah perusahaan akan membangun instalasi air bersih menggunakan pipa-pipa untuk mendistribusikan air barsih dari kota satu ke kota yang lain maka perusahaan tersebut akan mencari jarak terpendek untuk meminimumkan biaya.
Contoh lain misalnya sebuah perusahaan tekstil yang mendapat pesanan dalam skala besar dan kondisi perusahaan tersebut mempunyai beberapa mesin penghasil kain dengan kemampuan tertentu dalam menghasilkan jenis kain yang berbeda maka diperlukan suatu strategi jitu untuk memenuhi pesanan sehingga menghasilkan keuntungan maksimal tetapi dengan biaya produksi minimum.
Untuk menyelesaikan masalah tersebut, berbagai disiplin ilmu mengembangkan metode-metode untuk menyelesaikan kasus pencarian rute terpendek, salah satunya yaitu Artificial Intelegence (AI).
Artificial Intelegence sebagai cabang ilmu yang berusaha memahami kecerdasan manusia menyajikan bermacam-macam pokok bahasan di antaranya adalah teknik pencarian atau searching.
Metode pencarian dibedakan menjadi dua jenis yaitu metode pencarian buta/tanpa informasi atau blind/uninformed search dan metode pencarian heuristik/dengan informasi atau heuristic/informed search.
Alasan digunakannya kata blind atau buta pada jenis pertama metode pencarian karena tidak adanya informasi awal yang digunakan untuk awal proses pencarian sedangkan kata heuristik pada jenis kedua mengandung arti bahwa metode pencarian jenis ini mempunyai informasi awal sebagai acuan untuk melakukan proses selanjutnya dan metode ini juga mempunyai aturan tertentu dalam proses pencariannya untuk mencapai tujuan.
Dalam metode pencarian heuristik terdapat bermacam-macam teknik pencarian dan salah satunya adalah Hill Climbing (Pendakian Buki.
Teknik pencarian Hill Climbing (HC) dibagi menjadi dua jenis yaitu Simple HC (HC sederhana ) dan Steepest-Ascent HC ( HC dengan memilih kemiringan yang paling tajam/cura.
(Suyanto, 2007 : .
Dengan menggunakan metode pencarian HC diharapkan dapat memberikan solusi pada masalahan optimasi.
Untuk membantu perhitungan dalam penyelesaian masalah optimasi maka dibuatlah suatu algoritma HC yang diimplementasikan dengan MATLAB untuk mempermudah perhitungan dan akan diaplikasikan untuk mencari solusi beberapa masalah optimasi.
Algoritma HC menjadi salah satu cara yang dapat menjadi alternatif pilihan untuk menyelesaikan masalah TSP, karena algoritma ini dapat dengan cepat menemukan rute terdekat dari suatu permasalahan yang ada.
Akan tetapi, algoritma ini juga mempunyai beberapa kelemahan Ae kelemahan.
Oleh karena itu, algoritma ini menjadi sesuatu hal yang menarik untuk dapat dibahas dan di kaji kelebihan dan kelemahan dari dua metode, yaitu simple hill climbing (SHC) dan steepest ascent hill climbing (SAHC).
1 Travelling Salesman Problem Permasalahan TSP (Traveling Salesman Proble.
adalah permasalahan di mana seorang salesman harus mengunjungi semua kota di mana tiap kota hanya dikunjungi sekali, dan dia harus mulai dari dan kembali ke kota asal.
Tujuannya adalah menentukan rute dengan jarak total atau biaya yang paling minimum.
Selain masalah sarana transportasi, efisiensi pengiriman surat atau barang ditentukan pula oleh lintasan yang diambil untuk mengirimkan surat atau barang tersebut.
Oleh karena itu solusi optimal dari permasalahan TSP ini, akan sangat membantu perusahaan pengiriman surat atau barang untuk mengefisienkan proses pengiriman barang, baik dari segi waktu maupun dana.
2 Algoritma Hill Climbing Hill Climbing merupakan salah satu metode yang masuk ke dalam metode pencarian heuristik.
Jurnal Matematika Vol.
16 No.
Desember 2017
ISSN: 1412-5056 | 2598-8980
Penyelesaian Travelling Salesmen Problem (TSP) .
Metode pencarian heuristic/informed pencarian solusinya dilakukan menggunakan keadaan awal .
nitial stat.
dan aturan produksi berupa fungsi heuristik .
uatu fungsi untuk menghitung nilai atau biaya perkiraan dari suatu solusi permasalah yang dicar.
sebagai modal untuk melakukan iterasi menuju goal state.
Hill Climbing (HC) dibagi menjadi dua bagian, yaitu: Simple Hill Climbing (SHC) dan SteepestAscent Hill Climbing (SAHC).
Secara garis besar, langkah Ae langkah dari HC adalah sebagai berikut:
Dibentuk lintasan awal sebagai keadaan awal .
nitial stat.
, kemudian dilakukan pengujian dari keadaan awal tersebut.
Pengujian dilakukan dengan menghitung total jarak yang ditempuh pada initial state.
Pengujian tersebut dilakukan untuk mendapatkan nilai heuristik sebagai pembanding terhadap nilai Ae nilai heuristik yang ada setelah dilakukan kombinasi pertukaran dua kota.
Hasil dari pengujian tersebut adalah jarak minimal yang ditempuh pada permasalahan TSP.
Hasil tersebut akan digunakan sebagai pembanding hasil dari langkah berikutnya.
Setelah dibentuk lintasan awal sebagai keadaan awal, langkah selanjutnya yaitu melakukan kombinasi penukaran dua kota kemudian dilakukan pengujian seperti pada poin a, hingga mencapai kondisi goal, jika tidak maka pilihlah elemen yang lain hingga mencapai goal.
Kondisi goal diartikan sebagai keadaan yang merupakan solusi optimum dari permasalahan TSP dengan kondisi: panjang jalur baru < panjang jalur lama.
Jika kondisi goal telah tercapai maka kondisi tersebut adalah solusinya, jika tidak, maka bukan Hasil dan Pembahasan 1 Algoritma Simple Hill Climbing dalam Menyelesaikan TSP Algoritma SHC untuk menyelesaikan masalah TSP adalah:
Evaluasi initial state.
Jika initial state adalah goal state maka jadikan state ini sebagai solusi dan keluar dari program.
Jika bukan goal state, lanjutkan proses dengan initial state sebagai current Ulangi sampai solusi ditemukan atau sampai tidak ada operator baru yang dapat diaplikasikan terhadap current state:
Pilih operator yang belum diaplikasikan terhadap current state dan aplikasikan operator tersebut sehingga menghasilkan new state.
Evaluasi new state :
Jika state ini merupakan goal state maka jadikan state ini sebagai solusi dan keluar dari Jika state ini bukan goal state tetapi lebih baik dari current state maka jadikan state ini sebagai current state baru.
Jika state ini tidak lebih baik dari current state maka kembali ke langkah 2.
Gambar 1.
Chinese Postman Problem Jurnal Matematika Vol.
17 No.
1 Mei 2018
ISSN: 1412-5056 | 2598-8980
Muhammad Irfan 2 Persoalan Tukang Pos Cina (Chinese Postman Proble.
Seorang tukang pos akan mengantar surat ke alamat-alamat sepanjang jalan di suatu daerah.
Bagaimana ia merencanakan rute perjalanannya supaya ia melewati setiap jalan tepat sekali dan kembali lagi ke tempat awal keberangkatan.
Gambar 2.
Diagram SHC Karena sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding nilai heuristik CABDEC=12, maka node CABDEC =12 adalah lintasan terpendek (SOLUSI).
Tukang pos tersebut dalam mengantar surat ke alamat-alamat yang dituju agar menempuh rute terpendek harus menempuh rute dari C Ae A Ae B Ae D Ae E - C dengan panjang lintasan yaitu 12 km.
Berikut adalah penggalan script dengan menggunakan MATLAB untuk menyelesaikan TSP dengan algoritma SHC.
%Iterasi Initial_State = 0.
Initial_State_Awal = 0.
PjgJalur = PjgJalur_Awal.
%Matrik kombinasi operator tukar dua kota a = combntns.
:N,.
Banyak_Operator = size.
disp(['Banyaknya operator penukaran kota = ' num2str(Banyak_Operato.
]).
disp('====================================').
A = zeros(Banyak_Operator,N).
%Matrik penukaran rute kota pada setiap level B = zeros(Banyak_Operator,.
%Matrik pjg_rute pada setiap level Iterasi = 1.
t = 1.
while Iterasi == 1.
Cur_Rute = Rute.
Cur_PjgJalur = PjgJalur.
disp(['Level ke ' num2str.
]).
it_level = 1.
i = 1.
while ( it_level == 1 ) & ( i <= Banyak_Operato.
Rute_1 = Rute.
b = a.
c = a.
d = Rute.
Rute.
= Rute.
Rute.
= d.
Initial_State = Initial_State_Awal.
Jurnal Matematika Vol.
17 No.
1 Mei 2018
ISSN: 1412-5056 | 2598-8980
Penyelesaian Travelling Salesmen Problem (TSP) .
for k = 1:1:(N-.
Initial_State = Initial_State D(Rute.
,Rute.
,k .
Initial_State = Initial_State D(Rute.
,N),Rute.
disp([' Rute >> ' num2str(Rut.
' Panjang Rute = ' num2str(Initial_Stat.
]).
if Initial_State < PjgJalur, it_level = 0.
PjgJalur = Initial_State.
Rute = Rute.
it_level = 1.
PjgJalur = PjgJalur.
Rute = Rute_1.
i = i 1.
if Cur_PjgJalur == PjgJalur.
Iterasi = 0.
Iterasi = 1.
disp([' **Rute terpendek sementara >> ' num2str(Rut.
' Panjang = ' num2str(PjgJalu.
]).
disp('====================================').
= toc.
t = t 1.
Rute_Terpendek = Rute.
Panjang_Rute_Terpendek = PjgJalur.
hold on P = X(Rute_Terpendek,:).
P = [P.
,:)].
plot(P(:,.
,P(:,.
,'bo-','linewidth',1.
hold off disp(['Lama proses ( dalam detik ) = ' num2str.
ime(:,:)))]).
disp(['Optimum pada level ke ' num2str.
]).
3 Algoritma Steepest-Ascent Hill Climbing dalam Menyelesaikan TSP Berikut ini adalah algoritma dari Steepest Ae Ascent Hill Climbing (SAHC):
Evaluasi initial state.
Jika initial state adalah goal state maka jadikan state ini sebagai solusi dan keluar dari program.
Jika bukan goal state, lanjutkan proses dengan initial state sebagai current Ulangi sampai solusi ditemukan atau sampai tidak ada perubahan terhadap current state :
Misalkan SUK adalah suatu state yang menjadi suksesor dari current state.
Untuk setiap operator yang bisa dilakukan terhadap current state, kerjakan :
Aplikasikan semua operator yang ada, untuk menemukan new state.
Evaluasi new state.
Jika merupakan goal state, jadikan ini sebagai solusi dan keluar dari Jika bukan goal state, bandingkan dengan new state dengan SUK.
Jika new state lebih baik dari SUK maka ganti SUK dengan new state.
Jika new state tidak lebih baik dari SUK, tidak perlu diganti.
Jika SUK lebih baik dari current state maka ganti current state dengan SUK.
Pada permasalahan Tukang Pos Cina (Chinese Postman Proble.
yang sebelumnya, akan dicari solusinya dengan menggunakan SAHC.
Berikut adalah diagram dari iterasi Ae iterasi di atas:
Jurnal Matematika Vol.
17 No.
1 Mei 2018
ISSN: 1412-5056 | 2598-8980
Muhammad Irfan Gambar 3.
Diagram SAHC Karena sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding nilai heuristik DECABD=12, maka node DECABD=12 adalah lintasan terpendek (SOLUSI).
Sehingga tukang pos tersebut dalam mengantar surat ke alamat-alamat yang dituju agar menempuh rute terpendek harus menempuh rute dari D Ae E Ae C Ae A Ae B - D dengan panjang lintasan yaitu 12 km.
Berikut adalah penggalan script dengan menggunakan MATLAB untuk menyelesaikan TSP dengan algoritma SAHC.
%Iterasi Initial_State = 0.
Initial_State_Awal = 0.
PjgJalur = PjgJalur_Awal.
%Matrik kombinasi operator tukar dua kota a = combntns.
:N,.
Banyak_Operator = size.
disp(['Banyaknya operator penukaran kota = ' num2str(Banyak_Operato.
]).
disp('====================================').
A = zeros(Banyak_Operator,N).
%Matrik penukaran kota pada setiap level B = zeros(Banyak_Operator,.
%Matrik pjg_rute pada setiap level Iterasi = 1.
t = 1.
while Iterasi == 1, disp(['Level ke ' num2str.
]).
Rute_1 = Rute.
for i = 1:1:Banyak_Operator, b = a.
c = a.
d = Rute.
Rute.
= Rute.
Rute.
= d.
,:) = Rute.
Initial_State = Initial_State_Awal.
for k = 1:1:(N-.
Initial_State = Initial_State D(A.
,A.
,k .
Initial_State = Initial_State D(A.
,N),A.
,:) = Initial_State.
disp([' Rute >> ' num2str(Rut.
' Panjang Rute = ' num2str(Initial_Stat.
]).
Initial_State = Initial_State_Awal.
Rute = Rute_1.
C = [A B].
Jurnal Matematika Vol.
17 No.
1 Mei 2018
ISSN: 1412-5056 | 2598-8980
Penyelesaian Travelling Salesmen Problem (TSP) .
e = C.
,size(C,.
Rute = C.
,1:N).
for l = 1:1:Banyak_Operator, if C.
,size(C,.
) < e, e = C.
,size(C,.
Rute = C.
,1:N).
e = e.
Rute = Rute.
if e < PjgJalur.
Iterasi = 1.
PjgJalur = e.
Rute = Rute.
Iterasi = 0.
PjgJalur = PjgJalur.
Rute = Rute_1.
disp([' **Rute terpendek sementara >> ' num2str(Rut.
' num2str(PjgJalu.
]).
disp('====================================').
t = t 1.
= toc.
Rute_Terpendek = Rute.
Panjang_Rute_Terpendek = PjgJalur.
hold on P = X(Rute_Terpendek,:).
P = [P.
,:)].
plot(P(:,.
,P(:,.
,'bo-','linewidth',1.
hold off disp(['Lama proses ( dalam deti.
= ' num2str.
ime(:,:)))]).
disp(['Optimum pada level ke ' num2str.
]).
Panjang = ' Dari hasil analisis rute terpendek dengan menggunakan MATLAB tersebut, maka hasil tersebut dapat disajikan dalam bentuk tabel sebagai berikut:
Tabel 1.
Analisis Rute Terpendek No.
Banyak Panjang rute
10,2333
29,5368
48,9862
76,0776
145,4273
727,6823
SHC
Lama proses .
0,076508 1,3792 7,3775 19,676 43,9535 427,1647 Optimum Level ke0 Panjang 10,2333 29,3997 45,0327 73,0083 129,0912 669,0115 SAHC Lama proses .
0,076508 1,7662 6,1237 17,8481 50,0819 473,6006 Optimum Level ke0 Dari tabel 1, terlihat perbandingan hasil dari SHC dengan SAHC, baik panjang rute, lama proses perhitungan, dan level optimumnya.
Pencarian solusi TSP dengan menggunakan metode SAHC membutuhkan waktu lebih lama, akan tetapi panjang rute yang diperoleh serta pencapaian optimumnya lebih baik dari pada SHC.
Jurnal Matematika Vol.
17 No.
1 Mei 2018
ISSN: 1412-5056 | 2598-8980
Muhammad Irfan Kesimpulan Berdasarkan hasil pembahasan mengenai penyelesaian TSP menggunakan algoritma Hill Climbing, maka dapat disimpulkan bahwa: .
Algoritma Hill Climbing dapat digunakan untuk menyelsaikan TSP.
Baik SHC maupun SAHC mempunyai dasar yang sama, yaitu kombinasi penukaran dua kota.
Dalam melakukan pengujian panjang rute SHC dikerjakan dari kiri ke kanan.
Ketika ada panjang rute yang lebih kecil dari pada yang sebelumnya, maka nilai dan lintasan tersebut menjadi new state dan iterasi berhenti.
Sedangkan SAHC harus membandingkan nilai heuristik dari seluruh lintasan dan dipilih nilai heuristik yang terkecil untuk dijadikan new state.
Dari kedua metode tersebut.
SAHC lebih efektif dalam menyelesaikan masalah TSP dibandingkan dengan SHC.
Hanya saja SAHC membutuhkan waktu yang lebih lama dari pada SHC dalam proses pencarian solusi.
Referensi