MODEL ASIMETRIS GABUNGAN INVENTORY DAN ROUTING UNTUK MINIMISASI HARGA KOMODITI

JURNAL MATEMATIKA DAN KOMPUTER Vol. 7. No. 2, 42 - 51, Agustus 2004, ISSN : 1410-8518

MODEL ASIMETRIS GABUNGAN INVENTORY DAN ROUTING UNTUK MINIMISASI HARGA KOMODITI Sarwadi, Susilo Hariyanto Jurusan Matematika FMIPA UNDIP Abstrak Dalam penelitian ini, akan dirumuskan suatu model matematik yang merupakan gabungan antara masalah inventory dan routing. Model dibangun dengan memperhatikan sifat asimetris matrik jarak antar kota. Masalah ini diselesaikan dengan menggunakan teori graph. Perumusan masalah dinyatakan ke model Mixed Integer Linier Programming. Model ini disusun untuk kasus minimisasi suatu harga komoditi. Selanjutnya, model yang dibangun dikaji karakteristik-karakteristiknya untuk membuktikan kesahihannya, sehingga diperoleh suatu model MILP yang valid untuk permasalahan inventory dan routing. Kata kunci : asimetris model, inventory dan routing

1. PENDAHULUAN Salah satu daya saing produk di era pasar bebas adalah mutu dan harga. Mutu dicapai lewat penerapan tekhnologi dan kontrol kualitas. Dan hal ini telah menjadi fokus upaya semua industri dan perusahaan untuk memberikan nilai tambah pada produknya. Namun demikian langkah ini kadang meningkatkan biaya produksi yang akhirnya produknya menjadi lebih mahal. Disisi lain, harga merupakan salah satu nilai kompetitif dan daya tarik suatu produk. Produk yang harganya relatif murah akan lebih berdaya saing. Secara ekonomi, harga komoditi tergantung pada ongkos produksi. Bila ongkos produksi bisa ditekan diharapkan bisa membuat harga komoditi menjadi murah dan lebih kompetitif. Langkah ini masih sedikit dilakukan karena memerlukan efisiensi di setiap segmen proses produksi. Dan efiensiesi bisa dicapai apabila bisa diperoleh perhitungan optimal di masing – masing tahapnya. Masalah Inventory-Routing (IRP) telah diteliti sejak tahun 80’an seperti : Federgruen dan Zipkin (1984) yang mencoba menformulasikan masalah ke dalam bentuk nonlinear program. Namun mereka belum memberikan formulasi matematis yang memungkinkan diturunkannya metode exact. Model Nonlinear yang diajukan belum ada solusi exactnya. Model ILP juga masih diselesaikan

42

Model Asimetris ……… ( Sarwadi, Susilo Hariyanto )

secara heuristik. Pada umumnya solusi yang diberikan masih merupakan solusi pendekatan, jadi belum optimal. Beberapa peneliti mencoba menyelesaikan berbagai kombinasi masalah seperti diantaranya adalah Anily dan Bramel (1999) mengkombinasikan vehicle routing dan supply chain; Chandra dan Fisher (1994) mengkoordinasikan antara rencana produksi dan distribusi, dll. Penyelesaian secara integrative ternyata memberikan hasil yang lebih baik karena memperhatikan interpedensi dari masing – masing komponen biaya. Tekhnik dekomposisi telah banyak diterapkan untuk mereduksi kompleksitas dari permasalahan. Langkah ini diantaranya diterapkan oleh Kim dan Kim (1999), Carter et. all.(1999) dan Chandra (1996). Model yang terstruktur masalah kombinasi telah dikembangkan pula oleh beberapa peneliti antara lain : Carter et.all.(1994), Chandra (1996) yang mengembangkan model program integer campuran atau Mixed Integer Linear Program (MILP) untuk masalah produksi dan distribusi. Anily dan Federgruren (1990, 1993), Anily (1994) mengembangkan model Nonlinear model untuk kombinasi inventory dan transportasi. Namun model ini tidak menarik karena penyelesaiannya yang rumit. Dan kebanyakan dari tekhnik solusi yang diusulkan bersifat heuristik atau aproksimasi. Struktur model yang dikembangkan Chandra belum menghasilkan metode exact namun memungkinkan untuk dimodifikasi agar bisa diturunkan metode exact. Berdasarkan akan hal ini, penelitian pendahuluan untuk pengembangan model terintegrasi antara inventory dan vehicle routing telah dilakukan Achuthan dan Sarwadi (2000). Modifikasi dan perbaikan model ini masih bisa dilakukan dengan memperhatikan sifat asimetris dari rute (jalan) yang pada umumnya asimetris.

2. PEMBAHASAN 2.1. Pemodelan Dalam penelitian ini akan diteliti suatu sistem distribusi yang terdiri dari sebuah gudang pusat dinyatakan dengan “0” (nol) dan n pengecer yang dinyatakan dengan j, 1 ≤ j ≤ n . Rentang waktu perencanaannnya

T periode dinyatakan

dengan t, 1 ≤ t ≤ T . Setiap pengecer j mempunyai permintaan yang tertentu untuk

43


suatu komoditas selama periode t dinyatakan dengan D tj , 1 ≤ j ≤ n , 1 ≤ t ≤ T . Kehabisan stok tidak diperkenankan, oleh karena itu setiap permintaan harus dipenuhi saat itu juga. Komoditas itu dibeli secara borongan oleh depot, menimbulkan biaya pesan O0 untuk tiap pembeliaan borongan. Depot menyimpan komoditas dan mendistribusikan ke pengecer dengan menggunakan beberapa kendaraan yang identik dengan kapasitas muatan sama yaitu W. Ketika pemesanan komoditas oleh pengecer j, maka biaya pemesanan dinyatakan dengan O tj , 1 ≤ j ≤ n , 1 ≤ t ≤ T . Untuk setiap unit komoditas yang berada di gudang pada setiap akhir periode dikenakan biaya inventory

H tj , 1 ≤ j ≤ n , 1 ≤ t ≤ T . Pada awal rentang waktu perencanaan, managemen harus menentukan jumlah supply komoditas untuk setiap pengecer dan depot di setiap periode t, 1 ≤ t ≤ T . Diasumsikan tidak ada waktu tunggu pemesanan. Lebih lanjut, managemen harus memutuskan route kendaraan untuk pendistribusian komoditas dari depot ke pengecer yang membutuhkan dalam setiap waktu. Selama pendistribusian komoditas, apabila kendaraan secara langsung mengantar komoditas dari pengecer j ke pengecer k, biaya transportnya dinyatakan dengan

C jk , 0 ≤ j ≠ k ≤ n .Pada awal periode 1, syarat awal inventory pengecer dan depot adalah 0. Permasalahan inventory dan pendistribusian adalah meminimalkan biaya keseluruhan (pemesanan, inventory dan pendistribusian) selama rentang waktu perencanaan dan menentukan nilai optimal dari : 1). Kuantitas supply setiap periode t untuk pengecer j, Q tj .2) Shedule pendistribusiannya, yaitu perjalanan kendaraan untuk setiap periode t. Selain variabel Q tj didefinisikan juga variabel keputusan berikut :

Z tj = Tingkat inventory di akhir periode t untuk pengecer j. Y jt = variabel 0-1 dan bernilai 1 jika dan hanya jika pemesanan dilakukan oleh pengecer j selama periode t.

r jkt = variabel 0-1 dan bernilai 1 jika dan hanya jika kendaraan melintas secara

44


langsung dari pengecer j ke pengecer k selama periode t. Perlu diketahui bahwa dalam kenyataannya route kendaraan yang melintas dari pengecer j ke pengecer k belum tentu sama dengan route kendaraan yang melintas dari pengecer k menuju pengecer j (route asimetris). Oleh karena itu model yang akan kita bangun dalam penelitian ini memperhatikan sifat asimetris dari suatu routing. Misalkan M dan K j adalah batas atas jumlah supply depot dan masingmasing pengecer. Untuk mempermudah penotasian, himpunan semua pengecer kita nyatakan dengan N = {1,2,3,..., n} . Selanjutnya himpunan semua pengecer dan depot kita nyatakan N 1 = N ∪ {0} . Misalkan untuk sebarang jadwal penambahan

yang

mungkin

τ = (Y jt , Q tj , Z tj , r jkt ) .

dari

Perhatikan

IRP

bahwa

dapat suatu

dinyatakan perjalanan

dengan kendaraan

(0, j1 , j 2 ,..., j p ,0) selama periode t akan diidentifikasi dengan sifat bahwa r0t j1 = r jt1 j2 = r jt2 j3 = ... = r jtp −1 j p = r jtp 0 = 1 . Suatu subtour adalah suatu cycle yang

tidak memuat depot. Lebih tepatnya,

suatu subtour adalah suatu cycle

( j1 , j 2 ,..., j p , j1 ) dengan j k ≠ 0, 1 ≤ k ≤ p dan r jt1 j2 = r jt2 j3 = ... = r jtp −1 j p = r jtp j1 = 1 . Untuk setiap S ⊂ N dimana 2 ≤ S ≤ n − 2 , dimisalkan l ( S ) batas bawah dari t

jumlah kendaraan yang dibutuhkan untuk melayani semua pengecer di dalam S. Perhatikan bahwa l ( S ) ≥ 1 , jika terdapat paling sedikit satu pengecer j ∈ S t

Q tj > 0 .

sedemikianhingga

Misalkan

S = N − S menyatakan

komplemen

sembarang S ⊂ N . Jadi, S tidak memuat depot. Untuk setiap schedule supply yang

τ = (Y jt , Q tj , Z tj , r jkt ) dari

feasible

IRP,

batas

bawah

t

l ( S ) dapat

divisualisasikan sebagai fungsi dari Q tj , j ∈ S . Di dalam persamaan (2.1.1) sampai dengan (2.1.14),akan dirumuskan model mixed integer linier programming untuk IRP yang asimetris. T

Meminimalkan

n

t =1 j = 0

2.1.1

45

T

n

T

n

∑∑ O tj Y jt + ∑∑ H tj Z tj + ∑∑ t =1 j = 0

n

∑C

t =1 j = 0 k = 0 , k ≠ j

t jk jk

r


Dengan kendala n

Z ot − Z 0t −1 − Q0t + ∑ Q tj = 0, ∀t = 1,2,3,... T j =1

2.1.2

Z tj − Z tj−1 − Q tj + D tj = 0, ∀t = 1,2,3,... T 2.1.3 Q0t − MY0t ≤ 0,

∀t = 1,2,3,... T

2.1.4

Q tj − K j Y jt ≤ 0,

∀t = 1,2,3,... T ; ∀j = 1,2,3,... n

2.1.5 n

∑r

t jk

− Y jt = 0,

∀t = 1,2,3,... T ; ∀j = 1,2,3,... n

t kj k =0, k ≠ j

− Y jt = 0,

∀t = 1,2,3,... T ; ∀j = 1,2,3,... n

k = 0, k ≠ j

2.1.6 n

∑r

2.1.7

 n t ∑Qj  n j =1 t ≥0 r0 j −  ∑  W  j =1    

∀t = 1,2,3,... T

2.1.8

∑∑ r + ∑ r k∈S j∈S

t kj

j∈S

t 0j

− l ( S ) ≥ 0, t

∀S , 2 ≤ S ≤ n − 2, ∀t = 1,2,3,... T

2.1.9

Z 0j = 0,

∀j = 0,1,2,... n

2.1.10

Z 0T = 0 2.1.11

Y jt ∈ {0,1}, ∀j dan ∀t 2.1.12

46


r jkt ∈ {0,1}, ∀j , k dan ∀t 2.1.13

Z tj , Q tj ≥ 0,

∀j dan ∀t

2.1.14

2.2. Validitas Model Sebelumnya, terlebih dahulu dijabarkan karakteristik dari pembataspembatas dalam IRP model (2.1.1) - (2.1.14) sebagai berikut: a)

Fungsi sasaran untuk diminimalkan terdiri dari total biaya pemesanan, total biaya inventory dan total biaya pengangkutan. Biaya-biaya tersebut adalah : T

n

∑ ∑O Y t =1 j = 0

t j

t j

=total biaya pemesanan yang ditimbulkan selama rentang waktu perencanaan T period;

T

n

∑∑ H t =1 j = 0

t j

Z tj = total biaya inventory yang ditimbulkan selama rentang waktu perencanaan T period dan

T

n

n

∑∑ ∑ C t =1 j = 0 k = 0 , k ≠ j

t jk jk

r =total

biaya

pengangkutan

selama

rentang

waktu

perencanaan T period untuk pengiriman keseluruh n pengecer. b)

Kendala (2.1.2) dan (2.1.3) masing-masing merupakan persamaan keseimbangan inventory untuk depot dan pengecer dalam setiap periode.

c)

Kendala (2.1.4) dan (2.1.5) menjamin bahwa jumlah penambahan adalah 0 (tidak ada penambahan) apabila Y jt bernilai 0. Kendala-kendala ini juga memberikan batas atas bagi kuantitas supply. Konstanta dari M dan K j dapat dipilih sebagai berikut: •

M =kapasitas maksimum yang tersedia di depot untuk suatu komoditas itu.

47

JURNAL MATEMATIKA DAN KOMPUTER Vol. 7. No. 2, 42 - 51, Agustus 2004, ISSN : 1410-8518 •

K j =min {W , C j } memberikan batas atas bagi kuantitas supply untuk pengecer j, dimana W adalah batas kapasitas kendaraan dan Cj adalah kapasitas maksimum yang tersedia di gudang pengecer j.

d)

Kendala (2.1.6) dan (2.1.7) disebut kendala out-degre dan kendala in-degre.

e)

Kendala (2.1.8), menjamin di setiap periode t jumlah kendaraan yang berangkat dari depot untuk mengirim ke para pengecer cukup sesuai kebutuhan. Kendala (2.1.8) dapat diganti dengan kendala berikut:

 n t ∑Qj  n j =1 t ≥0 rj 0 −  ∑  W  j =1     f)

∀t = 1,2,3,... T

Kendala (2.1.9) menghilangkan penyelesaian-penyelesaian yang memuat subtour dan atau yang melampaui kapasitas kendaraan..

g)

Kendala (2.1.10) dan (2.1.11) merupakan syarat awal level inventory untuk setiap pengecer dan level inventory di akhir rentang waktu perencanaan.

h)

Kendala (2.1.12) dan (2.1.13) kendala bernilai 0-1 untuk tiap-tiap Y jt dan

r jkt . i)

Kendala (2.1.14) merupakan batasan nonnegatif untuk Q tj dan Z tj . Dalam teorema berikut akan dibuktikan kendala penghilangan subtour

(2.1.9).

Teorema 2.2.1: (Achutan dan Sarwadi, 2000) Misalkan τ = (Y jt , Q tj , Z tj , r jkt ) menyatakan schedule supply yang feasible dari IRP. Maka τ memenuhi kendala (2.1.2)-(2.1.14).

Bukti: Dengan menggunakan beberapa karakteristik diatas, mudah untuk diperlihatkan bahwa τ memenuhi kendala (2.1.2)-(2.1.8) dan (2.1.10)-(2.1.14). Berikut ini, kita akan membuktikan bahwa τ juga memenuhi (2.1.9).

48


Misalkan S ⊆ {1,2,3,...N } , sedemikian hingga 2 ≤ S ≤ n − 2 . Untuk setiap j ∈ S, kita mengetahui bahwa (1.6) dan (1.7) dipenuhi. Jumlahkan (1.6) pada himpunan

 n t   ∑ r jk − Y jt  = 0 , atau ∑   j∈S  k = 0 , k ≠ j 

S, kita peroleh

∑ ∑

Karena itu,

j∈S k ∈S , k ≠ j

r jkt + ∑

∑ r +∑ r

j∈S k∈S , k ≠ j

t jk

j∈S



 r jkt + ∑ r jkt + r jt0 − Y jt  = 0 j∈S  k∈S , k ≠ j k∈S 

∑  ∑ t j0

− ∑ Y jt = 0 j∈S

Dengan cara serupa jumlahkan (2.1.7) pada himpunan S, kita peroleh

∑ ∑

j∈S k ∈S , k ≠ j

rkjt + ∑

∑ r +∑ r

t kj j∈S k∈S , k ≠ j

j∈S

t 0j

− ∑ Y jt = 0 j∈S

Dengan mengurangkan (2.1.6) dengan (2.1.7), diperoleh

∑∑ r

t jk

Jadi,

∑∑ r

j∈S k∈S

+ ∑ r jt0 − ∑∑ rkjt − ∑ r0t j = 0 j∈S

j∈S k∈S

j∈S k∈S

t jk

j∈S

+ ∑ r jt0 = ∑∑ rkjt − ∑ r0t j j∈S

Perhatikan bahwa

k∈S j∈S

∑∑ r j ∈S k ∈S

t jk

j∈S

+ ∑ rjt0 menunjukkan jumlah berapa kali kendaraanj ∈S

kendaraan melintas dari S ke S ∪ {0} di dalam τ yaitu shedule supply yang feasible. Secara analog

∑∑ r + ∑ r k ∈S j ∈S

t kj

j ∈S

t 0j

menunjukkan jumlah berapa kali kendaraan-

kendaraan di luar S yaitu S ∪ {0} (termasuk depot “0”) menuju S selama periode t. Jumlah ini harus lebih besar atau sama dengan jumlah minimum kendaraan yang dibutuhkan untuk melayani pengecer di S selama periode t. Jadi dapat dituliskan sebagai berikut:

∑∑ r + ∑ r k ∈S j ∈S

t kj

j ∈S

t 0j

≥ l (S ) . t

Di dalam model kita, jumlah in-degree depot sama dengan out-degreenya, termuat di dalam kendala (2.1.6), (2.1.7) dan (2.1.8). Kita tunjukkan di teorema 2.2.2 berikut:

49


Teorema 2.2.2: (Achutan dan Sarwadi,2000) Misalkan τ = (Y jt , Q tj , Z tj , r jkt ) sembarang schedule supply yang feasible dari IRP yaitu memenuhi kendala (2.1.2) - (2.1.14). Maka

n

n

j =1

j =1

∑ rjt0 = ∑ r0t j .

Dalam teorema selanjutnya, dijamin bahwa himpunan kendala-kendala yang dinyatakan (2.1.2) – (2.1.14) merupakan model IRP yang tepat.

Teorema 2.2.3: (Achutan dan Sarwadi, 2000) Misalkan τ = (Y jt , Q tj , Z tj , r jkt ) sembarang schedule supply yang feasible jika dan hanya jika τ memenuhi kendala (2.1.2) – (2.1.14). Bukti: Dari karakteristik dan teorema 2.2.2 jelas bahwa untuk setiap schedule supply yang feasible τ = (Y jt , Q tj , Z tj , r jkt ) memenuhi kendala (2.1.2)–(2.1.14). Untuk menunjukkan bagian yang lain, perhatikan suatu τ = (Y jt , Q tj , Z tj , r jkt ) yang memenuhi

kendala

(1.2)–(1.14).

Kita

akan

menunjukkan

bahwa

τ = (Y jt , Q tj , Z tj , r jkt ) merupakan schedule supply yang feasible. Dari (2.1.2)–(2.1.5) jelas bahwa Y jt , Q tj dan Z tj merupakan kuantitas supply dan inventory yang tepat sehingga permintaan D tj dari pengecer j selama periode t terpenuhi, untuk setiap j dan t. Lebih lanjut biaya pemesanan dan biaya inventory telah terpenuhi sesuai 2.1.1. Kita harus membuktikan

bahwa untuk setiap t, 1
kendaraan yang dibangun oleh rjkt untuk mengirim barang-barang ke pengecer j apabila Q tj > 0 , adalah tepat. Menurut (2.1.6) dan (2.1.7) jelas bahwa saat

Q tj > 0 maka

terdapat

l

dan

k

sehingga

rkjt = rjlt = 1, 0 ≤ k ≤ n, k ≠ j , 0 ≤ l ≤ n, l ≠ j . Jadi pengecer j dikunjungi dengan tepat satu kendaraan selama periode t jika Q tj > 0 . Dengan menggunakan argumen-argumen bukti teorema 2.2.2, dapat diklaim bahwa untuk setiap kendaraan yang sedang menuju depot akan mendatangi beberapa pengecer j

50


dengan Q tj > 0 dan kembali ke depot. Selanjutnya, himpunan kendala-kendala 2.1.9 menjamin bahwa subtour-subtour dihilangkan dan setiap tour yang dibangun memenuhi batas kapasitas kendaraan.

3. KESIMPULAN Dari studi tentang model yang diajukan di atas dapat disimpulkan bahwa model Mixed Integer Linier Programming merupakan model yang sahih dan dapat digunakan untuk menyelesaikan masalah gabungan antara inventory dan routing dari suatu komoditas.

DAFTAR PUSTAKA

Achutan, N.R and Sarwadi,Single Commodity Inventory Combined Vehicle Routing Problem, in Proceeding Asia Pasific Operations Research Society 2000 (Chuen, L. P. et al editor ), Singapore, 22 – 41, 2000. Anily, S. and Fedegruen, A., One warehouse multiple retailer systems with vehicle routing costs, Management Science,36(1), 92-114, 1990. Benjamin, J. ,An Analysis of Inventory and Transportation Costs in a Constrained network, Transportation Science 23 (3), 177-183,1989. Federgruen, A. and Zipkin, P. , A combined Vehicle Routing and Inventory Allocation Problem, Operation Research, 32, 1019-1037,1984. Chandra P , A Dynamic Distribution Model with Warehouse and Customer Repleshinement Requirement, Journal of Operation Research Societies, 44(7),681-692,1993.

51

MODEL ASIMETRIS GABUNGAN INVENTORY DAN ROUTING UNTUK MINIMISASI HARGA KOMODITI

Recommend Documents