1
BAB 1 PENDAHULUAN
1.1. Latar Belakang Persaingan dalam dunia usaha akan selalu terjadi bahkan peningkatan persaingan ini akan semakin tinggi.Apalagi pada tahun ini terjadi kenaikan harga bahan bakar minyak yang tentunya sangat memberatkan dunia usaha karena akan menambah beban biaya produksi maupun biaya transportasi. Kenaikan beban usaha tersebut secara otomatis akan menyebabkan harga jual ke konsumen semakin tinggi, Inflasi yang semakin tinggi pun menyebabkan daya beli konsumen menurun . Sebagai akibat dari harga jual yang semakin tinggi bersamaan dengan daya beli konsumen yang menurun maka dunia usaha saat ini mengalami kerugian yang cukup besar .Salah satu jalan untuk mengatasi kondisi sekarang adalah dengan melakukan efisiensi biaya transportasi bagi perusahaan. Banyaknya pembangunan jalan saat ini membuat banyak pilihan jalur distribusi barang dan jasa . CV SUMBER URIP adalah salah satu perusahaan pabrik limun di propinsi Lampung. Limun yang dijual oleh perusahaan tersebut adalah limun untuk pangsa pasar kelas menengah ke bawah . CV Sumber Urip sangat terkena dampak dari kenaikan bahan bakar minyak di tahun ini karena daya beli pelanggannya menurun. Pelanggan yang sebagian besar orang-orang yang tinggal di daerah pedesaan dan berpenghasilan rendah lebih mementingkan kebutuhan pokok nya terpenuhi dari pada kebutuhan lain yang kurang begitu pokok seperti membeli limun . Akibatnya omset penjualan menurun jauh.
2 Selama ini distribusi perusahaan dilakukan dengan menggunakan dua sampai tiga armada truk untuk melakukan pengantaran.Daerah pengantaran setiap harinya tidak menentu tergantung toko pelanggan mana yang stoknya sudah habis dan biasanya pelanggan yang inisiatif menghubungi melalui telepon . Jumlah pelanggan yang memesan setiap hari bisa mencapai sepuluh sampai lima belas toko, jadi pengantaran yang tidak direncanakan terlebih dahulu akan menyebabkan biaya transportasi menjadi bengkak karena tidak sesuai dengan omset perusahaan yang produk nya merupakan barang dengan harga murah, oleh karena itu sangat diperlukan suatu tools / aplikasi yang dapat membantu meng-optimalkan distribusi dari segi jarak untuk membuat biaya transportasi menjadi efisien. Untuk membuat perancangan aplikasi
optimasi distribusi diperlukan algoritma
yang tepat . Ada banyak algoritma yang dapat di pakai untuk memecahkan masalah optimasi distribusi ini yaitu : o
Metode Optimal
Konsekwensi dari metode ini adalah membutuhkan waktu yang cukup lama untuk menyelesaikannya . Algoritma yang menggunakan metode optimal ini antara lain :
Complete Enumeration
Algoritma ini mengenumerasi setiap kemungkinan yang terdapat dalam graph, setelah itu algoritma ini akan membandingkan lintasan mana yang paling minimum . Misal untuk kasus ini :
3
Jumlah titik yang terdapat adalah 4 buah dan banyak kemungkinan lintasannya adalah 6 buah. yaitu :
- Lintasan pertama = ( a , b , c , d , a). - Lintasan kedua = ( a , d , c , b , a ). - Kedua lintasan tersebut mempunyai panjang =10+12 + 8 + 15 = 45. - Lintasan ketiga = ( a , c , d , b , a ). - Lintasan keempat = ( a , b , d , c , a ). - Kedua lintasan tersebut mempunyai panjang = 12+ 5+ 9 + 15 = 41. - Lintasan ketiga = ( a , c , b , d , a). - Lintasan keempat = ( a , d , b , c , a ). - Kedua lintasan tersebut mempunyai panjang = 10 + 5 + 9 + 8 = 32. Hasil enumerasi dari algoritma ini adalah (n-1)! yang tidak akan efisien jika jumlah n besar.
Branch and Bound
4
Branch and Bound adalah suatu algoritma yang paing umum untuk mencari solusi optimal pada masalah optimasi kombinatorial seperti masalah penjadwalan. Didalam algoritma branch and bound terdapat 3 buah bagian utama yaitu : ekspresi batas bawah (Lower Bound (LB)) , strategi pencarian dan pencabangan procedur ini , suatu masalah dipecah
(Branching) . Di dalam
menjadi beberapa submasalah yang
merepresentasikan pembagian kerja secara parsial. Simpul-simpul terus bercabang lebih jauh sampai diperoleh solusi lengkap . Jika LB tidak digunakan maka segala kemungkinan penyelesaian harus dienumerasikan satu persatu. Oleh karena itu LB dikalkulasikan pada setiap simpul . Jika nilai LB yang dikalkulasikan lebih besar dari nilai solusi lengkap terbaik , eliminasi simpul tersebut. Prosedur ini terus diulang sampai pencarian pada pohon berakhir dan solusi optimal ditemukan.Algoritma Branch and Bound yang menggunakan fungsi heuristic merupakan algoritma yang cukup baik dan cukup efisien untuk menyelesaikan persoalan combinatorial.Hal ini disebabkan karena fungsi heuristic lebih mengoptimalisasi solusi yang sudah ada sehingga tidak perlu memeriksa atau mencoba semua kemungkinan yang ada.untuk n > 100 algoritma ini memakan memory yang sangat besar . Untuk n<100 algoritma ini tergolong sangat efisien di mana n adalah banyaknya kota. Berikut adalah ciri dari algoritma branch and bound :
5 •
Pohon ruang keadaan menggambarkan semua pencabangan yang mungkin (kombinatorial).
•
Pembatasan dilakukan untuk mempercepat perhitungan sehingga tidak semua lintasan harus dihitung.
•
Perhitungan dilakukan dengan fungsi pembatas tertentu , menghitung nilai batas untuk tiap-tiap simpul untuk dipilih sebagai simpul yang dibuat cabang nya.
•
Bila sebuah perjalanan lengkap diperoleh , akan menjadi batas minimum sementara , semua perjalanan sebagian yang nilainya lebih besar akan dikeluarkan dalam pencarian.
Brute force Pemakaian algoritma brute force menjamin penyelesaian solusi dengan baik dan
dikenal dengan sebutan exhaustive search . Kelemahan dari metode ini adalah pencarian solusi harus membangkitkan sebanyak (n-1)! /2 . untuk jumlah node yang sedikit pemakaian brute force sangat efisien , walaupun lebih efisien dari complete enumeration tetapi untuk jumlah node yang banyak , maka algoritma ini masih sangat tidak efisien. Algoritma brute-force menyelesaikan masalah TSP dengan cara: 1.
Enumerasi semua Sirkuit Hamilton dari graf lengkap TSP
2.
Menghitung bobot tiap sirkuit Hamilton yang telah ditemukan
3.
Memilih sirkuit Hamilton yang mempunyai bobot terkecil.
Karena algoritma ini menghitung bobot untuk setiap Sirkuit Hamilton yang mungkin terjadi,maka kompleksitasnya sebesar jumlah Sirkuit Hamilton untuk graf lengkap
6 bersimpul n yang dimulai dari sebuah simpul.Untuk mengehemat waktu enumerasi dan evaluasi pada langkah 1 dan 2, dapat digunakan algoritma DFS yang dimodifikasi. Adapun prinsip algoritma yang dipakai untuk mengefisienkan persoalan TSP ini adalah sebagai berikut: 1.
Bangun sebuah pohon yang cabangnya berupa simpul pada graf,
2.
Lakukan metode DFS pada tiap cabang sampai semua simpul dipilih (tidak ada yang dipilih dua kali),
3.
Hitung bobotnya,
4.
Lakukan langkah ke-2 dan ke-3 sampai seluruh simpul asal telah dipilih. Apabila pada waktu membangkitkan simpul anak ternyata lebih besar dari minimum sementara, maka simpul tersebut dimatikan.
o
Metode Aproksimasi
Greedy Algoritma greedy merupakan metode yang paling popular untuk memecahkan
persoalan optimasi. Pendekatan yang digunakan didalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum local ( local optimum) pada setiap langkah dengan harapan bahwa sisanya mengarah ke solusi optimum global (global optimum) . Algoritma ini memecahkan masalah langkah demi langkah pada setiap langkah dengan prinsip “take what you can get now ! ”. Ambil apa yang anda peroleh sekarang ! .Dalam kehidupan sehari-hari kita juga pernah menggunakan prinsip greedy ,misalnya : a.
Memilih jurusan di perguruan tinggi
b.
Memilih jalur tersingkat dari bandung ke Jakarta.
7
Pada algoritma ini pemilihan lintasan akan dimulai pada lintasan yang memiliki nilai paling minimum, setiap mencapai suatu kota algoritma ini akan memilih kota selanjutnya yang belum dikunjungi dan memiliki jarak yang paling minimum . algoritma ini disebut juga Nearest Neighbour . Kompleksitas algoritma ini memang sangat mengagumkan yaitu O(n) jadi jika algoritma greedy ini berhasil menemukan solusi maka algoritma ini merupakan algoritma yang paling cepat dari algoritma mana pun, tetapi pada kondisi tertentu hasil yang kita dapat bisa sangat jauh dari hasil yang optimal, semakin banyak kota semakin besar pula perbedaan hasil yang di capai.kelebihan lain dari algoritma ini mudah untuk di coding, mudah untuk di debug berjalan dengan cepat dan menggunakan memory yang kecil
o
Metode Heuristic Lainnya Teknik ini digunakan untuk mencari jawaban dari masalah kombinatorial secepat
mungkin. Algoritma tradisional akan gagal ketika menghadapi permasalahan secara rumit seperti permasalah TSP dengan banyaknya kota (n) yang sangat besar.Metode heuristic memberikan pendekatan untuk menyelesaikan permasalahan optimasi kombinatorial. Combinatorial search akan memberi kita hasil yang mungkin dan mencari hasil yang
8 mendekati optimal dari hasil – hasil tersebut.Tetapi mungkin memang tidak ada metode Heuristic yang menghasilkan solusi yang merupakan solusi optimal . metode heuristic seperti simulated annealing , genetic algorithm dan neural network mengusahakan suatu cara untuk mencari hasil yang baik tapi bukan yang terbaik.
o
Ant Colony System Ant Colony adalah salah satu Swarm Intelligent. Swarm Intelligence adalah suatu
metode pemecahan masalah dengan menggunakan sifat koloni hewan.Algoritma ini mempelajari cara semut – semut meninggalkan sarangnya untuk mencari makanan dan mencari kembali sarang mereka. Algoritma ini termasuk dalam metode metaheuristic karena pada awalnya di siklus pertama pemilihan pergerakan semut memanfaatkan pendekatan dengan strategi greedy.Hal ini dikarenakan pada status awal harga pheromone sama untuk setiap sisi sehingga dengan sendirinya pemilihan simpul tergantung dari panjang sisi ke simpul tersebut, iterasi selanjutnya pemilihan pergerakan semut tergantung dari tajamnya zat feromon yang ditinggalkan hasil dari eksplorasi semut yang berkoloni. Ciri - ciri dari algoritma ant colony ini adalah: o
Algoritma ini cocok untuk jumlah simpul yang sangat banyak karena algoritma ini menempatkan semut pada setiap simpul sehingga eksplorasi makin cepat.
o
Algoritma ini biasanya menempatkan satu semut pada satu kota karena lebih optimal untuk setiap iterasi ( jumlah iterasi akan dikalikan dengan jumlah semut )
o
Kompleksitas algoritma ini adalah O(NC.n2.m) di mana n : jumlah simpul m : jumlah semut NC : jumlah iterasi
9 Jadi dalam perancangan aplikasi optimasi distribusi ini penulis lebih memilih algoritma Ant Colony karena mempunyai kompleksitas algoritma yang kecil untuk simpul yang sangat banyak.
1.2. Ruang Lingkup & Batasan Masalah Ruang lingkup permasalahan : •
Pencarian rute minimum dalam proses distribusi limun dari pabrik ke pelanggan untuk menghemat waktu dan biaya transportasi . Batasan permasalahan :
•
Tidak membahas kondisi jalan yang rusak yang dapat menyebabkan transportasi jadi lebih boros ( tidak efisien ) yang seharusnya bisa melalui jalur alternatif
•
Tidak membahas masalah kemacetan yang juga dapat menyebabkan waktu dan biaya menjadi tidak efisien.
•
Tidak membandingkan dengan algoritma optimasi lainnya.
1.3. Rumusan Rancangan Bagaimana menggunakan algoritma Ant Colony untuk menyelesaikan masalah optimasi distribusi supaya lebih efisien dari segi jarak dalam menjalankan proses distribusi.
10 1.4. Tujuan dan Manfaat Perancangan Perancangan ini bertujuan untuk : •
Memberikan informasi yang paling efisien mengenai rute mana yang harus dikunjungi sehingga penggunaan biaya transportasi menjadi lebih efisien.
•
Menambah pengetahuan tentang algoritma metaheuristic.
•
Menghasilkan program aplikasi optimasi distribusi dengan tingkat akurasi yang mendekati solusi optimal dan waktu yang efisien dalam mengambil keputusan .
Perancangan ini diharapkan dapat memberikan manfaat kepada banyak pihak, baik secara langsung maupun secara tidak langsung. Manfaat yang diharapkan adalah sebagai berikut : •
Bagi perusahaan CV.Sumber Urip
Sebagai alat bantu untuk perencanaan kunjungan atau perencanaan distribusi limun.
Aplikasi ini dapat menekan biaya distribusi dengan cara penentuan rute minimum sehingga menghemat biaya BBM.
•
Bagi peneliti lain Aplikasi ini dapat menjadi referensi untuk penelitian lebih lanjut dalam menyelesaikan masalah optimasi lainnya.
11
1.5. Sistematika Penulisan Penulisan skripsi ini disusun atas lima bab, dan berikut adalah gambaran umum dari masing-masing bab tersebut : BAB 1 PENDAHULUAN Bab ini menjelaskan tentang latar belakang, ruang lingkup, perumusan masalah, tujuan dan manfaat serta sistematika penulisan. BAB 3 LANDASAN TEORI Bab ini menjelaskan tentang teori-teori yang menunjang penulisan skripsi ini. BAB 3 PERANCANGAN Bab ini menjelaskan tentang spesifikasi rumusan rancangan, perancangan modul, perancangan struktur menu, diagram transisi serta perancangan layar. BAB 4 IMPLEMENTASI DAN EVALUASI Bab ini menjelaskan tentang spesifikasi sistem, implementasi, evaluasi dan pembahasan rancangan. BAB 5 KESIMPULAN DAN SARAN Bab ini menjelaskan tentang kesimpulan dan saran.
