BAB 2 TINJAUAN PUSTAKA
Bagian ini menjelaskan tentang hal-hal yang erat kaitannya dengan masalah mring star. Salah satu cabang matematika yang cukup penting dan sangat luas penerapannya di banyak bidang ilmu adalah Teori Graph. Salah satunya adalah bidang jaringan telekomunikasi. Digunakan graph gabungan, dimana titik transisi dan pusat depot diasosiasikan dengan node, sementara sambungan antara node adalah edge atau arc berbobot. Berikut akan dijelaskan mengenai teori dasar graph yang akan digunakan untuk mendesain m-ring star.
2.1 Graph Suatu graph terdiri dari dua bilangan yaitu titik dan garis. Titik pada suatu graph disebut verteks dan garis yang menghubungkan dua titik disebut edge atau arc (untuk garis berarah). Secara formal suatu graph G didefinisikan sebagai berikut: Sebuah graf terdiri dari dua bagian, yaitu sebagai berikut. 1. Sebuah himpunan V = V (G) memiliki elemen-elemen yang dinamakan verteks, titik, atau simpul. 2. Sebuah kumpulan E = E(G) merupakan pasangan terurut dari verteks-verteks yang berbeda dinamakan sisi atau edge. 2.1.1 Graph sederhana Graph yang tidak mempunyai parallel edges atau edge ganda dan atau loop dinamakan graph sederhana atau simple graph. Contoh graph sederhana dapat dilihat pada Gambar 2.1 berikut ini.
5 Universitas Sumatera Utara
6
Gambar 2.1 Simple graph 2.1.2 Graph tak sederhana Graph yang mempunyai edge ganda dan atau loop dinamakan graph tak sederhana atau unsimple graph.
Gambar 2.2 Graph tidak sederhana 2.1.3 Graph berbobot Graph berbobot atau graph berlabel adalah graph yang setiap edgenya diberi sebuah nilai (bobot). Bobot pada tiap edge dapat menyatakan biaya transportasi dari suatu kota ke kota lainnya atau jarak antara dua tempat atau waktu tempuh antara dua tempat dan lain-lainnya. Berikut ini adalah contoh graph berbobot
Gambar 2.3 Graph berbobot
Universitas Sumatera Utara
7 Sebuah multigraf G = G(V, E) terdiri dari suatu himpunan V (verteks) dan suatu himpunan E (edge), kecuali E mengandung edge ganda, yaitu beberapa edge yang menghubungkan titik-titik ujung yang sama. E mungkin mengandung satu atau lebih loop, yaitu sebuah edge yang titik-titik ujungnya adalah verteks yang sama.
Gambar 2.4 Sebuah multigraf dengan tiga simpul dan lima edge Pada Gambar 2.4 , G adalah graf dengan: V = {P, Q, R} E = {(P, Q), (P, Q), (P, R), (R, R), (Q, R)} = {e1, e2 , e3, e4, e5} G mengandung edge ganda, e1 dan e2, yang menghubungkan dua verteks yang sama, yaitu P dan Q. G juga mengandung sebuah loop e4, yang titik-titik ujungnya sama, yaitu verteks R. Karena itu, graf di atas merupakan multigraf. Berdasarkan pada orientasi arah pada edge, maka secara umum graf dapat dibedakan atas 2 jenis sebagai berikut.
1. Graf tak berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah. Gambar 2.4 merupakan gambar graf tak berarah. 2. Graf berarah (directed graph atau digraph) Graf yang sisinya mempunyai orientasi arah. Gambar 2.5 merupakan gambar graf berarah.
Universitas Sumatera Utara
8
Gambar 2.5 Graf berarah M-ring star mendesain: 1. Susunan titik yang tidak teratur sebanyak m melewati pusat depot dan beberapa node lainnya. 2. Sekumpulan koneksi langsung dari pelanggan yang belum dikunjungi ke sebuah node dengan sebuah ring. Jumlah pelanggan yang dihubungkan ke ring akan dibatasi oleh Q (kapasitas dari ring). Tujuannya adalah meminimalkan biaya ring dan biaya koneksi pelanggan (min : cost ring + cost customer ). Berikut adalah beberapa contoh struktur m-ring star :
Struktur 1
Universitas Sumatera Utara
9
Struktur 2 Lebih jelasnya mRSK adalah sebagai berikut : misalkan gabungan graph G = 0
(V, E ∪ A) dimana V = 0, n + 1 ∪ V adalah sekumpulan node, E = {(i, j) : i, j ∈ V, i 6= j} adalah sekumpulan edge dan A adalah sekumpulan arc. Kumpulan node V
0
terbagi atas dua subset : U berisi node untuk setiap pelanggan dan W berisi node untuk titik transit (disebut juga Steiner node). Node 0 mewakili depot dan node n + 1 0
merupakan terminal. Untuk setiap pelanggan i ∈U misal Ci ⊂ V adalah himpunan bagian dari node, dimana pelanggan i bisa terhubung. Diasumsikan bahwa i ∈ Ci untuk semua pelanggan i ∈ U dan pelanggan itu akan terhubung dengan sendirinya jika ia berada didalam ring. Susunan A mewakili koneksi yang mungkin antara satu node dengan pelanggan yakni A = {(i, j) : i ∈ U, j ∈ Ci }. Susunan E adalah susunan yang mungkin dari edge ring. Setiap edge e = {i, j} ∈ E dihubungkan dengan biaya rute yang tidak negatif ce = cij , dimana (i, j) ∈ A dihubungkan dengan biaya koneksi yang tidak negatif (dengan dii = 0 untuk semua i ∈ U ). Diberikan sebuah himpunan 0
0
bagian E ⊂ E, V (E ) ditandai sebagai susunan titik untuk paling tidak satu edge pada 0
E . Dapat dikatakan bahwa pelanggan i ditempatkan untuk sebuah ring R apabila 0
dihubungkan oleh rute simple (yakni i ∈ V (E )) atau dihubungkan dengan sebuah 0
node dari ring (yakni ada sebuah edge j sehingga (i, j) ∈ A ). Ring sangat menguntungkan bila pelanggan yang terdaftar tidak melebihi kapasitas (Q) 100 kabel dapat melayani 50 pelanggan jumlah total dari titik pelanggan terkunjung atau yang dihubungkan ke ring terbatas (≤ Q). Biaya R adalah jumlah dari biaya rute dari garis di E ditambah jumlah biaya dari koneksi yang ada di ring A. Jumlah ring sebesar m dalam jaringan diketahui dan diberikan sebagai nilai input.
Universitas Sumatera Utara
10 Gambar 2.6 menunjukkan solusi dari mRSK yang sesuai dimana n = 25 dan m = 3.|U | = 12, |W | = 13 dan Q = 6. Dari gambar tersebut titik transisi dilambangkan dengan lingkaran dan pelanggan dengan segitiga, pusat depot dilambangkan dengan dua persegi hitam, garis yang tidak putus dilambangkan untuk garis rute dan garis putus-putus sebagai koneksi.
Gambar 2.6 m-Ring star berkapasitas
2.2 Formulasi Matematika Formulasi matematika untuk m-RSK dalam tesis ini digunakan formulasi dua arus komoditas. Formulasi dua arus komoditas m-RSK menggunakan model graph yang mengasosiasikan setiap edge {i, j} ∈ E dengan dua arc yang berlawanan dan dengan dua variabel arus yang bersesuaian yij dan yji . Kedua Arc mempunyai biaya yang sama cij ditetapkan bahwa dalam penyelesaian m-RSK layak total arus pada setiap edge dari ring tepat sama dengan Q. Variabel y mengidenti?kasi setiap ring melalui dua path arus. Pada path pertama yang bergerak dari node 0 ke node n + 1, arus yij menyatakan jumlah pemakai yang dilayani oleh ring setelah mengunjungi node i. Pada path yang berlawanan yang bergerak dari node n + 1 ke node 0, variable yij menyatakan jumlah potensial pelanggan yang dapat dilayani pada path maju dari 0 ke j. Dengan demikian
Universitas Sumatera Utara
11 total arus yang keluar dari node n + 1 sama dengan mQ. Setiap node pada ring yang mempunyai v pelanggan yang dialokasikan menyerap v unit aliran yang datang dari node 0 dan unit aliran yang datang dari node n + 1. Pada gambar 2.7 diperlihatkan lima pelanggan ring dalam gambar 2.6 dan kedua path arus (0, 22, 24, 17, 11, n + 1) dan (n + 1, 11, 17, 24, 22, 0). Gambar 2.7 : m-Ring Star Berkapasitas dengan 5 pelanggan
min
X 1 X cij (yij + yji ) + dij Zij Q {i,j}∈E
(i,j)∈A
s.t
X
y0j = |U |
(2.2)
yn+1j = mQ
(2.3)
j∈V
X j∈V
yj,n+1 = 0
(2.4)
y0j = mQ − |U |
(2.5)
j∈V
X j∈V
0
0
X
X
(2.1)
0
0
(yji + yij ) = 2Qzjj ,
j∈U
(2.6)
j∈V
X
(yji + yij ) = 2QWj , ∀J ∈ w
(2.7)
j∈V
X
zij = 1,
∀i ∈ U
(2.8)
j∈V
X j∈V
=2
X
Zij
∀J ∈ V
(2.9)
i∈U
yij + yji ∈ {0, Q} ∀{i, j} ∈ E yij ≥ 0,
∀i, j ∈ V
zij ∈ {0, 1} wi ∈ {0, 1}
(2.10) (2.11)
∀(i, j) ∈ A
(2.12)
j∈W
(2.13)
Universitas Sumatera Utara
12 Formulasi dua arus komoditas m-RSK adalah sebagai berikut : Persamaan (2.3) menetapkan bahwa arus keluar node 0 sama dengan jumlah pelanggan, sementara persamaan (2.4) menetapkan bahwa arus keluar pada node n + 1 sama dengan total kapasitas dari ke m ring. Persamaan (2.5) mengindikasikan bahwa tidak ada arus masuk node n + 1 sementara persamaan (2.6) menetapkan bahwa arus yang masuk node 0 sama dengan kapasitas residual ring. Diharuskan bahwa Q unit arus melalui setiap edge pada ring, maka untuk setiap node ring total arus yang masuk dan keluar dari node haruslah sama dengan 2Q. Ini ditetapkan oleh persamaan (2.7) dan (2.8). Persamaan (2.9) menjamin bahwa setiap pelanggan dialokasikan kepada satu node.Persamaan (2.10) adalah batasan konservasi arus yang memperhitungkan bahwa setiap pelanggan menerima satu unit arus dari node 0 dan satu unit arus dari node n + 1. Batasan (2.11) menetapkan persyaratan biner bahwa edge e = {i, j} ∈ E haruslah dikunjungi atau tidak oleh ring, yang dengan demikian menjelaskan fungsi tujuan (2.2).
2.3 Vehicle Routing Problem Vehicle Routing Problem (VRP) merupakan persoalan mRSK karena melibatkan banyaknya pelanggan dengan permintaan tertentu yang dilayani oleh satu atau beberapa pusat jaringan. VRP pertama kali dipaparkan oleh Dantzig dan Ramser (1954). VRP adalah permasalahan kompleks dari optimisasi kombinatorial, yang merupakan gabungan dari dua permasalahan, yaitu Travelling Salesman Problem (TSP) dan Bin Packing Problem (BPP). VRP merupakan NP-Hard, sehingga permasalahan ini sulit dipecahkan. VRP berhubungan dengan pengiriman dan/atau pengambilan barang. Masalah kritis VRP adalah rute dan pengaturan kendaraan pengangkut yang ada sehingga dapat melayani permintaan pelanggan seefisien mungkin berdasarkan pada kriteriakriteria yang ada. Sebuah rute adalah serangkaian lokasi yang harus dikunjungi kendaraan pengangkut untuk menyelesaikan pelayanannya, misalnya pelayanan pengiriman barang. Penyelesaian VRP menghasilkan rute, dan dapat juga menghasilkan penjadwalan kendaraan-kendaraan pengangkut dalam rute yang terbentuk.
Universitas Sumatera Utara
13 VRP adalah generalisasi dari TSP. Maka, TSP adalah sebuah VRP tanpa batasan seperti depot, pelanggan dan permintaan. M-TSP adalah VRP dengan sebuah depot dan m kendaraan pengangkut, termasuk bila tidak ada permintaan dari pelanggan. MTSP adalah transformasi dari TSP dengan memperbanyak jumlah depot. Pada kenyataannya, Vehicle Routing digambarkan dengan jaringan jalan, yang kemudian dituangkan dalam sebuah graf, baik graf berarah G = (V, A), graf tidak berarah G = (V, E), maupun graf campuran G = (V, A ∪ E). Penggunaan bentuk graf ini disesuaikan dengan daerah yang akan dikunjungi kendaraan pengangkut. Graf tak berarah digunakan jaringan jalan skala besar, meliputi negara dan negara bagian atau propinsi. Sedangkan graf berarah digunakan untuk jaringan jalan skala kecil, misal untuk menggambarkan jalan-jalan dalam satu kota. Verteks menggambarkan depot, pelanggan ataupun persimpangan jalan. Himpunan verteks dilambangkan dengan V = (v0, . . . , vn ). Verteks v0 mewakili pusat, di mana terdapat kendaraan pengangkut identik sejumlah k dengan kapasitas Q. Sedangkan verteks lainnya melambangkan kota atau pelanggan, yang memiliki permintaan di . Arc atau edge menggambarkan jalan-jalan yang ada. Edge dapat bersifat berarah (i, j) ∈ A, di mana A = {(v1, vj ) : i 6= j, v1 , vj ∈ V } dan tidak berarah, ` ∈ E. Biaya dan jarak perjalanan dilambangkan oleh cij , yang didefinisikan pada A, sedangkan waktu non-negatif dilambangkan oleh tij , yang juga didefinisikan pada A. Setiap verteks vi dalam V diasosiasikan dengan sejumlah barang qi yang akan diantarkan oleh satu kendaraan. V RP bertujuan untuk menentukan sejumlah k rute kendaraan dengan total biaya yang minimum, bermula dan berakhir di sebuah depot. Adapun setiap verteks dalam V dikunjungi tepat sekali oleh satu kendaraan. Jadi, P biaya dari solusi masalah ini adalah FV RP (S) = ki C(Ri )
Universitas Sumatera Utara
14
Gambar 2.7 Contoh Visualisasi Input dari Vehicle Routing Problem (sumber: Massimo Paolucci, 2001, p5)
Gambar 2.8 Salah satu output dari persoalan VRP dari input gambar 2.7 (sumber: Massimo Paolucci, 2001, p5)
Dalam tesis ini, penyelesaian VRP akan digunakan teknik Metaheuristik yaitu Variable Neighborhood Search (VNS).
Universitas Sumatera Utara
