PENYELESAIAN MASALAH GENERALIZED MINIMUM SPANNING TREE DENGAN METODE HEURISTIK LOCAL SEARCH
ALETHEA NOER
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
PERNYATAAN SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Penyelesaian Masalah Generalized Minimum Spanning Tree dengan Metode Heuristik Local Search adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, November 2014 Alethea Noer NIM G54100044
ABSTRAK ALETHEA NOER. Penyelesaian Masalah Generalized Minimum Spanning Tree dengan Metode Heuristik Local Search. Dibimbing oleh FARIDA HANUM dan PRAPTO TRI SUPRIYO. Generalized minimum spanning tree (GMST) merupakan minimum spanning tree dari suatu graf dengan simpul-simpulnya terbagi menjadi beberapa kumpulan simpul yang disebut cluster. GMST dapat diselesaikan menggunakan metode heuristik local search yang dalam langkah-langkah penyelesaian juga memerlukan algoritme Prim untuk menentukan minimum spanning tree. Dalam karya ilmiah ini masalah GMST diaplikasikan pada masalah penentuan lokasi gardu-gardu induk listrik di setiap kecamatan di Kota Palangkaraya. Setiap kecamatan memiliki beberapa kelurahan yang akan ditentukan sebagai lokasi pemasangan gardu induk listrik sehingga panjang kabel listrik yang digunakan adalah minimum. Kata kunci: generalized minimum spanning tree, jarak minimum, local search.
ABSTRACT ALETHEA NOER. The Solution of the Generalized Minimum Spanning Tree Problem with Local Search Heuristic Method. Supervised by FARIDA HANUM and PRAPTO TRI SUPRIYO. Generalized minimum spanning tree (GMST) is a minimum spanning tree of a graph with the nodes partitioned into some node-sets called cluster. GMST can be solved by using local search heuristic method which includes Prim algorithm in their steps to determine the minimum spanning tree. In this paper GMST problem is applied to the problem of determining the location of the primary electricity substations in every district in Palangkaraya. In each district, it will be decided a few number of villages as the location for the installation of electricity substations such that minimized the cable length. Keywords: generalized minimum spanning tree, minimum distance, local search.
PENYELESAIAN MASALAH GENERALIZED MINIMUM SPANNING TREE DENGAN METODE HEURISTIK LOCAL SEARCH
ALETHEA NOER
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
Judul Skripsi : Penyelesaian Masalah Generalized Minimum Spanning Tree dengan Metode Heuristik Local Search Nama : Alethea Noer NIM : G54100044
Disetujui oleh
Dra Farida Hanum, MSi Pembimbing I
Drs Prapto Tri Supriyo, MKom Pembimbing II
Diketahui oleh
Dr Toni Bakhtiar, MSc Ketua Departemen
Tanggal Lulus:
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Penyusunan karya ilmiah ini tidak lepas dari peranan berbagai pihak. Untuk itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada: 1 keluarga tercinta: ibu dan bapak yang telah mendoakan dan memberikan motivasi, untuk saudara-saudaraku da Alvi, Auly, dan Ainun yang selalu mendoakan dan memberikan semangat, 2 Dra Farida Hanum, MSi selaku dosen pembimbimg I yang selalu sabar dalam membimbing, memberi motivasi, semangat dan doa, 3 Drs Prapto Tri Supriyo, MKom selaku dosen pembimbing II yang telah memberikan ilmu, kritik dan saran, motivasi serta doanya, 4 Drs Siswandi, MSi selaku dosen penguji yang telah memberikan kritik dan saran serta doanya 5 semua dosen Departemen Matematika, terima kasih atas semua ilmu yang telah diberikan, semua staf Departemen Matematika, terima kasih atas bantuan yang telah 6 diberikan selama ini, 7 Bidik Misi yang telah membiayai perkuliahan selama 4 tahun, 8 semua teman Matematika 47 yang telah menjadi keluarga selama di Bogor, semua teman Matematika yang selalu mendukung agar terus berkembang, 9 10 Gumatika yang telah memberikan banyak pengalaman yang berkesan, 11 semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Semoga karya ilmiah ini bermanfaat bagi dunia ilmu pengetahuan khususnya bidang matematika dan menjadi inspirasi bagi penelitian selanjutnya.
Bogor, November 2014 Alethea Noer
DAFTAR ISI DAFTAR GAMBAR
vi
DAFTAR LAMPIRAN
vi
PENDAHULUAN
1
Latar Belakang
1
Tujuan Penelitian
1
TINJAUAN PUSTAKA Konsep-konsep dalam Teori Graf GENERALIZED MINIMUM SPANNING TREE (GMST)
1 2 3
Penentuan Minimum Spanning Tree dengan Algoritme Prim
3
Penyelesaian GMST
4
Batas Bawah untuk GMST
5
Batas Atas untuk GMST
5
APLIKASI
5
Penentuan Batas Bawah dan Batas Atas GMST
7
Penyelesaian GMST dengan Metode Heuristik Local Search
8
SIMPULAN DAN SARAN
16
Simpulan
16
Saran
16
DAFTAR PUSTAKA
16
LAMPIRAN
18
RIWAYAT HIDUP
25
DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Contoh solusi fisibel untuk GMST Peta Kota Palangkaraya Graf kasus Palangkaraya Graf tak terhubung T Spanning tree untuk batas bawah GMST Spanning tree untuk batas atas GMST Subgraf yang terbentuk dari simpul yang telah dipilih pada iterasi 1 MST pada kunjungan ke-1 MST pada kunjungan ke-2 MST pada kunjungan ke-3 MST pada kunjungan ke-4 MST pada kunjungan ke-5 Subgraf yang terbentuk dari simpul yang telah dipilih pada iterasi 2 MST pada kunjungan ke-1 MST pada kunjungan ke-2 MST pada kunjungan ke-3 MST pada kunjungan ke-5 Subgraf yang terbentuk dari simpul yang telah dipilih pada iterasi 3 MST pada kunjungan ke-1 MST pada kunjungan ke-2 MST pada kunjungan ke-3
4 5 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15
DAFTAR LAMPIRAN 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Data jarak antar kelurahan Langkah penentuan MST dengan adaptasi algoritme Prim Urutan jarak terkecil sampai terbesar Langkah penentuan MST dengan algoritme Prim pada iterasi 1 Perhitungan kunjungan 1 (cluster C1) pada iterasi 1 Perhitungan kunjungan 2 (cluster C2) pada iterasi 1 Perhitungan kunjungan 3 (cluster C3) pada iterasi 1 Perhitungan kunjungan 4 (cluster C4) pada iterasi 1 Perhitungan kunjungan 5 (cluster C5) pada iterasi 1 Langkah penentuan MST dengan algoritme Prim pada iterasi 2 Perhitungan kunjungan 1 (cluster C1) pada iterasi 2 Perhitungan kunjungan 2 (cluster C2) pada iterasi 2 Perhitungan kunjungan 3 (cluster C3) pada iterasi 2 Perhitungan kunjungan 4 (cluster C4) pada iterasi 2 Perhitungan kunjungan 5 (cluster C5) pada iterasi 2 Langkah penentuan MST dengan algoritme Prim pada iterasi 3 Perhitungan kunjungan 1 (cluster C1) pada iterasi 3 Perhitungan kunjungan 2 (cluster C2) pada iterasi 3 Perhitungan kunjungan 3 (cluster C3) pada iterasi 3 Perhitungan kunjungan 4 (cluster C4) pada iterasi 3 Perhitungan kunjungan 5 (cluster C5) pada iterasi 3
19 20 21 22 22 22 22 22 23 23 23 23 23 23 24 24 24 24 24 24 25
PENDAHULUAN Latar Belakang Listrik memegang peranan yang penting dalam kehidupan. Dapat dikatakan bahwa listrik telah menjadi sumber energi utama dalam setiap kegiatan, namun masih banyak daerah-daerah di Indonesia yang belum teraliri listrik. Hal ini disebabkan oleh belum dibangunnya gardu induk listrik di daerah tersebut. Salah satu kendala dalam pembangunan gardu induk listrik ialah besarnya biaya yang dikeluarkan. Dengan menerapkan teori graf dan pohon merentang minimum (minimum spanning tree) maka akan diperoleh jaringan listrik sehingga biaya yang dikeluarkan bisa diminimalkan. Permasalahan penentuan lokasi gardu induk listrik ini dapat dimodelkan menjadi generalized minimum spanning tree (GMST). Dalam karya ilmiah ini, GMST akan diselesaikan menggunakan metode heuristik yaitu metode heuristik local search. Sumber utama karya ilmiah ini ialah artikel yang berjudul Heuristic search for the generalized minimum spanning tree problem yang disusun oleh Bruce Golden dan kawan-kawan pada tahun 2005.
Tujuan Penelitian Tujuan penulisan karya ilmiah ini ialah menyelesaikan masalah generalized minimum spanning tree dengan metode heuristik local search dan mengaplikasikannya pada masalah penentuan lokasi gardu induk listrik di Kota Palangkaraya.
TINJAUAN PUSTAKA Suatu generalized minimum spanning tree (GMST) adalah minimum spanning tree (MST) dari graf G = (V, E) dengan simpul-simpulnya terbagi menjadi m kumpulan simpul yang disebut cluster. Misalkan banyaknya elemen himpunan V adalah |V| = n dan K = 1, 2, ... , m adalah indeks dari cluster, dengan ... Vm dan Vl Vk = untuk setiap l,k K dan l k. V = V1 V2 Diasumsikan sisi didefinisikan hanya antara simpul-simpul di cluster yang berbeda dan tiap sisi memiliki bobot taknegatif (Pop 2002). Cluster adalah hasil pengelompokan sekumpulan objek sehingga berada dalam satu kelompok yang sama. Feremans et al. (2002) menjelaskan delapan perbedaan formulasi integer programing (IP) dan mixed integer programming (MIP) untuk masalah GMST dan menunjukkan bahwa empat dari formulasi ini erat mendominasi empat lainnya dalam hal kualitas relaksasi linear. Raghavan (2002) menunjukkan bahwa GMST dapat dimodelkan sebagai Steiner tree problem dengan kendala degree pada beberapa simpul. Steiner menunjukkan bahwa formulasi yang dihasilkan setara (dalam hal relaksasi linear) dengan keempat formulasi yang diidentifikasikan oleh Feremans. Dror et al. (2000) membahas variasi yang agak
2 berbeda untuk GMST. Cluster tidak perlu terpisah satu sama lain tapi secara kolektif. Selanjutnya, daripada harus tepat satu simpul dari cluster dalam tree yang diinginkan, mereka mengharuskan setidaknya satu simpul dari setiap cluster yang berada pada tree (dengan demikian memungkinkan beberapa simpul dari cluster yang sama berada dalam tree). Salah satu aplikasi masalah GMST pertama kali diperkenalkan oleh Myung et al. (1995). Dalam aplikasi ini, beberapa local area network (LAN) di suatu daerah harus terhubung satu sama lain dan membentuk MST. Selain itu, GMST dapat diterapkan ke dalam masalah jaringan telekomunikasi. Berikut ini akan dijelaskan beberapa konsep-konsep dalam teori graf. Konsep-konsep dalam Teori Graf Definisi 1 (Graf) Suatu graf G adalah pasangan terurut (V,E) dengan V, biasa ditulis V(G), adalah himpunan berhingga dan takkososng dari elemen-elemen graf yang disebut verteks (node, simpul), sedangkan E, biasa ditulis E(G), ialah himpunan pasangan yang menghubungkan dua elemen subset dari V yang disebut sisi (edge). Setiap sisi {u,v} pada V biasanya dinotasikan dengan uv atau vu (Chartrand & Zhang 2009). Definisi 2 (adjacent dan incident) Misalkan u dan v verteks pada graf G. Verteks v dikatakan tetangga (adjacent) dari u jika ada sisi e yang menghubungkan verteks u dan v, yaitu e = uv. Himpunan semua tetangga dari verteks v dinotasikan dengan N(v). Jika e = uv adalah sisi pada graf G maka e dikatakan incident dengan verteks u dan v (Chartrand & Zhang 2009). Definisi 3 (Graf berbobot) Suatu graf G = (V, E) dikatakan berbobot jika terdapat sebuah fungsi w : E → R (dengan R adalah himpunan bilangan real) yang disebut bobot. Setiap bobot w(uv) dengan uv E dinotasikan dengan w(uv) (Foulds 1992). Definisi 4 (Subgraf) Graf H adalah subgraf dari graf G jika V(H) (Chartrand & Oellermann 1993).
V(G) dan E(H)
E(G)
Definisi 5 (Spanning subgraph) Suatu subgraf G dikatakan spanning subgraph jika subgraf tersebut mengandung semua verteks pada graf G (Vasudev 2006). Definisi 6 (Walk) Suatu walk W pada graf G adalah barisan bergantian antara verteks dan sisi yang dimulai dan diakhiri oleh verteks. Walk yang dimulai dari v0 dan berakhir di vn disebut walk v0 – vn dan walk W mempunyai panjang n karena melalui n sisi (tidak harus berbeda) (Chartrand & Oellermann 1993).
3 Definisi 7 (Walk tertutup) Suatu walk pada graf G dikatakan tertutup jika verteks awal dan verteks akhir pada walk tersebut adalah sama (Foulds 1992). Definisi 8 (Cycle) Cycle adalah walk tertutup, yang memuat sedikitnya tiga verteks, dan semua verteks pada walk tersebut berbeda (Foulds 1992 ). Definisi 9 (Path) Path adalah walk dengan tidak ada verteks yang diulang (Chartrand & Oellermann 1993). Definisi 10 (Terhubung/connected) Graf G dikatakan terhubungkan (connected) jika untuk setiap pasang verteks u dan v di G, maka u dihubungkan dengan v. Jika terdapat pasangan verteks u – v di G sehingga tidak ada path u – v, maka graf tersebut dikatakan tak terhubung (disconnected) (Chartrand & Oellermann 1993). Definisi 11 (Tree) Tree adalah graf terhubungkan yang tidak mempunyai cycle (Chartrand & Oellermann 1993). Definisi 12 (Spanning tree) Suatu spanning tree adalah spanning subgraph yang merupakan tree (Vasudev 2006).
GENERALIZED MINIMUM SPANNING TREE Masalah GMST merupakan masalah pencarian minimum spanning tree dengan simpul-simpulnya terbagi menjadi beberapa kumpulan simpul yang disebut cluster. Minimum spanning tree dari graf G adalah suatu spanning tree dari G dengan bobot terkecil. Penentuan Minimum Spanning Tree dengan Algoritme Prim Salah satu cara untuk menentukan minimum spanning tree dari suatu graf ialah menggunakan algoritme Prim. Menurut Balakrishnan (1997) langkahlangkah dalam algoritme Prim untuk menentukan minimum spanning tree T dari graf G ialah sebagai berikut: Misalkan diberikan graf G dengan banyaknya verteks adalah n, maka: Langkah 1. Sisi diurutkan dari kecil ke besar dan T = . Langkah 2. Sisi dari graf G yang berbobot minimum dipilih lalu dimasukkan ke dalam T. Langkah 3. Dipilih sisi uv di graf G yang memiliki bobot minimum dan adjacent dengan sisi di T. Jika uv tidak membentuk cycle, maka uv ditambahkan ke dalam T dan lanjut ke langkah 3. Sebaliknya, jika
4 penambahan sisi uv membentuk cycle, maka sisi tersebut tidak dipilih dan kembali ke langkah 2. Langkah 4. Proses berhenti jika T memiliki (n−1) sisi. Penyelesaian GMST Suatu GMST dapat diselesaikan dengan beberapa algoritme, yaitu dengan algoritme genetik dan algoritme local search. Namun dalam karya ilmiah ini penyelesaian GMST hanya menggunakan algoritme local search. Menurut Golden et al. (2005) langkah-langkah algoritme local search untuk GMST adalah sebagai berikut: 1. Banyak solusi fisibel yang akan dihasilkan, yaitu X ditentukan terlebih dahulu. Langkah 2 sampai 4 diulangi sebanyak X kali. 2. Dari setiap cluster dipilih satu simpul secara acak. Jika subgraf yang terbentuk dari simpul-simpul yang telah dipilih merupakan graf terhubung, maka diterapkan salah satu algoritme dari MST untuk mendapatkan MST. Jika tidak, maka pemilihan simpul dari setiap cluster diulangi hingga subgraf yang terbentuk merupakan graf terhubung. Pada karya ilmiah ini, algoritme yang digunakan ialah algoritme Prim. 3. Urutan cluster yang akan dikunjungi ditentukan secara acak. 4. Dengan urutan kunjungan seperti pada Langkah 3, langkah-langkah berikut diulangi sampai m kunjungan cluster secara berurutan sehingga tidak ada perbaikan yang signifikan. a. Ketika mengunjungi sebuah cluster, setiap simpulnya dipertimbangkan sebagai pengganti simpul saat ini di cluster yang terkandung dalam generalized spanning tree (GST) dan dihitung biaya solusi untuk setiap penggantian simpul. GST yaitu tree yang berisi tepat satu simpul dari tiap cluster (Pop 2002). b. Di antara solusi yang dihitung pada langkah sebelumnya, identifikasi MST yang memberikan peningkatan terbesar dalam fungsi tujuan (misalkan: penurunan terbesar dalam hal bobot jarak). Jika ada perbaikan, simpul yang mewakili cluster ditentukan dan tree saat ini diperbarui. Berikut ini adalah contoh gambar solusi fisibel untuk GMST:
Gambar 1 Contoh solusi fisibel untuk GMST
5 Batas Bawah untuk GMST Batas bawah untuk GMST dapat diperoleh dengan menyelesaikan masalah MST pada graf transformasi H. Graf transformasi H merupakan graf dengan tiap cluster diganti menjadi single node. Didefinisikan biaya antara dua simpul pada graf transformasi sama dengan biaya minimum antara dua cluster yaitu biaya antara dua simpul yang mewakili. Langkah-langkah untuk menentukan batas bawah yaitu: 1. dimulai dengan graf tak terhubung T dengan m buah cluster, 2. sisi pada graf G diurutkan dari bobot terkecil sampai terbesar, 3. sisi pada daftar urutan yang memiliki bobot terkecil dimasukkan ke dalam graf T asalkan tidak membentuk cycle antar cluster, 4. langkah 3 diulangi sampai T memiliki m−1 sisi. Batas Atas untuk GMST Batas atas untuk GMST dapat diperoleh dengan mengadaptasi algoritme Kruskal, algoritme Prim, atau algoritme Sollin. Pada karya ilmiah ini hanya adaptasi algoritme Prim saja yang diterapkan karena untuk kasus dengan simpul yang terlalu banyak, algoritme Prim lebih efisien dibandingkan dengan algoritme yang lain Adaptasi algoritme Prim dimulai dengan memilih starting node (setiap pemilihan starting node akan diperoleh hasil yang berbeda-beda). Langkah selanjutnya sama seperti algoritme Prim (Feremans et al. 2004).
APLIKASI Listrik merupakan kebutuhan yang sangat penting, namun hingga tahun 2014 masih banyak daerah di Indonesia yang belum teraliri arus listrik, salah satunya ialah Palangkaraya. Meskipun Palangkaraya merupakan ibukota provinsi Kalimantan Tengah, namun belum semua kecamatan di Palangkaraya teraliri listrik, seperti di beberapa kelurahan di Kecamatan Rakumpit (Fathurahman 2014). Keterangan : : letak kecamatan yang ada di Kota Palangkaraya
Gambar 2 Peta Kota Palangkaraya
6 Sketsa pada Gambar 2 merupakan peta dari Kota Palangkaraya dan letak kecamatan-kecamatan yang ada di Palangkaraya. Setiap kecamatan memiliki beberapa kelurahan yang akan ditentukan sebagai lokasi pemasangan gardu induk listrik dengan asumsi beberapa kelurahan yang dilalui oleh sungai tidak dipilih. Dari Gambar 2 dapat diperoleh graf sebagai berikut: G:
Gambar 3 Graf kasus Palangkaraya Keterangan: C1 C2 C3 C4 C5 A B C D E F G H
: Kecamatan Jekan Raya : Kecamatan Bukit Batu : Kecamatan Pahandut : Kecamatan Rakumpit : Kecamatan Sebangau : Kelurahan Bukit Tunggal : Kelurahan Menteng : Kelurahan Palangka : Kelurahan Petuk Ketimpun : Kelurahan Habaring Hurung : Kelurahan Marang : Kelurahan Sei Gohong : Kelurahan Tangkiling
I J K L M N O P Q R S T
: Kelurahan Tumbang Tahai
: Kelurahan Langkai : Kelurahan Pahandut : Kelurahan Panarung : Kelurahan Tanjung Pinang : Kelurahan Bukit Sua : Kelurahan Pager : Kelurahan Petuk Berunai : Kelurahan Bereng Bengkel : Kelurahan Petuk Bukit : Kelurahan Kalampangan : Kelurahan Sabaru
Tabel 1 Beberapa nama kelurahan dan kecamatan di Kota Palangkaraya Kecamatan Kelurahan Kecamatan Kelurahan Jekan Raya Bukit Tunggal Pahandut Pahandut Menteng Panarung Palangka Tanjung Pinang Petuk Ketimpun Rakumpit Bukit Sua Habaring Hurung Bukit Batu Pager Marang Petuk Berunai Sei Gohong Sebangau Bereng Bengkel Tangkiling Petuk Bukit Tumbang Tahai Kalampangan Pahandut Langkai Sabaru
7 Data jarak antarkelurahan ditampilkan dalam Lampiran 1. Penentuan Batas Bawah dan Batas Atas GMST Penentuan batas bawah Langkah 1. Graf tak terhubung T
Gambar 4 Graf tak terhubung T Langkah 2. Sisi pada graf G diurutkan dari jarak terkecil sampai terbesar (Lampiran 3) Langkah 3. Berdasarkan Lampiran 3, sisi dengan bobot terkecil adalah CJ dengan simpul C berada pada cluster C1 dan simpul J berada pada cluster C3, sehingga dipilih sisi dengan bobot terkecil yaitu C1C3 = 2.2 dan dimasukkan ke dalam graf T Langkah 4. Langkah 3 diulangi sampai T memiliki m−1 sisi. Sisi dengan bobot terkecil berikutnya ialah C1C2 dengan bobot 11.7, C3C5 dengan bobot 12.3, C4C5 dengan bobot 16.4 sehingga didapat batas bawah untuk GMST sebesar 2.2 + 11.7 + 12.3 + 16.4 = 42.6 km.
Gambar 5 Spanning tree untuk batas bawah GMST
8 Penentuan batas atas Dalam karya ilmiah ini, penentuan nilai batas atas dilakukan dengan menentukan spanning tree menggunakan adaptasi dari algoritme Prim. Pada adaptasi algoritme Prim dimulai dengan memilih starting node (setiap pemilihan starting node yang berbeda dapat memberi hasil yang berbeda-beda). Misalkan simpul A dipilih sebagai starting node. Dengan algoritme Prim (Lampiran 2) didapatkan minimum spanning tree seperti pada gambar berikut:
Gambar 6 Spanning tree untuk batas atas GMST sehingga didapat nilai batas atas untuk GMST sebesar 98.5 km. Penyelesaian GMST dengan Metode Heuristik Local Search Langkah ini dimulai dengan menentukan banyaknya solusi fisibel yang dihasilkan sebanyak X, sehingga pengulangan dapat dibatasi sebanyak X. Dalam karya ilmiah ini X = 3 pengulangan. Iterasi 1. Langkah 1. Dipilih simpul secara acak dari tiap cluster, misalkan dipilih simpul B, F, L, N, Q. Karena subgraf yang terbentuk dari simpul yang telah dipilih adalah graf terhubung, maka diterapkan algoritme Prim untuk menentukan MST.
Gambar 7 Subgraf yang terbentuk dari simpul yang telah dipilih
9 Dengan algoritme Prim (Lampiran 4) didapatkan MST dengan bobot minimum sebesar 111.4. Garis yang bercetak tebal pada Gambar 7 merupakan MST. Langkah 2. Menentukan urutan cluster yang akan dikunjungi secara acak, misalkan C1, C2, C3, C4, C5. Langkah 3. Mengunjungi sebuah cluster dan mengganti setiap simpulnya yang memberikan nilai MST lebih kecil sehingga tree saat ini diperbarui. Kunjungan ke-1 (C1) Dari hasil perhitungan (Lampiran 5) didapat MST dengan bobot sebesar 110.9 seperti pada gambar berikut:
Gambar 8 MST pada kunjungan ke-1 Kunjungan ke-2 (C2) Dari hasil perhitungan (Lampiran 6) didapat MST dengan bobot sebesar 108.2 seperti pada gambar berikut:
Gambar 9 MST pada kunjungan ke-2
10 Kunjungan ke-3 (C3) Dari hasil perhitungan (Lampiran 7) didapat MST dengan bobot sebesar 101.6 seperti pada gambar berikut:
Gambar 10 MST pada kunjungan ke-3 Kunjungan ke-4 (C4) Dari hasil perhitungan (Lampiran 8) didapat MST dengan bobot sebesar 94.9 seperti pada gambar berikut:
Gambar 11 MST pada kunjungan ke-4 Kunjungan ke-5 (C5) Dari hasil perhitungan (Lampiran 9) didapat MST dengan bobot sebesar 91.4 seperti pada gambar berikut:
11
Gambar 12 MST pada kunjungan ke-5 Dari hasil perhitungan pada iterasi pertama didapatkan solusi fisibel dengan nilai 91.4.
`
Iterasi 2. Langkah 1. Misalkan dipilih simpul D, G, K, O, S
Gambar 13 Subgraf yang terbentuk dari simpul yang telah dipilih Dengan algoritme Prim (Lampiran 10) didapatkan MST dengan bobot minimum sebesar 109.1. Garis yang bercetak tebal merupakan MST. Langkah 2. Menentukan urutan cluster yang akan dicari secara acak, misalkan C1, C2, C3, C4, C5. Langkah 3. Lakukan seperti langkah 3 pada iterasi 1.
12 Kunjungan ke-1 (C1) Dari hasil perhitungan (Lampiran 11) didapat MST dengan bobot sebesar 104 seperti pada gambar berikut:
Gambar 14 MST pada kunjungan ke-1 Kunjungan ke-2 (C2) Dari hasil perhitungan (Lampiran 12) didapat MST dengan bobot sebesar 96.9 seperti pada gambar berikut:
Gambar 15 MST pada kunjungan ke-2 Kunjungan ke-3 (C3) Dari hasil perhitungan (Lampiran 13) didapat MST dengan bobot sebesar 91.1 seperti pada gambar berikut:
13
Gambar 16 MST pada kunjungan ke-3 Kunjungan ke-4 (C4) Dari hasil perhitungan (Lampiran 14) tidak didapatkan jarak yang lebih kecil dari 91.1 maka tree tidak diperbarui. Kunjungan ke-5 (C5) Dari hasil perhitungan (Lampiran 15) didapat MST dengan bobot sebesar 90.7 seperti pada gambar berikut:
Gambar 17 MST pada kunjungan ke-5 Dari hasil perhitungan pada iterasi kedua didapatkan solusi fisibel dengan nilai 91.1 Iterasi 3. Langkah 1. Misalkan dipilih simpul D, I, M, O, R
14
Gambar 18 Subgraf yang terbentuk dari simpul yang telah dipilih Dengan algoritme Prim (Lampiran 16) didapatkan MST dengan bobot minimum sebesar 94.8. Garis yang bercetak tebal merupakan MST. Langkah 2. Menentukan urutan cluster yang akan dicari secara acak, misalkan C1, C2, C3, C4, C5. Langkah 3. Lakukan seperti langkah 3 pada iterasi 1. Kunjungan ke-1 (C1) Dari hasil perhitungan (Lampiran 17) didapat MST dengan bobot sebesar 86.9 seperti pada gambar berikut:
Gambar 19 MST pada kunjungan ke-1
15 Kunjungan ke-2 (C2) Dari hasil perhitungan (Lampiran 18) didapat MST dengan bobot sebesar 83.9 seperti pada gambar berikut:
Gambar 20 MST pada kunjungan ke-2 Kunjungan ke-3 (C3) Dari hasil perhitungan (Lampiran 19) didapat MST dengan bobot sebesar 72.8 seperti pada gambar berikut:
Gambar 21 MST pada kunjungan ke-3 Kunjungan ke-4 (C4) Dari hasil perhitungan (Lampiran 20) tidak didapatkan jarak yang lebih kecil dari 72.8 maka tree tidak diperbarui. Kunjungan ke-5 (C5) Dari hasil perhitungan (Lampiran 21) tidak didapatkan jarak yang lebih kecil dari 72.8 maka tree tidak diperbarui.
16 Dari hasil perhitungan pada iterasi ketiga didapatkan solusi dengan nilai 72.8. Dari ketiga iterasi yang dilakukan, solusi pada iterasi ketiga yang memiliki nilai minimum, sehingga simpul yang dipilih adalah simpul C, F, J, O, R dengan gambar seperti pada Gambar 21. Solusi ini berada pada selang antara batas bawah yaitu 42.6 dan batas atas yaitu 98.5. Ini berarti akan dibangun gardu induk listrik di Kelurahan Palangka Kecamatan Jekan Raya, Kelurahan Marang Kecamatan Bukit Batu, Kelurahan Langkai Kecamatan Pahandut, Kelurahan Pager Kecamatan Rakumpit, Kelurahan Petuk Bukit Kecamatan Sebangau. Jika iterasi yang dilakukan lebih banyak, maka solusi yang didapat akan lebih baik dan mendekati nilai batas bawah.
SIMPULAN DAN SARAN Simpulan Masalah Generalized Minimum Spanning Tree (GMST) dapat diselesaikan menggunakan metode heuristik Local Search. Telah diperlihatkan bahwa masalah GMST dapat diterapkan pada penentuan lokasi gardu induk listrik di Kota Palangkaraya. Hasil yang didapat yaitu akan dibangun gardu induk listrik di Kelurahan Palangka Kecamatan Jekan Raya, Kelurahan Marang Kecamatan Bukit Batu, Kelurahan Langkai Kecamatan Pahandut, Kelurahan Pager Kecamatan Rakumpit, Kelurahan Petuk Bukit Kecamatan Sebangau. Saran Jika ada yang ingin mendalami karya ilmiah ini, disarankan untuk menggunakan metode lain seperti algoritme genetika dan membangun software yang dapat menerapkan metode heuristik local search.
DAFTAR PUSTAKA Balakrishnan VK. 1997. Schaum’s Outline of Theory and Problems of Graph Theory. New York (US): McGraw-Hill. Chartrand G, Oellermann OR. 1993. Applied and Algorithmic Graph Theory. New York (US): McGraw-Hill. Chartrand G, Zhang P. 2009. Chromatic Graph Theory. London (GB): CRC Pr. Dror M, Haoari M, Chaouachi J. 2000. Generalized spanning trees. Eur. J. Oper. Res. 120:583-592.doi:10.1016/S0377221799000065. Fathurahman. 2014 Maret 26. Hingga kini listrik PLN belum masuk di Rakumpit. Banjarmasin Post. Feremans C, Labbe M, Laporte G. 2002. A comparative analysis of several formulations for the generalized minimum spanning tree problem. Networks 39:29-34.doi:10.1002/net.10009.
17 Feremans C, Labbe M, Laporte G. 2004. The generalized minimum spanning tree problem: Polyhedral analysis and branch and cut algorithm. Networks 43:71-86.doi:10.1002/net.10105. Foulds LR. 1992. Graph Theory Applications. New York (US): Springer Publishing. Golden B, Raghavan S, Staanojevic D. 2005. Heuristic search for the generalized minimum spanning tree. Informs. 17(3):290-304.doi:10.1287 /ijoc.1040.0077. Myung YS, Lee CH, Tcha DW. 1995. On the generalized minimum spanning tree problem. Networks 26:231-241.doi:10.1002/net.3230260407. Pop PC. 2002. The generalized minimum spanning tree problem. [tesis]. Twente (ID): University of Twente. Raghavan S. 2002. On modeling the generalized minimum spanning tree. Technical report. The Robert H. Smith School of Business, University of Maryland, College Park, MD. Vasudev C. 2006. Graph Theory with Application. New Delhi (IN): New Age International.
-
-
-
-
30.0
11.7
33.9
24.6
21.3
18.3
20.2
23.6
29.4
67.3
61.9
63.3
37.9
45.5
34.8
34.4
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
A
A
Kelurahan
-
-
-
-
17.8
18.2
56.8
21.3
74.6
73.2
78.6
12.9
7.1
5.7
3.7
32.6
35.9
45.2
23.0
41.3
B
-
-
-
-
18.2
18.6
54.2
21.7
72.0
70.6
76.0
13.3
8.8
4.1
2.2
30.0
33.3
42.6
20.4
38.7
C
Lampiran 1 Data jarak antar kelurahan (km)
-
-
-
-
32.6
33.0
47.7
36.1
65.4
64.1
69.5
27.7
21.9
15.7
16.6
23.5
26.7
36.1
13.9
32.1
D
56.6
57.0
31.1
60.0
48.9
47.5
52.9
51.6
45.8
42.4
40.5
-
-
-
-
-
32.1
38.7
41.3
30.0
E
38.3
38.7
33.8
41.8
51.6
51.0
60.0
33.3
27.5
24.1
22.2
-
-
-
-
-
13.9
20.4
23.0
11.7
F
61.6
60.9
19.2
64.0
36.9
35.5
40.9
55.6
49.8
46.4
44.5
-
-
-
-
-
36.1
42.6
45.2
33.9
G
51.2
51.6
21.0
54.6
38.7
37.7
44.4
46.2
40.4
37.0
35.1
-
-
-
-
-
26.7
33.3
35.9
24.6
H
47.9
48.3
27.2
51.4
45.0
43.6
49.0
42.9
37.1
33.7
31.8
-
-
-
-
-
23.5
30.0
32.6
21.3
I
17.5
17.9
56.1
21.0
73.8
72.4
77.8
-
-
-
-
31.8
35.1
44.5
22.2
40.5
16.6
2.2
3.7
18.3
J
21.4
21.8
58.0
24.9
75.7
74.4
79.8
-
-
-
-
33.7
37.0
46.4
24.1
42.4
15.7
4.1
5.7
20.2
K
18.4
18.8
63.0
21.8
80.7
79.3
84.7
-
-
-
-
37.1
40.4
49.8
27.5
45.8
21.9
8.8
7.1
23.6
L
12.3
23.0
67.2
26.0
84.9
83.5
88.9
-
-
-
-
42.9
46.2
55.6
33.3
51.6
27.7
13.3
12.9
29.4
M
93.9
94.3
21.8
97.4
-
-
-
88.9
84.7
79.8
77.8
49.0
44.4
40.9
60.0
52.9
69.5
76.0
78.6
67.3
N
88.5
88.9
16.4
92.0
-
-
-
83.5
79.3
74.4
72.4
43.6
37.7
35.5
51.0
47.5
64.1
70.6
73.2
61.9
O
89.9
90.3
17.7
93.3
-
-
-
84.9
80.7
75.7
73.8
45.0
38.7
36.9
51.6
48.9
65.4
72.0
74.6
63.3
P
-
-
-
-
93.3
92.0
97.4
26.0
21.8
24.9
21.0
51.4
54.6
64.0
41.8
60.0
36.1
21.7
21.3
37.9
Q
-
-
-
-
17.7
16.4
21.8
67.2
63.0
58.0
56.1
27.2
21.0
19.2
33.8
31.1
47.7
54.2
56.8
45.5
R
-
-
-
-
90.3
88.9
94.3
23.0
18.8
21.8
17.9
48.3
51.6
60.9
38.7
57.0
33.0
18.6
18.2
34.8
S
-
-
-
-
89.9
88.5
93.9
12.3
18.4
21.4
17.5
47.9
51.2
61.6
38.3
56.6
32.6
18.2
17.8
34.4
T
18
19 Lampiran 2 Langkah penentuan MST dengan adaptasi algoritme Prim Langkah 1. Menentukan starting node, pilih simpul A sebagai starting node. Langkah 2. Ambil sisi AF, karena sisi AF merupakan sisi terkecil dan adjacent dengan simpul A. T = {AF}
Iterasi 1: Langkah 3. Pilih sisi AJ, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. Sisi FD lebih minimum dari AJ namun A dan D berada pada satu cluster sehingga sisi yang dipilih yaitu sisi AJ. 𝑇 = {AF, AJ}
Langkah 4. 𝑇 memiliki 2 sisi, maka kembali ke Langkah 3. Iterasi 2: Langkah 3. Pilih sisi JT, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {AF, AJ, JT}
Langkah 4. 𝑇 memiliki 3 sisi, maka kembali ke Langkah 3. Iterasi 3: Langkah 3. Pilih sisi FO, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {AF, AJ, JT, FO}
Langkah 4. 𝑇 memiliki 4 sisi, maka iterasi berhenti.
20 Lampiran 3 Urutan jarak terkecil sampai terbesar Sisi CJ BJ CK BK BL CL AF MT BM CM DF DK OR DJ JT PR BT JS BS CT AJ LT CS LS GR AK CF HR JQ AI BQ KT CQ KS LQ NR DL FJ BF MS DI AL FK AH KQ MQ DH IR FL
Jarak 2.2 3.7 4.1 5.7 7.1 8.8 11.7 12.3 12.9 13.3 13.9 15.7 16.4 16.6 17.5 17.7 17.8 17.9 18.2 18.2 18.3 18.4 18.6 18.8 19.2 20.2 20.4 21.0 21.0 21.3 21.3 21.4 21.7 21.8 21.8 21.8 21.9 22.2 23.0 23.0 23.5 23.6 24.1 24.6 24.9 26.0 26.7 27.2 27.5
Sisi DM AM AE CI ER IJ DE BI DT DS CH FM IK FR AG AT AS HJ GO BH DG DQ GP HK IL HO AQ FT CE FS HP HL EJ GN BE FQ EK CG IM IO HN GJ IP BG AR EL HM GK EO
Jarak 27.7 29.4 30.0 30.0 31.1 31.8 32.1 32.6 32.6 33.0 33.3 33.3 33.7 33.8 33.9 34.4 34.8 35.1 35.5 35.9 36.1 36.1 36.9 37.0 37.1 37.7 37.9 38.3 38.7 38.7 38.7 40.4 40.5 40.9 41.3 41.8 42.4 42.6 42.9 43.6 44.4 44.5 45.0 45.2 45.5 45.8 46.2 46.4 47.5
Sisi DR IT IS EP IN GL FO HT IQ EM FP HS EN CR HQ GM JR ET BR ES KR EQ FN GS GT AO LR AP GQ DO DP MR AN DN CO CP JO BO JP KO BP KP CN JN BN LO KN LP MO
Jarak 47.7 47.9 48.3 48.9 49.0 49.8 51.0 51.2 51.4 51.6 51.6 51.6 52.9 54.2 54.6 55.6 56.1 56.6 56.8 57.0 58.0 60.0 60.0 60.9 61.6 61.9 63.0 63.3 64.0 64.1 65.4 67.2 67.3 69.5 70.6 72.0 72.4 73.2 73.8 74.4 74.6 75.7 76.0 77.8 78.6 79.3 79.8 80.7 83.5
21 Sisi LN MP OT MN
Jarak 84.7 84.9 88.5 88.9
Sisi OS PT PS OQ
Jarak 88.9 89.9 90.3 92.0
Sisi PQ NT NS NQ
Jarak 93.3 93.9 94.3 97.4
Lampiran 4 Langkah penentuan MST dengan algoritme Prim pada iterasi 1 Langkah 1. Ambil sisi BL. T = {BL} Iterasi 1: Langkah 2. Pilih sisi BQ, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {BL, BQ} Langkah 3. 𝑇 memiliki 2 sisi, maka kembali ke Langkah 2. Iterasi 2: Langkah 2. Pilih sisi BF, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {BL, BQ, BF} Langkah 3. 𝑇 memiliki 3 sisi, maka kembali ke Langkah 3. Iterasi 3: Langkah 3. Pilih sisi FN, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {BL, BQ, BF, FN}. Langkah 4. 𝑇 memiliki 4 sisi, maka iterasi berhenti. Lampiran 5 Perhitungan kunjungan 1 (cluster C1) pada iterasi 1
AL + AQ + AF + FN = 23.6 + 37.9 + 11.7 + 60 = 133.2 CL + CQ + CF + FN = 8.8 + 21.7 + 20.4 + 60 = 110.9 < 111.4 DL + DQ + DF + FN = 21.9 + 36.1 + 13.9 + 60 = 131.9
Lampiran 6 Perhitungan kunjungan 2 (cluster C2) pada iterasi 1
CL + CQ + CE + EN = 8.8 + 21.7 + 38.7 + 52.9 = 122.8 CL + CQ + CG + GN = 8.8 + 21.7 + 42.6 + 40.9 = 114 CL + CQ + CH + HN = 8.8 + 21.7 + 33.3 + 44.4 = 108.2 < 110.9 CL + CQ + CI + IN = 8.8 + 21.7 + 30 + 49 = 109.5
Lampiran 7 Perhitungan kunjungan 3 (cluster C3) pada iterasi 1
CJ + CQ + CH + HN = 2.2 + 21.7 + 33.3 + 44.4 = 101.6 < 108.2 CK + CQ + CH + HN = 4.1 + 21.7 + 33.3 + 44.4 = 103.5 CM + CQ + CH + HN = 13.3 + 21.7 + 33.3 + 44.4 = 112.7
Lampiran 8 Perhitungan kunjungan 4 (cluster C4) pada iterasi 1
CJ + CQ + CH + HO = 2.2 + 21.7 + 33.3 + 37.7 = 94.9 < 101.6 CJ + CQ + CH + HP = 2.2 + 21.7 + 33.3 + 38.7 = 95.9
22 Lampiran 9 Perhitungan kunjungan 5 (cluster C5) pada iterasi 1
CJ + CR + CH + HO = 2.2 + 54.2 + 33.3 + 37.7 = 127.4 CJ + CS + CH + HO = 2.2 + 18.6 + 33.3 + 37.7 = 91.8 CJ + CT + CH + HO = 2.2 + 18.2 + 33.3 + 37.7 = 91.4 < 94.9
Lampiran 10 Langkah penentuan MST dengan algoritme Prim pada iterasi 2 Langkah 1. Ambil sisi DK. T = {DK} Iterasi 1: Langkah 2. Pilih sisi KS, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {DK, KS} Langkah 3. 𝑇 memiliki 2 sisi, maka kembali ke Langkah 2. Iterasi 2: Langkah 2. Pilih sisi DG, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {DK, KS, DG} Langkah 3. 𝑇 memiliki 3 sisi, maka kembali ke Langkah 3. Iterasi 3: Langkah 3. Pilih sisi GO, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {DK, KS, DG, GO} Langkah 4. 𝑇 memiliki 4 sisi, maka iterasi berhenti. Lampiran 11 Perhitungan kunjungan 1 (cluster C1) pada iterasi 2
AK + KS + AG + GO = 20.2 + 21.8 + 33.9 + 35.5 = 111.4 BK + KS + BG + GO = 5.7 + 21.8 + 45.2 + 35.5 = 108.2 CK + KS + CG + GO = 4.1 + 21.8 + 42.6 + 35.5 = 104 < 109.1
Lampiran 12 Perhitungan kunjungan 2 (cluster C2) pada iterasi 2
CK + KS + CE + EO = 4.1 + 21.8 + 38.7 + 47.5 = 112.1 CK + KS + CF + FO = 4.1 + 21.8 + 20.4 + 51 = 97.3 CK + KS + CH + HO = 4.1 + 21.8 + 33.3 + 37.7 = 96.9 < 104 CK + KS + CI + IO = 4.1 + 21.8 + 30 + 43.6 = 99.5
Lampiran 13 Perhitungan kunjungan 3 (cluster C3) pada iterasi 2
CJ + JS + CH + HO = 2.2 + 17.9 + 33.3 + 37.7 = 91.1 < 96.9 CL + LS + CH + HO = 8.8 + 18.8 + 33.3 + 37.7 = 98.6 CM + MS + CH + HO = 13.3 + 23 + 33.3 + 37.7 = 107.3
Lampiran 14 Perhitungan kunjungan 4 (cluster C4) pada iterasi 2 CJ + JS + CH + HN = 2.2 + 17.9 + 33.3 + 44.4 = 97.8 CJ + JS + CH + HP = 2.2 + 17.9 + 33.3 + 38.7 = 92.1
23 Lampiran 15 Perhitungan kunjungan 5 (cluster C5) pada iterasi 2
CJ + JQ + CH + HO = 2.2 + 21 + 33.3 + 37.7 = 94.2 CJ + JR + CH + HO = 2.2 + 56.1 + 33.3 + 37.7 = 129.3 CJ + JT + CH + HO = 2.2 + 17.5 + 33.3 + 37.7 = 90.7 < 91.1
Lampiran 16 Langkah penentuan MST dengan algoritme Prim pada iterasi 3 Langkah 1. Ambil sisi OR. T = {OR} Iterasi 1: Langkah 2. Pilih sisi RI, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {OR, RI} Langkah 3. 𝑇 memiliki 2 sisi, maka kembali ke Langkah 2. Iterasi 2: Langkah 2. Pilih sisi ID, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {OR, RI, ID} Langkah 3. 𝑇 memiliki 3 sisi, maka kembali ke Langkah 3. Iterasi 3: Langkah 3. Pilih sisi DM, karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {OR, RI, ID, DM} Langkah 4. 𝑇 memiliki 4 sisi, maka iterasi berhenti. Lampiran 17 Perhitungan kunjungan 1 (cluster C1) pada iterasi 3
OR + RI + IA + AM = 16.4 + 27.2 + 21.3 + 29.4 = 94.3 OR + RI + IB + BM = 16.4 + 27.2 + 32.6 + 12.9 = 89.1 OR + RI + IC + CM = 16.4 + 27.2 + 30 + 13.3 = 86.9 < 94.8
Lampiran 18 Perhitungan kunjungan 2 (cluster C2) pada iterasi 3
OR + RE + EC + CM = 16.4 + 31.1 + 38.7 + 13.3 = 99.5 OR + RF + FC + CM = 16.4 + 33.8 + 20.4 + 13.3 = 83.9 < 86.9 OR + RG + GC + CM = 16.4 + 19.2 + 42.6 + 13.3 = 91.5 OR + RH + HC + CM = 16.4 + 21 + 33.3 + 13.3 = 84
Lampiran 19 Perhitungan kunjungan 3 (cluster C3) pada iterasi 3
OR + RF + FC + CJ = 16.4 + 33.8 + 20.4 + 2.2 = 72.8 < 83.9 OR + RF + FC + CK = 16.4 + 33.8 + 20.4 + 4.1 = 74.7 OR + RF + FC + CL = 16.4 + 33.8 + 20.4 + 8.8 = 79.4
Lampiran 20 Perhitungan kunjungan 4 (cluster C4) pada iterasi 3
NR + RF + FC + CJ = 21.8 + 33.8 + 20.4 + 2.2 = 78.2
24
PR + RF + FC + CJ = 17.7 + 33.8 + 20.4 + 2.2 = 74.1
Lampiran 21 Perhitungan kunjungan 5 (cluster C5) pada iterasi 3
OQ + QF + FC + CJ = 92 + 41.8 + 20.4 + 2.2 = 156.4 OS + SF + FC + CJ = 88.9 + 38.7+ 20.4 + 2.2 = 150.2 OT + TF + FC + CJ = 88.5 + 38.3 + 20.4 + 2.2 = 149.4 .
25
RIWAYAT HIDUP
Penulis dilahirkan di Jakarta pada tanggal 16 September 1992 sebagai anak kedua dari empat bersaudara, anak pasangan Harsyad dan Sobriyanti. Tahun 2004 penulis lulus dari SD Negeri Sukatani III Depok, tahun 2007 penulis lulus dari SMP Negeri 11 Depok, tahun 2010 penulis lulus dari SMA Negeri 4 Depok. Penulis diterima di Institut Pertanian Bogor pada tahun 2010 melalui jalur Undangan Seleksi Masuk IPB (USMI) dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Penulis mendapatkan beasiswa Bidik Misi tahun 2010-2014. Selama kuliah, penulis aktif dalam organisasi kemahasiswaan Himpunan Profesi Gumatika sebagai Bendahara Divisi Sosial dan Lingkungan pada tahun 2011-2012. Penulis pernah menjadi Kepala Divisi acara “Math Camp” dan bakti sosial pada tahun 2013. Penulis juga pernah menjadi panitia dan koordinator di berbagai acara kemahasiswaan serta pernah mengajar privat Matematika.
