BAB 2 LANDASAN TEORI. Sebuah graf G fully weighted didefinisikan sebagai quadruple G = (V, E, f, g)

BAB 2 LANDASAN TEORI

2.1 Graf Dinamis (Dynamic Graph) Sebuah graf G fully weighted didefinisikan sebagai quadruple G = (V, E, f, g) dimana V adalah himpunan terhingga titik (verteks), E adalah himpunan terhingga garis (edge) yang menghubungkan titik satu dengan lainnya, f merupakan fungsi yang diberikan pada himpunan titik sebagai f : V → N, dan g merupakan fungsi yang diberikan pada himpunan edge sebagai g : E → N . Sebuah graf G dinamis diperoleh dengan mengubah sembarang V, E, f atau g. Harary (Harary, 1997) mengklasifikasikan graf dinamis dengan mengubah satu atau lebih kondisi berikut ini:

1. Node dynamic (di)/graph dimana himpunan verteks V berubah dari waktu ke waktu 2. Edge/Arc dynamic (di)/graph dimana himpunan garis E berubah dari waktu ke waktu 3. Node weighted dynamic (di)/graph dimana fungsi f berbeda dari waktu ke waktu 4. Edge/Arc weighted dynamic (di)/graph dimana fungsi g berbeda dari waktu ke waktu 8

9 Sebuah graf disebut dinamis penuh (fully dynamic), jika perubahan yang dimungkinkan adalah penambahan dan penghapusan verteks dan/atau garis. Sebaliknya sebuah graf disebut dinamis sebagian (partially dynamic), jika perubahan yang dimungkinkan hanya penambahan atau penghapusan garis dan/atau verteks. Selanjutnya, sebuah graf dinamis disebut incremental jika operasi yang dimungkinkan hanya penambahan dan disebut decremental jika operasi yang dimungkinkan hanya penghapusan. Dalam penggunaannya, graf dinamis dimungkinkan untuk berubah dari waktu ke waktu seperti penambahan dan penghapusan garis dan verteks serta perubahan informasi/atribut dari garis dan verteks. Dalam masalah graf dinamis, terdapat sejumlah pertanyaan seperti: apakah graf tersebut terhubung atau tidak (connectivity), bagaimana mendapatkan lintasan terpendek antar verteks (shortest path), bagaimana melakukan clustering, bagaimana menghasilkan spanning forest, bagaimana memastikan keterjangkauan (reachability) dan lain-lain. Tujuan dari algoritma graf dinamis adalah memperbaharui solusi atas masalah secara efisien setelah terjadinya perubahan tanpa harus menghitungnya kembali dari awal. Operasi penambahan verteks mengharuskan penambahan garis dengan menghubungkan verteks baru ke salah satu verteks yang ada pada graf sebelumnya. Sementara operasi penghapusan garis mengharuskan penghapusan titik, jika ada titik yang terisolasi. Sedangkan operasi pembaharuan atribut dapat dilakukan dengan mengubah informasi pada dua buah titik yang dihubungkan oleh satu garis

10 dan perubahan bobot pada garis tertentu. Dengan kemampuan yang fleksibilitas tersebut, maka pengembangan dan analisis algoritma serta struktur data dinamis untuk graf dinamis biasanya lebih sulit dibandingkan dengan graf statis. 2.1.1 Operasi Dinamis untuk Graf Tak Berarah Pada sub bab ini dijelaskan teknik yang utama yang digunakan untuk menyelesaikan masalah pada graf dinamis tak berarah seperti partisi garis / titik dan dekomposisi graf serta perubahan pohon secara dinamis. 2.1.1.1 Clustering. Teknik clustering didasarkan pada partisi graf menjadi kumpulan subgraf terhubung yang sesuai, yang disebut cluster, sedemikian hingga setiap operasi perubahan hanya melibatkan sebagian kecil clusters. Biasanya operasi dekomposisi didefinisikan secara rekursif dan informasi tentang subgraf dikombinasikan dengan topologi pohon. Perbaikan teknik clustering dalam konsep struktur data bersifat ambivalen (Frederikson, 1997), dimana garis dapat merupakan bagian dari grup berbeda, dan hanya satu grup yang terpilih tergantung pada topologi pohon telusur (spanning tree). Aplikasi clustering terhadap masalah mempertahankan sebuah minimum spanning forest seperti dijelaskan oleh Frederikson (Frederickson, 1985). Misalkan G = (V, E) sebuah graf dengan sebuah spanning tree S. Clustering digunakan untuk menghasilkan partisi verteks V ke dalam subpohon yang terhubung dalam

11 S, sedemikian hingga setiap subpohon hanya terhubung dengan beberapa subpohon yang lain. Sebuah pohon topologi digunakan untuk merepresentasikan partisi pohon S secara rekursif. Algoritma dinamis penuh yang hanya didasarkan pada level clustering tunggal dapat dilakukan dengan kompleksitas waktu O(m2/3) - (lihat pada Galil dan Italiano, 1992, dan Rauch, 1995). Jika partisi dapat dilakukan secara rekursif, maka diperoleh kompleksitas waktu yang lebih baik yakni O(m1/2 ) dengan menggunakan pohon topologi 2-dimensi (Frederickson, 1985, Frederickson, 1997).

Teorema 2.1 Minimum spanning forest dari sebuah graf tak berarah dapat di√ hitung dalam waktu O( m) untuk setiap update, dimana m adalah jumlah garis pada graf tersebut. √ Dengan teknik yang sama, kompleksitas waktu O( m) dapat juga diperoleh untuk masalah konektivitas dinamis penuh dan konektivitas 2-dimensi (Frederickson, 1985, Frederickson, 1997). Akan tetapi, jenis clustering yang digunakan sangat tergantung masalah yang ingin diselesaikan. 2.1.1.2 Sparcification. Menurut Epstein et al. (Epstein et al., 1997), sparsification merupakan teknik umum yang dapat digunakan sebagai black box (tanpa mengetahui internal secara rinci) untuk menghasilkan algoritma graf dinamis. Sparsification merupakan teknik yang bersifat divide-and-conquer yang memungkinkan mengu-

12 rangi ketergantungan terhadap jumlah garis dalam sebuah graf, sedemikian hingga kompleksitas waktu untuk mempertahankan sifat tertentu dalam graf sebanding dengan waktu untuk menghitungnya dalam graf jarang (sparse graph). Lebih rinci, bila teknik tersebut dapat digunakan, kompleksitas waktu T (n, m) untuk sebuah graf dengan n verteks dan m garis dapat ditingkatkan menjadi T (n, O(n)) yakni waktu yang dibutuhkan jika graf merupakan sparse graph. 2.1.1.3 Randomisasi. Clustering dan sparsification memungkinkan untuk menghasilkan algoritma deterministik yang efisien untuk masalah dinamis penuh. Berikut ini dijelaskan cara kerja teknik randomisasi dengan input masalah konektivitas dinamis penuh. Misalkan G = (V, E) sebuah graf yang ingin dipertahankan secara dinamis dan misalkan F merupakan sebuah spanning tree dari G.Dinyatakan sebuah garis pada F sebagai garis pohon dan garis pada E\F adalah garis non-tree. Algoritma oleh Henzinger dan King (Henzinger dan King, 1999) didasarkan pada pertimbangan berikut:

1. Maintaining spanning forest: pohon dipertahankan menggunakan struktur data Euler Tour yang memungkinkan untu mendapatkan waktu logaritma untuk algoritma update dan query 2. Random sampling: jika garis e dihapus dari graf pohon T , maka digunakan random sampling diantara garis dari non-tree T 0 untuk menghasilkan garis

13 pengganti e secara cepat 3. Graph decomposition: pertimbangan terakhir adalah menggabungkan randomisasi dengan dekomposisi graf. Dekomposisi garis pada graf G yang ada dipertahankan dengan menggunakan waktu O(log n)

Teorema 2.2 (Henzinger dan King,1999). Misalkan G merupakan graf dengan m0 garis dan n verteks dengan operasi yang dimungkinkan hanya penghapusan garis. Sebuah spanning forest F dari G dapat dipertahankan dalam waktu O(log3 n) untuk setiap penghapusan, jika terdapat setidaknya Ω(m0) penghapusan. Waktu untuk query adalah O(log n)

2.1.2 Operasi Dinamis untuk Graf Berarah Pada sub bab ini dijelaskan teknik yang utama yang digunakan untuk menyelesaikan masalah lintasan dinamis pada graf berarah yakni algoritma transitive closure dan lintasan terpendek. Kedua masalah tersebut memainkan peran penting dalam sejumlah aplikasi seperti optimisasi jaringan dan transportasi, sistem informasi lalu lintas, database, compiler, garbage collection, interactive verification systems, robotik, analisis aliran data dan lain-lain. 2.1.2.1 Kleene Closure. Masalah lintasan seperti transitive closure dan lintasan terpendek sangat terkait dengan perjumlahan dan perkalian matriks dalam satu semiring tertutup

14 (Cormen et al., 2001). Transitive closure dari sebuah digraf dapat diperoleh dari matriks tetangga dari graf tersebut melalui operasi pada semiring dari matriks Boolean, yang dinotasikan dengan {+, •, 0, 1}. Operasi + dan • menyatakan perjumlahan dan perkalian dalam matriks Boolean.

Lemma 2.3 Misalkan G = (V, E) sebuah digraf dan T C(G) merupakan transitive closure dari G. Jika X adalah matriks tetangga Boolean dari graf G, maka matriks tetangga Boolean dari T C(G) adalah Kleene closure dari X pada {+, •, 0, 1} Boolean semiring: X∗ =

n−1 X

Xi

(2.1)

i=0

Dengan cara yang sama, jarak lintasan terpendek dalam sebuah digraf dengan bobot bilangan riel dapat diperoleh dari matriks bobot dari graf melalui operasi-operasi pada semiring dari matriks bilangan riel, yang dinotasikan dengan {

L J , , R} atau lebih sederhana dengan {min, +}. Dalam hal ini R adalah

himpunan nilai riel dimana

L

dan

J

didefinisikan sebagai berikut. Misalkan dua

buah matriks bernilai riel A dan B, maka C = A

L

B adalah matriks perjum-

lahan sedemikian hingga C[u, v] = min{A[u, w], B[w, v]} dan D = A

J

B dalah

matriks perkalian sedemikian hingga D[u, v] = min1≤w≤n {A[u, w] + B[w, v]} yang juga dapat dinotasikan dengan AB dimana AB[u, v] merupakan entry dari matriks AB.

Lemma 2.4 Misalkan G = (V, E) sebuah digraf berbobot tanpa bobot negatif sik-

15 lus. Jika X adalah matriks bobot sedemikian hingga X[u, v] merupakan bobot dari garis (u, v) dalam G, maka matriks jarak dari G adalah Kleene closure dari X pada semiring {

L J , , R}

X∗ =

n−1 M

Xi

(2.2)

i=0

Berikut dijelaskan dua metode yang biasa digunakan untuk menghitung Kleene closure X ∗ dari X dengan asumsi X adalah matriks n × n.

1. Logarithmic decomposition: merupakan metode untuk menghitung X ∗ berdasarkan operasi kuadrat berulang yang membutuhkan waktu terburuk sebesar O(nµ log n), dimana O(nµ ) merupakan waktu yang dibutuhkan untuk menghitung perkalian dua buah matriks pada sebuah semiring tertutup dan µ ≤ 2, 38 (pangkat terbaik untuk perkalian matriks saat ini). Metode ini melakukan log2 n perjumlahan dan perkalian dalam bentuk Xi+1 = Xi +Xi2 , dimana X = X0 dan X ∗ = Xlog2 n 2. Recursive decomposition: metode lain seperti dikemukakan Munro (Munro, 1971) yang didasarkan pada strategi divide-and-conquer dan menghitung X ∗ dalam O(nmu ) untuk waktu terburuk. Munro menjelaskan bahwa jika X dipartisi ke dalam 4 submatriks A, B, D, C dengan ukuran n/2 × n/2 (susunan submatriks sesuai dengan arah jarum jam), dan matriks X ∗ dipartisi menjadi E, F, H, G dengan ukuran n/2 × n/2, makaX ∗ diperoleh secara

16 rekursif sesuai dengan persamaan berikut:

E = (A + BD∗ C)∗ | F = EB | G = D∗ CE | H = D∗ + D∗ CEBD∗ (2.3)

Terkait dengan closure didefinisikan fully dynamic transitive closure problem, dimana ingin dipertahankan sebuah digraf G = (V, E) dengan operasi gabungan berikut:

1. Insert(u, v): sisipkan (tambah) sebuah garis (u, v) dalam G; 2. Delete(u, v): hapus garis (u, v) dari G; 3. Query (u, v): output yes jika ada lintasan dari u ke v dalam G, dan no jika tidak.

Solusi sederhana atas masalah di atas terdiri dari mempertahankan graf dengan operasi sisip dan hapus, kemudian mengecek apakah v terjangkau dari u setelah masing-masing operasi. Operasi insert dan delete membutuhkan waktu O(1) serta O(m) untuk operasi query, dimana m adalah jumlah garis saat ini pada graf setelah operasi. 2.1.2.2 Locality. Demetreseu dan Italiano (Demetreseu dan Italiano, 2003) mengajukan pendekatan baru untuk masalah lintasan dinamis berdasarkan pada pemeliharaan

17 kelas lintasan yang ditentukan oleh sifat-sifat lokal, yakni, sifat-sifat yang tetap berlaku untuk semua sublintasan sempurna, meskipun sifat-sifat tersebut mungkin tidak berlaku untuk keseluruhan lintasan. Mereka menunjukkan bahwa pendekatan tersebut memainkan peranan penting dalam memepertahan-kan lintasan terpendek.

Definisi 2.1 Sebuah lintasan π dalam sebuah graf disebut locally shortest jika dan hanya jika setiap sublintasan sempurna dari π adalah lintasan terpendek.

Definisi 2.1 diinspirasi oleh sifat substruktur optimal dari lintasan terpendek yakni: semua sublintasan dari sebuah lintasan terpendek adalah terpendek. Akan tetapi, lintasan terpendek secara lokal mungkin tidak terpendek. Fakta bahwa lintasan terpendek lokal merupakan sebuah kasus khusus memungkin-kan lintasan terpendek lokal tersebut menjadi alat yang berguna dalam menghitung dan mempertahankan jarak dalam sebuah digraf. Pada dasarnya lintasan terpendek yang diperoleh secara lokal mempunyai sifat-sifat kombinatorial menarik dalam graf yang berubah secara dinamis. Sebagai contoh, tidak sulit membuktikan bahwa jumlah lintasan terpendek lokal yang mungkin berubah akibat dari perubahan bobot sebuah garis adalah O(n2 ) jika perubahan yang terjadi adalah perubahan parsial (hanya penambahan atau penghapusan)

Teorema 2.5 Misalkan G merupakan sebuah graf yang mengalami perubahan bobot garis berupa increase-only atau decrease-only, maka jumlah lintasan yang

18 start dan stop yang terpendek secara lokal pada setiap operasi adalah O(n2 )

Definisi 2.2 Sebuah lintasan terpendek historis (historical shortest path) adalah lintasan yang telah menjadi terpendek paling tidak sekali setelah perubahan terakhir

Dalam hal ini diasumsikan bahwa sebuah lintasan diperbaharui bila bobot dari salah satu garis pada lintasan tersebut berubah. Dengan menggunakan teknik locality terhadap lintasan historis, akan diperoleh lintasan historis secara lokal. Dengan demikian sebuah lintasan p disebut historis secara lokal jika dan hanya jika setiap sublintasan sempurna dari p juga adalah historis. Lintasan lokal yang historis juga termasuk di dalam lintasan terpendek, dan fakta ini memberikan kemudahan dalam menghitung dan mempertahankan jarak dalam graf.

Lemma 2.6 Jika himpunan lintasan terpendek, lintasan terpendek lokal dan lintasan terpendek historis dalam sebuah digraf dinotasikan SP, LSP dan LHP secara berturut-turut, maka berlaku hubungan SP ⊆ LSP ⊆ LHP Berbeda dengan lintasan terpendek lokal, lintasan terpendek historis mempunyai sifat kombinatorial yang menarik dalam digraf yang dapat digunakan untuk operasi dinamis penuh. Secara khusus, dimungkinkan untuk membuktikan bahwa jumlah lintasan yang menjadi historis secara lokal dalam digraf pada setiap operasi perubahan bobot garis tergantung pada jumlah lintasan historis dalam graf tersebut.

19 Teorema 2.7 Misalkan G merupakan sebuah graf dengan urutan operasi perubahan (update). Jika pada saat tertentu selama perubahan terdapat paling banyak O(h) lintasan historis dalam graf tersebut, maka jumlah lintasan renumerasi yang menjadi historis secara lokal pada setiap update adalah O(h)

Untuk membuat perubahan dalam lintasan historis lokal kecil, diharapkan untuk memiliki lintasan historis sesedikit mungkin. Pada dasarnya, dimungkinkan untuk mentransformasikan setiap urutan update ke dalam sebuah barisan yang lebih panjang yang ekivalen dengan yang menghasilkan sedikit lintasan historis. Secara khusus, terdapat sebuah strategi yang halus dengan urutan update S dengan panjang k menghasilkan sekuens F (Σ) yang secara operasional ekivalen dengan panjang O(k log k) yang hanya menghasilkan O(log k) lintasan terpendek historis antara masing-masing verteks dalam graf (Demetreseu dan Italiano, 2003). Menurut teorema 2.7 di atas, teknik ini mengakibatkan bahwa hanya O(n2 log k) lintasan historis lokal yang berubah pada setiap update dalam smoothed sequence F (Σ). Dengan lemma 2.3, lintasan historis lokal terdapat dalam lintasan terpendek, sehingga ini adalah algoritma yang efisien untuk all pairs shortest path yang dinamis penuh. 2.1.2.3 Fully Dynamic Single-Source Shortest Paths Problem. Tujuan dari Fully Dynamic Single-Source Shortest Paths Problem adalah mempertahankan graf G = (V, E, w) dengan operasi campuran berikut:

20 1. Increase (u, v, ): meningkatkan bobot garis (u, v) sebesar  2. Decrease (u, v, ): mengurangi bobot garis (u, v) sebesar ) 3. Query (v): output lintasan terpendek antara verteks asal tertentu dengan verteks v dalam graf G jika ada

Algoritma insert (incremental): semua algoritma incremental mempunyai waktu eksekusi O(1) untuk operasi query, sepanjang transitive closure dari graf dapat dipertahankan. Solusi incremental pertama diberikan oleh Ibaraki dan Katoh (Ibaraki dan Katoh, 1983) yang didasarkan ide sangat sederhana: ketika menambahkan garis (x, y), apakah ada lintasan dari u ke x dan lintasan dari x ke v, maka v terjangkau (reachable) dari u, jika sebelumnya tidak. Kompleksitas waktu dari algoritma adalah O(n3 ) untuk sembarang operasi sisip. Batas waktu tersebut kemudian diperbaiki menjadi O(n) oleh Italiano (Italiano, 1986) dimana algoritma tersebut juga dapat menghasilkan sebuah lintasan antara sembarang pasangan verteks, jika ada, dalam waktu linier dalam panjang lintasan itu sendiri. Waktu O(n) per operasi dan O(1) per query juga didapatkan oleh La Poutre dan Leeuwen (La Poutre dan Leeuwen, 1988). Akhirnya, Yellin (Yellin, 1993) memberikan algoritma dengan waktu eksekusi yang baik pada graf dengan degree terbatas dengan kompleksitas waktu O(m∗ D) untuk m sisi, dimana m adalah jumlah garis dalam transitive closure akhir dan D adalah out-degree dari graf akhir.

21 Algoritma delete (decremental): solusi hapus diberikan oleh Ibaraki dan Katoh (Ibaraki dan Katoh, 1983) dimana mereka mengajukan algoritma depthfirst dengan waktu eksekusi O(n2 ) per operasi hapus. Batas tersebut diperbaiki oleh La Poutre dan Leeuwen (La Poutre dan Leeuwen, 1988) dengan waktu O(m) per operasi hapus. Italiano (Italiano, 1988) mengajukan algoritma decremental pada acyciclic digraph dengan waktu penghapusan O(n). Berikutnya, Yellin (Yellin, 1993) memberikan algoritma dengan waktu O(m∗ D) untuk m sisip, dimana m adalah jumlah garis dalam transitive closure akhir dan D adalah outdegree dari graf awal. Terakhir, Henzinger dan King (Henzinger dan King, 1995) mengajukan algoritma decremental transitive closure dengan kompleksitas waktu O( logn n ) untuk query dan O(n log n) untuk operasi update. 2.2 Algoritma Kunang-kunang (Firefly Algorithm) 2.2.1 Pengenalan Algoritma Fireflies (kunang-kunang), merupakan jenis kumbang ukuran kecil (termasuk dalam keluarga Lampyridae) yang mempunyai kemampuan untuk menghasilkan cahaya (cold light) untuk menarik perhatian pasangannya. Kunangkunang diyakini mempunyai satu mekanisme seperti kapasitor yang dialiri arus dengan ukuran tertentu sampai batas tertentu, dimana mereka dapat memancarkan energi dalam bentuk cahaya, kemudian siklus berulang. Hasil eksperimen menunjukkan bahwa tanpa stimulus eksternal, individu kunang-kunang memancarkan cahaya dengan durasi siklus yang konsisten. Selanjutnya, masing-masing

22 individu mempunyai kesamaan frekuensi pancaran cahaya. Meskipun mekanisme pasti tidak diketahui, diyakini bahwa individu kunang-kunang tersebut merespon pancaran cahaya dari individu lain dengan cara menyesuaikan muatan listrik dalam kapasitornya. Dengan cara seperti ini, masing-masing individu secara perlahan menyesuaikan pancaran cahaya dengan kunang-kunang yang ada di sekitarnya untuk menciptakan pancaran cahaya yang sinkron dan robust. Mekanisme tersebut sederhana dalam basis individu, namun perilaku yang terjadi akan sangat kompleks dalam kelompok dimana perubahan sedikit saja dari satu individu memberikan akibat yang sangat signifikan terhadap sinkronisasi grup. Studi telah menunjukkan bahwa kunang-kunang dari spesies berbeda menggunakan satu dari dua mekanisme utama untuk mencapai sinkronisasi, yakni: fase tunda dan fase lanjut (Smith, 2008, Durkota, 2011). Algoritma Kunang-kunang (Firefly Algorithm) yang selanjutnya disingkat dengan FA merupakan salah satu perkembangan terbaru sebagai metode dalam kecerdasan kelompok (swarm intelligence) yang dikembangkan oleh Xin-She Yang pada tahun 2008 dari Cambridge University (Yang, 2008). Algoritma ini termasuk algoritma meta-heuristik, yang terinspirasi dari alam dan bersifat stokastik berdasarkan pada pola pancaran cahaya (seperti: bentuk, warna, ukuran, intensitas,irama dan frekuensi) kunang-kunang dalam bersosialisasi (Sayadi et al., 2010). Stokastik dalam arti menggunakan randomisasi dalam mencari himpunan solusi, sementara meta-heuristik mengandung makna bahwa berada pada level yang lebih

23 tinggi dimana proses pencarian yang digunakan dalam algoritma dipengaruhi oleh pilihan antara randomisasi dan pencarian lokal. Setiap proses pencarian metaheuristik tergantung pada keseimbangan antara dua komponen utama yakni eksplorasi dan ekploitasi (Fister et al., 2013). Kedua komponen didefinisikan secara implisit dan tergantung penentuan parameter kendali dari algoritma. Algoritma FA telah menjadi alat yang semakin penting dalam kecerdasan kelompok (swarm intelligence) yang telah diaplikasikan dalam hampir semua masalah optimisasi. Banyak masalah dari berbagai bidang telah sukses diselesaikan dengan menggunakan algoritma FA dan variannya. Algoritma FA didasarkan pada pola pancaran cahaya yang dilakukan oleh kunang-kunang untuk menarik pasangan atau memberikan peringatan pada calon pemangsa. Algoritma FA telah banyak digunakan untuk menyelesaikan masalah optimisasi kontinu, kombinatorial, multi-objektif dan kendala, dan optmisasi dalam lingkungan yang noisy dan dinamis. Di samping itu, algoritma FA juga dapat diaplikasikan dalam bidang machine learning, data mining, dan jaringan syaraf tiruan (Fister et al., 2013). Pada dasarnya algoritma FA menggunakan aturan ideal berikut:

1. Kunang-kunang merupakan hewan unisex sehingga seekor kunang-kunang hanya tertarik pada kunang-kunang lain terlepas dari jenis kelamin 2. Daya tarik (attractiveness) proporsional pada intensitas cahaya antar keduanya, dan cahaya tersebut akan meredup apabila jarak semakin jauh. Jika

24 dua kunang-kunang yang saling memancarkan cahaya, maka kunang-kunang dengan cahaya redup akan mendekat pada yang memancarkan cahaya yang lebih terang. 3. Kecerahan cahaya yang dipancarkan tergantung pada lingkungan terkait dengan bentuk analitik dari fungsi objektif. Untuk permasalahan maksimum, kecerahan dapat dianggap proporsional terhadap nilai fungsi biaya (Yang, 2008)

Daya tarik (attractiveness) dari seekor kunang-kunang ditentukan oleh intensitas cahaya yang pada gilirannya diasosiasikan dengan fungsi objektif. Dalam kasus sederhana untuk masalah optimisasi, intensitas I dari kunang-kunang pada posisi x tertentu dapat dinyatakan sebagai I(x) ≈ f(x). Akan tetapi daya tarik β adalah relatif dan tergantung pada jarak antara kunang-kunang i dengan kunangkunang j. Intensitas cahaya akan meredup seiring dengan pertambahan jarak dan diserap oleh lingkungan. Intensitas cahaya I(r) bervariasi sesuai dengan jarak r secara monotonik dan eksponensial, sebagai berikut:

I(r) = I0 e−γr

2

(2.4)

dimana I0 adalah intensitas cahaya mula-mula dan γ adalah koefisien penyerapan cahaya. Karena daya tarik kunang-kunang proporsional pada intensitas cahaya yang

25 dilihat oleh kunang-kunang lain di sekitarnya, maka variasi daya tarik β dapat didefinisikan untuk jarak r dengan rumus:

β = β0e−γr

2

(2.5)

dimana β0 adalah nilai daya tarik pada saat r = 0. Secara umum digunakan β0 ∈ [0, 1], Nilai γ memengaruhi variasi ketertarikan dengan pertambahan jarak dari kunang-kunang yang berkomunikasi. Secara umum nilai γ yang digunakan adalah [0, 10] meskipun dimungkinkan untuk menggunakan nilai [0, ∞). Karena menghitung

1 (1+r 2 )

lebih cepat dibandingkan dengan fungsi eksponensial, maka

nilai β dapat didekati dengan :

β=

β0 1 + γr2

(2.6)

Pergerakan kunang-kunang i yang tertarik pada kunang-kunang dengan intensitas cahaya yang lebih tinggi j ditentukan oleh persamaan :

2

xt+1 = xti + β0e−γri (xtj − xti ) + αt εti i

(2.7)

Suku kedua dari persamaan (2.7) tergantung pada daya tarik, suku ketiga adalah randomisasi dengan α0 ∈ [0, 1] merupakan parameter acak, dan εti adalah sebuah vektor bilangan acak yang didapatkan dari distribusi Gauss atau distribusi

26 uniform lainnya pada saat t. Jika β0 = 0, maka akan terjadi pencarian acak sederhana (simple random walk). Jika γ → 0, maka daya tarik β = β0 artinya daya tarik menjadi konstan di setiap titik dalam ruang pencarian. Perilaku ini menjadi kasus khusus dari particle swarm optimization (PSO). Sebaliknya, jika γ → ∞, maka suku kedua dari persamaan (2.7) menjadi hilang dan kunangkunang akan bergerak secara acak yang pada prinsipnya menjadi sebuah versi paralel dari simulated annealing. Faktanya, setiap implementasi algoritma FA akan berada pada dua sifat asimtotis tersebut (Fister et al., 2013). Jarak antara kunang-kunang i dan j didefinisikan dengan : v u n uX rij =k xi − xj k= t (xi,k − xj,k )2

(2.8)

k=1

dimana xi,k adalah komponen dari koordinat spasial xi dari kunang-kunang ke-k. Dalam kasus 2 − D, ri,j diperoleh :

ri,j =

q

(xi − xj )2 − (yi − yj )2

(2.9)

2.2.2 Penentuan Parameter dan Deskripsi Algoritma FA Seperti disebutkan di atas, algoritma FA dikendalikan oleh tiga buah parameter yakni: parameter randomisasi α, attaractiveness β dan koefisien penyerapan (absorpsi) γ. Sesuai dengan pengaturan parameter, algoritma FA membedakan

27 dua karakteristik asimtotis yakni γ → 0 dan γ → ∞. Jika γ → 0, maka parameter β = β0 yakni attractiveness menjadi konstan di dalam ruang pencarian. Parameter αt pada prinsipnya mengendalikan keacakan (dalam hal tertentu, keragaman solusi), yang dapat disesuaikan parameter ini pada saat iterasi sedemikian hingga dapat bervariasi sesuai dengan iterasi t. Dengan demikian cara yang baik menyatakan αt adalah menggunakan:

αt = α0δ t ; 0 < δ < 1

(2.10)

dimana α0 merupakan faktor skala keacakan awal, dan δ merupakan faktor penyejuk (cooling factor). Untuk kebanyakan aplikasi, biasanya digunakan nilai δ = 0, 95 sampai 0, 97. Terkait dengan nilai awal α0 , simulasi menunjukkan bahwa FA akan lebih efisien jika α0 dikaitkan dengan skala peubah rancangan. Misalkan L merupakan skala rata-rata problema, maka dapat diberikan nilai awal α0 = 0, 01L. Faktor 0,01 bermula dari fakta bahwa random walk membutuhkan sejumlah langkah untuk mencapai target sambil menyeimbangkan eksploitasi lokal tanpa melompat terlalu jauh dalam beberapa langkah (Yang, 2009, Das, 2011). Parameter β mengendalikan ketertarikan, dan studi menunjukkan bahwa nilai β = 1 dapat digunakan untuk kebanyakan aplikasi. Akan tetapi, γ harus dikaitkan dengan skala L dengan nilai γ = pat diberikan nilai γ = O(1).

√1 . L

Jika variasi skala tidak signifikan, maka da-

28 Untuk jumlah kunang-kunang (n) yang besar, jika n  m, dimana m adalah jumlah optima lokal dari problema optimisasi, konvergensi algoritma dicapai. Dalam hal ini lokasi awal dari n kunang-kunang terdistribusi secara merata pada semua ruang pencarian, dan selama iterasi algoritma berlangsung sampai semua optimum lokal mencapai konvergensi. Dengan membandingkan solusi terbaik diantara optima lokal yang ada, optima global akan diperoleh. Dengan penyesuaian parameter γ dan α, algoritma FA dapat melebihi algoritma Harmony Search dan PSO. Algoritma FA juga mungkin memperoleh optimal global serta optimal lokal secara bersamaan dan efektif. Algoritma FA didasarkan pada formula fisik dari intensitas cahaya I yang melemah sebanding dengan kuadrat jarak (r2 ). Akan tetapi, jika jarak bertambah maka daya serap cahaya mengecil yang mengakibatkan cahaya tersebut semakin lemah. Fenomena tersebut dapat diasosiasikan dengan fungsi objektif yang ingin dioptimalkan. Dengan demikian, algoritma FA dasar dapat diformulasikan dalam pseudocode seperti pada Gambar 2.1 berikut ini (Fister et al., 2013). Populasi kunang-kunang diinisialisasi oleh fungsi InitialisasiFA (biasanya fungsi ini dilakukan secara acak). Proses pencarian oleh kunang-kunang dilakukan di dalam loop while (baris 3 − 10) yang terdiri dari langkah-langkah berikut: Mula-mula, fungsi AlphaNew digunakan untuk memodifikasi nilai awal parameter α (perlu dicatat bahwa langkah ini bersifat opsional). Berikutnya, fungsi EvaluateFA mengevaluasi kualitas solusi (implementasi fungsi fitness f(s) di-

29

Gambar 2.1 Algoritma Dasar FA lakukan di dalam fungsi ini). Selanjutnya, fungsi OrderFA mengurutkan populasi kunang-kunang berdasarkan nilai fitness-nya. Setelah itu, fungsi FindTheBest memilih individu terbaik di dalam populasi. Terakhir, fungsi MoveFA melakukan pergerakan posisi kunang-kunang dalam ruang pencarian ke arah individu yang lebih atraktif. Proses pencarian kunang-kunang dikendalikan oleh maksimum jumlah fungsi evaluasi fitness (MAXF ES ). Dekripsi lain dari algoritma FA diberikan pada Gambar 2.2 berikut (Saibal et al., 2012). 2.2.3 Kompleksitas dan Klasifikasi Algoritma FA Hampir semua algoritma meta-heuristik sederhana dalam hal kompleksitas, sehingga algoritma tersebut mudah untuk diimplementasikan. FA mempunyai 2 buah inner loops pada saat menjalani semua populasi n, dan satu buah outer loop

30

Gambar 2.2 Algoritma FA Lebih Lengkap untuk iterasi t. Sehingga kompleksitas algoritma dalam keadaan ekstrim adalah O(n2 t). Dengan n kecil (biasanya n = 40), dan t besar (misalnya t = 5000), waktu komputasi relatif murah karena kompleksitas algoritma linier dalam t. Biaya komputasi utama terjadi pada evaluasi fungsi objektif, khususnya untuk fungsi objektif kotak hitam eksternal. Untuk masalah optimisasi, waktu paling besar digunakan untuk mengevaluasi fungsi objektif (Yang dan He, 2013). Jika n relatif besar, dimungkinkan untuk menggunakan satu buah inner loop dengan memberikan peringkat terhadap ketertarikan atau intensitas cahaya dari semua kunang-kunang dengan menggunakan algoritma pengurutan. Dalam hal ini, kompleksitas algoritma FA adalah O(nt log(n)). Algoritma FA mempunyai

31 waktu eksekusi lebih efisien dibandingkan dengan algoritma swarm lainnya dengan alasan: 1. Algoritma FA dapat secara otomatis membagi populasi ke dalam subgrup, karena fakta bahwa ketertarikan lokal lebih kuat dibandingkan dengan ketertarikan jarak jauh. Sebagai akibatnya, algoritma FA dapat menangani masalah optimisasi dengan non-linier yang tinggi dan multi-modal secara alamiah dan efisien 2. Algoritma FA tidak menggunakan historis individu terbaik s∗, dan juga tidak mempunyai global terbaik g ∗ . Hal ini dapat mencegah terjadinya konvergensi yang prematur seperti pada algoritma PSO. Selanjutnya, algoritma FA tidak menggunakan kecepatan sehingga tidak mengalami masalah yang berhubungan dengan kecepatan seperti pada PSO 3. Algoritma FA mempunyai kemampuan untuk mengendalikan modalitas dan menyesuaikan dengan cakupan masalah dengan mengendalikan penskalaan parameter seperti γ. Dalam kenyataannya, algoritma FA merupakan generalisasi dari SA, PSO dan DE (Fister et al., 2013).

Algoritma FA mempunyai sejumlah varian dalam literatur, sehingga dibutuhkan skema klasifikasi tertentu untuk membedakannya. Cara termudah adalah berdasarkan penentuan parameter algoritma (strategi penentuan parameter). Penentuan parameter tersebut menjadi krusial untuk mendapatkan kinerja algoritma yang lebih baik, sehingga harus ditentukan dengan cermat. Pada sisi penyesuaian parameter, kemungkinan nilai yang baik dapat diperoleh sebelum algoritma dijalankan. Di sisi lain, pengendalian parameter dilakukan dengan memodifikasi nilai parameter selama eksekusi algoritma. Lebih lanjut, sifat dari algoritma FA tidak hanya tergantung pada nilai parameter, tetapi juga pada komponen atau fitur yang diberikan. Berikut ini merupakan aspek-aspek penting dalam menentukan klasifikasi algoritma FA, yakni:

32 1. Apa yang dimodifikasi 2. Bagaimana melakukan modifikasi 3. Berapa luas cakupan modifikasi

Berdasarkan aspek yang pertama, algoritma FA dapat diklasifikasikan menurut komponen atau fitur mana yang dimiliki, yakni: a. Representasi kunang-kunang (biner atau riil) b. Skema populasi (swarm atau multi-swarm) c. Evaluasi fungsi fitness d. Penentuan solusi terbaik (non-elitism atau elitism) e. Pergerakan kunang-kunang (uniform, Gauss, Levy flight, atau distribusi chaos)

Sementara menurut aspek yang kedua, kategori parameter algoritma FA dapat dibedakan menjadi: deterministik, adaptif, atau self-adaptive. Kemudian untuk aspek ketiga, modifikasi algoritma FA dapat memengaruhi: satu kunangkunang, seluruh kunang-kunang atau keseluruhan populasi. Pada tahap awal, algoritma FA digunakan untuk menyelesaikan masalah global, seperti masalah optimisasi kontinu. Untuk itu diperkenalkan ide hibrida / penggabungan dengan algoritma optimisasi lainnya, teknik machine learning, heuristik dan lain-lain. Penggabungan dapat terjadi pada hampir semua komponen algoritma FA, seperti prosedur inisialisasi, fungsi evaluasi, fungsi pergerakan dan sebagainya. Dalam perkembangannya, algoritma FA telah mengalami modifikasi dan penggabungan seperti terlihat pada Gambar 2.3

33

Gambar 2.3 Taksonomi Algoritma FA 2.2.4 Intelligent Firefly Algorithm Pada algoritma FA di atas, pergerakan (persamaan 2.7) ditentukan oleh daya tarik dari kunang-kunang lainnya dimana ketertarikan adalah sebuah fungsi jarak antar kunang-kunang. Akibatnya, seekor kunang-kunang dapat tertarik pada yang lain hanya karena kedekatan yang mungkin menjauhkan minimum global. Kunang-kunang diurutkan berdasarkan intensitas cahaya yang dihasilkan yakni berdasarkan nilai dari fungsi objektif pada lokasi di mana dia berada. Akan tetapi pengurutan (yang merupakan informasi penting) tersebut tidak digunakan untuk menentukan dalam persamaan pergerakan. Seekor kunang-kunang tertarik satu sama lain sehingga keduanya memberikan kontribusi pada pergerakan dengan tingkat daya tarik masing-masing. Kondisi ini dapat mengakibatkan penundaan dalam pergerakan kolektif menuju minimum global. Ide dari algoritma

34 FA cerdas (IFA) adalah menggunakan hasil pengurutan sedemikian hingga setiap kunang-kunang digerakkan oleh daya tarik sebagian kunang-kunang bukan keseluruhannya. Partisi ini merepresentasikan bagian paling atas dari kunang-kunang berdasarkan urutannya. Dengan demikian, seekor kunang-kunang bertindak cerdas bergerak berdasarkan urutan teratas bukan hanya sekedar berdasarkan daya tarik. Pseudocode algoritma IFA dikembangkan oleh Fateen et. al (Fateen et al., 2014) dapat dilihat pada Gambar 2.4 di bawah ini. Parameter baru φ merupakan bagian dari kunang-kunang yang digunakan untuk menentukan pergerakan. Parameter ini digunakan sebagai batas atas untuk indeks j dalam inner loop. Dengan demikian setiap kunang-kunang digerakkan hanya oleh bagian teratas φ. Algoritma FA biasa menggunakan φ = 1 Kekuatan dari algoritma IFA adalah bahwa lokasi terbaik kunang-kunang tidak memengaruhi arah dari pencarian, sehingga tidak terjebak pada minimum lokal. Akan tetapi, pencarian atas minimum global membutuhkan komputasi tambahan karena ada kemungkinan banyak kunangkunang yang bergerak tak tentu arah pada daerah yang kurang menarik. Dengan modifikasi yang cerdas, nilai parameter φ yang sesuai dapat mempertahankan kelebihan yang tidak terjebak dalam minimum lokal, serta dapat meningkatkan kecepatan mendapatkan minimum global. Nilai φ yang sesuai memberikan keseimbangan antara kemampuan algoritma terhindar dari jebakan minimum lokal dan kemampuan mengeksploitasi solusi terbaik yang diperoleh. Prosedur secara

35

Gambar 2.4 Algoritma Intelligent FA iteratif dapat digunakan untuk mencapai nilai φ yang baik untuk masalah yang dioptimalkan. Modifikasi algoritma FA ini dapat meningkatkan kinerja algoritma secara signifikan. Dengan pilihan parameter α, β, γ dan jumlah iterasi k yang lebih besar dapat mengurangi keacakan sampai solusi minimum global ditemukan. Algoritma IFA dapat meningkatkan reliabilitas dan efektifitas dari algoritma. Dalam beberapa kasus minimum global tidak dapat ditemukan dengan algoritma FA biasa, tetapi dengan modifikasi ini menjadi mungkin (Fateen et al., 2014). 2.3 Manajemen Rantai Pasokan Menurut Global Supply Chain Forum (GSCF), manajemen rantai pasokan (supply chain manajemen) didefinisikan sebagai ”integrasi proses bisnis kunci dari

36 pengguna akhir hingga pemasok awal yang menyediakan produk, layanan, dan informasi yang menambahkan nilai bagi pelanggan dan stakeholder lainnya” (Chan et al., 2003). Christoper (Christoper, 1998) menyatakan bahwa rantai pasokan adalah jaringan organisasi yang melibatkan keterkaitan upstream dan downstream dalam proses dan aktivitas berbeda yang menghasilkan ”nilai” dalam bentuk produk dan servis. Rantai pasokan memainkan peran penting dalam sumber daya korporasi, yang pada gilirannya memengaruhi aspek sosial, ekonomi dan lingkungan dari bisnis (Tate et al., 2010). Dengan asumsi demikian, korporasi semakin melihat isu rantai pasokan sebagai bagian dari program berkelanjutan. Koplin et al. (Koplin et al., 2007) mengidentifikasikan dua alasan besar untuk hal ini. Alasan pertama adalah bahwa korporasi saat ini diwajibkan bertanggung jawab untuk masalah sosial dan lingkungan yang disebabkan oleh operasional rantai pasokan. Alasan kedua adalah bahwa peningkatan saham dalam nilai korporasi diciptakan pada level pemasok. Dalam lingkungan bisnis saat ini yang sangat kompetitif, manajemen rantai pasokan yang efektif akan menjadi faktor penting untuk mencapai keunggulan kompetitif. Akan tetapi, bagaimana integrasi dilakukan, artinya masih terdapat jurang terkait dengan pengukuran kinerja rantai pasokan berkelanjutan (Vermeule dan Seuring, 2009; Krause et al., 2009; Seuring dan Muller, 2008a). Storey et al. (Storey et al., 2006) lebih lanjut menjelaskan bahwa manajemen rantai pasokan dapat dilihat sebagai tren yang lebih jauh melibatkan kerangka outsourcing, cross-boundary dan bentuk organisasi baru yang membentuk hirarki, tim, pemberdayaan dan seterusnya sehingga bukan lagi

37 sebagai komando dan kendali yang kaku. Sejumlah tantangan dan kendala dalam penerapan sustainable supply chain manajemen(sSCM) terkait dengan: (1) kurangnya pemahaman keterkaitan yang kompleks antara aktivitas ekonomi, lingkungan dan sosial dan bagaimana hal tersebut memengaruhi ekonomi, (2) komitmen investasi modal, (3) memonitor dan mengelola risiko, (4) pengukuran kinerja, (5) transparansi informasi dan pengetahuan, (6) penyesuaian strategi korporasi dengan inisiatif sSCM dan (7) budaya korporasi (Christoper, 1998; Linton et al., 2007; Seuring dan Muller, 2008b; Storey et al., 2006). Kebanyakan riset tentang rantai pasokan berkelanjutan hanya membahas tentang ekonomi dan lingkungan, sangat sedikit yang memasukkan aspek sosial dalam kajiannya. Manajemen rantai pasokan berkelanjutan Sustainable Supply Chain Management (sSCM) berawal dari akarnya yakni manajemen rantai pasokan (SCM). Harland (Harland, 1996) mendefinisikan supply chain management sebagai ”manajemen jaringan saling terkait dalam bisnis untuk penyediaan produk akhir dan paket layanan yang dibutuhkan oleh pelanggan akhir.” Pada tahap berikutnya SCM diperluas dengan menambahkan aspek sustainability. Aspek tersebut merupakan integrasi isu sosial, lingkungan dan ekonomi (Carter dan Roger, 2008). Carter dan Roger (Carter dan Roger, 2011) mengidentifikasi empat faktor pendukung atau fasilitator dari sSCM, yakni: (1) strategi secara holistik dan kontinu mengidentifikasikan inisiatif sSCM secara individu yang menyelaraskan dan

38 mendukung strategi keseluruhan rantai pasokan, (2) manajemen risiko, termasuk contingecy planning untuk upstream dan downstream dalam rantai pasokan, (3) budaya organisasi yang secara mendalam yang berakar dan mencakup organizational citizenship, dan mengandung standar etis yang tinggi dan ekspektasi dengan memberi respek terhadap masyarakat (di dalam maupun di luar organisasi) dan lingkungan alam, serta (4) transparansi dalam hal partisipasi proaktif dan mengkomunikasikannya dengan pemangku kepentingan kunci dan mempunyai traceability dan visibility baik upstream maupun downstream dalam rantai pasokan, seperti terlihat pada Gambar 2.5 di bawah ini.

Gambar 2.5 Sustainable Supply Chain Management (Carter dan Roger, 2011)

Shrivasta (Shrivasta, 2007) mendefinisikan sustainability sebagai ”potensi untuk mengurangi risiko jangka panjang terkait dengan penurunan sumber daya, fluktuasi harga energi, obligasi produk, dan polusi serta pengelolaan limbah”.

39 Selanjutnya, Sikdar (Sikdar, 2003) mengungkapkan sudut pandang makro yang mengandung aspek sosial, lingkungan dan ekonomi yang mendefinisikan sustainability sebagai keseimbangan yang bijaksana antara kinerja ekonomi, perlindungan lingkungan dan tanggung jawab sosial. Dari sudut pandang makro rantai pasokan sefta untuk mencapai keseimbangan antara dimensi ekonomi, lingkungan dan sosial (dikenal dengan triple bottom line) yang dikembangkan oleh Elkington (Elkington, 2004), Teuteber dan Wittstruck (Teuteber dan Wittstruck, 2010) sSCM didefinisikan sebagai pencapaian strategis dan terintegrasi oleh satu perusahaan dalam tujuan sosial, lingkungan dan ekonomi. Hal tersebut dicapai melalui koordinasi sistemik dari proses bisnis yang saling terkait antar organisasi untuk meningkatkan kinerja ekonomi jangka panjang dari perusahaan secara individu dan jaringan nilainya, seperti dikemukakan oleh Carter dan Roger (Carter dan Roger, 2008). Gambar 2.6 berikut ini merupakan area dan cakupan dari sSCM yang disebut dengan ”House of Sustainable Supply Chain Management”. ”Rumah” tersebut dibangun di atas triple bottom line yakni kinerja ekonomi, perlindungan lingkungan dan tanggung jawab sosial (Carter dan Roger, 2008; Elkington, 2004). Ketiga dimensi sustainability divisualisasikan sebagai pilar yang dibutuhkan untuk menjaga keseimbangan bangunan. Manajemen risk and compliance membentuk fondasi dari bangunan. Untuk mencapai keuntungan jangka panjang, risiko harus diidentifikasikan dan diperkecil. Hukum, acuan dan standar

40

Gambar 2.6 House of sSCM (Carter dan Roger, 2008) digunakan sebagai titik awal untuk implementasi prinsip dan praktik sustainability sepanjang rantai pasokan. Sebagai tambahan, sSCM juga membutuhkan pengembangan nilai dan etika di seluruh organisasi, lingkungan teknologi informasi yang efisien, fleksibilitas dan konsep green serta penyesuaian strategi korporasi untuk mencapai pembangunan yang berkelanjutan. Jika ukuran-ukuran tersebut dapat dijalankan, maka organisasi dapat melindungi jaringan terhadap ancaman dan risiko terkait lingkungan dan sosial. Rumah sSCM tidak terbatas hanya pada pengendalian jaringan rantai pasokan, tetapi juga menerapkan manajemen teknologi informasi, manajemen kepatuhan dan lingkungan serta sosial (Teuteber dan Wittstruck, 2010). Kajian manajemen rantai pasokan terkait erat dengan green supply chain, reverse logistics, closed-loop supply chain management, environmentally conscious

41 manufacturing dan product recovery, dan lain-lain (Bloemhof, 2005). Area manajemen rantai pasokan dapat dibagi menjadi dua bidang yakni: (i) konsep triple-P yang terdiri dari optimisasi profit (aspek ekonomi), people (aspek sosial) dan kinerja terkait dengan planet (aspek lingkungan), yang merupakan metrik untuk mengukur kinerja dari forward supply chain tradisional, dan (ii) konsep closed-loop supply chain management (CLSC) yang mengkombinasikan forward dan reverse supply chain dengan menutup aliran materi untuk membatasi emisi gas dan limbah (Bloemhof, 2005). Perubahan cuaca, kelangkaan energi, dan pertumbuhan penduduk yang pesat serta perkembangan teknologi memberikan tekanan luar biasa terhadap kemampuan rantai pasokan global untuk menyediakan barang dan layanan secara efektif dan efisien (Beamon, 2008). Dalam literatur disebutkan bahwa terdapat dua kebutuhan riset lanjutan dalam sSCM. Pertama, adanya kebutuhan berkelanjutan guna mengeksplorasi pendekatan untuk mengintegrasikan ketiga pilar sustainability dari manajemen rantai pasokan yakni dimensi lingkungan, ekonomi dan sosial. Kedua, adanya kebutuhan untuk mengembangkan sistem pengukuran kinerja untuk sSCM. Selanjutnya, studi literatur mengharapkan bahwa riset lanjutan harus bergerak di luar dari kedua area pembahasan secara terpisah, melainkan harus mengarah kepada pendekatan yang lebih terintegrasi. Pendekatan ini menekankan integrasi strategis terhadap dimensi lingkungan, sosial dan ekonomi dari proses bisnis kunci secara inter-organizational (Morali dan Searcy, 2010).

42 2.4 Fleksibilitas dalam Rantai Pasokan Sejak tahun 1990-an, banyak perusahaan mencoba meningkatkan kinerja ekonominya dengan menerapkan berbagai inisiatif dalam rantai pasokan. Inisiatif tersebut dimaksudkan untuk meningkatkan pendapatan (misalnya dengan menawarkan produk lebih bervariasi, perkenalan produk baru yang lebih cepat, memperbanyak saluran pemasaran), mengurangi biaya (dengan mengurangi pasokan, e-commerce, lelang online, produksi off-shore manufacturing, sistem pasokan just-in-time, dan vendor-managed inventory, mengurangi aset (dengan outsourcing manufacturing), pemanfaatan RFID dan GPS, serta logistik. Inisiatif tersebut akan bekerja efektif dalam kondisi stabil. Akan tetapi, dengan meningkatnya jumlah jaringan rantai pasokan dan banyaknya pihak yang terlibat dalam rantai pasokan, mengakibatkan rantai pasokan global tersebut menjadi lebih ”panjang” dan lebih ”kompleks” yang pada akhirnya membuat manajemen rantai pasokan semakin rumit dan membutuhkan tingkat fleksibilitas yang lebih tinggi (Tang dan Tomlin, 2008). Rantai pasokan beroperasi dalam lingkungan dinamis yang terdiri dari sekumpulan tujuan rantai pasokan, strategi keseluruhan rantai pasokan, dan sistem ukuran kinerja. Sejumlah penulis telah meneliti masalah bagaimana menggunakan proses fleksibilitas dalam rantai pasokan. Iravani et al. (Iravani et al., 2005) memperkenalkan konsep fleksibilitas untuk menyatakan kemampuan struktur fleksibilitas untuk merespons variabilitas permintaan. Graves dan Tomlin (Graves dan

43 Tomlin, 2003) memberikan kerangka kerja untuk menganalisis keuntungan dari fleksibilitas dalam sebuah rantai pasokan multistage dan mengembangkan ukuran fleksibilitas dan panduan untuk fleksibilitas investasi. Paper mereka menjawab pertanyaan tentang struktur fleksibilitas seperti apa yang paling efisien dengan syarat semua tahapan dalam rantai pasokan menggunakan struktur fleksibilitas yang sama. Studi lain, diantaranya Fine dan Freund (Fine dan Freund, 1990), Gupta et al. (Gupta et al., 1992), Suarez et al. (Suarez et al., 1995) dan Van Mieghem (Van Mieghem, 1998). Tantangan yang dihadapi rantai pasokan saat ini antara lain: pelanggan menuntut harga yang lebih murah, pergantian yang lebih cepat, tingkat layanan yang tinggi, keterbukaan dan visibility terhadap semua proses yang terjadi (Microsoft, 2009). Fleksibilitas telah dianggap sebagai faktor utama untuk memenangkan persaingan dalam persaingan pasar yang semakin tinggi. Pujawan (Pujawan, 2004) mengidentifikasikan lima dimensi penting dalam fleksibilitas yakni: sourcing flexibility, product development flexibility, production flexibility, supply flexibility dan delivery flexibility. Fleksibilitas dalam pengiriman produk terdiri dari: (1) terdapat mode transportasi berbeda dalam pengiriman barang ke pelanggan akhir, (2) secara teknis dan ekonomis mudah menggabungkan beberapa produk dalam satu kali pengiriman, (3) jumlah pengiriman minimum diperkecil, (4) tidak ada batasan jumlah pengiriman dalam sebuah truk, kontainer atau angkutan lain, (5) dalam hal darurat, percepatan pengiriman produk dimungkinkan dengan memilih mode

44 transportasi berbeda, (6) dimungkinkan untuk memenuhi permintaan pelanggan yang berasal dari gudang berbeda atau dimungkinkan untuk pengiriman barang antar gudang atau antar retailer yang dikenal dengan istilah transhipment, (7) pelanggan dimungkinkan untuk mengubah jumlah, jenis dan/atau tanggal pengiriman dalam waktu yang singkat dengan biaya pengiriman yang minimum. Menurut Angel dan Perez (Angel dan Perez, 2005) dimensi fleksibilitas terdiri dari: (1) product flexibility, yakni kemampuan untuk menangani pesanan yang tidak standar guna memenuhi spesifikasi pelanggan khusus dan menghasilkan karakteristik produk dengan sejumlah fitur, opsi, ukuran dan warna, (2) volume flexibility, yakni kemampuan dalam menaikkan dan menurunkan volume produksi secara efektif untuk memenuhi permintaan pelanggan yang secara langsung memengaruhi kinerja rantai pasokan dengan mencegah kondisi out-of-stock untuk produk dengan permintaan tinggi atau menghindarkan persediaan yang terlalu tinggi, (3) routing flexibility, yakni kemampuan untuk memroses bagian tertentu menggunakan mesin berbeda, penanganan material yang fleksibel, dan jaringan transportasi yang berbeda; fleksibilitas ini mengurangi dampak negatif dari ketidakpastian lingkungan dan inefisiensi yang tak terlihat dalam proses produksi, (4) delivery flexibility, yakni kemampuan untuk beradaptasi terhadap waktu tunda atas permintaan pelanggan jika pemasok mengirimkan produk ke pelanggan dalam jumlah, tempat dan waktu yang tepat, (5) transhipment flexibility melibatkan perpindahan stok antar lokasi pada level eselon yang sama dimana jarak

45 fisik antara lokasi permintaan dan sumber tidak terlalu jauh, (6) sourcing flexibility terkait dengan kemampuan perusahaan untuk mencari sumber lain untuk komponen atau material khusus, (7) postponement flexibility mengimplikasikan kemampuan untuk menyimpan produk selama mungkin untuk memenuhi kebutuhan pelanggan pada level berikutnya, (8) launch flexibility, yakni kemampuan untuk memperkenalkan produk baru dari ragam produk dengan cepat yang mengintegrasikan sejumlah aktivitas nilai sepanjang rantai pasokan, (9) access flexibility, yakni kemampuan perusahaan menyediakan cakupan distribusi yang intensif dan meluas, serta (10) dimensional flexibility yang cocok terhadap sejumlah industri yakni tingkat respons terhadap pasar target. Lee (Lee, 2004) dalam Triple-A Supply Chain, menekankan bahwa rantai pasokan terbaik bukan hanya cepat dan cost effective, tetapi harus agile, adaptable dan semua kepentingan perusahaan harus tetap aligned. Agility mempunyai tujuan untuk merespon perubahan jangka pendek dalam pasokan dan permintaan dengan cara: (1) tetap memberikan informasi secara kontinu terkait pasokan dan permintaan terhadap semua partner dalam rantai pasokan, (2) berkolaborasi dengan pemasok dan pelanggan untuk mendesain ulang proses, komponen dan produk sedemikian hingga memberikan keunggulan dari saingan, (3) menyelesaikan produksi hanya apabila diperoleh informasi yang akurat tentang keinginan pelanggan, dan (4) menyimpan persediaan yang sedikit untuk komponen yang tidak mahal dan ukuran kecil untuk menghindarkan penundaan produksi. Sementara itu,

46 adaptability mempunyai tujuan menyesuaikan rantai pasokan terhadap perubahan pasar yang ditempuh melalui: (a) menelusuri perubahan ekonomi, khususnya di negara berkembang, (b) menggunakan perantara untuk mendapatkan penjual terpercaya di daerah yang kurang dikenal, (c) menciptakan fleksibilitas untuk menjamin produk berbeda menggunakan komponen berbeda dan proses berbeda, dan (d) menciptakan rantai berbeda untuk produk berbeda guna mengoptimalkan kemampuan masing-masing. Kemudian alignment mempunyai tujuan untuk mengembangkan insentif kepada mitra dalam rantai pasokan, sehingga meningkatkan kinerja keseluruhan rantai dengan cara: (i) menyediakan akses yang sama kepada semua mitra terkait dengan data penjualan, perencanaan dan perkiraan, (ii) memperjelas peran masing-masing mitra untuk menghindarkan konflik, (iii) mendefinisikan ulang kemitraan untuk menanggung bersama risiko, biaya dan penghargaan untuk meningkatkan kinerja rantai pasokan, dan (iv) menyusun ulang insentif sehingga semua pemain dalam rantai pasokan memaksimalkan kinerja rantai dan juga memaksimalkan keuntungan masing-masing dari kemitraan tersebut. 2.5 Tantangan dalam Manajemen Rantai Pasokan Ciri khas pasar global saat ini adalah tak terduga dan penuh risiko (IBM, 2010). Globalisasi mengakibatkan rantai pasokan semakin kompleks dan selanjutkan akan mengakibatkan terbukanya rantai pasokan terhadap gangguan dan risiko. Kesalahan perhitungan dan keputusan sekecil apa pun dapat mengaki-

47 batkan guncangan besar terhadap rantai pasokan. Lima tantangan menurut laporan ini adalah: (1) cost containment: perubahan harga cepat dan terus terjadi mengguncang dan melemahkan kekuatan rantai pasokan dalam beradaptasi, (2) visibility: membanjirnya informasi membuat pengambil keputusan berjuang untuk memahami dan bertindak atas informasi yang akurat dan tepat, (3) risk: manajemen risiko merupakan agenda penting setiap pengambil keputusan dalam rantai pasokan, (4) customer intimacy: meskipun prinsip demand-driven sudah meluas penggunaannya, perusahaan biasanya mempunyai hubungan yang lebih baik terhadap pemasok dibandingkan dengan pelanggannya, dan (5) globalization: berbeda dengan alasan semula, ternyata globalisasi terbukti lebih pada pertumbuhan pendapatan dibandingkan penghematan biaya. Menurut laporan ini, para pengambil keputusan mempersepsikan kelima tantangan di atas memengaruhi rantai pasokan dengan tingkat yang berbeda, seperti terlihat pada Gambar 2.7 berikut ini. Untuk menghadapi tantangan tersebut, salah satu upaya adalah dengan membangun dan menerapkan Smarter Supply Chain. Hal ini dicapai dengan menggunakan tiga konsep yakni: (1) instrumented - informasi yang sebelumnya diciptakan oleh manusia berubah menjadi machine-generated, penggunaan teknologi akan semakin meluas yang dilengkapi dengan sensor cerdas, (2) interconnection - rantai pasokan secara keseluruhan saling terkait yang memungkinkan rantai pasokan global untuk merencanakan dan mengambil keputusan secara

48

Gambar 2.7 Lima Tantangan Teratas Rantai Pasokan Global (IBM, 2010) besama-sama, dan (3) smart - sistem yang lebih cerdas akan mampu mengambil keputusan secara otomatis tanpa campur tangan manusia. Dengan menerapkan sistem lebih cerdas ini, perusahaan dapat meningkatkan level visibility sepanjang rantai nilai untuk beradaptasi dengan perubahan lingkungan dan mengantisipasi kebutuhan mendesak, yang dikenal dengan sistem Business Intelligence. Sistem ini dapat meningkatkan berbagai kinerja rantai pasokan terkait dengan pengiriman barang dan material, pengurangan stok, waktu siklus pemenuhan permintaan, akurasi prediksi, produktivitas secara keseluruhan, penurunan biaya rantai pasokan, tingkat pemenuhan, dan realisasi kapasitas. Dengan demikian, maka proses integrasi antar pemain dalam rantai pasokan dapat dibangun. Integrasi fungsi bisnis yang terdapat dalam rantai pasokan dapat digunakan

49 untuk mengurangi risiko yang disebabkan berbagai faktor. Chopra dan Sodhi (Chopra dan Sodhi, 2004), Kleindorfer dan Saad (Kleindorfer dan Saad, 2005), Rice dan Caniato (Rice dan Caniato, 2003), serta Sheffi (Sheffi, 2005) mengemukakan enam jenis risiko dalam rantai pasokan yang harus diatasi dengan menerapkan fleksibilitas. Keenam risiko yang dimaksud adalah: supply risks, process risks, demand risks, intelectual property risks, behavioral risks, dan political/social risks. Terdapat dua ukuran umum dari risiko yakni: kemungkinan terjadinya peristiwa buruk dan implikasi negatif dari peristiwa tersebut. Bogataj dan Bogataj (Bogataj dan Bogataj, 2007) mengembangkan pendekatan program linier parameter untuk mengukur risiko rantai pasokan dalam hal gangguan penundaan pengiriman barang. Sejumlah peristiwa yang tidak diinginkan terkait dengan risiko pasokan, proses, dan permintaan (termasuk peningkatan harga dalam rantai pasokan, penurunan kemampuan rantai pasokan, ketimpangan antara permintaan dalam perkiraan dengan permintaan aktual, dan lain-lain). Untuk mengatasi risiko yang pertama terdapat dua mekanisme yang efektif yakni: berdasarkan pada konsep menghindarkan risiko dan berdasarkan sejumlah prinsip Total Quality Management (TQM). Tang dan Tomlin (Tang dan Tomlin, 2008) lebih jauh menawarkan strategi fleksibilitas dalam risiko biaya pasokan melalui muliple suppliers, risiko komitmen pasokan melalui kontrak pasokan yang fleksibel, risiko proses melalui proses manufaktur yang fleksibel, serta risiko permintaan melalui penundaan dan penentuan harga yang responsif.

50 2.6 Transshipment dalam Rantai Pasokan Inventory transshipment merupakan salah satu strategi yang menjanjikan dalam memberikan fleksibilitas operasional untuk menghadapi akibat dari permintaan tak pasti yang pada akhirnya dapat mengurangi biaya persediaan (Lien et al., 2011). Transshipment antar pemain dalam eselon yang setingkat dalam rantai pasokan dimaksudkan untuk (1) meningkatkan kemampuan memberikan respon atas permintaan pelanggan, (2) memberikan fleksibilitas untuk penyesuaian siklus produksi dan pengiriman. Penelitian tentang transshipment fokus pada keputusan operasional pada desain jaringan tetap : jumlah yang diperoleh melalui transshipment antar lokasi dalam satu eselon dan jumlah yang diterima dari pemasok pada setiap lokasi. Herer et al. (Herer et al., 2006), meneliti masalah transshipment dengan mempertimbangkan lokasi dengan variasi pada permintaan dan parameter biaya. Selanjutnya, Taragas dan Vlachos (Taragas dan Vlachos, 2002) meneliti kemungkinan waktu tunda replenishment adalah satu, sementara waktu tunda transshipment dapat diabaikan dalam satu periode. Herer et al. (Herer et al., 2006) membandingkan lima konfigurasi berbeda dalam kemampuan transshipment dan menunjukkan nilai transshipment pada masing-masing lokasi. Sementara Yu et al. (Yu et al., 2005) meneliti jaringan transshipment dengan satu pemasok dan tiga retailers dan membahas enam rancangan jaringan yang mungkin, yang mereka sebutkan sebagai level fleksibilitas operasional. Mereka menggunakan model

51 jaringan dari Van Mieghen dan Rudi (Mieghen dan Rudi, 2002) untuk menentukan jumlah optimal retailer untuk tingkat fleksibilitas tertentu serta menganalisis interaksi antara optimisasi jumlah pesanan dan peningkatan fleksibilitas operasional. Chou et al. (Chou et al., 2006) memperkenalkan pendekatan/kerangka yang robust untuk menganalisis sistem distribusi dengan strategi transshipment. Mereka menunjukkan efisiensi komputasi untuk jaringan distribusi skala besar dengan menganalisis dampak transshipment pada pengurangan biaya dari sistem distribusi dengan berbagai konfigurasi dan karakteristik dari retailer. Secara khusus, mereka menganalisis dua jenis konfigurasi yakni garis dan lingkaran dengan membandingkan biaya penyimpanan, biaya transshipment dikaitkan dengan jumlah permintaan baik untuk retailer yang homogen dan non-homogen. Berdasarkan pengujian yang mereka lakukan diperoleh bahwa penghematan biaya melalui transshipment cukup substansial jika biaya penyimpanan lebih besar dibandingkan dengan biaya transshipment dalam sistem distribusi yang besar. Selanjutnya keuntungan yang diperoleh pada konfigurasi lingkaran lebih signifikan dibandingkan dengan konfigurasi garis. Tujuan dari masalah operasional transshipment adalah meminimumkan ekspektasi biaya per periode untuk sebuah desain jaringan dengan menggunakan parameter sebagai berikut (Lien et al., 2011):

52 Par. N K ci cs ch

Keterangan Himpunan lokasi retailer (nodes) i ∈ {1, . . . , N} Himpunan link transshipment berarah (i, j) ∈ K yang didefinisikan oleh konfigurasi K ⊆ (N × N) Biaya transshipment untuk satu unit pada sebuah link Biaya kekurangan stok untuk satu unit dalam satu periode Biaya penyimpanan satu unit dalam persediaan dalam satu periode

Peubah keputusan dideskripsikan sebagai berikut (Lien et al., 2011): Peubah Si Xij Di Ii

+

Ii

−

Keterangan Order-up-to level pada lokasi i ∈ N Jumlah item untuk dikirimkan melalui transshipment pada link (i, j) ∈ N Peubah acak yang menyatakan permintaan pada lokasi i ∈ N dalam satu periode Net surplus pada akhir periode (setelah transshipment) pada lokasi i ∈ N Net shortage pada akhir periode (setelah transshipment) pada lokasi i ∈ N

Awalnya kita mengoptimalkan X, matriks Xij untuk bentuk umum orderup-to level, kemudian menunjukkan metode iterasi untuk menemukan order-up-to level yang optimal. Dalam setiap periode, untuk vektor S yang merupakan orderup-to level dan permintaan D, diselesaikan dengan program linier berikut:

z(K, S, D) = minimize : ci

X

(i,j)∈N

Xij + cs

X i∈N

I i − + ch

X i∈N

Ii +

(2.11)

53 subject to: X

i:(ij)∈N

Xij + Ii + − Ii − = Si − Di , ∀i ∈ N X

i:(ij)∈N

Ii

+

Xij ≤ Si , ∀i ∈ N

Xij ≥ 0, ∀(i,j) ∈ N , −Ii − ≥ 0, ∀i ∈ N

(2.12)

Fungsi objektif – persamaan (2.11)– adalah meminimumkan total biaya transshipment, kekurangan dan biaya penyimpanan dengan mengetahui K, S, dan D. Dengan kendala: (1) semua permintaan dipenuhi melalui replenishment dan transshipment atau backlogged ; (2) membatasi jumlah transshipment; (3) persyaratan non-negatif untuk transshipment, persediaan dan kekurangan. Penyelesaian model di atas diperoleh dengan menyelesaikan masalah operasional transshipment untuk menghasilkan ekspektasi biaya yang optimal.