Comparison of Dynamic Programming Algorithm and Greedy Algorithm on Integer Knapsack Problem in Freight Transportation

Global Ilham Sampurno, Endang Sugiharti, Alamsyah Alamsyah

Abstract


At this time the delivery of goods to be familiar because the use of delivery of goods services greatly facilitate customers. PT Post Indonesia is one of the delivery of goods. On the delivery of goods, we often encounter the selection of goods which entered first into the transportation and  held from the delivery. At the time of the selection, there are Knapsack problems that require optimal selection of solutions. Knapsack is a place used as a means of storing or inserting an object. The purpose of this research is to know how to get optimal solution result in solving Integer Knapsack problem on freight transportation by using Dynamic Programming Algorithm and Greedy Algorithm at PT Post Indonesia Semarang. This also knowing the results of the implementation of Greedy Algorithm with Dynamic Programming Algorithm on Integer Knapsack problems on the selection of goods transport in PT Post Indonesia Semarang by applying on the mobile application. The results of this research are made from the results obtained by the Dynamic Programming Algorithm with total weight 5022 kg in 7 days. While the calculation result obtained by Greedy Algorithm, that is total weight of delivery equal to 4496 kg in 7 days. It can be concluded that the calculation results obtained by Dynamic Programming Algorithm in 7 days has a total weight of 526 kg is greater when compared with Greedy Algorithm.


Keywords


Integer Knapsack problem, Greedy Algorithm, Dynamic Programming Algorithm, freight transportation.

Full Text:

PDF

References


Alamsyah & Putri, I. T. (2014). Penerapan Algoritma Greedy Pada Mesin Penjual Otomatis (Vending Machine). Scientific Journal of Informatics, 1(2), 201-209.

Trianto, E., & Revina, W. Perancangan Sistem Iinformasi Pencatatan Pengiriman Barang di PT. TIKI Jalur Nugraha Ekakurir Cabang Bandung.

Fitriana, E. N., & Sugiharti, E. (2015). Implementasi Algoritma Genetika dengan Teknik Kendali Logika Fuzzy untuk Mengatasi Travelling Salesman Problem Menggunakan Matlab. Unnes Journal of Mathematics, 4(2).

Husni, T. S. & Arief, A. (2008). Implementasi 0-1 Knapsack Menggunakan Algoritma Dynamic Programming Pada Aplikasi Perhitungan Harga Satuan Produk Percetakan Berbasis Web (Studi Kasus: Cv Tunas Utama). Jurnal InforSAINS 2(3): 31-35.

Supriana, I. W. (2016). Optimalisasi Penyelesaian Knapsack Problem Dengan Algoritma Genetika. Lontar Komputer: Jurnal Ilmiah Teknologi Informasi, 182-192.

Paryati, P. (2015). Optimasi Strategi Algoritma Greedy untuk Menyelesaikan Permasalahan Knapsack 0-1. In Seminar Nasional Informatika (SEMNASIF), 1(1): 101-110.

Isnaeni, S., Supriyono, S., & Arini, F. Y. (2014). Implementasi Algoritma Pemrograman Dinamik Untuk Penyelesaian Persoalan Knapsack Dalam Penentuan Keuntungan Optimal Penjualan Barang. Unnes Journal of Mathematics, 3(2): 97-102.

Puspa, S. K., Mrunal, T. V. & Suhas. C. (2016). A Study of Performance Analysis on Knapsack Problem. International Journal of Computer Applications, 0975 – 8887:1

Pajjan, S. P., Roogi, R., Badiger, V., & Amaragatti, S. (2014). A New Approach to Solve Knapsack Problem. Oriental Journal Of Computer Science & Technology, 7(2):219.

Supriadi, D. (2016). Perbandingan Penyelesaian Knapsack Problem Secara Matematika, Kriteria Greedy Dan Algoritma Greedy. Indonesian Journal on Computer and Information Technology,1(2):91.

V. Springer. (2005). Knapsack 0-1 Problem. Yogyakarta: Graha Ilmu.

Faisal. (2014). Penerapan Metode Greedy Knapsack Dalam Menentukan Komposisi Buah Pada Masalah Keranjang. Jurnal Teknologi Informasi, 10(2): 32-37.

Malik, A., Sharma, A., Saroha, V. (2013). Greedy Algorithm. International Journal of Scientific and Research Publications, 3(8):1.

Tari, F.G. (2016). A Hybrid Dynamic Programming for Solving Fixed Cost Transportation with Discounted Mechanism. Hindawi Publishing Corporation Journal of Optimization, 2016(8518921):1-9.

Pratiwi, A & Rochmad M. (2014). Implementasi Algoritma Branch And Bound Pada 0-1 Knapsack Problem Untuk Mengoptimalkan Muatan Barang. Unnes Journal of Mathematics, 3(2): 90-96.

Surjawan, D, J & Susanto I. (2015). Aplikasi Optimalisasi Muat Barang Dengan Penerapan Algoritma Dynamic Programming Pada Persoalan Integer Knapsack. Jurnal Teknik Informatika dan Sistem Informasi, 1(2):151-162.

Ashari A. I., Muslim, M.A., & Alamsyah. (2016). Comparison Performance of Genetic Algorithm and Ant Colony Optimization in Course Scheduling Optimizing. Scientific Journal of Informatics, 3(2): 150.

Sugiharti, E., Firmansyah, S., & Devi, F.R. (2017). Redictive Evaluation Of Performance Of Computer Science Students Of Unnes Using Data Mining Based On Naïve Bayes Classifier (Nbc) Algorithm. Journal of Theoretical and Applied Information Technology, 95(4): 905.

Amin, S., Muslim, M.A., & Alamsyah. (2012). Sistem Deteksi Dini Hama Wereng Batang Coklat Menggunakan Jaringan Syaraf Tiruan Backpropagation. Unnes Journal of Mathematics, 1(2): 119.

Alamsyah & Arus, A.A. (2014). Analisis Sistem Pendaftaran pada Web Forum Ilmiah Matematika Unnes. Scientific Journal of Informatics, 1(1): 110.

Sugiharti, E., & Muslim, M.A. (2016). On-Line Clustering Of Lecturers Performance Of Computer Science Department Of Semarang State University Using K-Means Algorithm. Journal of Theoretical and Applied Information Technology, 83 (1): 66.

Patel, U.A., & Jain N.K. (2013). New Idea In Waterfall Model For Real Time Software Development. International Journal of Engineering Research & Technology (IJERT), 2(4): 115.

Rukmana, S.H., & Muslim, M. A. (2016). Sistem Pendukung Keputusan Tender Proyek Menggunakan Metode Benefit Cost Ratio. Jurnal Sains & Teknologi, 5(2): 817-822.

Saxena, A., & Upadhyay, P. (2016). Waterfall vs. Prototype: Comparative Study of SDLC. Imperial Journal of Interdisciplinary Research (IJIR), 2(6):1012-1013.

Roviaji, R., & Muslim M.A. (2017. Pembuatan Sistem Informasi Gardu Induk PT. Pln (Persero) App Semarang Se-Kota. Prosiding Seminar Ilmu Komputer dan Teknologi Informasi. Samarinda: Universitas Mulawarman.

Pressman, R.S. (2001). Software Engineering. Online. Tersedia di http://www.resource.mitfiles.com/ [diakses 18-2-2017].

Nugroho, Z.A., & Arifudin, R. Sistem Informasi Tracer Study Alumni Universitas Negeri Semarang Dengan Aplikasi Digital Maps. Scientific Journal of Informatics, 1(2): 154.

Rukhansah, N., Muslim, M. A., & Arifudin, R. (2016). Peramalan Harga Emas Menggunakan Fuzzy Time Series Markov Chain Model. KOMPUTAKI, 1(1): 68.

Putra, A.T. 2014. Pengembangan E-Lecture menggunakan Web Service Sikadu untuk Mendukung Perkuliahan di Universitas Negeri Semarang. Scientific Journal of Informatics, 1(2): 170.

Muslim, M.A., Kurniawati I., & Sugiharti E. (2015). Expert System Diagnosis Chronic Kidney Disease Based on Mamdani Fuzzy Inference System. Journal of Theoretical and Applied Information Technology, 78(1): 71.

Purwinarko, A. (2014). Model Expertise Management System di Universitas Negeri Semarang. Scientific Journal of Informatics, 1(2): 178.

Mustaqbal, M.S., Firdaus, F.S., Rahmadi, H. (2015). Pengujian Aplikasi Menggunakan Black Box Testing Boundary Value Analysis. JITTER, 1(3): 35.

Sugiharti E & Triliani, S. E. (2014). Perancangan Aplikasi Surat Masuk dan Keluar pada PT. Angkasa Pura 1 Semarang. Scientific Journal of Informatics, 1(1): 41.

Hardyanto, W., Purwinarko, A., Sujito, F., Masturi., Alighiri., D. (2016). Applying an MVC Framework For The System Development Life Cycle With Waterfall Model Extended. Journal of Physics: Conference Series, 824 (1): 3.




DOI: https://doi.org/10.15294/sji.v5i1.13360

Refbacks

  • There are currently no refbacks.




Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.