OPTIMASI PENENTUAN TEMPAT KOST MENGGUNAKAN METODE TRAVELLING SALESMAN PROBLEM (TSP) Teo Sulaksono1), Eneng Tita Tosida1), Sufiatul Maryana1). Email:
[email protected] 1) Program Studi Ilmu Komputer FMIPA Universitas Pakuan Bogor
ABSTRAK Tempat kost merupakan suatu kebutuhan pokok bagi mahasiswa, khususnya mahasiswa perantau. Dalam memilih tempat kost, para mahasiswa sering kebingungan dalam hal kenyamanan, harga, dan tentu saja jarak serta waktu tempuh dari kampus ke tempat kost, juga sebaliknya. Jarak antara tempat kost ke kampus dan sebaliknya sangat berpengaruh bagi kelancaran perkuliahan seorang mahasiswa. jika jarak semakin pendek, maka waktu yang dibutuhkan mahasiswa untuk sampai ke kampus lebih sedikit. Namun, jika jarak antara tempat kost ke kampus semakin jauh, maka semakin banyak juga waktu yang dibutuhkan. Untuk itu diperlukan penentuan rute yang tepat agar dapat menekan waktu tempuh seminimal mungkin. Maka dari itu penelitian ini dilakukan guna membantu pengguna dari segi navigasi agar dapat lebih optimal dalam pencarian kost-kostan, dengan metode mencari jalur terpendek dari simpul-simpul yang tersimpan di database. Dengan adanya pembuatan aplikasi ini diharapkan mampu membantu para mahasiswa untuk memudahkan dalam pencarian tempat tinggal sementara/kost-kostan di sekitar kampus Universitas Pakuan. Kata Kunci: Travelling Salesman Problem, Shortest path, Node,Rute. banyak pula waktu yang dibutuhkan. Untuk itu diperlukan penentuan rute yang tepat agar dapat menekan waktu tempuh seminimal mungkin. Penelitian sebelumnya telah disusun oleh (I Wayan, 2011) “Analisis Delivery Route (City Courier) di Wilayah Bandung Selatan Dengan Menggunakan Metode Travelling Salesman Problem (TSP) di PT. Dakota Logistik dan Ekspress”. Dalam penelitian ini dijelaskan bahwa metode TSP mempermudah perusahaan untuk mengoptimalisasi biaya dengan menentukan jarak terdekat yang dilalui oleh kurir perusahaan. Lalu penelitian yang dilakukan (Helni, 2012) “Analisis dan Perancangan Sistem Web Kos-Kosan Berbasis Client/Server Sebagai Sarana Pelayanan Jasa dan
I. PENDAHULUAN 1. Latar Belakang Tempat kost merupakan suatu kebutuhan pokok bagi para mahasiswa, khususnya mahasiswa perantau. Dalam memilah tempat kost, para mahasiswa sering kebingungan dalam hal kenyamanan, harga, dan tentu saja jarak serta waktu tempuh dari kampus ke tempat kost, juga sebaliknya. Jarak antara tempat kost ke kampus dan kampus ke tempat kost sangat berpengaruh bagi kelancaran perkuliahan seorang mahasiswa. Jika jarak semakin pendek, maka waktu yang dibutuhkan mahasiswa untuk sampai ke kampus lebih sedikit. Namun, jika jarak antara tempat kost dan kampus semakin jauh, semakin 1
Informasi”. Pada penelitian ini dijelaskan bagaimana agar user bisa berperan sebagai pencari jasa (calon penyewa kos-kosan) atau melayani jasa (pemilik kosan). Selanjutnya (Dahlan, 2013) “Sistem Tracer Paket pada Unit Processing Center Pos Indonesia (PERSERO) Menggunakan Metode Travelling Salesman Problem”. Dalam penelitian ini peneliti berhasil memecahkan masalah yang dihadapi oleh kurir dari kantor Pos Indonesia untuk menghemat waktu dan biaya dalam perjalanan mengantarkan surat dengan metode Graph-Travelling Saleman Problem (TSP). Maka dari itu penelitian ini dibuat untuk membantu pengguna dari segi navigasi agar dapat lebih optimal dalam pencarian kos-kosan, dengan metode mencari jalur terpendek dari simpulsimpul yang tersimpan di database. Dengan adanya pembuatan aplikasi ini diharapkan mampu membantu para mahasiswa untuk memudahkan dalam pencarian tempat tinggal sementara/koskosan di sekitar kampus Universitas Pakuan. . 2. Tujuan
3. Data yang digunakan dalam sistem ini adalah hasil tinjauan langsung ke lapangan (rute, data jarak, dan data tempat kost yang ada di dekat kampus Universitas Pakuan). 4. Bahasa pemrograman yang akan digunakan dalam pembuatan aplikasi ini yaitu Php dengan Adobe Dreamweaver CS6 sebagai perangkat lunak pengembang aplikasi berbasis website. 4. Manfaat Manfaat dari penelitian ini adalah: 1. Mempermudah mahasiswa untuk mencari kost-kostan di sekitar kampus. 2. Menghemat waktu dan tenaga ketika akan mencari kost-kostan, karena sudah diterapkan metode TSP untuk mencari rute terdekat. 3. Sebagai sumber referensi untuk penelitian selanjutnya. II. TINJAUAN PUSTAKA 1. Algoritma Algoritma adalah urutan langkahlangkah logis penyelesaian masalah yang disusun secara sistematis. Langkahlangkah logis berarti kebenarannya harus dapat ditentukan benar atau salah (Munir, 1999). Langkah-langkah di dalam algoritma harus logis, ini berarti hasil dari urutan langkah-langkah tersebut harus dapat ditentukan, benar atau salah. Langkah-langkah yang tidak benar dapat memberikan hasil yang salah.
Tujuan dari penelitian ini adalah untuk Optimasi Penentuan Tempat Kost Menggunakan Metode Travelling Salesman Problem. 3. Ruang Lingkup Ruang lingkup penelitian ini meliputi: 1. Form input meliputi titik awal dan titik akhir (tujuan), proses meliputi perhitungan jarak terpendek menggunakan algoritma TSP, output berupa jarak terpendek yang dihasilkan dari perhitungan algoritma TSP. 2. Rute awal di dalam aplikasi ini mengacu pada titik yang telah ditentukan sebagai tempat perkuliahan (kampus).
2. Travelling Salesman Problem (TSP) TSP (Travelling Salesman Problem) adalah permasalahan dimana seorang salesman harus mengunjungi semua kota dimana 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. 2
dokumen masukan, dokumen keluaran dan simpanan data.
III. METODE PENELITIAN 1. Tahapan Penelitian Tahapan dalam melakukan penelitian ini dilakukan dengan metodeSystem Development Life Cycle (SDLC).
4. Perancangan Tahap perancangan adalah membuat spesifikasi secara rinci mengenai arsitektur program, gaya, tampilan dan kebutuhan material / bahan untuk program. 1. Sistem dirancang dengan menggunakan Flowchart yaitu untuk menentukan proses input dan dan proses output dalam sistem. Berikut adalah flowchart untuk front end dan back end dalam sistem. 2. Menentukan titik-titik dalam graf. 3. Menentukan rute-rute yang bisa dilewati dari titik awal (kampus) ke titik-titik selanjutnya. 4. Menentukan rute terpendek atau nilai minimumnya dengan menggunakan algoritma TSP.
Perencanaan
Analisis
Perancangan
Implementasi
Uji Coba
Valid
5. Implementasi Tahap implementasi merupakan tahap yang dilakukan jika kebutuhan penggunaan sistem sudah terpenuhi. Pada tahap ini aplikasi sudah bisa dijalankan dan digunakan.
Penggunaan
Gambar 1. Tahapan SDLC 2. Perencanaan Tahap perencanaan merupakan tahapan untuk memperoleh data-data pendukung dalam pembuatan sistem. Sistem penyedia layanan tempat kost ini melakukan pengamatan terhadap data yang diteliti, wawancara dengan beberapa penghuni tempat kost yang berada di daerah kampus di kota Bogor.
6. Uji Coba Pada tahap ini dilakukan pengujian masing–masing fitur dan fungsi untuk mengetahui apakah aplikasi bekerja dengan semestinya. Jika aplikasi belum berjalan sesuai fungsinya maka dilakukan penganalisaan ulang terhadap sistem berjalan sehingga aplikasi dapat berjalan sesuai fungsinya. Rancangan program usulannya menggunakan Dreamweaver dan untuk database menggunakaan Mysql yang terdapat pada paket Xampp.
3. Analisis Tahap analisis merupakan tahap yang dilakukan setelah melakukan pengumpulan data. Data dianalisa dan dikelompokan sesuai dengan kebutuhan sistem yang berjalan yaitu terdiri dari
7. Waktu dan Tempat Penelitian
3
Dalam pelaksanaan penelitian ini dilakukan dalam kurun waktu tiga bulan yaitu terhitung dari bulan Juni 2015 sampai dengan Agustus 2015. Penelitian ini dilakukan di Laboraturium Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Pakuan, Bogor. IV. PERANCANGAN IMPLEMENTASI
Tabel 2. Verteks dalam graph. No.
Nama Kostan
Harga
Gender
Verteks Asal
1. 2. 3. 4. 5.
Melati Wanda Gladiol Paviliun Abi
600.000/bln 500.000/bln 600.000/bln 900.000/bln 500.000/bln
Perempuan Perempuan Laki-Laki L/P L
B S F C L
DAN 3. Akuisisi Data Jarak Antar Verteks. Setelah dilakukan penentuan vertex yang akan digunakan dalam graph, langkah selanjutnya yaitu mencari nilai jarak antara vertex-verteks dengan menggunakan google maps.
Berikut pencarian rute terpendek dengan metode Travelling Salesman Problem (TSP) dengan pendekatan Dijsktra dan Greedy. Langkah – langkah yang diperlukan adalah seperti berikut : 1. Menentukan Verteks Dalam Graph Dalam penelitian ini, vertex yang digunakan berupa wilayah/kompleks yang sekiranya terdapat banyak kos-kosan. dan memiliki range jarak 1,5 Km ke Kampus. Tabel 1. Verteks dalam graph Nama Wilayah Gerbang Pakuan Gg. Jembatan
Inisial Node
Jarak
Banyak Tempat Kost
A1
-
Tidak Ada
3.
F. Teknik
F
4.
Gg. Mesjid
L
5.
Gg. Padi
S
No. 1. 2.
B
133 meter 504 meter 408 meter 546 meter
Gambar 2. Map Kost-Kostan Gambar diatas adalah proses penentuan jarak antara satu vertex dengan yang lainnya. Penentuan jarak menggunakan bantuan aplikasi dari Google yaitu Google Maps. pada contoh gambar diatas ditentukan jarak antara vertex A1 ke A2 yaitu 120 Meter.
8 3 7 5
4. Pembuatan Model Peta Wilayah Kost Sekitar Universitas Pakuan.
2. Menentukan Kost-Kostan
Setelah penentuan dan penyeleksian data pada ketiga tahap diatas, selanjutnya adalah membuat graph atau model peta wilayah yang akan digunakan pada sistem. Model peta ini dibuat menggunakan Microsoft Visio 2007. Berikut adalah graph yang telah dibuat:
Setelah menentukan vertex yang akan digunakan dalam sistem, selanjutnya dilakukan pemilihan kost-kostan yang ada pada wilayah tersebut dengan batasan harga sewa dibawah satu juta rupiah. Berikut beberapa kost-kostan yang ditentukan:
4
Tabel 4. Mengisi bobot pada matriks perhitungan TSP.
P 561 209
334
N o d e S t a t u s B o b o t
I 540
64
Q
287
J
K
449
O
334
230 247
211
A3
H
A4
N
F 86
75
119
KAMPUS
201
189 M
407
L 368
A1
73
A2 174
E 129
61
302 162
133 R
G
B 78 338
S
923 C
Keterangan: · A1 – A4 · B–S
: Gerbang Universitas Pakuan : Wilayah disekitar Universitas Pakuan yang terdapat beberapa kost-kostan
JALAN TOL 241 D
Gambar 3. Model Peta
A 1
A 2
A 3
A 4
B
C
D
E
F
G
H
I
J
K
L
M N
O
P
Q
R
S
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-
1 7 4
8 6
-
1 3 3
-
-
-
-
-
-
-
-
-
4 8 0
-
-
-
-
7 4 1
4 6 8
-
2. Cari jarak terpendek antara A1 dengan node yang berhubungan, lalu inisialisasikan status menjadi ‘1’.
Pada gambar di atas, ada 22 titik/node yang dipetakan untuk dihitung jarak terpendeknya. Dalam model peta diatas juga telah dicantumkan bobot jarak antara node-node.
Tabel 5. Contoh proses awal perhitungan TSP
5. Penerapan Metode TSP (algoritma Djikstra)
N o d e S t a t u s B o b o t P r e d o s e s o r
Setelah menentukan graf, maka selanjutnya adalah dilakukan perhitungan dengan mencari jarak yang tersedia dari titik asal yang dipilih. Untuk algoritma Dijkstra, hal pertama yang harus dilakukan adalah memilih jarak terpendek dari titik asal ke beberapa titik yang tersedia dan selanjutnya membuat tabel Iterasinya. 1. Langkah awal adalah status dari node yang belum terpilih diinisialisasikan dengan 0, dan yang sudah terpilih dengan 1. Misalkan dimulai dari A1. Tabel 3. Inisialisai node pada matriks perhitungan TSP.
A 1
A 2
A 3
A 4
B
C
D
E
F
G
H
I
J
K
L
M N
O
P
Q
R
S
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-
1 7 4
8 6
-
1 3 3
-
-
-
-
-
-
-
-
-
4 8 0
-
-
-
-
7 4 1
4 6 8
-
A 1
A 1
A 1
-
A 1
-
-
-
-
-
-
-
-
-
A 1
-
-
-
-
A 1
A 1
-
Dari tabel diatas, pilih node dengan bobot terkecil, dan statusnya ‘0’. Didapat yaitu node A3 = 86, untuk itu status node A3 berubah menjadi ‘1’ dan predosesor/ node sumber tetap A1, karena sumber terdekat dari node A3 adalah node A1. Selanjutnya dicari apakah ada node
Tentukan bobot dari node yang langsung berhubungan dengan predosesor/sumber yaitu node A1.
5
yang berhubungan dengan A3, yaitu node K dan A4. Ubah predosesor K dan A4 menjadi A3.
334
J
209
I
540
K
64
H A3
247
211 A4 119
86 A2
201
E
A1
302 G 923
B
338
Q
449
133 741
230 F
129
174
Tabel 6. Hasil perhitungan TSP pada matriks.
75
C
P
241
561
D
O
480 287
L 368 468
M R
189
N
78 S
Gambar 5. Graph untuk algoritma Greedy Terdapat enam jalur yang memungkinkan yaitu jalur A1-A3 dengan jarak 86, A1-A2 dengan jarak 174, A1-B dengan jarak 133, A1-Q dengan jarak 741, A1-L dengan jarak 480 dan A1-R dengan jarak 468. Jarak A1-A3 dipilih karena memiliki jarak yang terpendek atau minimum. Untuk jalur selanjutnya, cara perhitungan sama. Dan node yang sudah diseleksi tidak diperdulikan pada pencarian selanjutnya.
Dari tabel diatas bisa dilihat status K berubah menjadi ‘1’. Dan bobot node A4 dan K terisi, juga predosesornya yaitu A3. Sehingga: A
7. Flow Chart Sistem Data diagram flowchart menggambarkan alur informasi dan transformasi pada saat data bergerak dari input ke output. Flowchart menggambarkan alur sistem yang dibuat ke sebuah diagram dari simbol, gambar, dan keterangan untuk menjelaskan informasi tersebut. Yang dimulai dari (start) dari berakhir di (end).
1
A3
Gambar 4. Ilustrasi jarak yang diperoleh. Gambar diatas merupakan representasi jarak yang dihitung menggunakan algoritma Dijkstra. Untuk jarak keseluruhan, tahap yang dilakukan sama. Hingga ditemukan seluruh jarak yang optimal.
6. Penerapan Metode TSP (algoritma Greedy) Dalam perhitungan jarak terpendek menggunakan algoritma Greedy, mula mula proses berawal dari verteks A1 sebagai awal keberangkatan dan I sebagai titik akhir perjalanan. 6
Mulai
V. HASIL DAN PEMBAHASAN Pilih 1
Pilih 2
Pilih 3
Kost
Jarak
Logout
Login
1. Hasil Hasil dari penelitian ini adalah dengan menggunakan metode TSP (Travelling Salesman Problem) memakai algoritma Dijkstra dan algoritma Greedy untuk menentukan jarak terpendek antara kampus dan kost-kostan yang ada di sekitaran kampus. Analisis dilakukan dengan mengambil 72 kost-kostan dan 18 wilayah di sekitar Univ. Pakuan untuk dibandingkan jaraknya, antara algoritma Greedy dan algoritma Dijsktra. hasil analisis dapat dilihat dari Gambar 3 dan 4.
Username tidak
Tambah Kost
Tambah Jarak
Edit Kost
Edit Jarak
Delete Kost
Delete Jarak
Halaman logout
Password Selesai
Benar?
ya Database Menu Utama
Tampilan Berhasil
A
Pilihan: 1. Kost 2. Jarak 3. Logout
A
Gambar 6. Flowchart Back-End Flowchart Back-end yaitu hanya bisa diakses oleh website. dimana memanajemen isi website ini.
halaman yang administrator administrator dari halaman
Mulai
Halaman utama
Gambar 8. Hasil perhitungan algoritma Dijkstra.
1. Home 2. About 3. Cari Kost
A
Pilih 1
Pilih 2
Pilih 3
Keluar
Home
About
Cari Kost
Selesai
A
A
Input (A)*
Input (n)*
Gambar diatas menunjukkan hasil pencarian rute terpendek menggunakan algoritma dijkstra. Terlihat pada gambar form input asal diisi dengan A1 dan form input tujuan diisi dengan A4. Hasil yang diperoleh dari algoritma dijkstra menunjukan rute yang berawal dari node A1, lalu A2 dan terkahir A4. Jarak yang ditempuh dari node A1 menuju A4 yaitu sejauh 293 meter.
tidak
Sesuai?
Ya Database
Cari
Output
A
*A= Node Awal (Kampus) *n= Node Tujuan (Kostan)
Gambar 7. Flowchart Front-End
Gambar 9. Hasil Perhitungan Algoritma Greedy
7
Gambar diatas menunjukkan hasil pencarian rute terpendek menggunakan algoritma greedy. Terlihat pada gambar, form input asal diisi dengan A1 dan form input tujuan diisi dengan A4. Hasil yang diperoleh dari algoritma greedy menunjukkan rute yang berawal dari node A1, lalu A3 dan terakhir A4. Jarak yang ditempuh dari node A1 menuju A4 yaitu sejauh 297 meter.
Tabel 8. Uji Coba Fungsional
2. Uji Coba Struktural Uji coba struktural dilakukan untuk mengetahui apakah sistem yang dibuat sesuai dengan yang telah direncanakan.Uji coba struktural dapat dilihat pada:
N o
Form
1
Form login admin
2
Form data kost dan jarak admin Form node asal dan tujuan user Form hasil perhitun gan
3
Tabel 7. Uji Coba Struktural N o 1
Form
Action
Keterangan
Hasil
Form Login Admin
Input usernam e dan passwor d Input data kost dan jarak
login
Sesua i
Dapat menginputk an kost dan jarak yang baru Dapat memilih awal dan menentukan tujuan yang akan diinputkan nilainya Menampilka n hasil Atau jarak terpendek
Sesua i
2
Form data kost dan jarak admin
3
Form node asal dan tujuan user
4
Form hasil perhitung an
Input cari kost
-
4
Deskrip si Kebutu han Usernam e dan passwor d
Input data kost dan jarak Input cari kost
Hasil perhitun gan TSP
Fungsion al
Keteran gan
Masuk halaman jika benar dan sebalikny a jika salah Sebagai input data yang dibutuhka n sistem Sebagai input nilai jarak yang akan dicari Menampil kan hasil perhitung an
Berfungs i
Berfungs i
Berfungs i
Berfungs i
4. Uji Coba Validasi Uji coba validasi dilakukan untuk mengetahui keakuratan hasil data yang diolah pada sistem dengan hasil perhitungan manual.
Sesua i
Tabel 9. Tabel hasil perhitungan algoritma Dijkstra secara manual N o d e S t a t u s B o b o t P r e d o s e s o r
Sesua i
3. Uji Coba Fungsional Uji coba fungsional sistem berfungsi untuk mengetahui apakah sistem yang telah dibuat berfungsi dengan benar, pengujian ini dilakukan disetiap form sistem.
8
A 1
A 2
A 3
A 4
B
C
D
E
F
G
H
I
J
K
L
M N
O
P
Q
R
S
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-
1 7 4
8 6
2 9 3
1 3 3
4 7 1
7 1 2
3 0 3
5 0 4
6 0 5
3 7 8
6 9 3
3 5 9
1 5 0
4 8 0
8 4 8
1 0 3 7
1 3 2 4
1 1 9 0
7 4 1
4 6 8
5 4 6
A 1
A 1
A 1
A 2
A 1
B
C
A 2
E
E
E
J
K
A 3
A 1
L
M N
Q
A 1
A 1
R
Tabel di atas, menunjukan hasil perhitungan seluruh rute yang dilewati dengan menggunakan algoritma Dijkstra. Misalkan node tujuan kita adalah A4, node A4 memiliki predosesor = A2, dan A2 memiliki predosesor = A1, jadi rute yang dilalui dari A1 ke A4 adalah A1 => A2 => A4 dengan jarak 293 Meter. Predosesor pada tabel menunjukan node yang dilalui terakhir sebelum sampai pada node tujuan.
jarak asal. Berikut perhitungan manual dengan algoritma dijkstra. Tabel 10. Perhitungan node sama jarak N o d e S t a t u s B o b o t P r e d o s e s o r
A 1
A 2
A 3
A 4
B
C
D
E
F
G
H
I
J
K
L
M N
O
P
Q
R
S
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-
8 6
8 6
2 0 5
8 6
4 2 4
6 6 5
2 1 5
4 1 6
5 1 7
2 9 0
6 4 6
3 5 9
1 5 0
4 8 0
8 4 8
1 0 3 7
1 3 2 4
1 1 9 0
7 4 1
4 6 8
5 4 6
A 1
A 1
A 1
A 2
A 1
B
C
A 2
E
E
E
F
K
A 3
A 1
L
M N
Q
A 1
A 1
R
Pada Tabel di atas. hasil perhitungan tiga jarak yang sama, tidak jauh berbeda dengan graf yang sudah ada. Perbedaannya hanya terletak pada jarak yang didapat setiap node. Dalam menentukan jalur/rute dengan 3 node yang sama, algoritma dijkstra tetap mencari total jalur yang paling pendek (optimal) dari ketiga node yang sama tersebut ke node tujuan.
Gambar 10. Hasil Perhitungan Algoritma Greedy Secara Manual Gambar di atas. menunjukan hasil perhitungan seluruh rute yang dilewati dengan menggunakan algoritma Greedy. Misalkan node tujuan kita adalah A4, sesuai dengan prinsip algoritma Greedy, penentuan rute terpendek adalah memilih node dengan jarak paling minimum, dalam hal ini yaitu A3. Setelah node kedua dipilih, selanjutnya memeriksa node yang tersedia, dalam hal ini K dan A4. Jika tujuannya ditemukan, maka algoritma langsung menetapkan tujuan akhir, sehingga diperoleh A1 => A3 => A4 dengan jarak 297 Meter.
Gambar 11. Ilustrasi Perhitungan Node yang Mempunyai Jarak Sama Pada Gambar di atas, perhitungan diawali dari node awal yang menemukan tiga node yang mempunyai jarak yang sama. Pada kasus ini, algoritma dijkstra memeriksa node selanjutnya sampai bertemu node tujuan. Ketiga node yang mempunyai jarak yang sama, dieksekusi
5. Pengujian node sama jarak Pada tahap ini, dilakukan pengujian terhadap graf. Dimana diberikan tiga node yang mempunyai jarak yang sama dari
9
oleh algoritma berurutan. Yang dipilih sebagai node selanjutnya adalah node yang mempunyai jarak yang paling optimal ke tujuan. Pada Gambar di atas, node A1 adalah node asal. Node A4 adalah node tujuan. Dapat dilihat bahwa yang dipilih oleh node A1 yaitu node B. Karena node B mempunyai total jarak yang paling minimum untuk sampai ke node A4.
Dengan pendekatan algoritma Dijkstra dan Greedy. Setelah kedua algoritma dibandingkan, ternyata algoritma dijkstra medapatkan hasil rute yang lebih optimal. Walaupun algoritma greedy membutuhkan waktu yang lebih sedikit, tapi algoritma greedy tidak menghasilkan rute yang optimal dan ada node yang tidak ditemukan jalurnya. Sebaliknya, algoritma dijkstra mencari jalur secara menyeluruh dan menghasilkan rute yang paling optimal dari kandidat rute yang ada. Optimasi penentuan tempat kost menggunakan metode travelling saleman problem, memiliki kekurangan. Pertama, node yang digunakan dalam grafik berupa wilayah yang terdapat beberapa kostkostan. Kedua, ada node tujuan yang tidak ditemukan ketika memakai algoritma greedy.
6. Pengujian waktu komputasi Dari hasil percobaan perbandingan algoritma dijkstra dan algoritma greedy dalam sistem, didapatkan waktu komputasi sebagai berikut:
2. Saran Dari hasil penelitian ini algoritma Dijkstra dapat memberikan hasil optimal untuk menetukan rute terpendek dalam metode Travelling Salesman Problem. Sebagai saran, sistem ini dapat dikembangkan ke ruang lingkup yang lebih luas. Yaitu dengan menambahkan jarak atau verteks dalam cakupan yang lebih banyak. Menggunakan tempat kost sebagai node dalam grafik. serta mengimplementasikannya dengan bahasa pemrograman yang berbeda dan menggunakan algoritma yang berbeda pula.
Gambar 12. Perbandingan Waktu Komputasi Pada Gambar di atas, Algoritma dijsktra lebih membutuhkan waktu yang lebih lama dari algoritma greedy. Ratarata perbedaan waktu pada pengujian ini yaitu 0.1 detik. Namun, walaupun greedy mempunyai waktu yang singkat untuk perhitungan, rute yang didapatkan algoritma greedy tidak seoptimal yang di dapatkan oleh algoritma dijkstra.
DAFTAR PUSTAKA Abdullah, D. & Hardi, R. 2013.”Sistem Tracer Paket Pada Unit Processing Center Pos Indonesia (PERSERO) Menggunakan Metode Travelling Salesman Problem”.Aceh.
VI. KESIMPULAN DAN SARAN 1. Kesimpulan Optimasi penentuan tempat kost ini dirancang mengunakan entity relationship diagram (ERD). Menggunakan metode travelling salesman problem (TSP).
Amin, A.R. 2012. “Travelling Salesman Problem”.Bandung.
10
Giri, I.W.K. 2011. “Analysis Route (City Courier) di Wilayah Bandung Selatan Dengan Menggunakan Metode Travelling Salesman Problem (TSP) di PT. Dakota Logistik dan Ekspress”. Bandung.
Program Studi S1 Ilmu Komputer dan D3 Komputer, Buku Panduan Penulisan Karya Ilmiah.Bogor. Syahwari, H. 2012. “Analisis dan Perancangan Sistem Web KosKosan Berbasis Client/Server Sebagai Sarana Pelayanan Jasa dan Informasi”.
Lukman, A. 2011. “Penyelesaian Travelling Salesman Problem dengan Algoritma Greedy”. Makassar.
Utomo, H. T. 2012. “Minimisasi Biaya Distribusi Tempe Dengan Menggunakan Metode Travelling Salesman Problem (TSP)”. Malang.
Prameswari, D.S. 2014. Algoritma.www.kompasiana.com. 3 September 2015.
11
