Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
METODE MAX MIN VOGEL’S APPROXIMATION METHOD UNTUK MENEMUKAN BIAYA MINIMAL PADA PERMASALAHAN TRANSPORTASI Bilqis Amaliah 1), Agri Krisdanto2), dan Astris Dyah Perwita3) 1,2,3)Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Jl. Teknik Kimia, Gedung Teknik Informatika, Surabaya 60111, Indonesia e-mail: 1)
[email protected], 2)
[email protected], dan 3)
[email protected]
ABSTRAK Vogel’s Approximation Method (VAM) adalah salah satu metode yang sering digunakan untuk mencari biaya minimum pada persoalan transportasi. Namun pada kenyataannya VAM memiliki banyak celah pada langkah-langkah pengerjaannya sehingga dapat menghasilkan nilai yang tidak optimal (mencapai biaya minimal). Oleh karena itu, diusulkan sebuah metode modifikasi VAM yaitu Max Min Vogel’s Approximation Method (MM-VAM) untuk menyempurnakan langkah-langkah pengerjaan VAM. Metode yang diusulkan dapat menghasilkan nilai yang lebih optimal daripada VAM, karena menggunakan Max-Min penalti dan matriks Total Oportunity Cost (TOC). Untuk membuktikan MM-VAM lebih baik dari pada VAM, maka akan diberikan contoh perhitungan numerik. Dari hasil penelitian, MMVAM menghasilkan nilai biaya yang lebih kecil daripada VAM dan dapat mecapai nilai optimal atau mendekati optimal dengan tingkat akurasi 99% . Kata kunci: Vogel’s Approximation Method (VAM), persoalan transportasi, Total Oportunity Cost.
PENDAHULUAN Permasalahan transportasi masih menjadi permasalahan klasik yang muncul pada banyak bidang diantaranya manajemen kan pendistribusian barang dari sumber (source) ke tujuan (destination). Telah banyak penelitian untuk menemukan biaya minimal pada permasalahan transportasi ini. Salah satu penyelesaian yang banyak di pakai adalah Vogel’s Approximation Method (VAM). Telah banyak penelitian yang bertujuan untuk menyempurnakan VAM. Berikut ini adalah beberapa penelitian yang bertujuan menemukan biaya minimum yang lebih rendah daripada VAM. Soomro, memodifikasi VAM untuk menentukan banyaknya barang yang dapat dikirimkan dari source ke destination sehingga kebutuhan dapat terpenuhi dan biaya pengiriman minimal (Soomro, 2015). Sebuah permasalahan transportasi memiliki permasalahan utama yang bergantung dari keefektifan fungsi yang dijalankannya. Keefektifan fungsi ini mengatur hubungan antara Source dengan peluang alokasinya ke beberapa pekerjaan atau job. Permasalahan akan diketahui dari jumlah source dan job atau destination yang tersedia. Tujuan dari penyelesaian masalah ini ditujukan untuk menemukan hubungan yang paling efektif diantara keduanya sesuai dengan batas yang telah ditentukan (Singh, 2012).
ISBN: 978-602-70604-3-2 A-2-1
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
Berbagai macam metode tersedia untuk menyelesaikan permasalahan transportasi. Beberapa metode dasar yang sudah dikenal antara lain metode Stepping Stone(Charnes, 1954), metode Modified Distribution (Danziq, 1963), metode Modified Stepping-Stone (Shih, 1987), algoritma Simplex-Type (Arsham, 1989), dan pendekatan Dual-Matrix (Ji.P, 2002). Tiap metode yang diusulkan, bertujuan untuk mencari biaya minimum yang hasilnya lebih rendah dari VAM. Namun pada kenyataannya VAM memiliki banyak celah pada langkah-langkah pengerjaannya sehingga dapat menghasilkan nilai yang tidak optimal (mencapai biaya minimal). Oleh karena itu diusulkan sebuah metode modifikasi VAM yaitu Max Min Vogel’s Approximation Method (MM-VAM) untuk menyempurnakan langkahlangkah pengerjaan VAM. Max Min Vogel’s Approximation Method (MM-VAM) yang diusulkan dapat menghasilkan nilai yang lebih optimal daripada VAM, karena memodifikasi beberapa langkah yang ada di VAM. Modifikasi yang dilakukan adalah: pertama adalah mencari matriks Total Oportunity Cost (TOC), berikutnya mencari penalti dengan cara mengurangkan antara biaya terbesar (Max) dengan biaya terkecil (Min), selanjutnya pilih dua penalti terbesar dan terakhir menggunakan minimal (biaya X alokasi) untuk memilih cell. Untuk mengevaluasi performa dan untuk membuktikan bahwa MM-VAM lebih baik dari pada VAM, maka akan diberikan dua contoh perhitungan numerik. Hasil dari MM-VAM akan dibandingkan dengan VAM. Selain dibandingkan dengan VAM, hasil MM-VAM juga akan dibandingkan dengan hasil optimal yang di dapat dari program TORA.
FORMULA PERMASALAHAN TRANSPORTASI Komponen penting permasalahan transportasi terdiri atas source sejumlah m dan destination sejumlah n. Kondisi didukung oleh komponen: = jumlah barang yang ditransportasikan dari source ke-i menuju destination ke-j, x ij c ij = biaya yang dibutuhkan untuk mentransportasikan barang dari source ke-i menuju destinasi ke-j, ai = jumlah barang yang tersedia di source ke-i, = jumlah barang yang dibutuhkan di destination ke-j. bj Formulasi solusi permasalahan trasnportasi dapat dinotasikan pada Persamaan 1 dengan batasan pada Persamaan 2, 3, dan 4 (Girmay, 2013). (1) (2) (3) (4)
ISBN: 978-602-70604-3-2 A-2-2
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
Algoritma VAM VAM adalah model solusi heuristik dan biasanya menghasilkan solusi awal yang lebih baik daripada metode lain (Nort West dan biaya terkecil). Namun pada kenyataannya, solusi yang dihasilkan VAM belum tentu sebuah solusi yang optimal. Adapun langkah-langkah metode VAM adalah sebagai berikut (Singh, 2012): 1. Hitung penalti dari setiap baris dan kolom. Nilai penalti didapat dari selisih antara nilai terkecil dari baris atau kolom dengan nilai terkecil kedua dari baris atau kolom yang sama. 2. Pilih Penalti terbesar. 3. Alokasikan sebanyak mungkin barang pada sel dengan biaya terkecil. 4. Hentikan proses bila semua barang telah dialokasikan dan semua permintaan telah dipenuhi. Bila belum, 5. Ulangi langkah 1 dengan syarat baris/kolom dengan jumlah barang 0 tidak ikut diperhitungkan pada iterasi berikutnya. VAM biasanya menghasilkan nilai yang optimal atau mendekati optimal dengan tingkat akurasi hingga 80%. Algoritma Max Min VAM (MM-VAM) Metode yang diajukan pada penelitian ini dinamakan Max Min Vogel’s Approximation Method (MM-VAM) dan merupakan modifikasi dari VAM dasar. Max Min Vogel’s Approximation Method (MM-VAM) yang diusulkan dapat menghasilkan nilai yang lebih optimal daripada VAM, karena memodifikasi beberapa langkah yang ada di VAM. Metode modifikasi ini merupakan metode heuristik dan melibatkan matriks Total Opportunity Cost (TOC). Matrix TOC diperoleh dari penjumlahan antara Opportunity Cost (OC) baris dan OC kolom. OC baris merupakan nilai matriks yang didapatkan dari pengurangan setiap baris dengan nilai terkecil dari baris tersebut. Sedangkan OC kolom adalah nilai matriks yang didapatkan dari pengurangan setiap kolom dengan nilai terkecil dari kolom tersebut. Setelah didapatkan marix TOC, berikutnya mencari penalti dengan cara mengurangkan antara biaya terbesar (Max) dengan biaya terkecil (Min), selanjutnya pilih dua penalti terbesar dan terakhir menggunakan minimal (biaya X alokasi) untuk memilih cell. Detail dari langkah-langkah algoritma MM-VAM adalah sebagai berikut: 1. Hitung penalti dari setiap baris dan kolom. Nilai penalti didapatkan dari pengurangan nilai maksimal dengan nilai minimal dari setiap baris dan kolom. 2. Pilih dua penalti tertinggi. Jika terdapat nilai penalti yang sama, pilih semua. 3. Cari sel dengan biaya terkecil pada tiap penalti. 4. Alokasikan sebanyak mungkin barang pada sel tersebut. 5. Diantara beberapa sel yang terpilih, pilih sel yang memiliki nilai transportasi (biaya x alokasi) terkecil. a. Jika terdapat nilai transportasi yang sama, pilih biaya terkecil. b. Jika biaya terkecil sama, maka pilih alokasi tertinggi. c. Jika alokasi tertinggi sama, pilih nilai penalti tertinggi. 6. Hentikan proses bila semua barang telah dialokasikan dan semua permintaan telah dipenuhi. Bila belum, 7. Ulangi langkah 1 dengan syarat baris/kolom dengan jumlah barang 0 tidak ikut diperhitungkan pada iterasi berikutnya.
ISBN: 978-602-70604-3-2 A-2-3
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
Ilustrasi Numerik Pada bagian ini, akan di diperlihatkan uji coba untuk dua matriks. Setiap matriks di selesaikan dengan menggunakan metode MM-VAM dan VAM. Penelitian ini juga menyertakan solusi optimal yang diproses dengan program TORA. 1.
Contoh Kasus pertama Matriks yang diteliti pada penelitian ini ditunjukkan oleh Matriks 1. Hasil perhitungan OC baris ditunjukkan pada Matriks 2 dan hasil perhitungan OC Kolom ditunjukkan pada Matriks 3. Sedangkan matriks TOC ditunjukkan pada Matriks 4.
O1 O2 O3 O4 Demand
D1 65 31 63 96 12
D2 8 66 19 97 13
D3 73 54 28 77 10
D4 56 42 27 46 10
D5 38 97 11 91 5
Supply 15 10 5 20 50
Matriks 1. Matriks Awal
O1 O2 O3 O4
D1 57 0 52 50
D2 0 35 8 51
D3 65 23 17 31
D4 48 11 16 0
D5 30 66 0 45
Matriks 2. Matriks OC Baris
O1 O2 O3 O4
D1 34 0 32 65
D2 0 58 11 89
D3 45 26 0 49
D4 29 15 0 19
D5 27 86 0 80
Matriks 3. Matriks OC Kolom
O1 O2 O3 O4
D1 91 0 84 115
D2 0 93 19 140
D3 110 49 17 80
D4 77 26 16 19
D5 57 152 0 125
Matriks 4. Matriks TOC
Proses MM-VAM dilakukan dengan langkah-langkah seperti yang telah dijelaskan pada bab sebelumnya yang terus diulang setiap iterasi. Pada setiap iterasi dilakukan perhitungan penalti dan pengambilan keputusan untuk penempatan barang atau supply yang diminta. Setiap proses iterasi akan ditunjukkan pada Matriks 5 hingga Matriks 10.
ISBN: 978-602-70604-3-2 A-2-4
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
O1 O2 O3 O4 Request
D1
D2
91
0
D3
D4
D5
Supply
110
77
57
15
Penalty 1 2
13 0
93
49
26
152
10
84
19
17
16
0
5
115
140
80
19
125
20
12
13
10
10
5
50/50
93
61
152
Penalty 1 115
0
140
110 152 84 121
Matriks 5. Iterasi 1 Proses MM-VAM
O1 O2 O3 O4 Request Penalty
D1
D2
D3
D4
D5
Supply
91
0
110
77
57
2
93
49
26
152
10
84
19
17
16
0
5
115
140
80
19
125
20
0
10
10
5
50/50
x
93
61
152
53
13 0
0
10
12
2
2 115
Penalty 2
152 84 106
Matriks 6. Iterasi 2 Proses MM-VAM
O1 O2 O3 O4 Request Penalty
D1
D2
D3
D4
D5
Supply
91
0
110
77
57
2
93
49
26
152
0
19
17
16
0
5
53
13 0
126
10 84
5 115
140
80
19
125
2
0
10
10
5
x
93
61
152
3 31
Matriks 7. Iterasi 3 Proses MM-VAM ISBN: 978-602-70604-3-2 A-2-5
20 0
50/50
Penalty 3
0
84 106
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
O1 O2 O3 O4 Request Penalty
D1
D2
D3
D4
D5
Supply
91
0
110
77
57
2
93
49
26
152
0
19
17
16
0
33
13 0
X
10 84
0
X
5 115
140
2 4 24
80
19
0
10
10
x
30
58
10 0
Penalty 4
125
20
10
0
50/50
96
x
Matriks 8. Iterasi 4 Proses MM-VAM
O1 O2 O3 O4 Request Penalty
D1
D2
91
0
O2 O3 O4 Request
D4
D5
Supply
110
77
57
2
0
93
49
26
152
0
19
17
16
0
0
x
10 84
x
5 115
140
2
80
0
5 24
10
19 10 0
125
10
0
50/50
10 0
Penalty 5 19
13
0
35
x 30 x x Matriks 9. Iterasi 5 Proses MM-VAM
D1 O1
D3
D2
91
D3
D4
D5
Supply
110
77
57
2
93
49
26
152
0
19
17
16
0
0
0 2
0
13
10 84
5 115
140
80
19 10
2
Penalty 6 91
125
0 50/50
10
0
0
0
0
x
x
x
x
Matriks 10. Iterasi 6 Proses MM-VAM
ISBN: 978-602-70604-3-2 A-2-6
Penalty 6 91 x x x
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
Setelah didapatkan semua alokasi yang diinginkan untuk setiap permintaan, maka dilakukan perhitungan biaya yang melibatnya biaya dari matriks awal. Matriks akhir lengkap beserta alokasi yang telah diputuskan oleh sistem ditunjukkan pada Matriks 11. D1
D2
65
O1
D3
D4
D5
73
56
38
66
54
42
97
19
28
27
11
8 2
15
13
31
O2
Supply
10
10 63
O3
5
5 96
O4
97
77
46 10
12
Request
13
10
91
20
10 10
50/50
5
Matriks 11. Matriks Akhir Solusi
Solusi akhir perhitungan adalah: (65*2)+(8*13)+(31*10)+(77*10)+(46*10)+(11*5)= 1.829 Contoh Kasus kedua Pada percobaan kedua, dilakukan penyelesaian masalah dengan prosedur MM-VAM yang ditunjukkan pada Matriks 12. Hasil prosedur MM-VAM ditunjukkan pada Matriks 13. D1 91 96 98 76 97 85 17
S1 S2 S3 S4 S5 S6 Demand
D2 76 87 98 88 82 82 12
D3 65 59 79 61 98 78 21
D4 76 79 90 99 76 81 9
D5 71 87 92 87 76 88 9
D6 90 88 74 89 80 91 5
D7 90 89 85 91 99 71 6
Supply 6 12 15 15 21 10
Matriks 12. Matriks Awal
O1 O2 O3 O4 O5 O6 Request
D1
D2
D3
D4
D5
91
76
65
76
71
D6
D7
90
90 89
Supply 6
6 96
87
59
79
87
88
90
92
74
12
12 98
98
79
10 76
88
61
6 97
99
98
87
76
9 82 1 17
15
89
91
80
99
91
71
15
9 82
85
85 5
76 9
78
81
88
3 12
21
3 6
21
9
9
5
10
6
Matriks 133. Matriks Akhir Solusi
Solusi akhir perhitungan adalah: (98*10)+(76*6)+(85*1)+(82*9)+(82*3)+(59*12)+(61*9) +(76*9)+(76*3)+(74*5)+(71*6)= 5.896 ISBN: 978-602-70604-3-2 A-2-7
Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016
ANALISA HASIL DAN KESIMPULAN Pada setiap percobaan, diperoleh biaya total dari jumlah keseluruhan biaya x alokasi yang telah terpilih. Selain itu dilakukan pula perhitungan biaya dengan metode VAM dan perhitungan biaya optimal dengan bantuan program TORA. Perbandingan biaya inilah yang menjadi acuan performa dari metode MM-VAM yang diajukan pada penelitian ini. Hasil perbandingan antara metode MM-VAM, VAM dan nilai optimal yang ditunjukkan pada tabel. Tabel Perbandingan Metode MM-VAM, VAM, dan optimal Contoh Pertama Kedua
MM-VAM 1829 5896
VAM 1940 5971
Optimal 1829 5854
akurasi (%) 100 99
Pada contoh kasus pertama didapatkan hasil MM-VAM sebesar 1829 yang juga merupakan solusi optimal dari Permasalahan yang ada. Hasil ini juga menyatakan bahwa hasil MM-VAM lebih baik daripada metode VAM. Pada contoh kasus kedua didapatkan hasil MM-VAM sebesar 5896. Walaupun nilai yang didapatkan belum mencapai optimal, namun hasil dari proses MM-VAM masih lebih baik daripada metode VAM. Sehingga dapat disimpulkan bahwa Metode MM-VAM Modifikasi dapat menyelesaikan permasalahan transportasi dan menghasilkan biaya yang lebih kecil daripada VAM. Metode MM-VAM dapat juga mecapai nilai optimal atau mendekati optimal dengan tingkat akurasi 99%.
DAFTAR PUSTAKA Arsham, H. dan Kahn, A. (1989). A simplex-type for generall transportation problems: An alternative to Stepping-Stone. Journal of Operational Reseach Society, 40(6), pp. 581-590. Charnes, A. dan Cooper, W. (1954). The Stepping-Stone method for explaining linear programming calculations in transportation problem. Management Science, 1(1), pp. 49-69. Dantzig, G. (1963). Linear Programming and Extensions. Princeton: NJ:Princeton University Press. Girmay, N. dan Sharma, T. (2013). Balance An Unbalanced Transportation Problem By A Heuristic Approach. International Journal of Mathematics And Its Application, 1(1), pp. 13-19. Ji, P. dan Chu, K. (2002). A dual-matrix approach to the transporation problem. Asia-Pasific Journal of Operation Research , 19(1), pp. 35-45. Shih, W. (1987). Modified Stepping-Stone Method as a teaching aid for capacitated transportation probems. European Journal of Operational Research, Volume 122, pp. 662-676. Singh, S., Dubey, G. dan Shrivastava, R. (2012). Optimization and analysis of some variants through Vogel's approximation method (VAM). IOSR Journal of Engineering, 2(9), pp. 20-30. Soomro, A. S., Junaid, M. dan Tularam, G. A. (2015). Modified Vogel's Approximation Method for Solving Transportation Problems. Mathematical Theory and Modeling, 5(4). ISBN: 978-602-70604-3-2 A-2-8
