BAB 1 PENDAHULUAN
1.1 Latar Belakang Masalah Komputer merupakan salah satu alat bantu untuk menyelesaikan masalah. Untuk dapat menyelesaikan masalah maka perlu dirumuskan terlebih dahulu langkahlangkah dalam suatu rangkaian instruksi. Sekumpulan instruksi yang merupakan penyelesaian masalah dinamakan “program”. Program dapat berjalan pada komputer bila ditulis dalam bahasa yang dimengerti oleh Komputer. Bahasa yang digunakan dalam menulis program dinamakan bahasa pemograman. Dalam menyelesaikan masalah dengan bantuan komputer, langkah pertama yang harus dilakukan adalah membuat desain (rancangan). Desain menyajikan cara berpikir pemogram dalam menyelesaikan masalah. Desain ini berisi urutan langkah-langkah pencapaian solusi yang dituliskan dalam notasi-notasi deskriptif. Urutan langkah-langkah yang sistematis untuk menyelesaikan masalah dinamakan algoritma. Persoalan pendistribusian suatu komoditi dari sebuah depot (agen) ke pelanggan yang tersebar di berbagai tempat merupakan masalah yang sering dijumpai dalam kehidupan sehari-hari. Dalam pendistribusian tersebut, masalah yang sering timbul adalah bagaimana meminimumkan biaya yang harus dikeluarkan. Salah satu pendekatan untuk menyelesaikan persoalan tersebut adalah Traveling Salesman Problem (TSP). Traveling Salesman Problem (TSP) adalah salah satu masalah yang telah menarik perhatian dari para ahli matematika dan ahli komputer karena traveling
salesman problem begitu mudah dideskripsikan tetapi begitu sulit untuk dipecahkan. Traveling Salesman Problem merupakan masalah optimasi kombinatorial yang tergolong dalam NP-complete problem (non deterministic polynomial complete problem), yaitu suatu permasalahan di mana dengan bertambahnya variabel secara linear maka waktu yang diperlukan untuk memecahkan masalah itu bertambah secara eksponensial. Traveling Salesman Problem merupakan suatu masalah bagaimana menetukan perjalanan melewati semua titik dimana tiap titik harus dilalui dan hanya boleh dilalui satu kali saja dan perjalanan harus berakhir dengan kembali ke titik pertama. Dalam hal ini titik-titik tersebut merupakan kota-kota (node) dalam suatu wilayah tertentu yang dihubungkan dengan edge atau garis yang dapat merupakan representasi dari biaya perjalanan antara satu kota dengan kota lainnya, jarak yang menghubungkan antara kota yang satu dengan yang lainnya, atau dapat juga berupa waktu yang dibutuhkan seorang salesman dari satu kota ke kota lainnya. Contoh Traveling Salesman Problem antara lain pengaturan rute bis sekolah untuk menjemput murid-murid di suatu daerah, mencari rute terpendek untuk layanan antar makanan ke tempat tinggal konsumen, menentukan rute truk pengambilan barang, dan sebagainya. Solusi pemecahan yang paling mudah adalah dengan menggunakan rumus permetasi (ordered combinations) dan melakukan pengecekan rute mana yang paling pendek dengan menggunakan brute force search, tetapi dengan adanya permetasi dari jumlah kota dengan jumlah angka (n-1)! (faktorial dari jumlah kota n-1), solusi ini menjadi sangat tidak praktis. Bayangkan bila jumlah kota ada 11 kota, maka kemungkinan rute yang dapat dilalui akan bertambaha menjadi 10 kali lipat, yaitu ada (11-1)! = 10! atau 3.628.880 kemungkinan rute yang dapat dilalui (termasuk rute
yang sama tapi dengan arah yang berbeda, yang biasanya disebut dengan asymmetric traveling salesman problem sedangkan dalam symmetric traveling salesman problem atau yang biasa disebut dengan traveling salesman problem saja, kemungkinan rutenya dapat dirumuskan dengan (n-1)!/2, di mana untuk rute yang sama dengan arah yang berbeda hanya dihitung 1 kemungkinan saja (jarak dari A ke B sama dengan jarak dari B ke A). Maka dicari algoritma-algoritma lain yang dapat digunakan untuk menyelesaikan problem optimasi dengan memilih arsitektur jaringan yang sesuai untuk mendapatkan solusi yang optimal. Algoritma yang ada diharapkan dapat memberikan reduksi waktu eksekusi yang sangat signifikan untuk jumlah kota lebih besar dari 9, dan dapat memberikan optimasi yang lebih baik dibandingkan dengan algoritma ataupun metode yang telah ada. Berbagai penelitian telah dilakukan untuk menentukan cara yang terbaik dalam menyelesaikan traveling salesman problem, antara lain dengan menggunakan genetic algorithm, tabu search, branch and bound, metode greedy, dynamic programming, algoritma koloni semut (ant colony system) yang baru-baru ini cukup dikenal, dan masih banyak lagi. Semuanya memiliki kelebihan dan keterbatasannya masing-masing, tergantung pada kondisi permasalahannya, karena sangatlah sulit untuk mencari solusi yang optimal bagi sebuah masalah optimasi kombinatorial atau NP-complete problem seperti Traveling Salesman Problem dalam berbagai kemungkinan keadaan. Dalam penelitian ini, untuk memecahkan masalah Traveling Salesman Problem digunakan Algoritma Metropolis. Algoritma metropolis adalah salah satu dari metode optimasi matematika yang dapat diterapkan dalam Traveling Salesman Problem untuk mengoptimasikan jarak yang perlu ditempuh seorang sales untuk
mengunjungi n kota. Algoritma Metropolis dapat mencari rute terpendek antara n kota, di mana n dapat lebih dari 50 dan kinerja algoritma Metropolis ini lebih cepat, lebih akurat dan tidak terlalu membutuhkan memori yang terlalu besar dibandingkan dengan pemecahan Traveling Salesman Problem yang menggunakan metode dynamic programming. Pada kesempatan ini penulis mencoba merancang suatu prototipe program aplikasi yang dapat menyelesaikan Traveling Salesman Problem dengan menggunakan algoritma Metropolis. 1.2 Tujuan dan Manfaat 1.2.1 Tujuan Tujuan perancangan ini adalah: 1. Merancang program aplikasi yang dapat menenentukan rute terpendek distribusi buku daerah DKI Jakarta dengan menggunakan algoritma Metropolis. 2. Melihat tingkat optimalitas algoritma Metropolis 1.2.2 Manfaat Perancangan ini akan memberikan manfaat kepada banyak pihak baik secara langsung maupun tidak langsung. Manfaat yang dimaksud adalah sebagai berikut: 1. Bagi pihak yang membutuhkan pemecahan masalah Traveling Salesman Problem. Dengan prototipe ini selanjutnya akan dapat dikembangkan untuk rute dari distribusi dalam kota yang sebenarnya. 2. Bagi ilmu pengetahuan: a. Hasil yang didapat dari implementasi program aplikasi yang dirancang merupakan sumbangan terhadap ilmu pengetahuan
tentang kemampuan algoritma metropolis dalam menyelesaikan optimasi Traveling Salesman Problem. b. Penelitian ini memberikan suatu alternatif penyelesaian Traveling Salesman Problem yang selama ini merupakan masalah yang sulit untuk diselesaikan. c. Penelitian ini diharapkan menjadi dasar bagi penelitian dan pengembangan penggunaan algoritma Metropolis untuk aplikasiaplikasi yang lebih luas di berbagai perusahaan. 3. Bagi penulis Dengan
mempelajari
algoritma
Metropolis
maka
penulis
dapat
memperkaya pengetahuan dan dapat mempelajari lebih mendalam tentang Traveling Salesman Problem dan cara penyelesaiannya. 1.3 Metodologi 1.3.1 Metode studi kepustakaan Algoritma Metropolis untuk memecahkan Traveling Salesman Problem yang mendukung penyusunan skripsi dan pembuatan program aplikasi didapatkan dengan mempelajari materi yang berkaitan dari perpustakaan, internet maupun sumber yang lain. 1.3.2 Metode penelitian laboratorium Algoritma metropolis dalam menyelesaikan Traveling Salesman Problem diuji di laboratorium menggunakan komputer melalui program aplikasi 1.3.3
Metode perancangan Dalam perancangan untuk menyelesaikan Traveling Salesman Problem dengan bantuan komputer, algoritma Metropolis dipilih sebagai metode yang
digunakan. Ada beberapa alasan yang mendukung pemilihan algoritma Metropolis sebagai alternartif penyelesaian traveling salesman problem yang juga termasuk salah satu masalah optimasi ini, antara lain Algoritma Metropolis relatif sederhana sehingga komputasinya lebih sederhana dan tidak memakan kinerja komputer dan juga menghindari terperangkapnya solusi dalam local minima atau memungkinkan penyelesaian Traveling Salesman untuk mendapatkan absolute minimum. 1.4 Ruang Lingkup Penelitian dilakukan pada perusahan PT TIGA LANCAR SEMESTA, khususnya pada bagian marketing dan distribusi, dimana perusahaan ini bergerak dalam bidang printing dan publishing. Pengantaran buku dilaksanakan tiap tanggal tertentu tiap bulannya, sesuai dengan rencana buku akan diterbitkan. Agar penyelesaian masalah dapat lebih terarah dan jelas, maka ruang lingkup akan dibatasi antara lain sebagai berikut: 1. Lingkup distribusi hanya dilakukan di daerah DKI Jakarta, karena perusahaan menggunakan penyewaan jasa pengantaran untuk daerah di luar DKI Jakarta. 2. Masalah yang harus dipecahkan adalah untuk mencari jarak terpendek yang dapat dicapai, dengan membagi DKI Jakarta menjadi 5 wilayah yaitu, Jakarta Utara, Jakarata Barat, Jakarta Pusat, Jakarta Timur dan Jakarta Selatan. 3. Saat melakukan pencarian rute terpendek, diasumsikan jarak dari toko A ke B dan toko B ke A dianggap sama, dan faktor eksternal lainnya, seperti faktor kemacetan diabaikan. 4. Jarak antar toko satu dengan toko lainnya di-input oleh user.
Program komputer yang disusun digunakan sebagai alat pendukung untuk menentukan rute distribusi buku yang diusulkan kepada perusahaan agar hasil program mendapatkan hasil rute yang terpendek.
