Modul 1
Kelompok :
resume jurnal tentang database yang diambil dari
PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA CHEAPEST INSERTIONS HEURISTICS DAN BASIS DATA
Ada banyak algoritma untuk memecahkan masalah Travelling Salesman Problem (TSP), di antaranya: Linear Programming, Algoritma Genetik, Nearest Neighbourhood Heuristic, dan Cheapest Insertion Heuristic (CIH). Jurnal ini membahas tentang implementasi algoritma CIH untuk menyelesaikan TSP menggunakan Borland Delphi 6 dan Interbase 6. Permasalahan TSP sendiri adalah mencari rute terpendek ynag bias dilalui salesman yang ingin mengunjungi beberapa kota tanpa harus mndatangi kota yang sama lebih dari satu kaili. Algoritma CIH berhasil diimplementasikan dengan mengetahui jumlah kota yang terhubung dan jarak di antaranya, rute perjalanan, dan total panjang rute untuk mengunjungi semua kota dalam jaringna dapat diketahui. Namun demikian, implementasi algoritma belum mampu menyelesaikan masalah pencarian rute jika ada 2 kota yang mempunyai bobot yang berbeda dengan melihat arahnya dan jika ada 2 kota yang tidak terhubung.
Pada penelitian tersebut menggunakan metode:
1. Perancangan algoritma
Melakukan perancangan algoritma pencarian jarak terpendek dengan metode CIH dengan menggunakan basis data
2. Implementasi rancangan
Setelah algoritma tersebut dibentuk akan diimplementasikan menjadi sebuah pernagkat lunakdengan menggunkan bahasa pemrograman Delphi 6 dan Basis Data Interbase
3. Uji coba
Menguji kebenaran perhitungan dengan membandingkan perhitungan manual dan perhitungan aplikasi. Diuji pula waktu yang diperlukan untuk memproses solusi dengan jumlah kota yang berbeda-beda.
Perancangan penelitian ini adalah:
- Input dari program TSP dengan CIH
· Jumlah kota
· Jarak antar kota
- Input dari program TSP dengan CIH
· Proses pemiliha lintasan
· Lintasan terpendek
· Jarak lintasan
Berdasarkan penelitian dan uji coba, dapat disimpulkan:
1. Basis data dapat digunakan sebagai alat bantu dalam mengimplementasikan algoritma Cheapest Insertion Heuristic dengan baik
2. Peran basis data dalam implementasi ini adalah untuk penyimpanan data proses sehingga pengambilan informasi jarak minimal dari beberapa alternatif yang ada dapat dilakukan dengan mudah yaitu dengan menggunakan query
3. Banyaknya kota sangat mempengaruhi proses penyelesaian. Fungsi waktu proses terhadap jumlah kota adalah Y=14/5 X – 27, dengan Y= waktu proses (detik), X= jumlah kota
Kelompok 6
1. Septika Rosiana D (L2H009003)
2. M. Kamaludin (L2H009097)
3. Rayana Andari B. (L2H009121)
Kelompok 6
1. Septika Rosiana D (L2H009003)
2. M. Kamaludin (L2H009097)
3. Rayana Andari B. (L2H009121)
Tidak ada komentar:
Posting Komentar