PERANCANGAN PROGRAM SIMULASI OPTIMASI...
Click here to load reader
Transcript of PERANCANGAN PROGRAM SIMULASI OPTIMASI...
100 Jurnal Mat Stat, Vol. 10 No. 2 Juli 2010: 100-113
PERANCANGAN PROGRAM SIMULASI OPTIMASI PENYUSUNAN BARANG DALAM KONTAINER
MENGGUNAKAN ALGORITMA GREEDY
Wikaria Gazali1; Ngarap Im Manik2
1,2 Jurusan Matematika, Fakultas Sains dan Teknologi, Universitas Bina Nusantara Jln. K.H. Syahdan No. 9, Palmerah, Jakarta Barat 11480
[email protected], [email protected]
ABSTRACT
Due to the development of technology and the increasing requirement of goods delivery from one country to another, BG Express feels the need to improve its performance by using a computer program. This program will be used for optimizing the storage process in a container. The method used in designing this program is the Greedy Algorithm. Greedy Algorithm is a step by step solution where in each step there are many choices which can be further explored. Due to this feature, it is important to take the best decision upon determining the choice. Hopefully, by implementing this program, we can raise added value in Information Technology so that it can solve storage problems and gain an edge over competitors.
Keywords: greedy algorithm, container, simulation
ABSTRAK
Seiring dengan perkembangan teknologi dan peningkatan kebutuhan pengiriman barang antar negara, maka BG Ekspress merasa perlu untuk meningkatkan kinerjanya dengan pemanfaatan program komputer. Adapun program tersebut dimanfaatkan untuk mengoptimalkan pengisian barang dalam kontainer. Metode yang dimanfaatkan dalam merancang program ini adalah Greedy. Algoritma Greedy sendiri merupakan solusi langkah per langkah di mana pada setiap langkahnya banyak pilihan yang perlu dieksplorasi oleh sebab itu harus dibuat keputusan yang terbaik dalam menentukan pilihan. Diharapkan dengan implementasi program optimasi ini dapat memberikan nilai tambah di bidang Teknologi Informasi sehingga mampu menyelesaikan masalah pengiriman barang serta unggul dalam persaingan.
Kata kunci: algoritma greedy, kontainer, simulasi
Perancangan Program …... (Wikaria Gazali; Ngarap Im Manik) 101
PENDAHULUAN
Sejak dimulainya revolusi industri yang terjadi pada akhir abad ke-18 dan awal abad ke-19 sampai sekarang telah bermunculan berbagai macam industri yang memproduksi suatu produk secara massal. Seiring dengan perkembangan zaman dan ketatnya persaingan dalam dunia industri, setiap industri dituntut untuk dapat efisien dengan tujuan mendapatkan laba yang maksimal. Salah satu bidang yang membutuhkan keefisienan tersebut adalah pengiriman barang.
Pengiriman barang menjadi kendala disebabkan oleh besar barang yang dikirim berbeda satu dengan yang lainnya, sehingga dibutuhkan pemikiran matang agar barang yang disusun untuk dikirim dapat ditempatkan secara optimal dengan jumlah intensitas pengiriman yang minimal. Banyak hal yang harus dipertimbangkan dalam menempatkan barang dan itu bukan hal yang mudah karena petugas di lapangan akan mencoba-coba meletakkan posisi barang dan menggeser barang lainnya agar optimal. Hal ini menyebabkan banyak waktu yang terbuang dan tenaga petugas akan terkuras sehingga penghematan biaya akan sulit tercapai bahkan akan mengeluarkan biaya lebih. Misalkan pengiriman barang dengan menggunakan kontainer, jika tidak dapat mengoptimalkan luas kontainer dengan jumlah barang yang akan dikirim maka akan dibutuhkan kontainer berikutnya untuk mengangkut barang tersebut. Namun lain halnya jika dapat mengoptimalkan luas kontainer dengan jumlah barang yang akan dikirim.
Setelah sampai di tempat yang dituju maka barang akan dikeluarkan, pada prosesnya akan
terjadi masalah yang serius. Jika pada saat awal memasukkan barang terlihat mudah, seringkali pada saat mengeluarkannya justru terlihat sangatlah sulit. Hal ini disebabkan proses memasukkan barang bersifat coba-coba dan tanpa perhitungan. Masalah lain dalam pengiriman barang adalah banyaknya ruang kosong yang seharusnya dapat digunakan untuk menampung barang yang lain. Penyusunan awal yang tidak optimal adalah sebab banyaknya ruang kosong, akibatnya intensitas pengiriman barang akan bertambah dan pengeluaran perusahaan akan semakin besar. Oleh sebab itu, optimalisasi tata letak pengiriman barang sangatlah penting selain dapat menghemat biaya juga dapat menghemat waktu dan tenaga. Untuk itu penulis ingin membuat suatu program simulasi untuk dapat membantu mengoptimalisasi penyusunan barang khususnya dalam kontainer. Program ini dapat mengoptimalisasi barang dengan mengatur tata letaknya dalam suatu kontainer ruang tiga dimensi dengan bidang berupa balok yang memiliki panjang, lebar dan tinggi tertentu.
Tujuan dari penelitian ini adalah untuk membuat sebuah program perangkat lunak yang dapat
mengoptimalkan letak penyusunan barang dalam kontainer dan juga langkah-langkah penyelesaiannya, sehingga dapat memudahkan penyelesaian masalah yang terjadi pada keadaan nyata dan juga dapat menekan biaya pengiriman barang. Diharapkan juga aplikasi perangkat lunak yang akan penulis buat membuka peluang bagi munculnya pengembangan yang lebih lanjut dalam penelitian ini dan mendapatkan hasil yang lebih optimal dengan metode yang lain. Sedangkan untuk penyelesaiannya dilakukan dengan algoritma Greedy (Greedy Algorithm) menggunakan bahasa pemrograman Visual C++ 2005.
METODE
Kontainer Kontainer diberikan dalam bentuk tiga dimensi. Gambar 1 menggambarkan bagian kiri, depan dan bagian lainnya. Penggambaran satu set kotak direpresentasikan dalam bentuk vector. Tinggi kontainer didefinisikan sebagi hc, lebar kontainer didefinisikan sebagai wc dan panjang kontainer didefinisikan sebagai lc.
102 Jurnal Mat Stat, Vol. 10 No. 2 Juli 2010: 100-113
Gambar 1 Kontainer dalam Sistem Koordinat Tiga Dimensi
Berbagai asumsi telah dibuat dalam rangka untuk menyederhanakan, memformulasikan dan menyelesaikan masalah penyusunan barang pada kontainer ini. Beberapa asumsi yang dimaksud adalah sebagai berikut ; Bidang yang digunakan berbentuk persegi panjang (kotak atau balok) dengan ukuran yang berbeda-beda, Kotak tersebut harus diatur sedemikian rupa di dalam kontainer dan paralel dengan bagian dinding-dindingnya, Kotak tersebut dapat dirotasi maupun tidak, tergantung kebutuhan dan keadaan yang terjadi. Rotasi tersebut memiliki enam kemungkinan posisi. Posisi tersebut diantaranya akan diperlihatkan pada gambar berikut:
Gambar 2 Enam Kemungkinan Posisi Barang
Kotak dengan ukuran paling besar harus disusun terlebih dahulu yang diikuti dengan kotak yang lebih kecil, Kotak tersebut diseimbangkan dengan cara mengisi bagian-bagian yang kosong dengan busa. (Pisinger, 1998), Kotak yang berada paling atas didukung oleh kotak-kotak yang ada di bawahnya. Model matematika umum untuk memaksimalkan volume kontainer yang digunakan dapat diformulasikan sebagai berikut : (Juraitis dkk.,2003).
Perancangan Program …... (Wikaria Gazali; Ngarap Im Manik) 103
Di mana:
i = Kotak ke-1 sampai dengan kotak ke-n j = Kontainer ke-1 sampai dengan kontainer ke-n Si = Ukuran kotak ke-1 sampai dengan ke-n Vi
=
Volume kotak ke-1 sampai dengan ke-n
Smax = Ukuran kontainer
Metode Greedy Pengisian barang dalam kontainer ruang tiga dimensi merupakan suatu permasalahan NP-Hard (Pisinger,1998). Sampai sekarang ini, hanya ada beberapa metode yang dapat digunakan untuk menyelesaikan permasalahan ini. Terno dkk. (2000) mengembangkan model umum untuk solusi yang tepat dalam ruang multi-dimensi. Martello et al, (2000) memperkenalkan metode Branch & Bound (B&B) untuk pengisian barang dalam kontainer dalam ruang tiga dimensi. Metode yang akan digunakan pada pengisian kontainer ini adalah metode greedy yang dapat diartikan rakus, tamak. Di mana prinsip dari metode ini sendiri adalah “take what you can get now”. Algoritmanya sendiri merupakan solusi langkah per langkah dan pada setiap langkahnya banyak pilihan yang perlu dieksplorasi oleh karena itu pada setiap langkah perlu dibuat keputusan yang terbaik dalam menentukan pilihan. Pada setiap langkah juga didapat hasil yang dinamakan optimum lokal (local optimum) yang diharapkan langkah sisanya akan mengarah ke optimum global (global optimum).
Time windows sering dikarakteristikkan sebagai time interval, namun dalam formulasi matematika yang akan digunakan time windows ti merupakan single time dan merepresentasikan rentang waktu secara keseluruhan.
Gambar 3 Karakteristik Geometrik Kontainer dan Barang
104 Jurnal Mat Stat, Vol. 10 No. 2 Juli 2010: 100-113
Untuk mempertimbangkan kompatibilitas di antara produk yang berbeda, maka digunakan relasi ekivalen dimana relasi tersebut merupakan relasi yang sesuai, dinotasikan
dengan C. Relasi ini dapat dipresentasikan dengan q by q compatibility matrix yang dinotasikan dengan Z, di mana q merupakan jumlah kategori yang dipertimbangkan, sebagai contoh jika z13 = 0, maka itu berarti barang kategori 1 tidak sesuai dengan barang kategori Gambar 3 menunjukkan karakteristik geometrik kontainer dan barang.
xijk = (xi, yi, zi) yang merupakan koordinat tiga dimensi dari barang yang akan dimasukkan ke dalam kontainer. Selain itu, terdapat Eij yang merupakan bagian dari kontainer j (vehicle j) untuk barang tertentu.
Setiap kontainer terbagi menjadi beberapa potongan, yang dinamakan Nj jumlah potongan
dalam kontainer tersebut. Potongan dikarakteristikkan dengan lebar. Gambar 4 memberikan penjelasan lebih detil tentang potongan itu. (Lai dan Chan, 2001).
Gambar 4 Representasi Potongan Pada Kontainer
Masalah dalam pengisian barang dalam kontainer untuk meminimalkan tempat kosong dapat dideskripsikan dengan persamaan matematika berikut ini :
(1)
Persamaan (1) digunakan untuk meminimasi tempat kosong pada kontainer.
(2)
Persamaan (2) digunakan untuk memastikan bahwa barang-barang yang akan disusun dalam kontainer tidak melebihi berat maksimal yang dapat ditampung oleh kotainer tersebut.
Perancangan Program …... (Wikaria Gazali; Ngarap Im Manik) 105
(3)
Persamaan (3) digunakan untuk memastikan bahwa volume barang-barang yang akan disusun dalam kontainer tidak melebihi volume maksimal yang dapat ditampung oleh kotainer tersebut
(4)
Persamaan (4) membuat barang-barang tidak mungkin untuk disusun di luar dari kontainer, dengan kata lain semua barang berada di dalam kontainer
(5)
(6)
(7)
Persamaan (7) memastikan bahwa semua barang yang akan dimasukkan itu compatible. =1, jika barang i compatible dengan barang j, artinya keduanya berada dalam satu kontainer.
(8)
Persamaan (8) tidak mengizinkan setiap barang yang berbeda overlapping di dalam satu kontainer.
(9)
(10)
Persamaan (6) dan (9) berdasarkan letak barang untuk memperhatikan time windows. Sedangkan untuk persamaan (5) dan (10) digunakan untuk membatasi tiap barang untuk diletakkan hanya pada satu kontainer. (Bischoff, 2004).
(11)
106 Jurnal Mat Stat, Vol. 10 No. 2 Juli 2010: 100-113
(12)
(13)
Pertidaksamaan (11) berpotensial digunakan untuk meletakkan barang kurang dari satu kontainer berdasarkan pertimbangan beratnya dan pertidaksamaan (12) mempertimbangkan barang mana yang tingginya melebihi tinggi kontainer, barang mana yang lebarnya melebihi lebar kontainer dan barang mana yang panjangnya melebihi panjang kontainer. Dalam pertidaksamaan (13) diasumsikan bahwa berat barang lebih besar dari berat maksimal kontainer sebaliknya dalam kasus non-geometric , solusi yang didapat merupakan sebuah pilihan.
Sistem Pengiriman Barang Pada BG Ekspress
Penerapan program ini dilaksanakan pada sebuah perusahaan jasa pengiriman yang lebih dikenal dengan nama BG ekspres yang terletak di Jalan Pluit Mas Jakarta Utara. Saat mendapat pesanan untuk pengiriman barang dari suatu negara ke negara lain maka BG Ekspress akan mengikuti alur proses pengiriman barang seperti pada Gambar 5.
Gambar 5 Proses Pengiriman Barang pada BG Ekspress
Identifikasi Masalah Dari permasalahan yang sudah disebutkan di atas maka dirancang program aplikasi untuk menerima input dari user berupa: Panjang, lebar, tinggi dan berat kontainer; Panjang, lebar, tinggi dan berat barang yang akan dimasukkan ke dalam container; Jumlah barang yang akan dimasukkan ke dalam kontainer. Dengan input tersebut maka akan dihasilkan sebuah gambar tiga dimensi yang dapat diputar juga dapat diperbesar dan diperkecil. Unified Modeling Language (UML)
Pada program pengisian barang ke dalam kontainer ini, digunakan konsep Object Oriented Programming untuk mengembangkannya oleh karena itu dipilih Unified Modeling Language (UML) untuk merancang arsitektur program. UML digunakan meliputi: (Pressman, 2005).
Perancangan Program …... (Wikaria Gazali; Ngarap Im Manik) 107
Use Case Diagram
Gambar 6 Use Case Diagram
Seperti yang terlihat dari use case pada gambar 6, jelas bahwa user dapat memasukkan data kontainer maupun barang dan juga dapat menghapus, menyimpan data kontainer maupun barang. Selain itu data kontainer dapat diubah, juga dapat melihat hasilnya dalam bentuk tiga dimensi. Pada data kontainer yang dimasukkan oleh user adalah jenis kontainer yang akan digunakan untuk menampung barang, panjang kontainer, lebar kontainer, tinggi kontainer, toleransi kontainer dan berat kontainer. Gambar 7 menunjukkan flowchart program, dan Gambar 8 adalah rancangan layar dari program.
108 Jurnal Mat Stat, Vol. 10 No. 2 Juli 2010: 100-113
Flowchart
Gambar 7 Flowchart Input
Perancangan Layar
Gambar 8 Rancangan Layar “Menu Utama”
Perancangan Program …... (Wikaria Gazali; Ngarap Im Manik) 109
HASIL DAN PEMBAHASAN Hasil
Untuk mengimplementasikan aplikasi ini diperlukan beberapa komponen pendukung, yaitu konfigurasi perangkat keras (hardware) dan perangkat lunak (software) yang digunakan dalam pembuatan program ini. Spesifikasi hardware, program aplikasi menggunakan komputer dengan spesifikasi hardware sbb:.
Processor: Intel Pentium 2.5 Ghz ; Memory RAM: 512 Mbyte ;Video Graphic Adapter :ATI Radeon 9600 Pro; Monitor :S SyncMaster 753 DFX. Cara Penggunaan Program
Untuk menggunakan program ini dapat mengikuti langkah-langkah seperti berikut; masuk ke Microsoft Windows (Versi 98/2000/XP atau lainnya), double click pada KnapSackLoad.exe, setelah program berjalan akan tampil beberapa form seperti Gambar 9 dan 10 di bawah ini:
Gambar 9 Tampilan Layar Utama
110 Jurnal Mat Stat, Vol. 10 No. 2 Juli 2010: 100-113
Gambar 10 Tampilan Layar setelah Menerima Inputan Data Barang
Jika ingin melihat gambar tiga dimensinya user dapat menekan tombol Output. Seperti akan diperlihatkan pada gambar 11.
Gambar 11 Tampilan Tiga Dimensi
Perancangan Program …... (Wikaria Gazali; Ngarap Im Manik) 111
Apabila volume atau berat barang melebihi volume atau berat maksimal kontainer maka akan ada konfirmasi ke user bahwa ruang kontainer tidak cukup. Seperti diperlihatkan pada gambar di bawah ini: Pembahasan
Evaluasi dilakukan dengan menggunakan data lama perusahaan BG Ekspres, di mana pada data ini perusahaan tidak dapat mengoptimalkan tempat yang ada. Barang dikirim dari Gunagzhou, China ke Jakarta, Indonesia menggunakan kontainer berukuran 20 feet. Tabel 1 dan Tabel 2 berisikan data kontainer dan barang yang digunakan.
Tabel 1 Data Kontainer Perusahaan
Jenis Kontainer Panjang Lebar Tinggi Berat
20 Feet 590 230 230 30000 40 Feet 1200 230 260 70000
Tabel 2 Data Barang Perusahaan
Nama Barang Panjang Lebar Tinggi Berat Jumlah
T001 88 76 70 12 6 T010 110 98 88 25 8 S2552 85 75 71 15 6 KL56 150 100 88 33 2 JI88 90 68 74 21 4 P766 80 68 52 18 3
ZE118 200 80 80 23 1 AA06 110 100 95 18 2
Hasil perhitungan dengan menggunakan program yang telah dirancang ditunjukkan dalam Gambar 12.
Gambar 12 Hasil Perhitungan menggunakan Data Perusahaan
112 Jurnal Mat Stat, Vol. 10 No. 2 Juli 2010: 100-113
Data perusahaan sebelumnya menunjukkan bahwa barang dengan nama ZE118 tidak dapat dimuat ke dalam kontainer, tetapi dengan menggunakan progam ini semua barang berhasil dimasukkan semua ke dalam kontainer. Hasil perhitungan diperlihatkan di Tabel 3.
Tabel 3 Hasil Perhitungan Menggunakan Program
No. Urut [p, l, t] [x,y,z] Barang Dalam Kontainer
1 [110, 95, 100] 0 88 100 yes
2 [110, 95, 100] 0 88 0 yes
3 [80, 80, 200] 186 88 0 yes
4 [68, 52, 80] 186 168 0 yes
5 [68, 52, 80] 186 168 0 yes
6 [68, 52, 80] 417 159 85 yes
7 [74, 68, 90] 342 88 90 yes
8 [74, 68, 90] 342 88 0 yes
9 [74, 68, 90] 266 158 0 yes
10 [74, 68, 90] 266 158 90 yes
11 [150, 88, 100] 0 0 0 yes
12 [150, 88, 100] 0 0 100 yes
13 [75, 71, 85] 417 159 0 yes
14 [75, 71, 85] 417 88 85 yes
15 [75, 71, 85] 342 156 85 yes
16 [75, 71, 85] 492 88 0 yes
17 [75, 71, 85] 342 156 0 yes
18 [75, 71, 85] 417 88 0 yes
19 [110, 88, 98] 480 0 98 yes
20 [110, 88, 98] 370 0 98 yes
21 [110, 88, 98] 260 0 98 yes
22 [110, 88, 98] 150 0 98 yes
23 [110, 88, 98] 150 0 0 yes
24 [110, 88, 98] 260 0 0 yes
25 [110, 88, 98] 370 0 0 yes
26 [110, 88, 98] 480 0 0 yes
27 [76, 70, 88] 266 88 88 yes
28 [76, 70, 88] 110 158 88 yes
29 [76, 70, 88] 110 88 88 yes
30 [76, 70, 88] 110 88 0 yes
31 [76, 70, 88] 110 158 0 yes
32 [76, 70, 88] 266 88 0 Yes
Perancangan Program …... (Wikaria Gazali; Ngarap Im Manik) 113
PENUTUP
Berdasarkan hasil perancangan program ini didapat bahwa: Algoritma Greedy dapat digunakan dan diimplementasikan untuk mencari solusi optimal dalam permasalahan Three Dimensional Container Loading Problem. Program ini tidak hanya dapat diterapkan pada kontainer melainkan dapat diterapkan pula di truk bahkan di mobil box, karena pada prinsipnya kerjanya sama hanya bentuknya saja yang berbeda, asalkan diketahui panjang, lebar, tinggi maupun berat tempat yang akan digunakan untuk memasukkan barang. Waktu yang dibutuhkan untuk melakukan proses optimalisasi berbanding lurus dengan jumlah barang yang akan dimasukkan. Pada proses penyusunan barang dalam ruang tiga dimensi user harus memperhatikan hal-hal sebagai berikut : Beban maksimal yang dapat ditampung oleh kontainer. Volume maksimal yang dapat ditampung oleh kontainer. Keseimbangan posisi barang terhadap barang yang ada dibawahnya agar tumpukan barang tidak roboh dan menyebabkan kehancuran pada barang.
DAFTAR PUSTAKA
Bischoff, E.E. (2004). Three dimensional packing of items with limited load bearing strength. European Journal of Operational Research, Vol. 168, pp.952–966.
Juraitis M., Riškus A., dan Stonys, T. (2003) A Randomized Heuristic for the Container Loading
Problem. Information technology and control, Kaunas Technologija, No.1 (26), 23-31. Lai, K.K. dan Chan W.M. (2001). An Evolutionary algorithm for the rectangular cutting stock
problem. International Journal of Industrial Engineering, 4, 130-139. Martello, S., Pisinger, D. and Toth, P. (2000) ‘New trends in exact algorithms for the 0–1 knapsack
problem’, European Journal of Operational Research, Vol. 123, pp.325–332. Pisinger, D. (1998) Heuristics for the container loading problem. European Journal of Operational
Research, Vol. 141, pp.143-153. Pressman, R.S. (2005). Software Engineering A Practitioner’s Approach. Sixth Edition. McGraw-Hill
Companies, Inc, New York. Terno, J., Scheithauer G., Sommerweiß U., dan Riehme J.. (2000).An Efficient Approach for the Multi-
Pallet Loading Problem. Institute for Numerical Mathematics, Technical University Dresden, Dresden, Germany.