Penerapan Algoritma Particle Swarm Optimization pada Multidimensional Bounded Knapsack Problem

Abstract

Optimasi adalah usaha untuk mendapatkan hasil terbaik dalam keadaan tertentu dengan tujuan meminimalkan usaha ataupun memaksimalkan keuntungan yang diinginkan. Permasalahan nyata terkait optimasi seringkali terjadi di kehidupan sehari-hari, seperti pemilihan kombinasi produk untuk mendapatkan keuntungan maksimal dengan keterbatasan yang ada. Pendekatan optimasi mampu mengurangi biaya distribusi secara nyata sekaligus meningkatkan standar pengiriman. UD. Raja Tani dalam pendistribusian barang yang akan dijual tentunya mempertimbangkan kapasitas daya tampung transportasi dan anggaran pembelian untuk mengoptimalkan keuntungan. Pemilihan kombinasi barang yang tidak tepat menyebabkan keuntungan yang diperoleh tidak optimal. Salah satu pemodelan matematika yang digunakan untuk menyelesaikan permasalahan tersebut adalah knapsack problem. Knapsack problem merupakan permasalahan optimasi untuk memilih barang dengan berat dan nilai tertentu guna memaksimalkan keuntungan tanpa melebihi kapasitas yang tersedia. Penelitian ini berfokus pada Multidimensional Bounded Knapsack Problem yang memiliki dua contraints. Permasalahan ini akan diselesaikan dengan Algoritma Particle Swarm Optimization yang terinspirasi dari kawanan burung. Permasalahan pada penelitian ini yaitu mencari total keuntungan yang diperoleh UD. Raja Tani dalam pembelian barang yang akan dijual. Terdapat 86 jenis barang dan setiap jenis barang memiliki berat, keuntungan, dan ketersediaan barang yang berbeda. Data yang diperoleh diselesaikan dengan algoritma PSO menggunakan bantuan program python. Solusi yang diambil merupakan nilai akhir dari 𝐺𝑏𝑒𝑠𝑡 terbaik yang ditemukan selama iterasi. Iterasi berlangsung hingga algoritma tidak menemukan solusi terbaik lagi selama beberapa iterasi maupusampai mencapai maksimum iterasi. Solusi yang optimal tentunya dipengaruhi oleh parameter yang digunakan. Beberapa kombinasi parameter diuji untuk menemukan kombinasi yang tepat dalam menemukan solusi yang optimal. Hasil akhir dari pengujian parameter diperoleh kombinasi parameter terbaik yaitu bobot inersia 𝑚𝑖𝑛 = 0.4, 𝜃𝑚𝑖𝑛 = 0.9, koefisien akselerasi 𝑐1 = 2.0, 𝑐2 = 2.0, dan jumlah partikel 𝑁 = 150. Solusi yang diperoleh UD. Raja Tani dari kombinasi parameter tersebut yaitu total keuntungan Rp5.049.500 dengan total berat 1173.74 kg, total modal Rp63.373.500, dan total kombinasi barang sebanyak 59 jenis.