Sardes Malau 1), Tulus 1) 1) Matematika FMIPA Universitas Sumatera Utara

Seminar Nasional dan ExpoTeknik Elektro 2012

ISSN : 2088-9984

Perencanaan Routing dengan Permintaan Acak Menggunakan Chance Constrained Programming Sardes Malau1), Tulus1) 1) Matematika FMIPA Universitas Sumatera Utara Jl. Bioteknologi 1, Medan 20155 Indonesia email: [email protected], [email protected]

Distribusi dari kumpulan trafik permintaan (aggregation traffic demand) dapat dianggap berdistrisbusi normal [1]. Pendekatan Chance Constrained Programming yang dikembangkan oleh Rao [4] dan Liu [4] dapat menjadi alternatif terhadap pendekatan syarat pemesanan bandwidth berdasarkan rata-rata. Dalam penelitian ini, variasi permintaan diatas rata-rata dapat ditangani secara statistik didasarkan pada tingkat jaminan (level of guarantee) tertentu. Dalam penelitian ini penulis mencoba menerapkan Chance Constrained Programming (CCP) dalam perencanaan routing dan alokasi bandwidth pada jaringan telekomunikasi dengan kendala permintaan acak, keterbatasan bandwidth serta menggabungkannya dengan tingkat jaminan pelayanan.

ABSTRAK Chance constrained progamming dikembangkan oleh Charnes dan Cooper merupakan salah satu bagian dari stochastic programming. Chance constrained programming adalah salah satu teknik yang dapat dipakai untuk menyelesaikan permasalahan yang mengandung kendala peluang. Dalam penelitian ini penulis mencoba memakai chance constrained programming sebagai model dalam perencanaan routing suatu jaringan yang mana permintaan (pemakaian bandwidth) seperti download dan upload dalam jaringan ini bersifat tidak pasti atau dapat dikatakan acak, dalam hal inilah chance constrained programming penulis gunakan yakni dalam menentukan suatu model routing terbaik serta pengalokasian bandwidth secara optimal dalam suatu jaringan, sehingga akan dicapai suatu jaringan yang baik serta biaya minimal dalam pengalokasian bandwidth dalam jaringan tersebut. chance constrained programming cocok digunakan dalam hal ini karena model ini dapat menggabungkan antara ketidakpastian permintaan pada jaringan dengan tingkat jaminan (level of guarantee) yang mau manajemen jaringan berikan kepada pengguna jaringan tersebut.

2. Landasan Teori Chance Constrained Programming Merupakan teknik kedua dari program stokastik yang dikembangkan oleh Charnes dan Cooper, seperti yang dinyatakan dari namanya program chance constrained adalah satu teknik yang bisa dipakai untuk menyelesaikan persoalan yang mengandung kendala peluang, kendala tersebut mempunyai peluang terbatas tertentu untuk dilanggar. Program chance constrained ini memperbolehkan kendala untuk dilanggar oleh sebuah peluang tertentu (peluang kecil) dimana teknik lain tidak ada. Rao memberika bentuk umum program chance constrained programming dari persoalan program linier stokastik sebagai berikut: Minimize

Kata kunci: Perencanaan Routing, Permintaan Acak, Chance Constrained Programming

1. Pendahuluan Pertumbuhan internet yang sangat cepat menimbulkan berbagai masalah seperti loading yang lambat bahkan tidak dapat terhubung (lost connected). Semua ini berhubungan dengan Routing dalam suatu jaringan telekomunikasi yaitu proses dari penentuan sebuah lintasan yang dipakai untuk mengirim data ke tujuan tertentu, dengan pengalokasian bandwidth atau dalam bahasa sehari-hari suatu perhitungan konsumsi data yang tersedia pada suatu jaringan telekomunikasi. Dihitung dalam satuan bits per seconds (bps), karena itu diperlukan suatu perencanaan routing dan pengalokasian bandwidth pada arsitektur jaringan di masa yang akan datang dirancang sesuai dengan permintaan yang bergerak secara dinamis, hal ini berarti aturan routing dapat dibuat dalam jangka pendek. Maka dari itu, jumlah bandwidth yang dibutuhkan untuk melayani permintaan dapat berubah secara dinamis.

𝑛

𝑓 𝑥 =

𝑐𝑗 𝑥𝑗

(1)

𝑗 =1

Dengan kendala 𝑛

𝑃

𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 ≥ 𝑝𝑖, 𝑖 = 1,2, … , 𝑚

(2)

𝑗 =1

𝑥𝑗 ≥ 0, 𝑗 = 1,2, … , 𝑛

(3)

Dimana 𝑐𝑗 , 𝑎𝑖𝑗 , dan 𝑏𝑖 adalah variabel acak dan 𝑝𝑖 adalah tingkat peluang tertentu. Perhatikan bahwa persamaan menunjukkan bahwa kendala ke-i

D-8

Seminar Nasional dan ExpoTeknik Elektro 2012

ISSN : 2088-9984

𝑛

𝑥𝑗 ≥ 0, 𝑗 = 1,2, … , 𝑛

𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖

(12)

𝑗 =1

2.2 Untuk Hanya 𝒃𝒊 yang Variabel Acak

Harus dipenuhi dengan sebuah peluang dari setidaknya 𝑝𝑖 dimana 0 ≤ 𝑝𝑖 ≤ 1. Untuk penyederhanaan asumsikan bahwa variabel keputusan 𝑥𝑗 adalah deterministik. Akan dimisalkan kasus dimana hanya 𝑐𝑗 atau 𝑎𝑖𝑗 atau 𝑏𝑖 adalah variabel acak. Diasumsikan bahwa semua variabel acak adalah berdistribusi normal dengan mean dan standar deviasi diketahui.

Dengan menggunakan prinsip yang sama seperti kasus a, maka program stokastik linier pada persamaan 1 sampai 3 adalah sama dengan persoalan program linier deterministik di bawah ini: Minimize 𝑛

𝑓 𝑥 = 2.1 Untuk Hanya 𝒂𝒊𝒋 yang Variabel Acak

𝑛

Misalkan 𝑎𝑗 dan 𝑉𝑎𝑟 𝑎𝑖𝑗 = merupakan ratarata dan varians distribusi normal variabel acak 𝑎𝑖𝑗 , 𝑖 = 1,2, … 𝑚 ; 𝑗 = 1,2, . . 𝑛, juga diketahui dengan covarian, 𝐶𝑜𝑣(𝑎𝑖𝑗 , 𝑎𝑘𝑙 ) antara variabel acak 𝑎𝑖𝑗 dan 𝑎𝑘𝑙 . Definisikan 𝑑𝑖 sebagai

𝑎𝑖𝑗 𝑥𝑗 − 𝑏𝑖 − 𝑒𝑖 𝑉𝑎𝑟(𝑏𝑖 ) ≤ 0 𝑗 =1

Sementara persoalan program linier stokastik yang dinyatakan pada persamaan 1 sampai 3 dapat diperoleh dengan menyelesaikan persamaan program nonlinier deterministik berikut: Minimize

Karena 𝑎𝑖1, 𝑎𝑖2 , … , 𝑎𝑖𝑛 berdistribusi normal dan 𝑥1 , 𝑥2 , … , 𝑥𝑛 merupakan konstan, 𝑑𝑖 juga akan berdistribusi normal dengan nilai rata-rata 𝑛

𝑎𝑖𝑗 𝑥𝑗 , 𝑖 = 1,2, . . , 𝑛

6

𝑛

𝑐𝑗 𝑥𝑗 + 𝑘2 𝑋 𝑇 𝑉𝑋

𝑓 𝑥 = 𝑘1

𝑗 =1

Dengan kendala

𝑉𝑎𝑟 𝑑𝑖 = 𝜎𝑑2𝑖 = 𝑋 𝑇 𝑉𝑖 𝑋

(7)

𝑛 𝑗 =1 𝑎𝑖𝑗 𝑥𝑗

Dimana 𝑉𝑖 adalah matriks covarian ke-i, maka kendala dapat diperlihatkan sebagai 𝑃 𝑑𝑖 ≤ 𝑏𝑖 ≥ 𝑝𝑖 𝑑𝑖 − 𝑑𝑖 𝑉𝑎𝑟(𝑑𝑖 )

𝑏𝑖 − 𝑑𝑖

≤

𝑉𝑎𝑟(𝑑𝑖 )

𝑛

𝑉𝑎𝑟(𝑐𝑗 )𝑥𝑗2

𝑐𝑗 𝑥𝑗 + 𝑘2

(19)

𝑗 =1

3. Metode Penelitian Karena penelitian ini bersifat studi literatur jadi penulis mencoba mencari sebanyak mungkin bahanbahan dari buku ataupun penelitian-penelitian sebelumnya yang berhubungan dengan permasalahan dalam penelitian ini. Pada penulisan penelitian ini, penulis memakai metode dengan langkah-langkah sebagai berikut:

(10)

𝑗 =1

Dengan kendala + 𝑒𝑖 𝑋 𝑇 𝑉𝑖 𝑋 − 𝑏𝑖 ≤ 0

𝑛

𝑗 =1

𝑛

𝑛 𝑗 =1 𝑎𝑖𝑗 𝑥𝑗

(18)

(9)

Dimana 𝑑𝑖 − 𝑑𝑖 / 𝑉𝑎𝑟(𝑑𝑖 ) dapat dipandang sebagai sebuah variabel normal standar dengan rata-rata nol dan varian satu. Maka dengan menggunakan prinsip distribusi normal standar persoalan program stokastik yang ditunjukkan pada persamaan 2 dan 3 dapat diubah menjadi persoalan program deterministik berikut: Minimize 𝑐𝑗 𝑥𝑗

(17)

Jika semua variabel acak 𝑐𝑗 adalah saling bebas, maka fungsi objektif persamaan 16 direduksi menjadi

(8) ≥ 𝑝𝑖

− 𝑏𝑖 ≤ 0

𝑥𝑗 ≥ 0, 𝑗 = 1,2, … , 𝑛

𝑓 𝑥 = 𝑘1

𝑓 𝑥 =

(16)

𝑗 =1

Dan sebuah varian dari

𝑃

(15)

(5)

𝑗 =1

𝑑𝑖 =

𝑥𝑖 ≥ 0, 𝑗 = 1,2, … , 𝑛

(14)

2.3 Untuk hanya 𝒄𝒋 yang Variabel Acak

𝑛

𝑎𝑖𝑗 𝑥𝑗 , 𝑖 = 1,2, . . 𝑚

(13)

Dengan kendala

𝜎𝑖𝑗2

𝑑𝑖 =

𝑐𝑗 𝑥𝑗 𝑗 =1

(11) D-9

Seminar Nasional dan ExpoTeknik Elektro 2012 1. 2. 3.

ISSN : 2088-9984 berdistribusi normal, dengan distribusi kumulatif 𝜙(. ) dan transformasi invers nya 𝜙 −1 (. ). misalkan 𝜙 −1 𝛼 = 𝐾. Oleh karena itu, 𝑃 𝐾 ≥ 𝜉 = 𝛼. Adalah benar bahwa 𝑃(𝑥 ≥ 𝜉) ≥ 𝛼 jika dan hanya jika 𝑥 ≥ 𝐾. Dalam tulisan ini, dimisalkan bahwa trafik permintaan 𝜉 adalah berdistribusi normal dengan rata-rata (𝜇) dan varian 𝑥−𝜇 (𝜎 2 ). Dengan 𝑧, diperoleh 𝑃 𝜎 ≥ 𝑧 ≥ 𝛼 jika dan

Menentukan variabel-variabel yang berhubungan dengan pokok permasalahan. Mencari suatu model optimisasi dengan chance constrained programming. Menyelesaikan model yang diperoleh sehingga pada akhirnya diperoleh lintasan optimal dan alokasi bandwidth pada setiap link.

hanya jika berikut:

4. Hasil dan Pembahasan Pada bagian ini penulis akan membahas model matematika chance constrained programming untuk perencanaan jaringan dengan permintaan acak. Untuk menguji model yang ada penulis akan mencoba memakai model tersebut dalam menyelesaikan contoh permasalahan. Karena kesulitan dalam mengambil contoh kasus nyata, maka dalam tulisan ini penulis menggunakan contoh pemisalan saja. 4.1

Model Umum Telekomunikasi

CCP

Untuk

𝑃 𝑥𝑖 ≥ 𝜉𝑖 ≥ 𝛼𝑖 , ∀𝑖 = 1,2 … , 𝑁

21

4.2

(26)

Model Matematika Perencanaan Jaringan Dengan CCP

Akan dicoba mengembangkan sebuah model matematika programming didasarkan pada CCP. Misalkan penulis ingin menentukan jumlah bandwidth yang harus dialokasikan pada link 𝑗, asumsikan bahwa link tersebut membawa trafik permintaan 𝜉1 , … , 𝜉𝐾 , dengan masing-masing berdistribusi normal dengan ratarata 𝜇𝐾 dan varian 𝜎𝐾2 , 𝑘 = 1, … , 𝐾, masing-masing permintaan mempunyai tingkat jaminan tertentu (𝛼𝐾 ). Dengan kata lain, tiap trafik permintaan akan dijamin sebesar 𝛼𝐾 sepanjang lintasan dari sumber ke tujuan. Didasarkan pada persamaan 26 yang telah diperoleh, maka total bandwdith yang dialokasikan untuk menjamin semua trafik permintaan pada link tersebut dapat ditentukan sebagai berikut:

22

𝑥𝑖 ≥ 0, ∀𝑖 = 1,2, … , 𝑁 (23) Dimana 0 ≤ 𝛼𝑖 ≤ 1. Kendala 21 merupakan kendala peluang digunakan untuk memastikan bahwa kapasitas atau bandwidth yang dialokasikan pada link 𝑖 adalah lebih besar atau sama dengan sebuah parameter tak pasti 𝜉𝑖 untuk peluang setidaknya 𝛼𝑖 . Dengan kata lai, model tersebut memperbolehkan kendala tersebut dapat dilanggar sampai dengan sebuah batas peluang kurang dari (1 − 𝛼𝑖 ), hal ini dapat dimasukkan dalam model untuk memastikan permintaan acak dapat dibawa dengan sebuah tingkat jaminan sebesar 𝛼. Kendala dari persamaan 21, yakni: 𝑃 𝑥≥𝜉 ≥𝛼

(25)

𝑥 = 𝜇 + 𝜙 −1 𝛼 𝜎

Dengan kendala:

𝑥𝑖 ≤ 𝑏𝑖 , ∀𝑖 = 1,2, … , 𝑁

≥ 𝜙 −1 𝛼 , atau dapat dituliskan sebagai

Ini merupakan persamaan deterministik dari kendala peluang 24, persamaan ini dapat diartikan sebagai berikut. “Untuk menjamin bahwa link dapat membawa/mendukung permintaan acak setidaknya 100(𝛼)%, perlu ,mengalokasikan bandwidth setidaknya 𝜙 −1 𝛼 𝜎 diatas rata-rata (𝜇) dari permintaan”. Jadi minimal bandwidth yang harus dialokasikan pada sebuah link dengan tingkat jaminan 𝛼 adalah

Misalkan 𝑁 himpunan variabel acak, dinotasikan dengan 𝜉𝑖 . Misalkan 𝑥𝑖 merupakan variabel keputusan yang dihubungkan dengan biaya 𝑐𝑖 . Dalam konteks sebuah jaringan, 𝑥𝑖 dapat menunjukkan kapasitas atau bandwidth yang dialokasikan pada link 𝑖 dalam batas 𝑏𝑖 . Andaikan bahwa bandwidth tersebut dapat digunakan untuk membawa beberapa permintaan acak dengan beberapa nilai peluang tertentu, sebuah formulasi sederhana dari CCP yang diberikan oleh Koonlachat Meesublak [3]. Adalah sebagai berikut: Minimize (20)

𝜎

𝑥 ≥ 𝜇 + 𝜙 −1 𝛼 𝜎

Jaringan

𝑛 𝑖=1 𝑐𝑖 𝑥𝑖

𝑥−𝜇

𝐾

𝜇𝑘 + 𝜙 −1 𝛼𝑘 𝜎𝑘

𝑥𝑗 =

(27)

𝑘=1

Berikut contoh jumlah bandwidth yang harus dialokasikan untuk sebuah link sepasang node, dicari berdasarkan jaminan statistika yang dibahas dalam tulisan ini. Misalkan dari beberapa permintaan diperoleh rata-rata permintaan adalah 225 Mbps, dan nilain maksimum adalah 342 Mbps, sedangkan standar deviasinya adalah 25 Mbps.

(24)

Misalkan 𝛼 = 0.95, maka 𝜙 −1 0.95 = 1.645 Misal banyak trafik permintaan: 𝜉1 , … , 𝜉10 distribusi dan parameter yang sama

Dapat diubah ke dalam sebuah persamaan deterministik. Misalkan bahwa sebuah variabel acak 𝜉 D-10

dengan

Seminar Nasional dan ExpoTeknik Elektro 2012

ISSN : 2088-9984 𝑘,𝑝

𝑐𝑗 𝜇𝑘 + 𝜙 −1 𝛼𝑘 𝜎𝑘 𝛿𝑗 𝑓𝑘,𝑝

𝐾

𝑥𝑗 =

𝜇𝑘 + 𝜙

−1

(28)

𝑗𝜖𝐴 𝑘𝜖𝐷 𝑝𝜖 𝑝 𝑘

𝛼𝑘 𝜎𝑘

𝑘 =1

Dengan kendala:

= 10 𝑋 225 + 𝜙 −1 0.95 25 𝑋 10 = 2250 + 1.645 𝑋 25 𝑋 10 = 2250 + 411.25 = 2661.25

𝑘,𝑝

𝑐𝑗 𝜇𝑘 + 𝜙 −1 𝛼𝑘 𝜎𝑘 𝛿𝑗 𝑓𝑘 ,𝑝 ≤ 𝑊𝑗 , 𝑘𝜖𝐷 𝑝𝜖 𝑝 𝑘

Jadi dapat disimpulkan bahwa untuk menjamin kemampuan link tersebut untuk menanggung semua trafik permintaan tersebut, maka perlu dialokasikan bandwidth sebesar 2661.25 Mbps Koonlachat Meesublak [3] Memberikan suatu formulasi CCP untuk perencanaan jaringan dengan permintaan acak. Misalkan sebuah jaringan didefinisikan sebagai sebuah graph (𝑁, 𝐴) dimana 𝑁 merupakan himpunan dari node, dan 𝐴 merupakan himpunan dari link. Notasi yang digunakan adalah sebagai berikut:  𝐷 menunjukkan kumpulan trafik permintaan dari titikke-titik. Dengan masing-masing rata-rata 𝜇 dan varian 𝜎𝑘2  𝑝𝑘 menunjukkan himpunan calon lintasan dari permintaan 𝑘𝜖𝐷  𝑐𝑗 menunjukkan biaya per unit bandwidth pada link 𝑗𝜖𝐴  𝛼𝑘 menunjukkan tingkat jaminan untuk permintaan 𝑘𝜖𝐷.  𝑤𝑗 menunjukkan batas bandwidth yang diperbolehkan pada link 𝑗𝜖𝐴.  𝑓𝑘 ,𝑝 menunjukkan variabel keputusan, dimana sama dengan 1 jika aliran dari permintaan 𝑘 memilih lintasan 𝑝 dari himpunan calon lintasan 𝑝𝑘 , dan 0 untuk lainnya. 𝑘,𝑝  𝛿𝑗 merupakan sebuah parameter biner. Sama dengan 1 jika lintasan 𝑝𝜖𝑝𝑘 untuk permintaan 𝑘 menggunakan 𝑘,𝑝 link 𝑗, dan 0 untuk lainnya. Perhatikan bahwa 𝛿𝑗 ditentukan ketika himpunan calon lintasan 𝑝𝑘 dicari.

∀𝑗 𝜖𝐴

𝑓𝑘,𝑝 = 1, ∀𝑗 𝜖𝐷

29

(30)

𝑝𝜖 𝑝 𝑘

𝑓𝑘 ,𝑝 𝜖 0, 1

(31)

Kendala 29 memastikan bahwa jumlah dari kapasitas bandwidth yang dialokasikan pada link 𝑗 tidak melebihi dari batas 𝑊𝑗 , yang merupakan batas atas dari bandwidth pada link tersebut yang ditentukan oleh manajemen jaringan atau kapasitas fisik link. Kendala 30 memaksa permintaan 𝑘 akan dirutekan pada lintasan tunggal untuk mempertahankan integritas aliran. Contoh 1.

Gambar 1. Jaringan dengan topologi mesh mempunyai 6 node dan 9 link terhubung

Diketahui sebuah jaringan dengan topologi seperti di atas mempunyai 6 node serta 9 link terhubung langsung. Dari jaringan di atas akan dicoba mencari lintasanlintasan terbaik untuk setiap permintaan yang diketahui di bawah ini sehingga diperoleh pengalokasian bandwidth optimal pada tiap link.

Tujuan dari model ini adalah untuk menentukan lintasan optimal atau dalam model ini himpunan terbaik dari 𝑓𝑘 ,𝑝 sehingga total biaya jaringan berupa total pengalokasian bandwidth minimal. Masukan ke dalam model ini mengandung parameter-parameter : Topologi jaringan, sebuah himpunan dari trafik permintaan acak dengan informasi probabilistik (rata-rata dan varian), parameter biaya, dan tingkat jaminan dari masing-masing permintaan. Sedangkan hasil keluaran dari model ini adalah pemilihan lintasan optimal dengan batas yang tidak pasti,bandwidth} yang dibutuhkan dalam setiap link, dan biaya optimal. Dengan notasi di atas, biaya minimum dari perencanaan jaringan dengan permintaan acak dapat diformulasikan sebagai berikut. Minimize

Himpunan trafik permintaan dari titik-ke-titik (𝐷): 𝑘1 : 1 ⟺ 6 dengan 𝜇1 = 45 dan 𝜎12 = 36 𝑘2 : 1 ⟺ 5 dengan 𝜇2 = 40 dan 𝜎22 = 25 𝑘3 : 1 ⟺ 4 dengan 𝜇3 = 35 dan 𝜎32 = 16 𝑘4 : 2 ⟺ 6 dengan 𝜇4 = 30 dan 𝜎42 = 16 𝑘5 : 2 ⟺ 5 dengan 𝜇5 = 42 dan 𝜎52 = 36 𝑘6 : 3 ⟺ 6 dengan 𝜇6 = 50 dan 𝜎62 = 49 Setiap permintaan di atas menunjukkan trafik permintaan acak timbal-balik dari sepasang node dalam hal ini penulis memisalkan bahwa sepasang node akan D-11

Seminar Nasional dan ExpoTeknik Elektro 2012

ISSN : 2088-9984

menggunakan lintasan tunggal. Misalkan untuk setiap trafik permintaan titik-ke-titik berlaku:  Tingkat jaminan 𝛼𝑘 setiap trafik permintaan acak tersebut adalah 0.99  Satuan biaya bandwidth Rp. 1 /Mbps pada semua link  Besar batas bandwidth 𝑊𝑗 yang diperbolehkan untuk setiap link adalah 130 Mbps

lintasan pada model ini adalah kapasitas bandwidth. Akan tetapi juga dapat dilihat bahwa model ini juga selalu berusaha mencari lintasan terbaik dengan kapasitas bandwidth yang memadai serta lintasan dengan jarak terpendek karena pada model yang menjadi tujuan adalah meminimalkan pengalokasian bandwidth, karena lintasan dengan jarak terpendek secara otomatis menunjukkan alokasi bandwidth terkecil(lebih sedikit link yang menanggung trafik permintaan tersebut).

𝑝𝑘 : Himpunan calon lintasan untuk trafik permintaan 𝑘𝜖𝐷, syarat pemilihan calon lintasan: 1. Maksimum Hop/node = 4. 2. Tidak terjadi loop. Ini berarti bahwa dalam lintasan tidak akan terjadi satu paket data melewati sebuah node lebih dari satu kali.

5. Kesimpulan Dari hasil penelitian ini dapat dilihat bahwa Chance Constrained Programming dapat menjadi salah satu model pendekatan untuk penghematan pengalokasian bandwidth dalam jaringan dengan kondisi ketidakpastian trafik permintaan. Chance Constrained Programming yang dipakai dalam model ini dapat langsung memasukkan ketidakpastian permintaan kedalam masalah perencanaan jaringan.

Untuk 𝑘 = 1 𝑃1 : 𝑗2 → 𝑗6 → 𝑗9 𝑃2 : 𝑗2 → 𝑗5 → 𝑗8 𝑃3 : 𝑗2 → 𝑗6 → 𝑗7 → 𝑗8 𝑃4 : 𝑗2 → 𝑗5 → 𝑗7 → 𝑗9 𝑃5 : 𝑗2 → 𝑗4 → 𝑗3 → 𝑗8 𝑃6 : 𝑗1 → 𝑗3 → 𝑗8 𝑃7 : 𝑗1 → 𝑗3 → 𝑗7 → 𝑗9 𝑃8 : 𝑗1 → 𝑗4 → 𝑗6 → 𝑗9 𝑃9 : 𝑗1 → 𝑗4 → 𝑗5 → 𝑗8

REFERENSI [1] Kilpi, J dan I. Norros. 2002. Testing the Gaussian approximation of aggregate traffic. In Proc. Internet Measurement Workshop, pages 49-61. [2] Liu, B. 2009. Theory and Practise of Uncertain Programming. Third Edition. Tsinghua University Beijing 100084, China. UTLAB. [3] Meesublak, Koonlachat. 2008. 12 Januari 2012. Network Design under Demand Uncertainty. http://www.apan.net/meetings/newzealand2008/pres entations/\\ nrw/Koonlachat.pdf. [4] Rao, S.S. 1977. Optimization : theory and application, Edisi kedua, Deptt. Of mechanical Engg. San Diego State University. San Diego. USA.

Untuk 𝑘 = 2 𝑃10 : 𝑗2 → 𝑗6 𝑃11 : 𝑗2 → 𝑗5 → 𝑗7 𝑃12 : 𝑗2 → 𝑗4 → 𝑗3 → 𝑗7 𝑃13 : 𝑗1 → 𝑗3 → 𝑗7 𝑃14 : 𝑗1 → 𝑗4 → 𝑗6 𝑃15 : 𝑗1 → 𝑗4 → 𝑗5 → 𝑗7 𝑃16 : 𝑗1 → 𝑗3 → 𝑗5 → 𝑗6 Dan seterusnya sampai 𝑘 = 6 Model matematik di atas penulis selesaikan dengan menggunakan program LINDO dan diperoleh hasil sebagai berikut: Kumpulan lintasan terbaik/optimal yaitu:      

Lintasan 𝑃2 : 𝑗2 → 𝑗5 → 𝑗8 untuk trafik permintaan 𝑘1 Lintasan 𝑃10 : 𝑗2 → 𝑗6 untuk trafik permintaan 𝑘2 Lintasan 𝑃17 : 𝑗1 → 𝑗3 untuk trafik permintaan 𝑘3 Lintasan 𝑃25 : 𝑗4 → 𝑗5 → 𝑗8 untuk trafik permintaan 𝑘4 Lintasan 𝑃30 : 𝑗3 → 𝑗7 untuk trafik permintaan 𝑘5 Lintasan 𝑃37 : 𝑗6 → 𝑗9 untuk trafik permintaan 𝑘6

Dari kumpulan lintasan optimal di atas dapat dilihat bahwa lintasan dengan jarak terpendek (jumlah node paling sedikit) tidak secara langsung menjadi lintasan terbaik untuk suatu trafik permintaan. Seperti pada $𝑘 = 4 yang dirutekan dengan menggunakan lintasan 𝑃25 sementara terdapat 𝑃23 yang lebih pendek. Hal ini karena parameter utama yang menjadi ukuran dalam pemilihan D-12