eISSN 2722-9886   pISSN 1411-6669 https://jurnal.unej.ac.id/index.php/MIMS/index
Solusi optimal masalah transportasi biaya tetap menggunakan metode pendekatan tangga
(Optimal solution of fixed cost transportation problem using stairs approach method )
Nizmi Fitri Rahayu, Fahrudin Muhtarulloh * , Dian Nuraiman
Jurusan Matematika, Fakultas Sains dan Teknologi, UIN Sunan Gunung Djati Bandung Jl. A.H. Nasution No. 105 Kec. Cibiru, Kota Bandung, Jawa Barat, Indonesia
*korespondensi: fahrudin.math@uinsgd.ac.id
Received: 19-12-2022, accepted: 04-03-2023

## Abstract
One special case in transportation problems is the problem of fixed cost transportation, where in this transportation problem there are two cost components, namely fixed costs and variable costs. The difficulty encountered when solving the problem of fixed costs is caused by the behavior of these costs which do not depend on the number of units loaded/transported on the route traversed. The  purpose  of  this  study  is  to  determine  the  optimal  solution  to  the  fixed  cost  transportation problem. This research uses Balinski's linear approach, namely the Stairs Approach Method. The case study used is unbalanced data measuring 3×8, where the fixed costs are vehicle rental costs and the variable costs are fuel. The optimal solution obtained is Rp. 11511.411.768.000,- (eleven trillion five hundred eleven million five hundred eleven billion four hundred eleven million seven hundred sixty-eight thousand rupiah). So it can be concluded that the Ladder Approach Method can be used to find the optimal solution to the fixed cost transportation problem.
Keywords: Fixed costs, transportation problems, stairs approach method, optimal solution MSC2020: 76N25

## 1. Pendahuluan
Semakin  berkembangnya  bidang  industri  menyebabkan  masalah  transportasi  menjadi salah satu permasalahan penting yang harus diperhatikan dalam menjalankan perusahaan [ 1 ].  Transportasi  berguna  dalam  berbagai  hal  bagi  perusahaan,  beberapa  di  antaranya yaitu:  jadwal  pengiriman  dari  pabrik  ke  titik  lokasi  gudang  ataupun  titik  pemasaran, penentuan  lokasi  pabrik/gudang,  jadwal  produksi,  penempatan  fasilitas/mesin,  dan sebagainya [ 2 ]. Untuk mendapatkan laba atau keuntungan, suatu perusahaan harus dapat menghasilkan  pendapatan  yang  lebih  besar  dibandingkan  dengan  jumlah  biaya  yang dikeluarkannya. Dengan begitu perusahaan perlu memahami konsep  biaya untuk dapat
meminimasi  biaya  serta  maksimasi  laba.  Berdasarkan  perilaku  biaya  maka  biaya dikelompokkan menjadi tiga kategori. Pertama, biaya variabel yaitu biaya yang berubah seiring  dengan  perubahan  tingkat  kegiatan  perusahaan.  Kedua,  biaya  tetap  merupakan biaya  yang  cenderung  tidak  berubah  meskipun  terdapat  perubahan  tingkat  kegiatan perusahaan dalam batas tertentu. Ketiga, biaya semi variabel yaitu biaya yang sebagian memiliki perilaku biaya variabel dan biaya tetap [ 3 ].
Pada  masalah transportasi klasik, biaya transportasi  yang ada  berbanding  lurus dengan jumlah barang yang akan dipindahkan. Sedangkan pada masalah transportasi biaya tetap, terdapat perilaku biaya lain yaitu biaya tetap itu sendiri yang akan dibebankan untuk tiap rute transportasi, di  mana perilaku biaya  ini  mungkin saja terjadi dalam kasus nyata di kehidupan  sehari-hari  [ 4 ].  Masalah  biaya  tetap  mungkin  merupakan  salah  satu  dari pemrograman matematika yang paling menarik banyak minat untuk dikaji. Strukturnya sangat mirip dengan pemrograman linear, tetapi satu perbedaan, yaitu adanya biaya tetap pada fungsi objektifnya, mempersulit pengembangan teori untuk mencari solusinya [ 5 ].
Pada  tahun  1961,  saat  itu  Balinski  [ 6 ]  menunjukkan  kasus  khusus  yaitu  masalah transportasi  biaya  tetap  dari  permasalahan  transportasi.  Balinski  mengajukan  metode pendekatan untuk mendapatkan hasil  yang  mendekati optimal. Selanjutnya, pada tahun 1962, Kuhn [ 7 ] menggunakan pendekatan heuristik dan akhirnya menjadi metode yang cukup  dikenal.  Banyak  pula  peneliti  lain  yang  mengembangkan  metode  heuristik  ini, beberapa diantaranya  yaitu  Cooper dan Drebes  [ 8 ], Diaby  [ 9 ], Sun dkk.  [ 10 ], Adlakha dkk. [ 11 ]. Pada tahun 1968, diajukan mengenai metode stage-ranking oleh Murty [ 4 ] dan beberapa  tahun  selanjutnya  oleh  Sadagopan  dkk. [ 12 ].  Pada tahun  1970,  Steinberg  [ 5 ] mengajukan algoritma berdasarkan metode branch and bound. Gray [ 13 ] di tahun 1971 mencoba  menemukan  solusi  optimal  menggunakan  dekomposisi.  Palekar  [ 14 ]  juga menggunakan  metode branch and bound di tahun 1990. Roberti dkk. [ 15 ]  memberikan algoritma berdasarkan formulasi masalah integer yang baru. Tari [ 16 ] mengajukan hybrid dynamic  programming  untuk  menyelesaikan  mekanisme  diskon  pada  masalah transportasi biaya tetap. Zhao dkk. [ 17 ] membentuk formulasi berdasarkan dekomposisi Lagrangian  dan  generasi  kolom.  Selain  itu,  masih  banyak  lagi  peneliti  yang  mengkaji tentang masalah transportasi biaya tetap.
Penelitian  ini  bertujuan  untuk  mencari  solusi  optimal  masalah  transportasi  biaya  tetap dengan menggunakan  metode pendekatan tangga yang diperkenalkan oleh Muralidaran dan Venkateswarlu [ 18 ]. Metode  pendekatan tangga  menggunakan  metode pendekatan linier yang telah diajukan oleh Balinski untuk mencari solusi optimal masalah transportasi biaya tetap.

## 2. Metodologi
Masalah  transportasi  biaya  tetap  yang  peniliti  lakukan  adalah  untuk  meminimumkan fungsi tujuan berikut:
P: min 𝑍 = ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗 + 𝑓 𝑖𝑗 𝑦 𝑖𝑗 𝑛 𝑗=1 𝑚 𝑖=1 (1)
dengan 𝑚 = jumlah sumber; 𝑛 = jumlah tujuan; 𝑥 𝑖𝑗 = jumlah unit yang dikirim dari sumber i sampai tujuan j ; 𝑐 𝑖𝑗 = biaya pengiriman unit dari sumber i sampai tujuan j ; dan 𝑓 𝑖𝑗 = biaya tetap (fixed cost) untuk pengiriman dari sumber i sampai tujuan j .
Dalam penelitian ini metode yang digunakan adalah metode pendekatan tangga. Tahapan- tahapan dalam metode ini adalah sebagai berikut [18]:
(1) Cari  minimum  dari  tiap  baris  dan  kurangi  dengan  entri  baris  masing-masing.  Dari hasil tersebut, cari minimum kolom dan kurangi dengan entri kolom masing-masing.
(2) Bentuk tabel penjatahan dengan memeriksa tiap baris persediaan harus kurang dari atau sama dengan total persediaan di mana biaya yang tereduksi pada baris tersebut adalah nol. Gunakan cara yang sama untuk kolom permintaan. Lanjut ke langkah 6 jika telah memenuhi. Jika tidak, lanjut ke langkah 4.
(3) Dari  tabel  transportasi  tereduksi,  untuk  menutupi  nilai  nol,  gambarkan  jumlah minimum  dari  garis  vertikal  dan  horizontal,  sedemikian  sehingga  untuk  entri kolom/dan baris yang belum memenuhi syarat tabel penjatahan.
(4) Cari  nilai  terkecil  dari  sel  yang  tidak  tertutup  garis  dan  tambahkan  pada  sel  yang tertutupi  dua  kali,  kurangi  dengan  sel  yang  tidak  tertutup  dan  biarkan  sel  yang tertutup satu kali. Kemudian lanjut ke langkah 3.
(5) Pada tabel penjatahan, pilih sel yang mempunyai biaya maksimum yang tereduksi, yaitu nilai nol (misalkan λ 𝑖𝑗 ). Pilih salah satu jika terdapat beberapa nilai maksimum.
(6) Pilih sel pada baris ke- i dan kolom ke- j dari sel λ 𝑖𝑗 sedemikian sehingga baris/kolom yang terpilih hanya memiliki satu nol. Alokasikan maksimum yang memungkinkan pada sel tersebut. Cari nilai maksimum selanjutnya jika sel tersebut tidak terjadi pada λ 𝑖𝑗 dan pilih sebagai λ 𝑖𝑗 baru.
(7) Ubah  kembali  tabel  biaya  tetap  dengan  menghapus  titik  persediaan  yang  telah digunakan dan titik tujuan yang telah dicapai.
(8) Ulagi  langkah  6  dan  7  sampai  seluruh  titik  permintaan  dan  titik  persediaan  telah hilang.

## 3. Hasil dan Pembahasan
Pada penelitian ini, data yang digunakan adalah data yang didapat dari jurnal Venn Y. I. Ilwaru, Yopi Andry Lesnussa, Jesica Tentua, “Optimasi Biaya Distribusi Beras Miskin (RASKIN)  Menggunakan  Masalah  Transportasi  Tak  Seimbang”.  BAREKENG:  Jurnal
Ilmu Matematika dan Terapan tahun 2020. Kasus minimasi tidak seimbang ( unbalance ) berukuran 3×8 [19]. Data tersebut berkaitan dengan penyaluran RASKIN yang berada di pulau Ambon pada bulan Januari tahun 2017. Dalam proses pendistribusian RASKIN ini, pertimbangkan bahwa pemerintah menggunakan jasa sewa kendaraan untuk mengangkut dan mendistribusikan beras dari sejumlah sumber ke sejumlah lokasi yang ada. Sumber yang  dimaksud  adalah  Gudang  Beras  Bulog  Solabar,  Gudang  Beras  Bulog  Halong, Gudang  Beras  Bulog  Tulehu,  masing-masing  dinotasikan  dengan  S1,  S2,  dan  S3. Sedangkan  tujuan  pendistribusian  adalah  Kec.  Nusaniwe,  Kec.Sirimau,  Kec.  Teluk Ambon, Kec. Baguala, Kec. Leitimur Selatan, Kec.Leihitu, Kec. Leihitu Barat, dan Kec. Salahutu yang masing-masing dinotasikan dengan D1, D2, D3, D4, D5, D6, D7, dan D8. Kendaraan yang digunakan dalam proses pengiriman yaitu truk dengan kapasitas muatan maksimal 10 ton. Dengan mempertimbangkan jumlah persediaan dan permintaan, maka jumlah kebutuhan truk dapat dinyatakan sebagai berikut:

## Kebutuhan truk =
{ persediaan kapasitas truk ; permintaan > persediaan, permintaan kapasitas truk ; permintaan < persediaan.
Kebutuhan truk di atas merupakan kebutuhan selama 1 bulan pengiriman. Dalam sehari, satu truk mampu melakukan pengiriman RASKIN sebanyak satu kali termasuk perjalanan keberangkatan  dan  kembalinya  truk  ke  gudang.  Sehingga  jumlah  minimal  truk  yang dibutuhkan dalam sebulan diperoleh dari pembagian kebutuhan truk dengan banyaknya hari selama satu bulan (31 hari). Biaya sewa kendaraan yaitu sebesar Rp 25.000.000/unit selama satu bulan. Sehingga total biaya sewa kendaraan adalah:
Biaya sewa kendaraan = jumlah minimal truk x biaya sewa per unit .
Selain biaya sewa kendaraan, terdapat pula biaya lain yaitu biaya bahan bakar. Biaya ini dihitung  mulai  dari  perjalanan  keberangkatan  sampai  kembali  ke  gudang.  Selanjutnya, untuk  1  liter  solar  dapat  digunakan  oleh  truk  selama  3  km  dengan  harga  Rp.  5.500. Perhitungan matematis untuk total biaya bahan bakar yaitu:

## Biaya bahan bakar = jumlah truk  × jarak  × harga 1 liter solar × 31.
Dari  perhitungan  sebelumnya  dapat  dibentuk  tabel  parameter  biaya  dengan  bentuk matriks sebagai berikut:
(𝑓 𝑖𝑗 ; 𝑐 𝑖𝑗 ) = (biaya sewa kendaraan, biaya bahan bakar) .
Tabel 1. Tabel parameter biaya transportasi (𝑓 𝑖𝑗 ; 𝑐 𝑖𝑗 ) Tujuan Sumber D1 D2 D3 D4 D5 D6 D7 D8 Supply S1 50.000; 767 75.000; 2.826 50.000; 3.832 50.000; 5.109 25.000; 4.311 50.000; 11.815 25.000; 6.227 50.000; 9.579 1.332.634 S2 50.000; 2.331 75.000; 1.533 50.000; 1.916 50.000; 2.268 25.000; 2.874 50.000; 9.899 25.000; 5.269 50.000; 6.706 1.461.624 S3 50.000; 8.622 75.000; 11.016 50.000; 7.025 50.000; 3.832 25.000; 3.672 50.000; 12.772 25.000; 7.823 50.000; 511 825.795
Demand 603.900  630.000  369.540  313.740  110.520  599.400  250.560  351.540
* biaya dalam ribuan
Dari  Tabel  1,  dibentuk  tabel  balinski  RTP  menggunakan  persamaan  8  dengan  hasil diberikan pada Tabel 2.
Tabel 2. Tabel balinski rtp ( 𝐷 𝑖𝑗 ) untuk metode pendekatan tangga Tujuan Sumber D1 D2 D3 D4 D5 D6 D7 D8 Supply S1 767,083  2.826,119  3.832,135 5.109,159 4.311,226 11.815,083  6.227,1  9.579,142 1.332.634 S2 2.331,083  1.533,119  1.916,135 2.268,159 2.874,226  9.899,083  5.269,1  6.706,142 1.461.624 S3 8.622,083 11.016,119 7.025,135 3.832,159 3.672,226 12.772,083  7.823,1  511,142  825.795 Demand 603.900 630.000 369.540  313.740  110.520 599.400  250.560  351.540
Karena studi kasus ini merupakan kasus tidak seimbang ( unbalanced ), dengan kata lain jumlah  total supply ≠  jumlah  total demand ,  maka  perlu  adanya  penambahan  variabel dummy. Setelah mengurangi tiap baris dan kolom dengan nilai minimum masing-masing, diperoleh tabel transportasi yang telah tereduksi sebagai berikut.

## Tabel 3. Tabel transportasi tereduksi
Tujuan Sumber D1 D2 D3 D4 D5 D6 D7 D8 Dummy  Supply S1 0 1.293 1.916 2.841 1.437 1.916 958 9.068 0 1.332.634 S2 1.564 0 0 0 0 0 0 6.195 0 1.461.624 S3 7.855 9.483 5.109 1.564 798 2.873 2.544 0 0 825.795
Demand  603.900  630.000  369.540  313.740  110.520  599.400  250.560  351.540  390.853
Dapat  dilihat  pada  Tabel  3  bahwa  tabel  tersebut  tidak  memenuhi  syarat  dari  tabel penjatahan pada S1 dan S3. Oleh karena itu, lanjut ke langkah berikutnya yaitu  langkah 4-5 hingga diperoleh tabel penjatahan yang dapat dilihat pada Tabel 4.

## Tabel 4. Tabel penjatahan
Tujuan Sumber D1 D2 D3 D4 D5 D6 D7 D8 Dummy  Supply S1 0 0 623 1.548 639 623 0 9.068 0 1.332.634 S2 2.857 0 0 0 495 0 335 7.488 1.293  1.461.624 S3 7.855 8.190 3.816 271 0 1.580 1.586 0 0 825.795
Demand 603.900  630.000  369.540  313.740 110.520  599.400  250.560 351.540 390.853
Selanjutnya,  alokasikan  maksimum  yang  memungkinkan  pada  sel  dengan  entri  nol. Setelah total permintaan dan total persediaan telah habis dialokasikan, maka tabel tersebut dapat dinamakan sebagai tabel alokasi yang dapat dilihat pada Tabel 5.
Tabel 5. Tabel alokasi
Tujuan Sumber D1 D2 D3 D4 D5 D6 D7 D8 Dummy  Supply S1 603.900  451.056 0 0 0 0 250.560 0 27.118  1.332.634 S2 0 178.944  369.540  313.740 0 599.400 0 0 0 1.461.624 S3 0 0 0 0 110.520 0 0 351.540  363.735  825.795 Demand 603.900  630.000  369.540  313.740  110.520  599.400  250.560  351.540  390.853
Dari Tabel 5, dapat disimpulkan bahwa untuk mendapatkan solusi optimal, alokasi untuk pendistribusian  RASKIN  yaitu:  Sumber  S1  perlu  mengirimkan  RASKIN  sebanyak 603.900 kg ke tujuan D1, 451.056 kg ke tujuan D2, dan 250.560 kg ke tujuan D7. Sumber S2 perlu mengirimkan RASKIN sebanyak 178.944 kg ke tujuan D2, 369.540 kg ke tujuan D3, 313.740 kg ke tujuan D4 dan 599.400 kg ke tujuan D6. Sumber S3 perlu mengirimkan RASKIN sebanyak 110.520 kg ke tujuan D5 dan  351.540 kg ke tujuan D8. Selain  itu, perlu  diingat  bahwa  variabel  dummy  tidak  dihitung.  Dengan  menggunakan  persamaan (1) diperoleh solusi optimal untuk masalah transportasi biaya tetap menggunakan metode pendekatan tangga yaitu sebesar Rp 11.511.411.768.000,-.

## 4. Kesimpulan
Berdasarkan  hasil  dan  pembahasan  yang  sudah  dikerjakan  sebelumnya,  dapat disimpulkan bahwa metode pendekatan tangga dapat menyelesaikan masalah transportasi biaya  tetap  dan  menghasilkan  solusi  yang  optimal.  Hasil  yang  diperoleh  dari  metode pendekatan tangga yaitu biaya minimum sebesar Rp 11.511.411.768.000,-.

## Daftar Pustaka
[1]  D.J.  Bowersox,  D.J.  Closs,  M.B.  Cooper, Supply  Chain  Logistics  Management , New York: The McGraw-Hill Companies, Inc., 2002.
[2]  A.  Meflinda,  Mahyarni, Operations  Research ( Riset  Operasi ),  Pekanbaru:  Unri Press, 2011.
[3]  W. Winarso, "Pengaruh biaya operasional terhadap profitabilitas (ROA) PT Industri Telekomunikasi Indonesia (Persero)," Ecodemica, vol. II, no. 2, pp. 258-272, 2014. [ CrossRef ]
[4]  K.G.  Murty,  "Solving  the  fixed  charge  problem  by  ranking  the  extreme  points," Operations Research, vol. 16, pp. 268-279, 1968. [ GreenVersion ]
[5]  D.I.  Steinberg, "The  fixed charge problem," Naval  Research Logistics Quarterly, vol. 17, pp. 217-235, 1970. [ CrossRef ]
[6]  M.L.  Balinski,  "Fixed-cost  transportation  problem," Naval  Research  Logistics Quarterly, vol. 8, pp. 41-54, 1961. [ CrossRef ]
[7]  H.W.  Kuhn,  W.J.  Baumol,  "An  approximation  algorithm  for  the  fixed  charge transportation  problem," Naval  Research  Logistics  Quarterly, vol.  9,  pp.  1-15, 1962. [ GreenVersion ]
[8]  L. Cooper, C. Drebes, "An approximate algorithm for the fixed charge problem," Naval Research Logistics Quarterly, vol. 14, no. 1, pp. 101-113, 1967. [ CrossRef ]
[9]  M. Diaby, "Successive linear approximation procedure for generalized fixed-charge transportation  problems," Journal  of  Operational  Research  Society, vol.  42,  pp. 991-1001, 1991. [ CrossRef ]
[10]  M.  Sun,  J.E.  Aronson,  P.G.  McKeown,  D.  Drinka,  "A  tabu  search  heuristic procedure  for  the  fixed  charge  transportation  problem," European  Journal  of Operational Research, vol. 106, no. 2-3, pp. 441-456, 1998. [ CrossRef ]
[11]  V.  Adlakha,  K.  Kowalski,  B.  Lev,  "A  branching  method  for  the  fixed  charge transportation problem," Omega, vol. 38, no. 5, pp. 393-397, 2010. [ CrossRef ]
[12]  S.  Sadagopan,  A.  Ravindran,  "A  vertex  ranking  algorithm  for  the  fixed-charge problem," Journal of Optimization Theory and Application , vol. 37, pp. 221-230, 1982. [ CrossRef ]
[13]  P. Gray, "Exact solution of the  fixed-charge transportation problem," Operations Research, vol. 19, pp. 1529-1538, 1971.
[14]  U.S. Palekar, M.H. Karwan, S. Zionts, “A branch-and-bound method for the fixed charge  transportation  problem,” Management  Science, vol.  36,  no.  9,  pp.  1092- 1105, 1990. [ GreenVersion ]
[15]  R.  Roberti,  E.  Bartolini,  A.  Mingozzi,  "The  fixed  charge transportation  problem: An  exact  solution  algorithm  based  on  a  new  integer  programming  formulation," Management Science, vol. 61, no. 6, 2014. [ GreenVersion ]
[16]  F.G.  Tari,  "A  hybrid  dynamic  programming  for  solving  fixed  cost  transportation with discounted mechanism," Journal of Optimization, pp. 1-9, 2016. [ CrossRef ]
[17]  Y. Zhao, T. Larsson, E. Ronberg, P.M. Pardalos, "The fixed charge transportation problem:  a  strong  formulation  based  on  Lagrangian  decomposition  and  column generation," Journal of Global Optimization, vol. 72, pp. 517-538, 2018. [ CrossRef ]
[18]  C. Muralidaran, B. Venkateswarlu, "Optimal  solution of fixed cost transportation problems by approximating staircase method," Advances in Mathematics: Scientific Journal, vol. 9, no. 8, pp. 6049-6058, 2020.
[19]  V.Y.I. Ilwaru,  Y.A.  Lesnussa,  J.  Tentua,  "Optimasi  biaya  distribusi  beras  miskin (raskin)  menggunakan  masalah  transportasi  tak  seimbang," BAREKENG:  Jurnal Matematika dan Terapan, vol. 14, no. 4, pp. 609-618, 2020. [ CrossRef ]