BAB 1 PENDAHULUAN
1.1. Pengantar Perkembangan jaman yang diiringi dengan kemajuan teknologi sekarang ini menyebabkan perubahan hampir di segala bidang. Salah satu aspeknya ialah teknologi komputerisasi
yang tentunya memiliki peran sangat penting dalam
berbagai aspek kehidupan. Hampir semua pekerjaan ataupun kegiatan dewasa ini sangat membutuhkan, bahkan ada yang sangat bergantung pada penggunaan komputer. Oleh karena itu, dapat dikatakan bahwa komputer merupakan merupakan kemajuan teknologi yang sedang dan akan terus berkembang nantinya, serta sangat berpengaruh kegunaannya terhadap kehidupan manusia. Sebuah sistem komputer pada dasarnya terdiri dari 3 bagian, yaitu perangkat komputer yang dikenal dengan perangkat keras (hardware), sistem komputer (software) atau yang lebih dikenal dengan istilah perangkat lunak, dan manusianya sendiri yang disebut dengan brainware. Komputer akan bisa berjalan dengan baik apabila memiliki ketiga unsur ini yang tentunya dapat berfungsi dengan baik pula. Perangkat lunak merupakan fasilitas yang digunakan untuk mengendalikan aktifitas seluruh piranti komputer, dan biasanya berupa suatu program. Fasilitas perangkat lunak antara lain aplikasi program yang terdiri dari seluruh prosedur pengelolaan informasi termasuk rancangan sistem informasi, petunjuk pelaksanaan dan aturan-aturan lain yang bertujuan menunjang kemudahan para penggunanya. Dalam menuliskan program, pertama kali harus ditentukan langkah apa yang harus diambil terlebih dahulu. Lalu prosedur urutan langkahlangkah tersebut ditata kemudian baru dituliskan. Prosedur tata urutan langkah yang demikian disebut algoritma. Traveling Salesman Problem, yang akan dibahas dalam tugas akhir kali ini, juga merupakan salah satu permasalahan yang memerlukan algoritma.
1
1.2. Latar Belakang Masalah Traveling Salesman Problem (TSP) merupakan salah satu kasus atau permasalahan yang memiliki banyak terapan penting seperti routing dan penjadwalan produksi. Dalam kasus Traveling Salesman Problem, peran komputer sebagai salah satu solusi pemecahan masalah sangatlah dibutuhkan, mengingat efisiensi, efektivitas, dan ketepatan perhitungan dari kinerja komputer yang jauh lebih tinggi dibandingkan dengan kerja secara manual. Kasus Traveling Salesman Problem, diasumsikan bahwa seseorang melakukan suatu perjalanan ke berbagai kota tujuan, dengan ketentuan bahwa orang tersebut berangkat dari kota asal kemudian mengunjungi ke semua kota tujuan satu per satu tanpa mengulangi kota/titik yang telah dilewati, dan kembali ke kota asal lagi dengan jarak yang sekecil-kecilnya. Untuk menyelesaikan permasalahan tersebut, diterapkanlah suatu sistem aplikasi dengan menggunakan algoritma tertentu sebagai metode untuk pencarian jarak terpendek.
1.3. Rumusan Masalah Secara garis besar, rumusan masalah yang dihimpun berdasarkan permasalahan yang telah disebutkan diatas adalah sebagai berikut: ¾ Membandingkan algoritma Nearest Neighbor dan Farthest Insertion yang diimplementasikan pada kasus Traveling Salesman Problem ¾ Menganalisis hasil perbandingan yang didapat berdasarkan jarak, dan waktu proses dari masing-masing algoritma
1.4. Batasan Masalah Batasan-batasan masalah dalam pembuatan tugas akhir ini adalah sebagai berikut :
2
¾ Input jumlah kota
dibatasi antara 2-10 kota untuk proses yang
menggunakan graf dan matriks, sedangkan untuk yang random dibatasi antara 2-999 kota ¾ Output yang dihasilkan berupa data jarak perjalanan terpendek, dan waktu proses dari kedua algoritma ¾ Algoritma yang digunakan adalah Nearest Neighbor dan Farthest Insertion ¾ Parameter perbandingan yang dilakukan adalah membandingkan waktu proses (kecepatan algoritma menyelesaikan rute yang dijalani), rute perjalanan, dan total panjang rute perjalanan yang ditempuh dari kedua algoritma tersebut.
1.5. Manfaat dan Tujuan Penulisan Adapun manfaat dan tujuan penulisan Tugas Akhir ini adalah : ¾ Bagi Universitas a. Agar Universitas dapat mengkaji sejauh mana kemampuan mahasiswa dalam mengimplementasikan ilmu yang diberikan selama berada di bangku perkuliahan. b. Menyiapkan mahasiswa sebagai tenaga kerja terdidik dan terlatih. c. Mengetahui perkembangan yang terjadi di dalam masyarakat sehingga nantinya dapat dilakukan kebijaksanaan mengenai matakuliah yang relevan ¾ Bagi Mahasiswa d. Membuat program aplikasi untuk memecahkan Traveling Salesman Problem dengan menggunakan algoritma Nearest Neighbor dan Farthest Insertion serta membandingkan hasil yang diperoleh dari kedua algoritma tersebut.
3
e. Agar mahasiswa mampu mengimplementasikan teori yang telah didapat selama perkuliahan menjadi suatu karya ilmiah yang memiliki bobot akademis dan dapat dipertanggungjawabkan f. Sebagai prasyarat yang harus ditempuh oleh mahasiswa Teknik Informatika guna memperoleh gelar sarjana strata 1
1.6. Hipotesis Perbandingan algoritma Nearest Neighbor dan Farthest Insertion digunakan sebagai solusi dalam kasus Traveling Salesman Problem untuk mendapatkan jarak terpendek dan efisien dalam suatu jalur perjalanan. Hasil perbandingan algoritma tersebut dilihat dari total jarak tempuh, rute perjalanan, dan waktu proses yang digunakan untuk menyelesaikan suatu perjalanan dimana hasil yang paling minimum merupakan hasil pemecahan Traveling Salesman Problem yang lebih akurat antara algoritma Nearest Neighbor dan Farthest Insertion.
1.7. Spesifikasi Sistem Sistem yang akan dibangun nantinya memungkinkan user membuat kotakota sendiri yang kemudian akan diproses. Kota-kota tersebut akan diwakili oleh vertex. Dengan inputan tersebut kemudian sistem melakukan proses pencarian terhadap jalur-jalur yang mungkin dilewati dan mencari jalur yang terpendek diantara kemungkinan-kemungkinan tersebut. Sistem menjalankan proses berdasarkan algoritma Nearest Neighbor dan Farthest Insertion sebagai solusinya. Setelah diproses, output akan menghasilkan visualisasi rute perjalanan dari kedua algoritma, beserta data perjalanannya masing-masing. Input
:
Kota-kota yang akan diproses
4
Proses
:
Proses pencarian jalur terpendek dengan algoritma Nearest Neighbor
dan
Farthest
Insertion,
yang
kemudian
diimplementasikan ke dalam bahasa pemrograman yang akan memberikan pemecahan Traveling Salesman Problem Output
:
Visualisasi rute perjalanan berupa graph cycle, beserta data perjalanannya
Untuk mendukung kelancaran penerapan sistem komputerisasi ini, maka diperlukan hardware dan software yang mendukung kebutuhan itu antara lain : ¾ Kebutuhan minimal perangkat keras :
Proccesor PentiumII 333 Mhz
Memori 256 MB
HardDisk dengan kapasitas 10 GB
Monitor yang mendukung SVGA (resolusi 1024x768)
Mouse dan Keyboard
¾ Kebutuhan minimal perangkat lunak :
Microsoft Windows 95/98
Borland Delphi 6.0
¾ Kebutuhan brainware :
Bagi Pengguna Pengguna yang dapat mengoperasikan program ini adalah pengguna yang mampu mengoperasikan sistem operasi Microsoft Windows 95/98 dan mengetahui pengoperasian program yang akan dibuat serta penganalisaan output yang dihasilkan.
Bagi Pengembang Pengembang selain mampu mengoperasikan Microsoft Windows 95/98 dan
program
itu
sendiri,
juga
harus
memahami
dan
mampu
mengoperasikan bahasa pemrograman Borland Delphi 6.0 agar dapat melakukan berbagai pengembangan terhadap program yang akan dibuat.
5
1.8. Metodologi Penulisan Metode yang digunakan dalam Tugas Akhir ini antara lain : 1. Penelitian pustaka ¾ Dilakukan studi pustaka dan literatur dengan menggunakan buku-buku yang mendukung proses pembuatan Tugas Akhir. ¾ Mencari sumber-sumber pustaka berbasis internet untuk membantu pembuatan program 2. Penelitian lapangan ¾ Melakukan pemahaman konsep melalui konsultasi dengan nara sumber untuk memperoleh keterangan dan informasi yang dibutuhkan untuk mendukung penyelesaian Tugas Akhir. ¾ Pengamatan dan studi tentang kebutuhan-kebutuhan yang mendasar untuk pembuatan program dengan melihat contoh-contoh program yang berkaitan dengan pembuatan tugas akhir ini. 3.
Penelitian dan Percobaan Laboratorium Melakukan percobaan secara langsung menggunakan program software di komputer dengan mengimplementasikan algoritma yang ada menjadi suatu program aplikasi. Kegiatan di laboratorium ini meliputi : ¾
Membuat program untuk menyelesaikan Traveling Salesman Problem dengan algoritma Nearest Neighbor dan Farthest Insertion
¾
Menjalankan program dengan memasukkan inputan berupa jumlah kota
¾
Mencatat hasil yang didapat dan dibandingkan
¾
Melakukan analisis perbandingan dari hasil yang telah didapat
1.9. Sistematika Penulisan Dalam pembuatan tugas akhir ini, sistematika penulisan laporan adalah sebagai berikut:
6
Bab 1 : Pendahuluan, berisi latar belakang dipilihnya topik tugas akhir ini, rumusan dan batasan masalah, uraian singkat landasan teori yang mendukung pembuatan tugas akhir, hipotesis dan spesifikasi system, serta tujuan, metodologi, dan jadwal penelitian. Bab 2 : Landasan Teori, , berisi teori-teori pendukung yang digunakan sebagai dasar pemecahan Traveling Salesman Problem serta dasar teori dari kedua algoritma tersebut. Bab 3 : Analisis dan Desain Sistem, berisi analisis masalah dan perancangan sistem aplikasi yang akan dibuat. Bab 4 : Implementasi Sistem, berisi analisis terhadap hasil yang dicapai dari kedua algoritma yang diperbandingkan dan juga menjelaskan cara penggunaan program aplikasi yang telah dibuat. Bab 5 : Kesimpulan dan Saran, berisi kesimpulan dan saran dengan melihat pada hasil analisis dan evaluasi yang telah didapat.
7
