IMPLEMENTASI HIERARCHICAL CLUSTERING DAN BRANCH AND BOUND PADA SIMULASI PENDISTRIBUSIAN PAKET POS

Artikel Skripsi Universitas Nusantara PGRI Kediri

IMPLEMENTASI HIERARCHICAL CLUSTERING DAN BRANCH AND BOUND PADA SIMULASI PENDISTRIBUSIAN PAKET POS

SKRIPSI Diajukan Untuk Memenuhi Sebagian Syarat Guna Memperoleh Gelar Sarjana Komputer (S.Kom.) Pada Program Studi Teknik Informatika Fakultas Teknik Universitas Nusantara PGRI Kediri

OLEH: EKA WAHYUNI NPM : 11.1.03.02.0109

FAKULTAS TEKNIK (FT) UNIVERSITAS NUSANTARA PERSATUAN GURU REPUBLIK INDONESIA

UNP KEDIRI 2015 Eka Wahyuni (11.1.03.02.0109) Teknik – Teknik Informatika

simki.unpkediri.ac.id Page 1 of 15


Eka Wahyuni (11.1.03.02.0109) Teknik – Teknik Informatika









IMPLEMENTASI HIERARCHICAL CLUSTERING DAN BRANCH AND BOUND PADA SIMULASI PENDISTRIBUSIAN PAKET POS

EKA WAHYUNI Prodi Teknik Informatika, Fakultas Teknik, UNP Kediri 2015 e-mail : [email protected]

ABSTRAK Penelitian ini dilatar belakangi hasil pengamatan dan penelitian peneliti, bahwa pembagian wilayah dan penentuan rute distribusi yang tidak tepat berakibat lamanya proses distribusi dan tingginya biaya distribusi. Namun pada prakteknya pembagian wilayah dan penentuan rute distribusi tidak lah mudah karena sangat komplek, rumit, dan memerlukan ketelitian yang tinggi. Identifikasi masalah pada penelitian ini adalah efektifitas dan efisiensi pengiriman akibat pembagian wilayah dan penentuan rute distribusi. Rumusan masalah pada penelitian ini adalah bagaimana mengimplementasikan metode Hierarchical Clustering dan Branch and Bound untuk merekomendasikan pembagian wilayah dan rute distribusi paket pos?. Penelitian ini menggunakan metode Hierarchical Clustering dan Branch and Bound. Hierarchical Clustering digunakan untuk pembagian wilayah dan Branch and Bound digunakan untuk penentuan rute distribusi paket pos. Kesimpulan dari penelitian ini adalah dengan mengimplementasikan Single Linkage, Djikstra dan Branch and Bound dapat menghasilkan aplikasi pengelompokkan wilayah dan penentuan rute untuk memudahkan distribusi paket pos. Dengan hasil simulasi yang lebih efektif dan efisien dalam pendistribusian paket pos Kata kunci : rute (lintasan/cycle), simulasi, Hierarchical Clustering, Branch and Bound, pos.



Artikel Skripsi Universitas Nusantara PGRI Kediri Maka

I. Latar Belakang Masalah Graf merupakan salah satu cabang ilmu Matematika

yang

diperlukan

pemanfaatan

teknologi untuk memudahkan pembagian

merepresentasikan

wilayah dan penetuan rute distribusi paket

objek – objek diskrit dan hubungan antara

pos yaitu aplikasi simulasi pembagian

objek – objek tersebut. Representasi visual

wilayah dan penentuan rute distribusi

graf adalah dengan menyatakan objek

paket pos dengan metode Hierarchical

sebagai simpul (Vertex) dan hubungan

Clustering

antar objek sebagai sisi (Edge). Dalam

Hierarchical Clustering adalah teknik

kehidupan sehari-hari banyak ditemukan

pengelompokan

permasalahan

kontruksi

yang

dapat

direpresentasikan dalam bentuk graf.

dan

Branch

and

yang

hirarki

Bound.

membentuk

atau

berdasarkan

tingkatan tertentu yang dilakukan secara

Seperti permasalahan yang ada di

bertahap. Sedangkan Branch and Bound

Kantor Pos Kediri Kota. Kantor Pos

adalah algoritma pencarian didalam ruang

Kediri Kota adalah pusat pelayanan Pos

solusi secara sistematis. Pada penelitian

diseluruh wilayah Kediri yang memiliki

ini

tugas

untuk

dimanfaatkan untuk pembagian wilayah

seluruh

distribusi antar kantor pos, sedangkan

dan

tanggung

mendistribusikan

kiriman

jawab ke

Metode

Hierarchical

Clustering

kantor pos cabang. Kiriman Pos dituntut

metode

harus tepat waktu karena itu proses

untuk mencari lintasan yang akan dilalui

pendistribusian tidak boleh mengalami

untuk mendistribusikan paket pos.

masalah

kalaupun

ada

harus

diminimalkan. Namun jarak antar Kantor

Branch and Bound digunakan

Penelitian ini berdasarkan penelitian sebelumnya yaitu;

Pos Pusat Kediri Kota dengan Kantor Pos

1). Penerapan Algortima Branch and

Cabang wilayah Kediri cukup jauh. Selain

Bound untuk menentukan rute objek

itu jalan atau rute pengiriman juga cukup

wisata di kota Semarang oleh Fera

beragam, jika tidak tepat dalam memilih

Marlinda Gurnitowati,

rute

yang

Supriyono menyatakan bahwa algoritma

ditempuh akan semakin jauh dan waktu

branch and bound dapat digunakan untuk

pengiriman akan semakin lama selain itu

menyelesaikan persoalan TSP dengan

akan menambah biaya perawatan mobil

permasalahan pencarian rute objek wisata

serta biaya transportasi.

yang ada di Kota Semarang.

pengiriman

maka

jarak


Rochmad dan


Artikel Skripsi Universitas Nusantara PGRI Kediri 2). Analisa

perbandingan

metode

Hierarchical Clustering, K-Means dan

(ii)

Himpunan E = E (G)

pasangan-pasangan tak berurut dari

gabungan keduanya dalam membentuk Cluster Data (studi kasus : problem kerja praktek jurusan Teknik Industri ITS) oleh Tahta Alfina, Budi Santosa, dan Ali Ridho Barakbah

dengan

hasil

vertex yang disebut edge (sisi) dari G. Banyaknya simpul (anggota V) disebut order Graf G, sedangkan

berdasarkan

parameter uji Cluster Variance, hasil Cluster terbaik dihasilkan oleh metode Single Linkage Clustering.

II. LANDASAN TEORI A. Definisi Graf

banyaknya ruas (anggota E) disebut ukuran (size) Graf G. Berikut gambar graf sederhana dan multigraf. B. Lintasan Lintasan adalah hubungan antar

Menurut Budayasa (2007) dalam

titik atau node dalam sebuah graf.

(Mardlootillah, H.I., Suyitno, A., &

Suatu lintasan yang berawal dan

Arini, F.Y. 2014:57),

berakhir pada node yang sama, maka

graf adalah himpunan berhingga tak kosong V(G) dari obyek-obyek yang disebut titik, dan himpunan berhingga (mungkin kosong) E(G) yang elemen-elemennya disebut sisi, sedemikian hingga setiap elemen e dalam E(G) merupakan pasangan tak berurutan dari titik-titik di V(G). Suatu Graf G terdiri dari dua hal : (i)

Himpunan V = V (G) yang

elemen–elemennya disebut vertex, titik sudut, atau simpul dari G.


disebut lintasan tertutup (close path), jika node awal dan node akhir dari lintasan

tersebut

berbeda,

disebut

lintasan terbuka (open path). Menurut Brandes (2001) dalam (Mardlootillah, H.I., Suyitno, A., & Arini, F.Y. 2014:57),

definisi sebuah lintasan (path) dari s € V sampai t € V adalah sebuah rangkaian titik-titik dan garis, dimulai dengan s dan berakhir di t dengan masing-masing garis menghubungkan titik-titik simki.unpkediri.ac.id Page 7 of 15

Artikel Skripsi Universitas Nusantara PGRI Kediri tersebut. Panjang sebuah lintasan adalah jumlah dari bobot pada garis-garis tersebut.

sangat terkenal dalam teori graph. Nama persoalan ini diilhami oleh masalah seorang pedagang yang akan

Lintasan terpendek adalah lintasan mengunjungi sejumlah kota. Uraian yang memiliki total bobot minimum persoalannya adalah sebagai berikut: untuk mencapai suatu tempat dari Suatu

pedagang

menggunakan

tempat tertentu. Lintasan terpendek waktunya untuk mengunjungi n kota dapat dicari dengan menggunakan graf. (nodes)

secara

siklus

perputaran.

Graf yang digunakan adalah graf yang Didalam satu kali perjalanan keliling, berbobot, yaitu graf yang setiap sisinya ia

harus

menentukan

urutan

dari

diberikan suatu nilai atau bobot. Bobot sejumlah kota yang harus dilaluinya, pada sisi graf dapat

menyatakan, setiap kota hanya boleh dilalui sekali

waktu, biaya dan sebagainya. dan hanya sekali dalam perjalanan, dan C. TSP (Travelling Salesman Problem) perjalanan berakhir pada kota awal Menurut

Rosa

(2012)

dalam dimana ia memulai perjalanan.

(Marlinda,

F.G.,

Rochmad.,

& Kebanyakan Travelling Salesman

Supriyono. 2014 : 50), Problem merupakan suatu simetris TSP adalah masalah optimasi, yaitu mengunjungi setiap tempat dari himpunan tempattempat yang ditentukan sekali dan hanya satu kali kemudian kembali ke tempat awal pada akhir dari rute perjalanan dengan jarak, waktu dan biaya yang minimum.

yang berarti untuk dua kota A dan B, jarak dari kota A ke kota B adalah sama dengan jarak dari kota B ke kota A.

Dalam

mendapatkan Travelling

Salesman

hal

ini,

panjang

kita

akan

perjalanan

Problem

keliling yang sama persis jika kita

termasuk ke dalam persoalan yang

membalikkan rute perjalanan tersebut.



Artikel Skripsi Universitas Nusantara PGRI Kediri Jadi tidak ada perbedaan antara suatu

dari

perjalanan keliling dan kebalikannya.

menggabungkan pendek

D. Hierarchical Clustering Hierarchical

Clustering adalah

digunakan

untuk

meng-

individu

dengan

jarak

paling

atau

similarities

(kemiripan) yang paling besar.

salah satu algoritma clustering yang dapat

entities

Pada

awalnya,

kita

harus

menemukan jarak terpendek dalam

cluster dokumen (document

D = {dik} dan menggabungkan

clustering). Dari teknik hierarchical

objek-objek

clustering, dapat dihasilkan suatu

misalnya,

kumpulan partisi yang berurutan.

mendapatkan

Metode Hierarchical Clustering yang

Langkah untuk menghitung jarak-

sering digunakan untuk menghitung

jarak antara (UV) dan cluster W

tingkat kemiripan diantaranya adalah

yang lain dengan cara:

menggunakan metode Single Linkage, Complete

Linkage,

dan

yang U dan

bersesuaian V ,

cluster

untuk (UV).

d ( UV )W= min{ d UW , dVW

Average

}.

Linkage. Namun dalam penelitian ini

Di sini besaran - besaran dUW

Hierarchical Clustering yang akan

dan dVW berturut-turut adalah

digunakan adalah :

jarak terpendek antara cluster -

1. Single Linkage

cluster U dan W dan juga cluster-

Input untuk algoritma single linkage bisa berwujud jarak atau similarities

antara

pasangan

-

cluster V dan W. E. Branch and Bound ”Algoritma Branch and Bound

pasangan dari objek - objek.

adalah

Kelompok -

didalam ruang solusi secara sistematis.

kelompok dibentuk


suatu

algoritma

pencarian


Artikel Skripsi Universitas Nusantara PGRI Kediri Ruang solusi digambarkan ke dalam

2.

Antrian Q diidentifikasi. Jika

pohon ruang status. Pohon ruang status

antrian Q kosong, maka solusi

tersebut dibangun dengan skema BFS”.

tidak

(Nugraha, 2010) dalam (Marlinda,

berhenti. Jika antian Q berisi,

F.G., Rochmad., & Supriyono. 2014 :

maka dipilih antrian Q simpul

50).

i yang mempunyai nilai c Breadth First Search (BFS) adalah

ada

dan

pencarian

paling kecil. Jika terdapat

algoritma pencarian simpul dalam graf

beberapa

(pohon) secara traversal yang dimulai

memenuhi, maka dipilih satu

dari simpul akar dan mengecek semua

secara sembarang.

simpul-simpul tetangganya. (Wijaya, 2007)

dalam

(Marlinda,

3.

F.G.,

i

yang

Simpul i diidentifikasi. Jika simpul i adalah simpul solusi,

Rochmad., & Supriyono. 2014 : 50). Langkah –

simpul

maka solusi telah ditemukan

langkah pencarian

dan pencarian berhenti. Jika

solusi algoritma branch and bound

simpul i bukan simpul solusi,

adalah sebagai berikut :

maka

1.

Simpul

akar

dimasukkan

kedalam

antrian

Q.

dibangkitkan.

Jika

maka

ditentukan

solusi

dan

telah

pencarian

berhenti.

Eka Wahyuni (11.1.03.02.0109) Teknik – Teknik Informatika 15

Jika

anak simpul

tidak memiliki anak , maka

simpul akar adalah simpul solusi,

semua

kembali kelangkah 2. 4.

Untuk setiap anak j dari simpul i, nilai c dihitung dan semua

anak

yang

sudah

simki.unpkediri.ac.id Page 10 of

Artikel Skripsi Universitas Nusantara PGRI Kediri dibangkitkan

5.

dimasukkan

Menurut

Wibowo

kedalam antrian Q.

Wicaksono

Kembali kelangkah 2.

(Mardlootillah, H.I., Suyitno, A., &

dalam

Arini, F.Y. 2014:57),

F. Dijkstra Algoritma yang dinamai menurut

Algoritma Dijkstra adalah sebuah prosedur komputasi yang mentransformasikan sejumlah input menjadi sejumlah output. Sebuah algoritma dikatakan “benar (correct)” jika untuk setiap inputnya menghasilkan output yang benar pula

penemunya, Edsger Dijkstra pada tahun 1959, adalah sebuah algoritma rakus

(2012)

&

(greedy

memecahkan

algorithm) permasalahan

dalam jarak

terpendek untuk sebuah graf berarah (directed graph) ataupun graf tidak berarah

(undirected

graph).

III. METODE PENGEMBANGAN 1. Diagram Use-Case

Algoritma ini akan mencari jarak

peta

terpendek sebuah simpul terhadap wilayah

semua

simpul

dalam

himpunan bantuan

pegawai kantor pos

simpul. Satu hal yang tidak dapat tentang aplikasi

dilakukan algoritma ini adalah adanya nilai negatif pada salah satu sisi. Namun

pada

penggunaan bobot diterapkan

untuk

kenyataannya negatif jarang penyelesaian

masalah.

Gambar 3.1 diagram use case Pada

gambar

diatas

terdapat 1 aktor yaitu Pegawai kantor

pos

yang

dapat

mengakses 4 use case. Use case tersebut adalah peta, wilayah,



Artikel Skripsi Universitas Nusantara PGRI Kediri bantuan dan tentang aplikasi.

Gambar 3.2 diagram sequence

Use case peta berfungsi untuk

Diagram

diatas

menampilkan peta kantor pos

menjelaskan alur proses yang

wilayah kota dan kabupaten

ada diaplikasi, yaitu pegawai

Kediri. Use

kantor pos masuk pada menu

case wilayah

berfungsi untuk rute

lintasan

menentukan

pendistribusian

paket pos. Use

peta

untuk

tampilan

memperoleh

peta

kantor

pos

case bantuan

wilayah kota dan kabupaten

berfungsi untuk memberikan

Kediri. Petugas kantor pos juga

penjelasan

yang

dapat mengakses menu wilayah

diperlukan pegawai kantor pos

untuk mengetahui hasil simulasi

dalam mengoperasikan aplikasi.

pembagian

Sedangkan use case

tentang

penetuan rute distribusi paket

penjelasan

pos. Jika pegawai kantor pos

aplikasi

bantuan

adalah

tentang aplikasi tersebut. 2. Diagram Urutan (Sequence Diagram) pegawai kantor pos

peta

wilayah

bantuan

1 : menampilkan()

tentang aplikasi

mengalami

wilayah

kesulitan

dan

dalam

mengoperasikan

aplikasi

simulasi

wilayah

pembagian

dan penentuan rute distribusi maka pegawai kantor pos dapat

2 : pembagian wilayah dan penentuan rute()

mengunakan

menu

bantuan.

3 : petunjuk()

Pegawai kantor pos juga dapat 4 : penjelasan()


memilih menu tentang aplikasi


Artikel Skripsi Universitas Nusantara PGRI Kediri untuk mengetahui penjelasan tentang aplikasi. 3.

2) Hasil

simulasi

pembagian

Diagram Aktifitas (Activity

wilayah

dan penentuan rute ditampilkan

Diagram)

3) selesai

peta

Bantuan

Gambar 3.3 diagram aktifitas peta Penjelasan

proses

dari

diagram aktifitas pada peta

masuk

aktifitas bantuan Penjelasan

adalah sebagai berikut ; 1) User

Gambar 3.5 diagram

pada

proses

dari

diagram aktifitas pada bantuan adalah sebagai berikut ;

menu peta

1) User

2) Peta ditampilkan

masuk

pada

menu bantuan

3) Keluar

2) User

mendapat

wilayah

penjelasan Gambar 3.4 diagram aktifitas wilayah Penjelasan

bantuan

penggunaan aplikasi 3) keluar

proses

dari

tentang aplikasi

diagram aktifitas pada wilayah Gambar 3.6 diagram adalah sebagai berikut ; aktifitas tentang 1) User

masuk

pada aplikasi

menu wilayah



Artikel Skripsi Universitas Nusantara PGRI Kediri Penjelasan

proses

dari

bantuan,

diagram aktifitas pada bantuan

aplikasi

adalah sebagai berikut ;

select.

1) User

masuk

pada

2) Kelas

menu tentang aplikasi 2) User

tentang

berisi

proses

select

label,jalur, batas kota, Kelas

wilayah, dan rute.

(Class

Diagram)

IV. HASIL PENELITIAN A. Desain Akhir Aplikasi

peta

menu +peta +wilayah +bantuan +tentang aplikasi

peta

3) Kelas wilayah berisi

3) keluar Diagram

proses

jalur.

aplikasi

4.

dan

proses select label dan

mendapat

penjelasan

tentang

+setlabel() +setjalur()

+select()

bantuan

wilayah +setlabel() +setjalur() +setbataskota() +setwilayah() +setrute()

tentang aplikasi

Gambar 3.7 diagram kelas Penjelasan diagram kelas diatas adalah sebagai berikut; 1) Kelas

Menu

atribut Eka Wahyuni (11.1.03.02.0109) Teknik – Teknik Informatika 15

berisi

V. KESIMPULAN Setelah melakukan penelitian dan pembahasan

pada

bab

sebelumnya

maka

dapat

-

bab ditarik

simulasi, simki.unpkediri.ac.id Page 14 of

Artikel Skripsi Universitas Nusantara PGRI Kediri kesimpulan

bahwa

dengan

mengimplementasikan Single Linkage, Djikstra dan Branch and Bound dapat menghasilkan pengelompokkan

aplikasi wilayah

dan

penentuan rute untuk memudahkan distribusi paket pos. Dengan hasil simulasi yang lebih efektif dan efisien dalam pendistribusian paket pos. IV. DAFTAR PUSTAKA Alfina, T., Santosa, B., & Barakbah, A.R. 2012. Analisa Perbandingan Metode Hierarchical Clustering, K-means dan Gabungan Keduanya dalam Cluster Data (Studi kasus : Problem Kerja Praktek Jurusan Teknik Industri ITS). Jurnal Teknik ITS, (Online), 1 : 521 – 525, tersedia: http:/ejurnal.its.ac.id, diunduh 28 April 2015 (21:34).

http://journal.unnes.ac.id/sju/index.p hp/ujm, diunduh 28 April 2015(21:34) Pugas, D.O., Somantri, M., & Satoto, K.I. 2011. Pencarian Rute Terpendek Menggunakan Algoritma Dijkstra dan Astar (A*) pada SIG Berbasis Web untuk Pemetaan Pariwisata Kota Sawahlunto. Jurnal Teknik UDS, (Online), 13 (1), 2011, 27-32, tersedia: http://ejournal.undip.ac.id/index.php /transmisi, diunduh 28 April 2015(21:34). Riyanti, E. 2004. Penerapan Algoritma Branch and Bound untuk penentuan rute objek wisata. Skripsi. Bandung:UKI Widodo, P, P. 2011. UML Secara Luas Digunakan Untuk Memodelkan Analisi & Desain Sistem Berorientasi Objek. Bandung : Informatika Bandung

Mardlootillah, H. I., Suyitno, A., & Arini, F.Y. 2014. Simulasi Algoritma Dijkstra dalam menanggani masalah lintasan terpendek pada Graf menggunakan Visual Basic. Jurnal Matematika, (Online), 3 (1) : 56-61, tersedia: http://journal.unnes.ac. id/sju/index.php/ujm, diunduh pada 28 April 2015. Marlinda, F.G., Rochmad., & Supriyono. 2014. Penerapan Algortima Branch and Bound untuk menentukan rute objek wisata dikota Semarang. Jurnal Matematika, (Online), 3 (1) : 49-55, tersedia: Eka Wahyuni (11.1.03.02.0109) Teknik – Teknik Informatika 15


IMPLEMENTASI HIERARCHICAL CLUSTERING DAN BRANCH AND BOUND PADA SIMULASI PENDISTRIBUSIAN PAKET POS

Recommend Documents