plagiat merupakan tindakan tidak … graf .....7 2.1.1 definisi graf .....7 2.1.2 definisi walk,...

i

Penerapan Algoritma Ants Colony System(ACS) Untuk Menentukan Rute

Terpendek Pengiriman Barang pada P.T. Pos Indonesia

Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Komputer

Program Studi Teknik Informatika

Oleh:

F.X. Alfa Suryo Utomo

NIM : 075314035

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2013

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJIPLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii

Ants Colony Algorithm (ACS) Implementation System Shortest

Route To Determine Shipping on PT Pos Indonesia

A Thesis

Presented as Partial Fullfillment of the Requirements

To Obtain the Sarjana Komputer Degree

In Informatics Engineering Study Program

By:


NIM : 075314035

INFORMATICS ENGINEERING STUDY PROGRAM

DEPARTMENTS OF SCIENCE AND TECHNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2013


v

HALAMAN PERSEMBAHAN

“Life's full of ups and downs.

That's why we need inspirations

from time to time, to remind us about

how blessed we are,

how much God loves us and

how beautiful this life can be. “

Karya ini kupersembahkan untuk ....

Tuhan Yesus Kristus dan Bunda Maria , atas limpahan cinta kasihNya

Kedua Orang Tua, atas dukungan moril dan materiil yang diberikan

Semua Keluargaku , Sahabat , dan Teman-teman, atas dukungan dan

doa yang telah mereka berikan kepadaku.

--- Terimakasih Untuk Semuanya ---


vi

PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak

memuat karya atau bagian karya orang lain, kecuali yang telah saya sebutkan

dalam kutipan dan daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, Januari 2013

Penulis


25


vii

ABSTRAK

Algoritma Ants Colony System (ACS) adalah salah satu algoritma optimasi

yang dapat digunakan untuk memecahkan berbagai masalah optimasi. Salah satu

masalah yang dapat dipecahkan oleh algoritma ACS adalah Travelling Salesman

Problem (TSP). TSP adalah masalah pencarian rute optimal tanpa mengunjungi

tempat yang sama lebih dari satu kali, seperti menentukan rute terpendek

pengiriman barang.

Tujuan dari penelitian ini adalah menerapkan algoritma ACS untuk

menentukan rute terpendek pada studi kasus pengiriman barang P.T. Pos

Indonesia untuk domisili Yogyakarta. Aplikasi yang dibangun adalah untuk

penentuan rute terpendek. Hal-hal yang menjadi pertimbangan dalam mencari rute

terpendek adalah kecepatan rata-rata atau bobot waktu, kondisi jalan yang

digunakan, parameter algoritma ACS yaitu parameter probabilitas semut (q0),

pheromone awal (t0), parameter koefisien penguapan pheromone (p), parameter

yang mempertimbangkan kepentingan relatif dari informasi heuristic (b), tingkat

kepentingan relatif dari pheromone (a), dan banyak iterasi atau banyak semut (m).

Penelitian ini akan menguji berbagai kemungkinan perubahan parameter dan

iterasi. Dari hasil pengujian ternyata semakin besar nilai parameter t0 dan p serta

iterasi rute (m) maka rute semakin pendek. Di lain sisi semakin besar nilai

parameter b akan maka rute jauh dari pendek.

Hasil pengujian dari 4 titik yang berbeda yaitu tglu3, wch2, kb35, gkan5

adalah 25 menit dengan jarak 70 km dengan penggunaan parameter q0 adalah 0.1,

t0 adalah 0.01, p adalah 0.1, b adalah 2 dan a adalah 0.1.

Kata kunci : Ants Colony System, Travelling Salesman Problem, Pengiriman

Barang, Rute Terpendek.


viii

ABSTRACT

Ants Colony System Algorithm (ACS) is one of many algorithm optimalization

can be solving all kinds problem optimalization. One of many problem can be solving

by ACS Algorithm is Travelling Salesman Problem (TSP). TSP is problem searching

optimal route without visit same place over than one time, as determine shortest route

packet transporting.

Goal of this research is applying ACS algorithm to determine shortest route

packet transporting at study case P.T. Pos Indonesia for domicile Yogyakarta.

Application will building for determine shortest route. The condition will be

consideration in searching shortest route is speed average or weight time, street

condition, parameter of ACS algorithm is parameter ant probability (q0), initial

pheromone (t0), parameter coefficient pheromone evaporation (p), parameter that

considers the relative importance of the heuristic information (b), the relative

importance of the pheromone (a), and many iteration or many ants (m).

This research will be test with varied kinds possibility change of parameter and

iteration. From result of testing obviously more large value of parameter t0 and p

including route iteration (m) more and more short. other side more large value of

parameter b will be more and more far from short.

Test results from four different points, namely tglu3, wch2, kb35, gkan5 is 25

minutes with a distance of 70 km with the use of this parameter q0 is 0.1, t0 is 0.01, p

is 0.1, B is 2 and a is 0.1.

Keywords : Ants Colony System, Travelling Salesman Problem, Packet Transporting,

Shortest Route.


ix

LEMBAR PERNYATAAN PERSETUJUAN

PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS

Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma

Nama : F.X. Alfa Suryo Utomo

Nomor Mahasiswa : 075314035

Demi pengembangan ilmu pengetahuan, saya memberikan Kepada Perpustakaan

Universitas Sanata Dharma karya ilmiah saya yang berjudul :

Penerapan Algoritma Ants Colony System(ACS) Untuk

Menentukan Rute Terpendek Pengiriman Barang pada

P.T. Pos Indonesia

beserta perangkat yang diperlukan (bila ada). Dengan demikian saya memberikan

Kepada Perpustakaan Universitas Sanata Dharma hak untuk menyimpan,

mengalihkan dalam bentuk media lain, mengelolanya di internet atau media lain

untuk kepentingan akademis tanpa perlu meminta ijin dari saya maupun

memberikan royalti kepada saya selama tetap mencantumkan nama saya sebagai

penulis.

Demikian pernyataan ini yang saya buat dengan sebenarnya.

Dibuat di Yogyakarta

Pada tanggal : Januari 2013

Yang menyatakan,

(F.X. Alfa Suryo Utomo)

25


x

KATA PENGANTAR

Puji dan syukur kehadirat Tuhan Yang Maha Esa, karena pada akhirnya

penulis dapat menyelesaikan penelitian tugas akhir ini yang berjudul “Penerapan

Algoritma Ants Colony System(ACS) Untuk Menentukan Rute Terpendek

Pengiriman Barang pada P.T. Pos Indonesia”.

Penelitian ini tidak akan selesai dengan baik tanpa adanya dukungan,

semangat, dan motivasi yang telah diberikan oleh banyak pihak. Untuk itu,

penulis ingin mengucapkan terima kasih kepada:

1. Bapak Eko Hari Parmadi, S.Si., M.Kom. selaku dosen pembimbing serta

dekan Fakultas Sains dan Teknologi yang telah membantu dan

membimbing dalam penulisan tugas akhir.

2. Puspaningtyas Sanjoyo Adi S.T., M.T. selaku ketua program studi Teknik

Informatika yang bertindak sebagai dosen penguji yang telah berkenan

memberikan motivasi, kritik, dan saran yang telah diberikan kepada

penulis.

3. Drs. J. Eka Priyatma, M.Sc., Ph.D. selaku dosen penguji atas motivasi,

kritik dan saran yang telah diberikan kepada penulis.

4. Kedua orang tua, bapak Antonius Slamet dan ibu Sunarti atas perhatian,

kasih sayang, semangat dan dukungan yang tak henti-hentinya diberikan

kepada penulis.

5. Kekasih, Apriyanti Putri Lestari yang telah memberikan doa, semangat

dan dukungan sehingga penulis dapat menyelesaikan tugas akhir ini.

6. Para sahabat Atanasius Tendy, Fendi Dwi Fauzi, Thomas Tri Ardianto,

Yudy Pratama, Dionisius Wahyu, Hariyo Koco, Yohanes Christian Aji, Iip

Yulianto, Guido Mukti, Yosep P. Nugroho, Juventus Robing, Ignatius

Adhitya, Ryan Herdianto, Dominikus Adi, Ricky Andrianto, Sigit Adi

Susila, dan seluruh teman-teman TI angkatan 2007. Terima kasih atas

segala bantuan, semangat, dan kesedianaan untuk berbagi solusi dalam

penyelesaian tugas akhir ini.


xi

7. Para sahabat Febri Arif Saputra dan seluruh teman-teman. Terimakasih

atas semangat dan doa yang telah diberikan.

8. Serta semua pihak yang tidak dapat disebutkan satu persatu yang telah

membantu penulis dalam menyelesaikan tugas akhir ini.

Penelitian tugas akhir ini masih memiliki banyak kekurangan. Untuk itu,

penulis sangat membutuhkan saran dan kritik untuk perbaikan di masa yang akan

datang. Semoga penelitian tugas akhir ini dapat membawa manfaat bagi semua

pihak.

Yogyakarta, Januari 2013

Penulis


25


xii

DAFTAR ISI

Halaman Judul ..........................................................................................................i

Halaman Judul (Inggris).......................................................................................... ii

Halaman Persetujuan ............................................................................................. iii

Halaman Pengesahan .............................................................................................. iv

Halaman Persembahan ............................................................................................. v

Pernyataan Keaslian Karya ..................................................................................... vi

Abstrak ..................................................................................................................vii

Abstract ............................................................................................................... viii

Lembar Persetujuan Publikasi ................................................................................. ix

Kata Pengantar......................................................................................................... x

Daftar Isi................................................................................................................xii

Daftar Tabel .......................................................................................................... xvi

Daftar Gambar ..................................................................................................... xvii

Daftar Simbol ........................................................................................................ xx

Bab1 Pendahuluan ................................................................................................... 1

1.1 Latar Belakang Masalah ..................................................................................... 1

1.2 Rumusan Masalah .............................................................................................. 3

1.3 Batasan Masalah ................................................................................................ 3

1.4 Tujuan Masalah.................................................................................................. 3

1.5 Manfaat Penelitian ............................................................................................. 3

1.6 Metodologi Penelitian ........................................................................................ 4

1.7 Sistematika Penulisan......................................................................................... 4


xiii

Bab II Landasan Teori ............................................................................................ 7

2.1 Graf ................................................................................................................... 7

2.1.1 Definisi Graf ................................................................................................... 7

2.1.2 Definisi Walk, Trail, Path dan Cycle ............................................................... 8

2.1.3 Graf Eulerian dan Graf Hamiltonian ................................................................ 9

2.1.4 Macam-macam Graf Menurut Arah dan Bobotnya .......................................... 9

2.2 Optimasi .......................................................................................................... 11

2.2.1 Definisi Optimasi .......................................................................................... 11

2.2.2 Definisi Nilai Optimal ................................................................................... 12

2.2.3 Macam-macam Permasalahan Optimisasi ...................................................... 12

2.2.4 Permasalahan Rute Terpendek....................................................................... 12

2.2.5 Penyelesaian Masalah Optimisasi .................................................................. 13

2.3 Travelling Salesman Problem (TSP)................................................................. 13

2.4 Algoritma Semut .............................................................................................. 16

2.4.1 Sejarah Algoritma Semut .............................................................................. 16

2.4.2 Cara Kerja Algoritma Semut Mencari Jalur Optimal ..................................... 16

2.4.3 Definisi Ants Colony System ........................................................................ 17

2.4.4 Tahapan Ants Colony System (ACS) ............................................................ 17

2.5 Cara Kerja Algoritma Ants Colony System ...................................................... 20

2.6 Analisis Algoritma Semut untuk Mencari Nilai Optimal .................................. 22

2.7 Analisis Parameter Pada Algoritma ACS .......................................................... 25

2.8 Contoh Penyelesaian Masalah TSP dengan Metode Ants Colony System ........ 27

Bab III Analisis & Desian ...................................................................................... 33

3.1 Identifikasi Sistem ........................................................................................... 33

3.2 Analisis Sistem ................................................................................................ 34

3.2.1 Analisis Data Awal ....................................................................................... 34

3.3 Analisis Kebutuhan Sistem............................................................................... 36


xiv

3.3.1 Diagram Use Case ......................................................................................... 36

3.3.2 Narasi Use Case ............................................................................................ 37

3.4 Perancangan Umum Sistem .............................................................................. 45

3.4.1 Masukan Sistem ............................................................................................ 45

3.4.2 Proses Sistem ............................................................................................... 46

3.4.3 Keluaran Sistem ........................................................................................... 61

3.4.4 Diagram Aktifitas ......................................................................................... 62

3.4.4.1 Diagram Aktifitas Update Data Kondisi Jalan ............................................ 62

3.4.4.2 Diagram Aktifitas Ubah Data Kecepatan .................................................... 63

3.4.4.3 Diagram Aktifitas Ubah Data Account ....................................................... 63

3.4.4.4 Diagram Aktifitas Update Dara Pengirim Penerima .................................... 64

3.4.4.5 Diagram Aktifitas Input Data Pengirim Penerima ....................................... 65

3.4.4.6 Diagram Aktifitas Hapus Data Pengirim Penerima ..................................... 66

3.4.4.7 Diagram Aktifitas Ubah Kondisi Pengiriman .............................................. 67

3.4.4.8 Diagram Aktifitas Perhitungan Pencarian Rute ........................................... 68

3.5 Perancangan Basis Data ................................................................................... 68

3.5.1 Entity Relationship Diagram ......................................................................... 68

3.5.2 Perancangan Fisikal ...................................................................................... 70

3.6 Diagram Kelas Analisis & Diagram Sekuen ..................................................... 74

3.6.1 Diagram Kelas Analisis & Diagram Sekuen Use Case Login ......................... 74

3.6.2 Diagram Kelas Analisis & Diagram Sekuen Use Case Logout ....................... 75

3.6.3 Diagram Kelas Analisis & Diagram Sekuen Use Case Mengubah Account ... 77

3.6.4 Diagram Kelas Analisis & Diagram Sekuen Use Case Mengisi Data Pengirim

Penerima ................................................................................................................ 78

3.6.5 Diagram Kelas Analisis & Diagram Sekuen Use Case Mengubah Data

Pengirim Penerima................................................................................................. 80

3.6.6 Diagram Kelas Analisis & Diagram Sekuen Use Case Menghapus Data

Pengirim Penerima................................................................................................. 82


xv

3.6.7 Diagram Kelas Analisis & Diagram Sekuen Use Case Melihat Daftar

Pengiriman ............................................................................................................ 84

3.6.8 Diagram Kelas Analisis & Diagram Sekuen Use Case Mengupdate Kondisi

Jalan ...................................................................................................................... 86

3.6.9 Diagram Kelas Analisis & Diagram Sekuen Use Case Mengubah Kecepatan

Jalan ...................................................................................................................... 87

3.7 Diagram Kelas Desain...................................................................................... 89

3.8 Perancangan Struktur Data ............................................................................... 93

3.9 Perancangan Antar Muka Sistem ...................................................................... 94

Bab IV Implementasi Program .............................................................................. 97

4.1 Perangkat Kebutuhan Sistem ........................................................................... 97

4.2 Uji Validasi Sistem .......................................................................................... 97

4.3 Implementasi Antar Muka Pengguna ................................................................ 97

4.4 Implementasi Diagram Kelas ......................................................................... 113

Bab V Analisis Hasil Implementasi ..................................................................... 120

Bab VI Penutup .................................................................................................. 126

6.1 Kesimpulan .................................................................................................... 126

6.2 Saran .............................................................................................................. 127

Daftar Pustaka .................................................................................................... 128

Lampiran1 .......................................................................................................... 129


xvi

DAFTAR TABEL

Tabel 1.1 Perbandingan Algoritma ACS……….....................................................2

Tabel 2.1Rute Pilihan Kota A ke Kota G………...................................................12

Tabel 2.2 Matriks Jarak..........................................................................................28

Tabel 2.3 Matriks Pheromone Awal .....................................................................28

Tabel 2.4 Matriks Invers…...................................................................................29

Tabel 2.5 Hasil Persamaan Probabilitas.................................................................29

Tabel 2.6 Matriks Hasil Update Pheromone Lokal A ke E....................................30

Tabel 2.7 Matriks Hasil Update Pheromone Lokal A, E, F,D,B,C........................30

Tabel 2.8 Matriks Hasil Update Pheromone Lokal A,E, F,D,B,C,A.....................31

Tabel 2.9 Matriks Hasil Update Pheromone Global..............................................31

Tabel 3.1 Data jarak peta.......................................................................................34

Tabel 3.2 Data Volume Kendaraan.......................................................................36


xvii

DAFTAR GAMBAR

Gambar 2.1 Contoh Graf G…………………………………….;……....................7

Gambar 2.2 Sisi Ganda dan Loop……………………………………………........8

Gambar 2.3 Contoh Graf G & Sub Graf G............................................................. 8

Gambar 2.4 Graf Hamilton & Graf Eulerian…………...........................................9

Gambar 2.5 Graf Berarah dan Berbobot................................................................10

Gambar 2.6 Graf Tidak Berarah dan Berbobot……………………......................10

Gambar 2.7 Graf Berarah dan Tidak Berbobot......................................................11

Gambar 2.8 Graf Tidak Berarah dan Tidak Berbobot............................................11

Gambar 2.9 Ilustrasi Masalah TSP………….........................................................14

Gambar 2.10 Graf ABCD……………………......................................................15

Gambar 2.11 Sirkuit Hamilton...............................................................................15

Gambar 2.12 Algoritma ACS.................................................................................21

Gambar 2.13 Lintasan Awal Semut menuju tempat makanan…….......................22

Gambar 2.14 Lintasan Semut menuju sarang………............................................23

Gambar 2.15 Lintasan Awal Semut menuju makanan iterasi ke 2.......................23

Gambar 2.16 Lintasan Semut menuju sarang iterasi ke 2....................................24

Gambar 2.17 Lintasan Optimal semut menuju tempat makanan...........................24

Gambar 2.18 ACS dengan beragam nilai β...........................................................25

Gambar 2.19 ACS dengan beragam parameter semut…………..........................26

Gambar 2.20 ACS dengan beragam parameter ρ..................................................26

Gambar 2.21 ACS dengan beragam parameter q0................................................27

Gambar 2.22 Contoh Graf lengkap……...............................................................27

Gambar 2.23 Hasil Rute Algoritma ACS 1 semut…………………....................32

Gambar 3.1 Diagram Use Case.............................................................................36

Gambar 3.2 Peta Per Cluster………..………………….......................................46

Gambar 3.3 Set Node Awal…………..................................................................47

Gambar 3.4 Set Wilayah Pengiriman....................................................................48

Gambar 3.5 Set Node Pengiriman.........................................................................49

Gambar 3.6 Mencari Urutan Cluster.....................................................................50


xviii

Gambar 3.7 Pencarian Rute Cluster ke 0..............................................................51

Gambar 3.8 Pencarian Rute Cluster ke i...............................................................52

Gambar 3.9 Pencarian Rute Cluster Akhir............................................................53

Gambar 3.10 Set Destinasi Ulang dan Pencarian rute semut ke n........................54

Gambar 3.11 Pencarian Rute Terbaik...................................................................55

Gambar 3.12 Proses Inisialisasi Status1...............................................................56

Gambar 3.13 Proses Inisialisasi Status2...............................................................57

Gambar 3.14 Proses Update Pheromone Lokal....................................................58

Gambar 3.15 Proses Menentukan pheromone yang akan di update di pheromone

global………………………………………….....................................................59

Gambar 3.16 Proses Update Pheromone Global..................................................60

Gambar 3.17 Diagram Konteks............................................................................61

Gambar 3.18 Diagram Aktifitas Update Kondisi Jalan........................................62

Gambar 3.19 Diagram Aktifitas Update Kecepatan.............................................63

Gambar 3.20 Diagram Aktifitas Update Data Account........................................63

Gambar 3.21 Diagram Aktifitas Update Data Pengirim Penerima.......................64

Gambar 3.22 Diagram Aktifitas Insert Data Pengirim Penerima.........................65

Gambar 3.23 Diagram Aktifitas Hapus Data Pengirim Penerima........................66

Gambar 3.24 Diagram Aktifitas Ubah Status Pengiriman....................................67

Gambar 3.25 Diagram Aktifitas Perhitungan Pengiriman Rute............................67

Gambar 3.26 ERD Database System....................................................................69

Gambar 3.27 Diagram Kelas Analisis Use Case Login........................................75

Gambar 3.28 Diagram Sekuen Use Case Login……………………….…….......75

Gambar 3.29 Diagram Kelas Analisis Use Case Logout......................................76

Gambar 3.30 Diagram Sekuen Use Case Logout.................................................76

Gambar 3.31 Diagram Kelas Analisis Use Case Mengubah Account……..........78

Gambar 3.32 Diagram Sekuen Use Case Mengubah Account.............................78

Gambar 3.33 Diagram Kelas Analisis Use Case Mengisi Data Pengirim Penerima

……………………………………………………………………….……..........80

Gambar 3.34 Diagram Sekuen Use Case Mengisi Data Pengirim Penerima........80

Gambar 3.35 Diagram Kelas Analisis Use Case Mengubah Data Pengirim

Penerima………………………………………………………………………….82


xix

Gambar 3.36 Diagram Sekuen Use Case Mengubah Data Pengirim

Penerima.................................................................................................................82

Gambar 3.37 Diagram Kelas Analisis Use Case Menghapus Data Pengirim

Penerima ……........................................................................................................84

Gambar 3.38 Diagram Sekuen Use Case Menghapus Data Pengirim Penerima..84

Gambar 3.39 Diagram Kelas Analisis Use Case Melihat Daftar Pengiriman …..85

Gambar 3.40 Diagram Sekuen Use Case Melihat Daftar Pengiriman..................86

Gambar 3.41 Diagram Kelas Analisis Use Case Mengupdate Kondisi Jalan …..87

Gambar 3.42 Diagram Sekuen Use Case Mengupdate Kondisi Jalan..................87

Gambar 3.43 Diagram Kelas Analisis Use Case Mengubah Kecepatan Jalan …88

Gambar 3.44 Diagram Sekuen Use Case Mengubah Kecepatan Jalan.................88

Gambar 3.45 Diagram Kelas Keseluruhan............................................................89

Gambar 3.46 Halaman Utama Staff Bagian Distribusi.........................................94

Gambar 3.47 Halaman Daftar Pengiriman............................................................94

Gambar 3.48 Halaman Hasil Rute pengiriman.....................................................95

Gambar 3.49 Halaman Utama Administrator.......................................................95

Gambar 3.50 Halaman Ubah Kondisi Jalan.........................................................96

Gambar 4.1 Halaman Login.................................................................................98

Gambar 4.2 Tampilan Login Jika salah...............................................................99

Gambar 4.3 Halaman Utama Staff Bagian Distribusi.........................................100

Gambar 4.4 Halaman Pengirim Penerima...........................................................101

Gambar 4.5 Halaman Daftar Pengiriman............................................................104

Gambar 4.6 Halaman Ubah Account..................................................................105

Gambar 4.7 Halaman Utama Administrator.......................................................107

Gambar 4.8 Halaman Ubah Bobot......................................................................108

Gambar 4.9 Halaman Ubah Kondisi Jalan..........................................................111

Gambar 4.10 Halaman Ubah Akun Administrator.............................................112


xx

DAFTAR SIMBOL

q = bilangan pecahan acak

q0 = probabilitas semut melakukan eksplorasi pada setiap tahapan

τ (t,u) = nilai dari jejak pheromone pada jarak (t,u)

η (t,u) = invers jarak antara titik t dan u

β = parameter yang mempertimbangkan kepentingan relative dari informasi

heuristic

Lnn = panjang tur yang diperoleh

C = jumlah lokasi

ρ = koefisien penguapan pheromone

∆ τ = perubahan pheromone

Lgb = panjang jalur terpendek pada akhir siklus

α = tingkat kepentingan relatif dari pheromone


1

BAB I

PENDAHULUAN

1.1 Latar Belakang Masalah

P.T. Pos Indonesia adalah perusahaan pelayanan jasa terbesar yang

dimiliki Negara Indonesia. Seperti di ketahui selain Pos Indonesia, perusahaan

asing yang memiliki bisnis jasa pelayanan yang sama antara lain DHL, FEDEX,

TIKI, JNE, dll. Maka untuk membangkitkan cinta tanah air sebaiknya kita

menggunakan jasa dalam negeri. P.T. Pos Indonesia untuk melakukan jasa

pelayanan komunikasi, logistik, transaksi keuangan, dan layanan pos lainnya. Dari

beberapa jasa pelayanan, pelayanan logistic khususnya jasa pengiriman barang

memiliki potensi paling besar bisnisnya, P.T. Pos Indonesia menggarapnya

dengan maksimal untuk meningkatkan kualitas serta mutu pelayanan masyarakat

sehingga dapat bersaing dengan perusahaan lainnya melalui pelayanan on time

every time. Pelayanan on time every time ini adalah pelayanan kilat pengiriman

paket sampai dalam 1 hari. Masalah yang muncul ketika akan meningkatkan

pelayanan pengiriman barang on time every time ini adalah rute yang dilalui

pengiriman barang ini tidak efisien dari sisi jarak dan waktu, misalnya suatu

ketika kendaraan pengiriman barang melalui jalur yang sama lebih dari sekali. Hal

ini membuat waktu dan jarak menjadi membengkak yang berakibat menjadi

tingginya biaya transportasi dan kualitas pelayanan yang kurang memuaskan

masyarakat. Permasalahan ini dapat dikategorikan menjadi Travelling Salesman

Problem (TSP) karena kendaraan pengiriman barang dari lokasi pusat harus


2

menuju semua titik lokasi barang yang akan dikirim dan kembali lagi ke lokasi

tersebut, tetapi tidak melalui jalur yang sama.

Ants Colony System (ACS) adalah algoritma optimasi untuk mendapatkan

hasil yang optimal. ACS merupakan penelitian yang dilakukan oleh M. Dorigo

dan L.M. Gambardella (1997) dalam penyelesaian TSP, terbukti bahwa algoritma

ACS mampu mendapatkan tur terbaik dibandingkan dengan algoritma genetic

(GA), evolutioning Programming (EP), Simulated Anneling (SA), dan Anneling-

Genetic Algorithm (AG). Perbandingan dari berbagai macam algoritma tercantum

dalam tabel 1.1 dibawah ini.

Tabel 1.1 Perbandingan Algoritma ACS

Kasus ACS GA EP SA AG Optimum

Oliver30

(30-city

problem)

420

(423.74)

[830]

421

(N/A)

[3,200]

420

(423.74)

[40,000]

424

(N/A)

[24,617]

420

(N/A)

[12,620]

420

(423.74)

Eil50

(50-city

problem)

425

(427.96)

[1,830]

428

(N/A)

[25,000]

426

(427.86)

[100,000]

443

(N/A)

[68,512]

436

(N/A)

[28,111]

425

(N/A)

Eil75

(75-city

problem)

535

(542.31)

[3,480]

545

(N/A)

[80,000]

542

(549.18)

[325,000]

580

(N/A)

[173,250]

561

(N/A)

[95,506]

535

(N/A)

KroA100

(100-city

problem)

21,282

(21,285.44)

[4,820]

21,761

(N/A)

[103,000]

N/A

(N/A)

[N/A]

N/A

(N/A)

[N/A]

N/A

(N/A)

[N/A]

21,282

(N/A)

Pada tabel 1.1 akan dibandingkan beberapa algoritma dengan kasus yang

sama akan masing-masing menghasilkan panjang tur terbaik dalam bentuk

bilangan integer, panjang tur terbaik dalam bentuk bilangan real (yang ada pada

bilangan dalam kurung) dan jumlah tur yang diperlukan untuk menghasilkan tur

terbaik pada bilangan integer (yang ada pada bilangan dalam kurung kurawal).

Nama kasus adalah Oliver30, Eil50, Eil75, KroA100. Oliver30 adalah kasus yang

ditemukan oleh (Oliver, Smith, Holland, 1987), sedangkan Eil50, Eil75, KroA100


3

ditemukan oleh (Eilon, Watson-Gandy, Christofides, 1969). Dari Table 1.1

bilangan yang paling optimum adalah yang di cetak tebal tiap kasus-nya.

Akhirnya yang paling optimal adalah ACS dan EP melebihi GA, SA, AG.

Untuk itu penelitian tugas akhir ini menerapkan algoritma Ant Colony

System (ACS) sebagai system usulan dalam pemilihan untuk mendapatkan rute

terpendek pada pengiriman barang PT. Pos Indonesia Yogyakarta.

1.2 Rumusan Masalah

Rumusan masalah untuk tugas akhir ini adalah menetukan rute terpendek

pengiriman barang pada P.T. Pos Indonesia menggunakan algoritma ACS.

1.3 Batasan Masalah

Pembatasan masalah untuk tugas akhir ini antara lain:

Titik awal (vertex awal) pencarian adalah kantor pos.

Tiap jalur/rute dibangun dengan 1 kali dilewati.

Peta hanya terbatas di kota Yogyakarta.

Perangkat lunak menggunakan pemrograman java dan database mysql.

1.4 Tujuan Penelitian

Adapun tujuan dari penulisan tugas akhir ini adalah untuk menentukan

rute pengiriman barang menggunakan algoritma Ant Colony System (ACS) dalam

pengiriman barang di PT. Pos Indonesia, Yogyakarta.

1.5 Manfaat Penelitian

Sedangkan manfaat dari penelitian ini adalah:

1. Mendapatkan rute pengiriman barang pada PT. Pos Indonesia Yogyakarta.

2. Mengimplementasikan Ant Colony System pada masalah menentukan rute

pengiriman barang.


4

1.6 Metodologi Penelitian

Penelitian ini dilakukan menggunakan metode Waterfall, tahap-tahap nya

antara lain:

1. Studi literatur

Menggunakan berbagai macam literatur yang berhubungan dengan

Graph, Ant Colony System, Optimasi dan Travelling Salesman Problem.

2. Analisis

Pada tahap ini dilakukan analisis terhadap ant colony system dan

Travelling Salesman Problem.

3. Perancangan Sistem

Pada tahap ini dirancang suatu system dengan algoritma ant colony

system yang dapat memecahkan Travelling Salesman Problem pada rute

pengiriman barang.

4. Implementasi Perangkat Lunak

Pada tahap ini algoritma diimplementasikan ke bahasa

pemrograman java.

5. Pengujian

Setelah proses pengkodean selesai maka akan dilakukan proses

pengujian terhadap program yang dibuat untuk mengetahui apakah

program sudah sesuai dengan maksud dan tujuan algoritma.

1.7 Sistematika Penulisan

Sistematika penulisan yang akan diuraikan dalam skripsi ini terbagi dalam

beberapa bab yang akan dibahas sebagai berikut:


5

BAB 1: Pendahuluan

Bab ini berisi pembahasan masalah umum yang meliputi latar

belakang masalah, rumusan masalah, batasan masalah, tujuan penelitian,

manfaat penelitian, metodologi penelitian dan sistematika penulisan.

BAB 2: Landasan Teori

Bagian ini memuat landasan teori yang berfungsi sebagai sumber

atau alat dalam memahami permasalahan yang berkaitan dengan teori

graph, optimasi, Travelling Salesman Problem (TSP) dan teori mengenai

ant colony system (ACS).

BAB 3: Rancangan Perangkat Lunak

Bagian ini memuat desain rancangan perangkat lunak dengan

metode waterfall. Desain disini dalam bentuk kasar sebagai dasar untuk

penyelesaian masalah.

BAB 4: Implementasi Perangkat Lunak

Bagian ini memuat implementasi dari perangkat lunak

sesungguhnya. Berisi dengan data-data yang disiapkan atau yang akan

diolah.

BAB 5: Analisa

Bab ini membahas tentang analisis kinerja dari perangkat lunak.

Pada bagian ini mengulas analisis hasil pengujian terhadap sistem yang

dibandingkan dengan kebenaran dan kesesuaiannya dengan hasil yang

didapat.


6

BAB 6: Penutup

Bab ini meliputi kesimpulan dan saran dari tugas akhir yang

dibuat.


7

BAB II

LANDASAN TEORI

Untuk mendukung penelitian ini diperlukan beberapa landasan teori dan

konsep-konsep yang relevan. Landasan teori dalam penelitian ini meliputi

pengertian graf, travelling salesman problem (TSP) dan ants colony system

(ACS).

2.1 Graf

2.1.1 Definisi Graf

Definisi graf menurut Wilson, R. J dan Watkhins, J. J, (1990) adalah

“Suatu Graf G terdiri atas himpunan yang tidak kosong dari elemen – elemen

yang disebut titik (vertek), dan suatu daftar pasangan vertek yang tidak terurut

disebut sisi (edge). Himpunan vertek dari suatu Graf G dinotasikan dengan V,

dan daftar himpunan edge dari Graf tersebut dinotasikan dengan E. Untuk

selanjutnya suatu Graf G dapat dinotasikan dengan G = (V, E).”(Gambar2.1).

Gambar 2.1 Contoh Graf G

Sedangkan “Dua edge atau lebih yang menghubungkan pasangan vertek

yang sama disebut sisi ganda, dan sebuah edge yang mengubungkan sebuah

vertek ke dirinya sendiri disebut loop.” (Gambar 2.2).


8

Gambar 2.2 Sisi ganda dan loop

Selanjutnya “Suatu subGraf G’ adalah suatu himpunan pasangan

berurutan (V’, E’) dimana V’ merupakan himpunan bagian dari V dan E’ adalah

himpunan bagian dari E. Dengan kata lain, subGraf dari G adalah suatu Graf

yang semua verteknya anggota V dan semua edgenya anggota E. Jika G suatu

Graf terhubung seperti pada gambar 2.2, dengan V = {1, 2, 3, 4} dan E = {(1,3),

(1,4), (2,4), (3,3), (3,4), (4,2)}.” (Gambar 2.3).

Gambar 2.3 Contoh Graf G dan subGraf G’

2.1.2 Definisi Walk, Trail, Path dan Cycle

Definisi walk menurut Evans, J. R dan Edward, M (1992) adalah “Suatu

walk (jalan) dalam Graf G adalah barisan vertek – vertek dan edge – edge yang

dimulai dan diakhiri oleh suatu vertek. Panjang suatu walk dihitung berdasarkan

jumlah edge dalam walk tersebut”.

Definisi trail menurut Wilson, R. J dan Watkhins, J. J (1990) adalah “Trail

adalah semua edge (tetapi tidak perlu semua vertek) adalah suatu walk berbeda”.

Definisi path menurut Wilson, R. J dan Watkhins, J. J (1990) adalah “Path

adalah semua vertek pada trail itu berbeda”.


9

Definisi cycle menurut Wilson, R. J dan Watkhins, J. J (1990) adalah

“semua edgenya berbeda, maka walk itu disebut trail tertutup (close trail).

Kemudian close trail dengan semua vertek berbeda disebut cycle.”

2.1.3 Graf Eulerian dan Graf Hamiltonian

Definisi graf Eulerian dan Hamilton menurut Wilson, R. J dan Watkhins,

J. J (1990) adalah “Graf terhubung G merupakan graf Euler (Eulerian) jika ada

close trail yang memuat setiap edge dari G. Trail semacam ini disebut trail Euler.

Graf terhubung G merupakan Graf Hamilton (Hamiltonian)jika ada cycle yang

memuat setiap vertek dari G. Cycle semacam ini disebut cycle Hamilton”.

Gambar 2.4 Graf Hamilton dan Graf Euler

Graf (i) merupakan Graf Euler dan Graf Hamilton,

Graf (ii) merupakan Graf Euler dan trail Eulernya bcgfeb,

Graf (iii) merupakan Graf Hamilton dengan cycle Hamiltonnya bcgefb.

2.1.4 Macam – macam Graf Menurut arah dan Bobotnya

Menurut arah dan bobotnya, Graf dibagi menjadi empat bagian,yaitu :

1. Graf berarah dan berbobot : setiap edge mempunyai arah (yang

ditunjukkan dengan anak panah) dan bobot. Gambar 2.5 adalah contoh

Graf berarah dan berbobot yang terdiri dari tujuh vertek yaitu vertek A, B,

C, D, E, F, G. Vertek A mempunyai dua edge yang masing – masing

menuju ke vertek B dan vertek C, vertek B mempunyai tiga edge yang


10

masing – masing menuju ke vertek C, vertek D dan vertek E. Bobot antara

vertek A dan vertek B pun telah di ketahui.

Gambar 2.5 Graf berarah dan berbobot

2. Graf tidak berarah dan berbobot : setiap edge tidak mempunyai arah tetapi

mempunyai bobot. Gambar 2.6 adalah contoh Graf tidak berarah dan

berbobot. Graf terdiri dari tujuh vertek yaitu vertek A, B, C, D, E, F, G.

Vertek A mempunyai dua edge yang masing – masing berhubungan

dengan vertek B dan vertek C, tetapi dari masing – masing edge tersebut

tidak mempunyai arah. Edge yang menghubungkan vertek A dan vertek B

mempunyai bobot yang telah diketahui begitu pula dengan edge – edge

yang lain.

Gambar 2.6 Graf tidak berarah dan berbobot

3. Graf berarah dan tidak berbobot : setiap edge mempunyai arah tetapi tidak

mempunyai bobot. Gambar 2.7 adalah contoh Graf berarah dan tidak

berbobot.


11

Gambar 2.7 Graf berarah dan tidak berbobot

4. Graf tidak berarah dan tidak berbobot : setiap edge tidak mempunyai arah

dan tidak terbobot. Gambar 2.8 adalah contoh Graf tidak berarah dan tidak

berbobot.

Gambar 2.8 Graf tidak berarah dan tidak berbobot

2.2 Optimisasi

2.2.1 Definisi Optimisasi

Definisi Optimisasi menurut Wardy (2007) adalah “suatu proses untuk

mencapai hasil yang optimal (nilai efektif yang dapat dicapai). Dalam disiplin

matematika optimisasi merujuk pada studi permasalahan yang mencoba untuk

mencari nilai minimal atau maksimal dari suatu fungsi riil. Untuk dapat

mencapai nilai optimal baik minimal atau maksimal tersebut, secara sistematis

dilakukan pemilihan nilai variabel integer atau riil yang akan memberikan solusi

optimal”.


12

2.2.2 Definisi Nilai Optimal

Definisi Nilai optimal menurut Wardy (2007) adalah “nilai yang didapat

melalui suatu proses dan dianggap menjadi solusi jawaban yang paling baik dari

semua solusi yang ada”. Nilai optimal yang didapat dalam optimisasi dapat

berupa besaran panjang, waktu, jarak, dan lain-lain.

2.2.3 Macam – macam Permasalahan Optimisasi

Permasalahan optimisasi adalah permasalahan yang sangat kompleks.

Berikut ini adalah termasuk beberapa persoalan optimisasi :

1. Menentukan rute terpendek dari suatu tempat ke tempat yang lain.

2. Menentukan jumlah pekerja seminimal mungkin untuk melakukan suatu

proses produksi agar pengeluaran biaya pekerja dapat diminimalkan dan hasil

produksi tetap maksimal.

3. Mengatur rute kendaraan umum agar semua lokasi dapat dijangkau.

4. Mengatur routing jaringan kabel telepon agar biaya pemasangan kabel tidak

terlalu besar dan penggunaannya tidak boros.

2.2.4 Permasalahan Rute Terpendek

Masalah rute terpendek merupakan masalah yang berkaitan dengan

penentuan edge-edge dalam sebuah jaringan yang membentuk rute terdekat antara

sumber dan tujuan. Tujuan dari permasalahan rute terpendek adalah mencari rute

yang memiliki jarak terdekat antara titik asal dan titik tujuan.

Dari contoh gambar 2.8 diatas, jika kita dari kota A ingin menuju Kota G.

Untuk menuju kota G, dapat dipilih beberapa rute yang tersedia :

Tabel 2.1 Rute Pilihan Kota A ke Kota G

A →B →C →D →E →G , A →B →C →D →F →G A →B →C →D →G

A →B →C →F →G A →B →D →E →G A →B →D →F →G

A →B →D →F →G A →B →D →G A →B →E →G

A →C →D →E →G A →C →D →F →G A →C →D →G

A →C →F →G


13

Berdasarkan data diatas, dapat dihitung rute terpendek dengan mencari

jarak antara rute-rute tersebut. Apabila jarak antar rute belum diketahui, jarak

dapat dihitung berdasarkan koordinat kota-kota tersebut, kemudian menghitung

jarak terpendek yang dapat dilalui.

2.2.5 Penyelesaian Masalah Optimisasi

Masalah pencarian rute terpendek terdapat dua metode penyelesaian, yaitu

metode konvensional dan metode heuristik. Metode konvensional dihitung dengan

perhitungan matematis biasa, sedangkan metode heuristik dihitung dengan

menggunakan system pendekatan.

Definisi metode konvensional menurut Mutakhiroh (2007) adalah “metode

yang menggunakan perhitungan matematika eksak. Ada beberapa metode

konvensional yang biasa digunakan untuk melakukan pencarian rute terpendek,

diantaranya algoritma Djikstra, algoritma Floyd-Warshall, dan algoritma

Bellman- Ford”.

Definisi metode heuristik menurut Mutakhiroh (2007) adalah “suatu

metode yang menggunakan system pendekatan dalam melakukan pencarian

dalam optimasi. Adabeberapa algoritma pada metode heuristik yang biasa

digunakan dalampermasalahan optimasi, diantaranya Algoritma Genetika, Ant

Colony Optimization, logika Fuzzy, jaringan syaraf tiruan, Tabu

Search,Simulated Annealing, dan lain-lain”

2.3 Traveling Salesman Problem (TSP)

Definisi permasalahan TSP adalah permasalahan dalam mencari jarak

minimal sebuah tour tertutup terhadap sejumlah n kota dimana kota-kota yang ada

hanya dikunjungi sekali.

Masalah Travelling Salesman Problem (TSP) adalah salah satu contoh

yang paling banyak dipelajari dalam combinatorial optimization. Masalah ini

mudah untuk dinyatakan tetapi sangat sulit untuk diselesaikan. TSP termasuk

kelas NP-Hard problem dan tidak dapat diselesaikan secara optimal dalam

Polynomial computation time dengan algoritma eksak. Bila diselesaikan secara


14

eksak waktu komputasi yang diperlukan akan meningkat secara eksponensial

seiring bertambah besarnya masalah.

Inti dari permasalahan Travelling Salesmen Problem (TSP) adalah

menemukan atau mencari jarak dan rute terpendek. Travelling Salesmen

Problem (TSP) juga merupakan masalah yang terkenal dalam teori graf yang

mana graf itu sendiri terdiri dari berbagai jenis, diantaranya graf sederhana, graf

tak sederhana, selain itu juga ada graf berarah dan tidak berarah. Graf sederhana

adalah graf yang tidak memiliki sisi ganda dan juga gelang. Sisi ganda merupakan

kondisi ketika dua buah simpul memiliki lebih dari satu sisi. Sisi gelang adalah

ketika ada sisi yang berasal dari satu simpul dan kembali pada simpul tersebut.

Sedangkan graf tak sederhana adalah graf yang memiliki sisi ganda dan/atau

gelang. Graf berarah merupakan graf yang setiap sisinya memiliki orientasi arah

dari suatu simpul ke simpul lainnya. Sedangkan graf tidak berarah merupakan graf

yang setiap sisinya tidak memiliki orientasi arah dari suatu simpul ke simpul

lainnya.

Dalam sebuah Graf, TSP digambarkan seperti gambar 2.9 dibawah ini :

Gambar 2.9 Ilustrasi masalah TSP

Berikut adalah contoh kasus TSP: “Diberikan sejumlah kota dan jarak

antar kota. Tentukan sirkuit terpendek yang harus dilalui oleh seorang pedagang

bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota

tepat satu kali dan kembali lagi ke kota asal keberangkatan.”


15

Apabila kita mengubah contoh kasus tersebut menjadi persoalan pada

Graf, maka dapat dilihat bahwa kasus tersebut adalah bagaimana menentukan

sirkuit Hamilton yang memiliki bobot minimum pada Graf tersebut.

Seperti di ketahui, bahwa untuk mencari jumlah sirkuit Hamilton didalam

Graf lengkap dengan n vertek adalah : (n - 1)!/2.

Gambar 2.10 Graf ABCD

Pada gambar 2.10 diatas, Graf memiliki (4−1)!

2 = 3 sirkuit Hamilton, yaitu:

L1 = (A,B,C,D,A) atau (A,B,C,D,A) => panjang = 10 + 12 + 8 + 15 = 45

L2 = (A,C,D,B,A) atau (A,B,D,C,A) => panjang = 12 + 5 + 9 + 15 = 41

L3 = (A,C,B,D,A) atau (A,D,B,C,A) => panjang = 10 + 5 + 9 + 8 = 32

Gambar 2.11 Sirkuit Hamilton

Pada gambar 2.11 diatas terlihat jelas bahwa sirkuit Hamilton terpendek

adalah L3 = (A, C, B, D, A) atau (A, D, B, C, A) dengan panjang sirkuit = 10 + 5 +

9 + 8 = 32. Jika jumlah vertek n = 20 akan terdapat (19!)/2 sirkuit Hamilton atau

sekitar 6 × 1016 penyelesaian.


16

2.4 Algoritma Semut

2.4.1 Sejarah Algoritma Semut

Algoritma semut diperkenalkan oleh Moyson dan Manderick dan secara

meluas dikembangkan oleh Marco Dorigo, merupakan teknik probabilistik untuk

menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui

grafik. Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari

koloninya menuju makanan.

2.4.2 Cara Kerja Algoritma Semut Mencari Jalur Optimal

Pada dunia nyata, semut berkeliling secara acak, dan ketika menemukan

makanan mereka kembali ke koloninya sambil memberikan tanda dengan jejak

feromon. Jika semut-semut lain menemukan jalur tersebut, mereka tidak akan

bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut, kembali dan

menguatkannya jika pada akhirnya merekapun menemukan makanan.

Seiring waktu, bagaimanapun juga jejak feromon akan menguap dan akan

mengurangi kekuatan daya tariknya. Lebih lama seekor semut pulang pergi

melalui jalur tersebut, lebih lama jugalah feromon menguap. Sebagai

perbandingan, sebuah jalur yang pendek akan berbaris lebih cepat, dan dengan

demikian kerapatan feromon akan tetap tinggi karena terletak pada jalur secepat

penguapannya. Penguapan feromon juga mempunyai keuntungan untuk mencegah

konvergensi pada penyelesaian optimal secara lokal. Jika tidak ada penguapan

sama sekali, jalur yang dipilih semut pertama akan cenderung menarik secara

berlebihan terhadap semut-semut yang mengikutinya. Pada kasus yang demikian,

eksplorasi ruang penyelesaian akan terbatasi.

Oleh karena itu, ketika seekor semut menemukan jalur yang bagus (jalur

yang pendek) dari koloni ke sumber makanan, semut lainnya akan mengikuti jalur

tersebut, dan akhirnya semua semut akan mengikuti sebuah jalur tunggal. Ide

algoritma koloni semut adalah untuk meniru perilaku ini melalui 'semut tiruan'

berjalan seputar grafik yang menunjukkan masalah yang harus diselesaikan.


http://id.wikipedia.org/wiki/Feromon

17

2.4.3 Definisi Ant Colony System (ACS)

Ant Colony System (ACS) adalah salah satu turunan dari algoritma semut.

Pada algoritma ACS, semut berfungsi sebagai agen yang ditugaskan untuk

mencari solusi terhadap suatu masalah optimisasi. ACS telah diterapkan dalam

berbagai bidang, salah satunya adalah untuk mencari solusi optimal pada

Traveling Salesman Problem (TSP). Dengan memberikan sejumlah n titik, TSP

dapat didefinisikan sebagai suatu permasalahan dalam menemukan jalur

terpendek dengan mengunjungi setiap titik yang ada hanya sekali.

2.4.4 Tahapan Ants Colony System (ACS)

Terdapat tiga tahapan utama dari ACS, yaitu : Aturan transisi status,

Aturan pembaruan pheromone lokal, Aturan pembaruan pheromone global.

1. Aturan transisi status

Aturan transisi status yang berlaku pada ACS adalah sebagai

berikut: seekor semut yang ditempatkan pada titik t memilih untuk menuju

ke titik v, kemudian diberikan bilangan pecahan acak q dimana 0≤q≤1, q0

adalah sebuah parameter yaitu Probabilitas semut melakukan eksplorasi

pada setiap tahapan, dimana (0≤ q0≤1) dan pk (t,v) adalah probabilitas

dimana semut k memilih untuk bergerak dari titik t ke titik v.

Jika q ≤ q0 maka pemilihan titik yang akan dituju menerapkan

aturan yang ditunjukkan oleh persamaan (1)

Temporary (t,u) = [(t,ui)] . [(t,ui)]i = 1,2,3,…,n

V = max{[(t,ui)] . [(t,ui)}…………………………………….(1)

Dengan v = titik yang akan dituju

Sedangkan jika q >q0 digunakan persamaan (2)

v = pk(t,v) = [τ(𝑡,𝑣)] .[η(𝑡,𝑣)β]

∑ [τ(𝑡,𝑢𝑖)] .[η(𝑡,𝑢𝑖)β]𝑛𝑖=1

........................................................(2)

Dengan η(𝑡, 𝑢𝑖) = 1

𝑗𝑎𝑟𝑎𝑘(𝑡,𝑢𝑖)


18

Dimana (t,u) adalah nilai dari jejak pheromone pada titik (t,u) ,

(t,u)adalah fungsi heuristik dimana dipilih sebagai invers jarak antara

titik t dan u, merupakan sebuah parameter yang mempertimbangkan

kepentingan relatif dari informasi heuristik, yaitu besarnya bobot yang

diberikan terhadap parameter informasi heuristik, sehingga solusi yang

dihasilkan cenderung berdasarkan nilai fungsi matematis. Nilai untuk

parameter β adalah ≥ 0. Pheromon adalah zat kimia yang berasal dari

kelenjar endokrin dan digunakan oleh makhluk hidup untuk mengenali

sesama jenis, individu lain, kelompok, dan untuk membantu proses

reproduksi. Berbeda dengan hormon, pheromon menyebar ke luar tubuh

dapat mempengaruhi dan dikenali oleh individu lain yang sejenis (satu

spesies). Proses peninggalan pheromon ini dikenal sebagai stigmergy,

sebuah proses memodifikasi lingkungan yang tidak hanya bertujuan untuk

mengingat jalan pulang ke sarang, tetapi juga memungkinkan para semut

berkomunikas dengan koloninya. Seiring waktu, bagaimanapun juga jejak

pheromon akan menguap dan akan mengurangi kekuatan daya tariknya,

sehingga jejak pheromon harus diperbaharui.

2. Aturan pembaruan pheromon lokal

Selagi melakukan tur untuk mencari solusi dari TSP, semut

mengunjungi ruas-ruas dan mengubah tingkat pheromon pada ruas-ruas

tersebut dengan menerapkan aturan pembaruan pheromon lokal yang

ditunjukkan oleh persamaan (3)

τ(𝑡, 𝑣)(1-ρ). τ(𝑡, 𝑣)+ρ.∆ τ(𝑡, 𝑣) ……………………………(3)

∆ τ(𝑡, 𝑣)=1

𝐿𝑛𝑛. 𝐶

dimana :

Lnn = panjang tur yang diperoleh

c = jumlah lokasi

= parameter dengan nilai 0 sampai 1


19

Δτ = perubahan pheromon

adalah sebuah parameter (koefisien evaporasi), yaitu besarnya

koefisien penguapan pheromon . Adanya penguapan pheromone

menyebabkan tidak semua semut mengikuti jalur yang sama dengan semut

sebelumnya. Hal ini memungkinkan dihasilka solusi alternatif yang lebih

banyak. Peranan dari aturan pembaruan pheromone lokal ini adalah untuk

mengacak arah lintasan yang sedang dibangun, sehingga titik-titik yang

telah dilewati sebelumnya oleh tur seekor semut mungkin akan dilewati

kemudian oleh tur semut yang lain. Dengan kata lain, pengaruh dari

pembaruan lokal ini adalah untuk membuat tingkat ketertarikan ruas-ruas

yang ada berubah secara dinamis: setiap kali seekor semut menggunakan

sebuah ruas maka ruas ini dengan segera akan berkurang tingkat

ketertarikannya (karena ruas tersebut kehilangan sejumlah pheromon-nya),

secara tidak langsung semut yang lain akan memilih ruas-ruas lain yang

belum dikunjungi. Konsekuensinya, semut tidak akan memiliki

kecenderungan untuk berkumpul pada jalur yang sama. Fakta ini, yang

telah diamati dengan melakukan percobaan [Dorigo dan Gambardella,

1997]. Merupakan sifat yang diharapkan bahwa jika semut membuat tur-

tur yang berbeda maka akan terdapat kemungkinan yang lebih tinggi

dimana salah satu dari mereka akan menemukan solusi yang lebih baik

daripada mereka semua berkumpul dalam tur yang sama. Dengan cara ini,

semut akan membuat penggunaan informasi pheromon menjadi lebih baik

tanpa pembaruanlokal, semua semut akan mencari pada lingkungan yang

sempit dari tur terbaik yang telah ditemukan sebelumnya.

3. Aturan pembaruan pheromon global

Pada sistem ini, pembaruan pheromon secara global hanya

dilakukan oleh semut yang membuat tur terpendek sejak permulaan

percobaan. Pada akhir sebuah iterasi, setelah semua semut menyelesaikan

tur mereka, sejumlah pheromon ditaruh pada ruas-ruas yang dilewati oleh


20

seekor semut yang telah menemukan tur terbaik (ruas-ruas yang lain tidak

diubah). Tingkat pheromon itu diperbarui dengan menerapkan aturan

pembaruan pheromon global yang ditunjukkan oleh persamaan (4).

(t,v) (1-α).(t,v)α.∆ τ(𝑡, 𝑣) ……………………………..(4)

∆ τ(𝑡, 𝑣) = {𝐿𝑔𝑏

−1 𝑗𝑖𝑘𝑎 (𝑡, 𝑣) ∈ 𝑡𝑢𝑟_𝑡𝑒𝑟𝑏𝑎𝑖𝑘

0

Dimana :

(t,v)= nilai pheromone akhir setelah mengalami pembaharuan lokal

Lgb = panjang jalur terpendek pada akhir siklus

= parameter dengan nilai antara 0 sampai 1

Δτ = perubahan pheromone

∆ τ(𝑡, 𝑣)bernilai 1

𝐿𝑔𝑏jika ruas (t,v) merupakan bagian dari rute

terbaik namun jika sebaliknya ∆ τ(𝑡, 𝑣)= 0, α adalah tingkat kepentingan

relatif dari pheromon atau besarnya bobot yang diberikan terhadap

pheromon, sehingga solusi yang dihasilkan cenderung mengikuti sejarah

masa lalu dari semut dari perjalanan sebelumnya, dimana nilai parameter α

adalah ≥ 0, dan Lgb adalah panjang dari tur terbaik secara global sejak

permulaan percobaan. Pembaruan pheromon global dimaksudkan untuk

memberikan pheromon yang lebih banyak pada tur-tur yang lebih pendek.

Persamaan (3) menjelaskan bahwa hanya ruas-ruas yang merupakan

bagian dari tur terbaik secara global yang akan menerima penambahan

pheromone.

2.5 Cara kerja algoritma Ants Colony System (ACS)

Sama halnya dengan cara kerja semut dalam mencari jalur yang optimal,

untuk mencari jalur terpendek dalam penyelesaian masalah Traveling Salesman

Problem (TSP) diperlukan beberapa langkah untuk mendapatkan jalur yang

optimal, ditunjukkan dengan bagan sebagai berikut :


21

Gambar 2.12. Algoritma ACS


22

2.6 Analisis Algoritma ACS untuk Mencari Nilai Optimal

Untuk mendiskusikan algoritma semut, Setiap edge memiliki bobot yang

menunjukkan jarak antara dua buah nodes yang dihubungkan oleh busur tersebut.

Algoritma ini menggunakan sistem agen, yang berarti kita akan mengerahkan

semut yang bergerak sebagai agen tunggal. Setiap semut menyimpan daftar yang

memuat nodes yang sudah pernah ia lalui, dimana ia tidak diijinkan untuk melalui

node yang sama dua kali dalam satu kali perjalanan (daftar ini disebut juga

sebagai jalur Hamilton, yaitu jalur pada graf dimana setiap node hanya dikunjungi

satu kali). Sebuah koloni semut diciptakan, dan setiap semut ditempatkan pada

masing-masing node secara merata untuk menjamin bahwa tiap node memiliki

peluang untuk menjadi titik awal dari jalur optimal yang dicari. Setiap semut

selanjutnya harus melakukan tur semut, yaitu perjalanan mengunjungi semua

nodes pada graf tersebut.

Berikut adalah tahapan-tahapan algoritma semut menggunakan graf:

1. Dari sarang, semut berkeliling secara acak mencari makanan kemudian

dicatat jarak antara node yang semut lalui.

2. Ketika sampai ke makanan, Total jarak dari tiap node yang semut

tempuh dijumlahkan untuk mendapatkan jarak dari sarang ke makanan.

Gambar 2.13. Lintasan Awal Semut Menuju Tempat Makanan

Keterangan Gambar 2.13:

A : Tempat awal koloni (sarang)

B : Tujuan koloni semut (makanan)

Jalur 1 (biru): Lintasan yang ditempuh oleh semut 1

Jalur 2 (hitam): Lintasan yang ditempuh oleh semut 2

3. Ketika kembali ke sarang, sejumlah konsentrasi pheromon ditambahkan

pada jalur yang telah ditempuh berdasarkan total jarak jalur tersebut.


23

Makin kecil total jarak (atau makin optimal), maka makin banyak kadar

pheromon yang dibubuhkan pada masing-masing busur pada jalur

tersebut.

Gambar 2.14. Lintasan Semut Menuju Sarang


A : Sarang semut B : Tempat ditemukannya makanan

Jalur 1 (biru) : Jalur yang ditempuh oleh semut 1 dengan pemberian kadar

pheromon yang tinggi

Jalur 2 (hitam) : Jalur yang ditempuh oleh semut 2 dengan pemberian

kadar pheromon yang rendah

4. Untuk memilih busur mana yang harus dilalui berikutnya, digunakan

sebuah rumus yang pada intinya menerapkan suatu fungsi heuristic untuk

menghitung intensitas pheromon yang ditinggalkan pada suatu busur.

Gambar 2.15. Lintasan Semut Menuju Makanan pada Iterasi ke-2


A : Sarang semut B : Tempat ditemukannya makanan

Jalur 1 : Jalur yang ditempuh oleh semut 1 karena kadar pheromon yang

tinggi

Jalur 2 : Jalur yang tidak ditempuh oleh semut karena kadar pheromon

yang rendah


24

Jalur 3 : Jalur yang ditemukan oleh semut 2

5. Pada iterasi berikutnya, busur-busur yang mengandung pheromon lebih

tinggi ini akan cenderung dipilih sebagai busur yang harus ditempuh

berikutnya berdasarkan rumus pemilihan busur. Akibatnya, lama-

kelamaan akan terlihat jalur optimal pada graf, yaitu jalur yang dibentuk

oleh busur-busur dengan kadar pheromon yang tinggi, yang pada akhirnya

akan dipilih oleh semua multi agen semut.

Gambar 2.16. Lintasan Semut Menuju Sarang pada Iterasi ke-2


A : Sarang semut

B : Tempat ditemukannya makanan

Jalur 1 (hitam) : Jalur yang ditempuh oleh semut 2 dengan pemberian

kadar pheromon yang rendah

Jalur 2 : Jalur yang tidak ditempuh

Jalur 3 (biru) : Jalur yang ditempuh oleh semut 2 dengan pemberian kadar

pheromon yang tinggi.

Gambar 2.17. Lintasan Optimal Semut Menuju Tempat Makanan


25


A : Sarang semut

B : Tempat ditemukannya makanan

Jalur 1 : : Jalur yang tidak ditempuh karena kadar feromon yang rendah

Jalur 2 : Jalur yang tidak ditempuh karena kadar feromon yang sangat

rendah

Jalur 3 : Jalur optimal yang ditempuh oleh semut karena kadar feromon

yang tinggi

2.7 Analisis Parameter pada Algoritma Ants Colony System

Pada kasus-kasus dari ACS, pengaruh dari β (besar pengaruh informasi

heuristic), m (banyak semut), ρ (faktor penguapan), q0 (probabilitas pemilihan

deterministic) kadang berbeda-beda. Gambar 2.18, Gambar 2.19, Gambar 2.20,

Gambar 2.21 merupakan hasil perbandingan parameter β, m, ρ, dan q0, secara

berturut-turut dengan kasus TSP 3000 titik.(Stutzle, 2010)

Parameter β (gambar 2.18): nilai β berkisar antara 2 sampai 5

menghasilkan waktu komputasi dan rute yang lebih baik. Jika nilai β lebih kecil

akan menghasilkan waktu komputasi yang baik tetapi rute tidak ditemukan yang

baik. Kemudian jika nilai β lebih besar maka akan menghasikan waktu komputasi

yang buruk.

Gambar 2.18. ACS dengan beragam nilai β


26

Parameter m (gambar 2.19): nilai m dengan 10 semut menghasilkan waktu

komputasi yang baik. Jika lebih kecil (misalnya m=1) maka akan menghasilkan

waktu komputasi yang buruk. Jika lebih besar (misalnya m=100) maka akan

menghasilkan waktu komputasi yang buruk juga.

Gambar 2.19. ACS dengan beragam parameter semut (m)

Parameter ρ (gambar 2.20): perbedaan nilai ρ tidak banyak berpengaruh

dalam waktu komputasi ACS.

Gambar 2.20. ACS dengan beragam parameter ρ

Parameter q0 (gambar 2.21): nilai q0 menghasilkan waktu yang lebih baik

ketika q0 bernilai 1. Tetapi beberapa kasus nilai 0.75 lebih baik.


27

Gambar 2.21. ACS dengan beragam parameter q0

2.8 Contoh Penyelesaian Masalah Travelling Salesman Problem (TSP)

Dengan Menggunakan Metode Ants Colony System (ACS)

Gambar 2.22. Contoh Graf Lengkap

Tahap-tahap penghitungan jarak terpendek dengan menggunakan

algoritma ACS, yaitu:

7

10

13

A

B

C

D

F

E

5

6

16

9

17

8

19

18

12

14

1511


28

Langkah 1 : Buat matriks jaraknya berdasarkan graf diatas.

Tabel 2.2 Matriks Jarak

A B C D E F

A 0 16 18 19 5 10

B 16 0 9 7 12 14

C 18 9 0 17 13 15

D 19 7 17 0 11 8

E 5 12 13 11 0 6

F 10 14 15 8 6 0

Langkah 2 : Tentukan banyak semut untuk menentukan berapa banyak

iterasi rute yang akan dihasilkan. Setiap satu semut satu rute. Di contoh

penyelesaian ini akan ditentukan 1 semut.

Langkah 3 : Tentukan vertek awal semut. Dimana akan ditentukan sebagai

sarang semut. Sehingga semut akan berjalan dari vertek tersebut dan akan kembali

ke vertek tersebut. Di contoh penyelesaian ini akan ditentukan vertex awal nya

adalah A.

Langkah 4 : Tentukan nilai pheromone awal semut tiap busur yang

tersedia. Di contoh penyelesaian ini akan ditentukan 0.0001 sebagai nilai

awalnya.

Tabel 2.3 Matriks Pheromone Awal

A B C D E F

A 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

B 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

C 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

D 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

E 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001


29

F 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

Langkah 5 : Tentukan invers η(𝑡, 𝑢𝑖) sebagai dasar perhitungan

probabilitas dengan rumus η(𝑡, 𝑢𝑖) = 1

𝑗𝑎𝑟𝑎𝑘(𝑡,𝑢𝑖). Kemudian buatlah matriks invers

nya.

Tabel 2.4 Matriks Invers

A B C D E F

A 0.0000 0.0625 0.0555 0.0552 0.2000 0.1000

B 0.0625 0.0000 0.1111 0.1420 0.0833 0.0710

C 0.0555 0.1111 0.0000 0.0588 0.0769 0.0666

D 0.0552 0.1420 0.0588 0.0000 0.0909 0.1250

E 0.2000 0.0833 0.0769 0.0909 0.0000 0.1666

F 0.100 0.0710 0.0666 0.1250 0.1666 0.0000

Langkah 6 : Tentukan parameter perhitungan probabilitas. Di contoh

penyelesaian ini akan ditentukan nilai q(pecahan acak) 0.9 sedangkan

q0(probabilitas semut) 0.1. β (tingkat informasi heuristic) 2.

Langkah 7 : Karena nilai q(pecahan acak) > q0(probabilitas semut). Maka

akan dipakai persamaan ke-2 yaitu persamaan probabilitas = [τ(𝑡,𝑣)] .[η(𝑡,𝑣)β]

∑ [τ(𝑡,𝑢𝑖)] .[η(𝑡,𝑢𝑖)β]𝑛𝑖=1

.

Tabel 2.5 Hasil persamaan probabilitas

A B C D E F

Probabilitas pk(t,v) 0 0.0561 0.0500 0.0500 0.6677 0.1669

Langkah 8 : Dari Tabel 2.26 probabilitas terbesar adalah vertek A ke E.

Maka rute yang terbentuk adalah A E. Dan semut sekarang berada pada vertek

E.


30

Langkah 9 : Melakukan perhitungan perubahan pheromone lokal dengan

menggunakan persamaan ∆ τ(𝑡, 𝑣)=1

𝐿𝑛𝑛. 𝐶 dan τ(𝑡, 𝑣) = (1-ρ). τ(𝑡, 𝑣)+ ρ.∆ τ(𝑡, 𝑣)

dengan ρ (koefisien penguapan) antara 0 ≤ ρ ≤ 1. Di contoh penyelesaian ini akan

ditentukan nilai ρ (koefisien penguapan) adalah 0.1.

Tabel 2.6. Matriks Hasil Update pheromone lokal A ke E

A B C D E F

A 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

B 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

C 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

D 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

E 0.00342 0.0001 0.0001 0.0001 0.0001 0.0001

F 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

Langkah 10 : Ulangi langkah 7-11. Sampai semua vertek terlewati. Hasil

rute yang terbentuk adalah A E F D B C. Dibawah ini merupakan

matriks pheromone yang telah di-update.

Tabel 2.7 Matriks Hasil Update pheromone lokal A, E, F, D, B, C.

A B C D E F

A 0.0001 0.0001 0.0001 0.0001 0.01564 0.0001

B 0.0001 0.0001 0.00762 0.0001 0.0001 0.0001

C 0.0001 0.0001 0.0001 0.0001 0.0001 0.0001

D 0.0001 0.00979 0.0001 0.0001 0.0001 0.0001

E 0.01564 0.0001 0.0001 0.0001 0.0001 0.01139

F 0.0001 0.0001 0.0001 0.00721 0.0001 0.0001


31

Langkah 11 : Setelah melewati semua vertek maka semut kembali ke

vertek awal A dengan menggunakan persamaan update pheromone lokal.

Dibawah ini merupakan matriks hasil update pheromone lokal.

Tabel 2.8 Matriks Hasil Update pheromone lokal A, E, F, D, B, C,A.

A B C D E F

A 0.0001 0.0001 0.0001 0.0001 0.01564 0.0001

B 0.0001 0.0001 0.0087 0.0001 0.0001 0.0001

C 0.00434 0.0001 0.0001 0.0001 0.0001 0.0001

D 0.0001 0.00979 0.0001 0.0001 0.0001 0.0001

E 0.0001 0.0001 0.0001 0.0001 0.0001 0.01302

F 0.0001 0.0001 0.0001 0.00908 0.0001 0.0001

Langkah 12 : Hitung jarak dari rute yang terbentuk oleh perjalanan semut.

Di contoh penyelesaian ini didapat jarak nya adalah 53.

Langkah 13 : Melakukan penghitungan perubahan pheromone global

dengan menggunakan persamaan (t,v)= (1-α).(t,v)α.∆ τ(𝑡, 𝑣). Sedangkan

sebelum nya tentukan nilai ∆ τ(𝑡, 𝑣) = {𝐿𝑔𝑏−1 𝑗𝑖𝑘𝑎 (𝑡, 𝑣) ∈ 𝑡𝑢𝑟_𝑡𝑒𝑟𝑏𝑎𝑖𝑘.

0 dan

nilai α (tingkat pheromone),≥ 0, 0.1 Di contoh penyelesaian ini ditentukan nilai α

(tingkat pheromone) adalah 0.1. Pada tabel dibawah ini merupakan hasil update

pheromone global.

Tabel 2.9 Matriks Hasil Update Pheromone Global

A B C D E F

A 0.00009 0.00009 0.00009 0.00009 0.01587 0.00009

B 0.00009 0.00009 0.00963 0.00009 0.00009 0.00009

C 0.00570 0.00009 0.00009 0.00009 0.00009 0.00009

D 0.00009 0.01061 0.00009 0.00009 0.00009 0.00009


32

E 0.00009 0.00009 0.00009 0.00009 0.00009 0.01351

F 0.00009 0.00009 0.00009 0.00997 0.00009 0.00009

Langkah 14 : Maka di dapat rute dengan panjang minimal 53 dengan

susunan vertek A-E-F-D-B-C-A. Di bawah ini merupakan ilustrasi hasil

perjalanan semut paling optimal dalam satu iterasi.

Gambar 2.23. Hasil Rute Algoritma Ants Colony System 1 semut.

7

10

13

A

B

C

D

F

E

5

6

16

9

17

8

19

18

12

14

1511


33

BAB III

ANALISIS & DESAIN

3.1 Identifikasi Sistem

P.T. Pos Indonesia wilayah Yogyakarta mempunyai sistem lama dalam

pelayanannya terhadap pengiriman paket ke pelanggan. Sistem pengiriman paket

antara lain adalah sebagai berikut:

1. Paket dari luar maupun dalam wilayah Yogyakarta di drop ke kantor pos

kemudian dipilah berdasarkan kecamatannya dan beratnya, jika beratnya dibawah

2 kg diantar dengan menggunakan motor beserta surat standar dan surat kilat.

Sedangkan jika diatas 2 kg paket diantar menggunakan mobil atau diambil sendiri

oleh pelanggan.

2. Setelah dipilah, setiap petugas mendapatkan sekitar 2 atau 3 kecamatan. Dan di

wilayah Yogyakarta terdapat sekitar 58 petugas yang akan mengantar paket ke

tiap tujuan diseluruh wilayah Yogyakarta.

3. Paket siap diantarkan oleh petugas pos.

Dari sistem lama diatas terdapat permasalahan yaitu jalur yang dilalui oleh

petugas pos tidak optimal seperti melewati jalur yang telah dilewati sehingga

dilewati 2 kali sehingga waktu dan biaya transpotasi menjadi membengkak. Dari

permasalahan sistem yang lama ini maka akan dibuatkan sistem yang baru sebagai

solusi dari permasalahan tersebut.

Sebelum membangun system baru, kami melakukan penelitian terlebih

dahulu untuk mengetahui strategi apa yang paling tepat untuk system baru yang

akan digunakan. Algoritma yang dipilih dari penelitian tersebut adalah algoritma

ACS. Dengan algoritma ini diharapkan terdapat peningkatan terhadap jalur yang

lebih singkat sehingga meningkatkan waktu dan biaya yang lebih optimal.


34

3.2. Analisis Sistem

3.2.1. Analisis Data Awal

Dalam penelitian ini data yang dibutuhkan adalah data jarak jalan dan data

volume kendaraan. Data jarak dibutuhkan untuk proses penghitungan rute

terpendek. Pemerolehan data jarak adalah hasil pengcapturean peta dari google

earth yang kemudian dilakukan proses penghitungan jarak dengan menggunakan

corel draw sehingga diperoleh panjang jalan dalam bentuk centimeter. Tabel

dibawah ini merupakan hasil penghitungan jarak dengan corel draw.

Tabel 3.1 Data jarak peta

Sumber:[Catur P, 2010]

Nama Jalan Jarak dipeta (cm) Jarak sebenarnya (m)

Laksda Adisucipto 8.5 395



Janti 14 651

Janti 17.4 809

Janti 7.5 349

Babarsari 9.5 442

Babarsari 12.9 600

Babarsari 16.2 753


Karena data sesungguhnya adalah dalam satuan meter. Maka diperlukan

skala peta supaya sesuai dengan hasil riil. Penghitungan skala dengan rumus

jarak sebenarnya

jarak pada peta. Maka skala yang didapat adalah 1: 46.51163.

Sedangkan untuk data volume adalah data yang didapat dari dinas

perhubungan DIY tahun 2008. Data volume ini nanti akan diolah menjadi data


35

kecepatan dengan metode greenshield. Untuk proses data volume menjadi data

kecepatan adalah sebagai berikut:

1. Tentukan kepadatan jalan dengan menggunakan rumus

v = −

𝑈𝑓 . D - [

−𝑈𝑓

𝐷𝑗] D2………………… (3.1)

Dimana,

V= volume, (smp/jam)

−

𝑈𝑓 = kecepatan rata-rata arus bebas (km/jam)

D = kepadatan (smp/km)

Dj = jam density (kepadatan saat macet) (smp/km)

Telah diketahui dari data dinas perhubungan untuk volume,

sedangkan kecepatan rata-rata arus bebas adalah kecepatan rata-rata yang

diperbolehkan. Data yang didapat adalah sebagai berikut:

V = 3049 smp/jam

Dj = 602 smp/jam

−𝑈𝑓 = 70 km/jam

Maka untuk mencari nilai D adalah, 3049 = 70 D - 70

602 D2 , maka

didapat D min = 554,73 smp/jam. Dmax = 47.26 smp/jam.

Kemudian cari kecepatan rata-rata (−𝑈𝑠) dengan menggunakan

rumus 3.2

−𝑈𝑠 =

−𝑈𝑓 − [

−𝑈𝑓

𝐷𝑗].D…………………………(3.2)

Maka didapat nilai −

𝑈𝑠 dengan D min adalah 5.4965 km/jam,

sedangkan nilai −𝑈𝑠 dengan D max adalah 64.5047 km/jam. Sehingga

didapat nilai kecepatan rata-rata −𝑈𝑠 terkecil adalah 5.4965 km/jam.

Dibawah ini merupakan tabel data volume jumlah kendaraan yang

merupakan data dinas perhubungan DIY.


36

Tabel 3.2 Data Volume Kendaraan

Sumber: Dinas Perhubungan DIY (2008)

No Nama Pagi

(smp/jam)

Siang-pagi

(smp/jam)

Siang

(smp/jam)

Siang– sore

(smp/jam)

Sore

(smp/jam)

Dj

(smp/km)

Vs

(km/jam)

1 Amplas

arah solo

3,049 2895.1 3,267 1300 3200 602 70

2 Amplas

arah

jogja

3,600 1179.3 3,802 1240 2986 602 70

3 Bantul

Niten

arah

jogja

3044 1300 1222.6 1135 1653 522 40

4 Bantul

Niten

arah

bantul

1389 1365 1356 1239 2863 522 40

3.3 Analisis Kebutuhan Sistem

3.3.1 Diagram Use Case

Gambar 3.1 Diagram Use Case

Adminisitator

Staff Bagian Distribusi

ubah data kondisi

jalan

ubah data

kecepatan

ubah data account

update data

pengirim penerima

input data pengirim

penerima

hapus data

pengirim penerima

ubah kondisi

pengiriman

perhitungan

pencarian rute


37

3.3.2 Narasi Use Case

Nama Use Case Update Data Kondisi Jalan

Aktor Administatror

Keterangan

Administrator dapat meng-update data kondisi jalan

Kondisi awal

Administator sudah login dan berada pada “kelola data Kondisi Jalan”

Kondisi akhir

Data kondisi jalan berhasi di-update

Skenario

Aksi Aktor Reaksi Sistem

Kondisi Normal Normal

1. Administator memilih menu data

kondisi jalan

2. Sistem menampilkan data kondisi

jalan yang di ambil dari tabel jalan.

3. Administator melakukan klik

”update” pada data yang akan di

pilih

4. Sistem menampilkan form isian

yang telah terisi data dari lokasi

yang di pilih.

5. Administator melakukan perubahan

data

6.Bagian Distribusi memilih tombol

Pengarang : Alfa

Tanggal : 16 Okt 2011


38

simpan

7.Konfirmasi ubah

8.Jika[ya], system mengubah data

lokasi. Jika [tidak] maka system tidak

akan melakukan pengubahan.

9. system memberikan konfirmasi

bahwa data telah berhasil diubah.

Nama Use Case Update Data Kecepatan

Aktor Administator

Keterangan

Administator dapat meng-update data kecepatan

Kondisi awal

Administator sudah login dan berada pada “kelola data kecepatan”

Kondisi akhir

Data kecepatan berhasil di-update

Skenario



1.Administator memilih menu data

Ubah Keceptan

2. Sistem menampilkan data ubah

kecepatan yang di ambil dari tabel

hitungKecepatan.

3. Administator melakukan klik

”update” pada data yang akan di

Pengarang : Alfa



39

pilih

4. Sistem menampilkan form isian yang

telah terisi data dari jarak yang dipilih.

5. Administator melakukan perubahan

data

6.Administator memilih tombol

simpan

7.Konfirmasi ubah

8.Jika[ya], system mengubah data jarak.

Jika [tidak] maka system tidak akan

melakukan pengubahan.

9. system memberikan konfirmasi bahwa

data telah berhasil di ubah.

Nama Use Case Ubah Account

Aktor Adminstator dan Staff Bagian Distribusi

Keterangan

Adminstator dan Staff Bagian Distribusi dapat mengubah data account

Kondisi awal

Adminstator dan Staff Bagian Distribusi sudah login dan berada pada “ubah

account”

Kondisi akhir

Data account berhasil di-input dan disimpan ke tabel (data lokasi)

Skenario



Pengarang : Alfa



40

1. Adminstator dan Staff Bagian

Distribusi memilih menu “ubah

account”


ubah account

3.Bagian Distribusi mengsisi data

account baru dan mengklik tombol

simpan.

4. Sistem menyimpan data account

dalam database pada table user.

Skenario alternatif (jika kosong) .

1. Menampilkan konfirmasi bahwa isian

belum lengkap atau ada yang belum

isi.

Nama Use Case Update Data Pengirim Penerima

Aktor Staff Bagian Distribusi

Keterangan

Bagian Distribusi dapat meng-update Data Pengirim Penerima

Kondisi awal

Bagian Distribusi sudah login dan tabel data pengirim penerima sudah terisi

Kondisi akhir

Data Pengirim Penerima di-update

Skenario


Pengarang : Alfa



41

Kondisi Normal

1. Sistem menampilkan tabel data

pengirim penerima.

2. Bagian Distribusi mengklik tabel

yang akan di-update

3. Sistem menampilkan form isian data

pengirim penerima

4. Bagian Distribusi mengisi form

isian data pengirim penerima yang

akan di-update. Dan mengklik simpan

perubahan

5.Sistem menyimpan data pengirim

penerima pada tabel pengirim penerima,

dan menampilkan konfirmasi bahwa data

pengirim penerima telah di-update

Skenario alternatif (jika kosong)

1. Menampilkan konfirmasi bahwa

isian belum lengkap atau ada yang

belum isi.

Nama Use Case Input Data Pengirim Penerima

Aktor Bagian Distribusi

Keterangan

Bagian Distribusi dapat melakukan input data pengirim penerima

Kondisi awal

Pengarang : Alfa



42

Bagian Distribusi sudah login

Kondisi akhir

Input data pengirim penerima berhasil

Skenario




data pengirim penerima.

2. Bagian Distribusi memasukkan data

pengirim penerima pada form dan

memproses dengan mengklik tombol

“simpan”.

3. Sistem menyimpan data pengirim

penerima pada tabel pengirim penerima

dan menampilkan konfirmasi bahwa data

telah disimpan

Skenario alternatif (jika kosong)

1. Menampilkan konfirmasi bahwa

isian belum di-isi.

Nama Use Case Hapus data pengirim penerima


Keterangan

Bagian Distribusi dapat menghapus data pengirim penerima

Kondisi awal

Bagian Distribusi sudah login dan tabel pengirim penerima sudah terisi

Pengarang : Alfa



43

Kondisi akhir

Data tabel pengirim penerima telah terhapus

Skenario




pengirim penerima

2. Bagian Distribusi mengklik data

tabel pengirim penerima yang akan

dihapus

3. Sistem menampilkan form data tabel

pengirim penerima

4. Bagian Distribusi menekan

tombol hapus

5. Sistem menghapus data pengirim

penerima

Nama Use Case Ubah data kondisi pengiriman


Keterangan

Bagian Distribusi dapat mengubah data kondisi pengiriman

Kondisi awal

Bagian Distribusi sudah login dan tabel pengirim penerima kondisi belum terkirim

Kondisi akhir

Pengarang : Alfa



44

Data tabel pengirim penerima telah telah dikirim

Skenario




pengirim penerima

2. Bagian Distribusi mengklik data

tabel pengirim penerima yang akan

dikirim

3. Sistem menampilkan form data tabel

pengirim penerima

4. Bagian Distribusi memilih

kirim dan menekan tombol simpan

5. Sistem mengubah data pengirim

penerima sudah dikirim pada tabel

pengirim penerima

Nama Use Case Perhitungan pencarian rute


Keterangan

Bagian Distribusi dapat melakukan perhitungan pencarian rute

Kondisi awal

Bagian Distribusi sudah login dan tabel pengirim penerima dalam kondisi kirim

Kondisi akhir

Pengarang : Alfa



45

Tampil rute pengiriman

Skenario




pengirim penerima dalam kondisi kirim

2. Bagian Distribusi mengisi form

parameter pada algoritma semut dan

menekan tombol tampil rute

pengiriman

3. Sistem menampilkan rute pengiriman

alternate dan terbaik

3.4 Perancangan Umum Sistem

Secara umum system aplikasi ditujukan untuk mencari rute pengiriman

barang secara optimal pada P.T. Pos Indonesia dengan algoritma Ants Colony

System.

3.4.1 Masukan Sistem

Data yang menjadi masukan sistem dalam penelitian ini adalah data peta

dan inputan parameter user . Data peta akan tersimpan di file .dmp terdiri dari data

koordinat x dan koordinat y serta nama titik. Karena data peta terlalu besar untuk

ditempatkan dalam satu array maka data peta perlu dibagi dalam 10 wilayah.

Pembagian wilayah ini juga di atur pada file vertexlist.dmp dan mapingbesar.dmp.

Gambar 3.2 merupakan gambar pembagian peta per cluster.


46

Gambar 3.2 Peta per Cluster

Sedangkan untuk inputan parameter terdiri dari nilai q0, nilai β, nilai α,

nilai ρ dan banyak semut.

3.4.2 Proses Sistem

Didalam sistem yang akan dibangun terdapat beberapa proses untuk

mencapai tujuan utama yaitu mencari rute terpendek. Tahap-tahap nya adalah

men-set tujuan pengiriman, mencari urutan cluster, mencari rute tercepat.

Tahap-tahap proses sistem yang akan dibangun:

1. Men-set tujuan pengiriman

Pada langkah awal ini sistem akan mengambil data daftar

pengirim&penerima, dari tabel pada frame DaftarPengirimanInternalFrame.

Kemudian data tesebut dicocokan dengan data peta yang ada diprogram.

Ketika nama node pada data peta mempunyai nama yang sama dengan node

pengirim&penerima, maka atribut destinasi pada node,wilayah pada peta,

akan di set true . Gambar 3.3, 3.4, 3.5 adalah diagram alir dari tahap 1.


47

Gambar 3.3 Set node Awal

Daftar pengirim&penerima ditampilkan

ditabel daftarpengirimanTabel, waktu

berangkat dipilih dari comboBox

wktbrgkt, parameter dan banyak semut

terima daftar node pengirim&penerima

dari tabel

terima daftar peta dari kelas load peta

set riut18 mjd

node awal

set variabel

string

Dest=riut18

A


48

Gambar 3.4 Set wilayah Pengiriman

For j=0 to jml

wilayah

true

set array vertexList = array

nama node ke j

For k = 0 to jml

vertexList

true

Jika nama vertexList

ke k = Dest

true

set tujuan pada

wilayah ke j

menjadi true

k++

j++

A

B

falsefalse

false


49

Gambar 3.5 Set node Pengiriman

2. Mencari urutan cluster pengiriman

Setelah menentukan node dan cluster pengiriman maka langkah

selanjutnya adalah mencari urutan cluster. Ditujukan untuk

mengetahui cluster mana yang akan dikunjungi lebih dahulu. Hal

ini ditujukan untuk mempersingkat waktu pencarian rute

pengiriman. Gambar 3.6 adalah diagram alir untuk mencari urutan

cluster pengiriman.

For j=0 to jml

wilayah

true

set array vertexList = array

nama node ke j

For k = 0 to jml

vertexList

true

Jika nama vertexList

ke k = Dest

true

set tujuan pada

wilayah ke j

menjadi true

k++

j++

A

B

falsefalse

false


50

Gambar 3.6 Mencari urutan Cluster

3. Mencari rute pengiriman tercepat

Setelah mendapatkan urutan cluster. Maka selanjutnya adalah

mencari rute pengiriman tercepat. Gambar 3.7, 3.8, 3.9, 3.10, 3.11

adalah diagram alir untuk mencari rute pengiriman tercepat.

A

mencari urutan waktu

pengiriman

mencari jalur

urutan cluster

mulai dari

vertexList 3

mengubah urutan

cluster ke angka

mencari rute pengiriman

kembali set cluster awal =

cluster akhir rute

set cluster

vertexList 3

menjadi Dest

mengubah

urutan cluster

ke angka

D


51

Gambar 3.7 Pencarian rute cluster ke 0

D

For i to bnyk

semut

set array vr= array nama node dengan cluster

urutan pengiriman pertama set array

amNew=array bobot waktu dengan urutan

cluster pengiriman pertama

mengubah susunan matrik amNew dan

array vr dengan titik 0 sebagai node awal

set array vrTmp= susunan node baru yang telah

diubah, set matriks amNewTmp =susunan matriks

yang telah diubah, set matriks amBobot =susunan

matriks invers

semut =0

true

set matriks

tMatAwal = matriks

pheromone awal

mencari rute

terpendek untuk

urutan cluster ke 0

get list finalPath = array susunan jalan terpendek, get

finalBobot = matriks bobot jalan, get finalTau = matriks

pheromone baru

E

set list gabungFT = tampung list

finalTau, gabungFP = tampung list

finalPath, gabungVertUrut =

tampung vrTmp

set matriks

tMatAwal = matriks

finalTau

false

for i=0 to

finalPath -1

set list gabungPath = tampung

finalPath-1, set gabungbobot =

finalBobot


52

Gambar 3.8 Pencarian rute cluster ke-i

E

for i=1 to

urutanCluster-1

set array vrIn= array nama node dengan cluster

urutan pengiriman ke i set array amIn=array bobot

waktu dengan urutan cluster pengiriman ke i

semut = 0

true

set matriks

tMatAwal2 = matriks

pheromone awal

set matriks

tMatAwal2 = matriks

tauTemp

false

mencari rute

terpendek untuk

urutan cluster ke i

memasukkan

rute terpilih ke

tmpInCluster

set finalPath tmpInCluster ke 0, set finalBobot

tmpInCluster ke 1, setfinalTau tmpInCluster ke 2,

set testVertexBaru tmpInCluster ke 3

set list tauTemp = tampung finalTau,

gabungFT = tampung finalTau, gabungFP =

tampung finalPath, gabungVertUrut

=tampung testVertexBaru

for d=0 to ukuran

finalPath-1

set gabungPath =tampung finalPath,

set gabungBobot = gabungBobot

sebelum + finalBobot, i++

F


53

Gambar 3.9 Pencarian rute cluster akhir

F

set vrLast = daftar vertex urutan cluster terakhir,

set amLast =daftar matriks urutan cluster akhir

semut = 0

set matriks

tMatAkhir =

matriks

pheromone awal

set matriks

tMatAkhir=

matriks finalTau

true false

mencari rute

terpendek untuk

urutan cluster

akhir

memasukkan

rute terpilih ke

tmpAkhCluster

set finalPath tmpAkhCluster ke 0, set

finalBobot tmpAkhCluster ke 1, set

finalTau tmpAkhCluster ke 2, set

testVertexAkhir tmpAkhCluster ke 3

set gabungFT = tampung finalTau, gabungFP

= tampung finalPath, gabungVertUrut

=tampung testVertexAkhir

for d=0 to ukuran

finalPath

set gabungPath =tampung finalPath,

set gabungBobot = gabungBobot

sebelum + finalBobot

set list bandingbobot = tampung gabungbobot,

set list bandingpath =tampung gabungpath

G


54

Gambar 3.10 Set destinasi ulang dan pencarian rute semut ke n

G

for j=o to ukuran

listVertexMap

set vertex vere =

listVertexMap ke j

for k=0 to

ukuran vere

vere ke k

DestNext =

true

set Dest vere =

true, k++

j++

D

H


55

Gambar 3.11 Pencarian rute terbaik

Selain diagram alir tersebuat ada proses-proses utama dalam tahap

pencarian rute terpendek dengan algoritma Ants Colony System.

1. Algoritma proses inisialisasi status

Algoritma ini merupakan tahap pertama algoritma Ants Colony

System. Algoritma ini dibagi dua yaitu inisialisasi status 1 dan inisialisasi

status 2. Dimana semut dapat memilih algoritma mana yang akan

digunakan. Jika nilaiQ <= nilaiQ0, maka dipilih inisialisasi status1, dan

jika nilaiQ > nilaiQ0, maka dipilih inisialisasi status2

H

set double bbtTerbaik = bandingbobot ke 0,

set list pathTerbaik = bandingPath ke 0, set

nilaiI = 0

for i = 1 to ukuran

bandingBobot

bbtTerbaik >

bandingBobot ke i

set bbtTerbaik = bandingBobot

ke i, set pathTerbaik =

bandingPath ke i, set nilaiI = i

set global =

pheromoneGloba

l

nilai balik rute

alternatif dan

terbaik


56

Gambar 3.12 Proses Inisialisasi Status 1

for i = 0 to

ukuran adjMat

for j = 0 to

ukuran adjMat

set krMatrik[i][j]

= adjMat[i][j],

j++

i++

for x = 1 to

ukuran B

for i = 0 to

ukuran adjMat

for j=0 to ukuran

adjMat

krMatrik[i][j] = krMatrik[i][j] * adjMat[i]

[j], j++

i++

x++

for i =0 to

ukuran

adjMat

for j = 0 to

ukuran

adjMat

baru[i][j] = tMatrik[i][j] * krMatrik[i][j],

j++

i++

return hasil

inisialisasi

status1


57

Gambar 3.13 Proses Inisialisasi Status 2

for i = 0 to

ukuran adjMat

for j = 0 to

ukuran adjMat

set krMatrik[i][j]

= adjMat[i][j],

j++

i++

for x = 1 to

ukuran B

for i = 0 to

ukuran adjMat

for j=0 to ukuran

adjMat

krMatrik[i][j] = krMatrik[i][j] * adjMat[i]

[j], j++

i++

x++

for i =0 to

ukuran

adjMat

for j = 0 to

ukuran

adjMat

baru[i][j] = tMatrik[i][j] * krMatrik[i][j],

j++

i++

for k = 0 to

ukuran baru

jumlah = 0

jumlah = jumlah + baru[angkajalanawal] [k]

for m = 0 to

ukuran baru

baru[angkajalanawal] [m] = baru[angkajalanawal] [m] / jumlah

return hasil

inisialisasi

status 2


58

2. Algoritma proses pheromone lokal

Gambar 3.14 Proses Update Phremone Lokal

Lnn = 0, c =

ukuran adjMat

for i = 0 to

ukuran adjMat

for j=0 to

ukuran

adjMat

vertexList ke i = jalanPresent &&

vertexList ke j = nextJalan

Lnn = adjMat[i][j]

j++

i++

true

false

set double

deltaT = 1/

(Lnn*C)

for i = 0 to ukuran

tMatriks

for j = 0 to ukuran

tMatriks

vertexList ke i = jalanPresent &&

vertexList ke j = nextJalan

tMatriks[i][j] = ((1-nilaiP) * tMatriks[i][j]) + (nilaiP*deltaT)

j++

i++

true

false

return tMatriks


59

3. Algoritma proses pheromone global

Gambar 3.15 Proses menentukan pheromone yang akan di update Pheromone

Global

set int bagi =

jmlcluster/bnyksemut, set

int q = 0

for i=0 to

ukuran tMatrik

for j=0 to

bnyk semut

jmlCluster==bnyksemut

for k=q to

bagi

set list baruTau = tampung tMatriks ke k,

set list baruVert = tampung InvVert ke k,

set baruRut = tampung rute ke k

k++

true

set q=bagi, set bagi =

bagi * semut

false

j++

i++

A


60

Gambar 3.16 Proses Update Pheromone Global

A

for i = 0 to

ukuran baruTau

set double perCluster = baruTau ke i,

set vertex perVert = baruRut ke i,

set string perRut = baruRut ke i

set double

deltaT1 = 1/Lgb,

set deltaT2 = 0

for j=0 to ukuran

perCluster

for k=0 to ukuran

perCluster

for l=0 to

ukuran

perRut-1

perVert[j].toString().equals(perRut[l].toString()) &&

perVert[k].toString().equals(perRut[l+1].toString())

hasilGlobal[j][k] = ((1-a) * percluster[j][k]) + (a*deltaT1) hasilGlobal[j][k] = ((1-a) * percluster[j][k]) + (a*deltaT2)

true false

l++

k++

j++

set list finalHasilGlobal = tampung nilai hasilGlobal,

i++

return finalHasilGlobal, baruVert, baruRut


61

Gambar 3.17 berikut ini merupakan diagram konteks dari proses yang

terjadi didalam system optimasi rute terpendek pengiriman barang P.T. Pos

Indonesia secara umum.

Bagian DistribusiSistem Informasi Pencarian Rute

Pengiriman Barang

Petugas PosData jarak

Daftar lokasi Pengiriman (jumlah node)dan

Parameter Perhitungan(pheromone awal, qo, beta,

rho, alpha)

Rute Pengiriman Barang

3.17 Diagram Konteks

3.4.3 Keluaran Sistem

Keluaran sistem Penerapan Rute Terpendek P.T Pos Indonesia adalah ruter

yang dilewati, nilai bobot waktu serta nilai jarak dan pembentukan peta

rute terpendek beserta alternatifnya.


62

3.4.4 Diagram Aktifitas

3.4.4.1 Diagram Aktifitas Update Data Kondisi Jalan

Gambar 3.18 Diagram Aktifitas Update Data Kondisi Jalan

Pilih Menu Update data

Kondisi Jalan

Menampilkan data

Kondisi Jalan

Diagram Aktifitas Update Data Kondisi Jalan

Start

Administator Sistem

Klik data yang akan di

updateMenampilkan Form Isian

Ubah kondisi Jalan, dan

Klik simpan

Menyimpan data kondisi

jalan pada tabel jalan


63

3.4.4.2 Diagram Aktifitas Update Data Kecepatan

Gambar 3.19 Diagram Aktifitas Update Data Kecepatan

3.4.4.3 Diagram Aktifitas Ubah Data Account

Gambar 3.20 Diagram Aktifitas Ubah Data Account

Pilih Menu Update data

Kecepatan

Menampilkan data

Kecepatan

Diagram Aktifitas Update Data Kecepatan

Start

Administrator Sistem

Klik data yang akan di

updateMenampilkan Form Isian

Ubah Kecepatan, dan

Klik simpan

Menyimpan data

kecepatan pada tabel

hitungKecepatan dan

jalan

Klik tombol simpan ke

teks

Menyimpan data ke file

dmp

Pilih Menu Ubah Data

Account

Menampilkan form Data

Account

Diagram Aktifitas Ubah Data Account

Start

Staff Bagian Distribusi/

AdministatorSistem

Isi Username dan

password baru, dan klik

simpan

Konfirmasi data

data valid

simpan data account ke

table user

data kosong/ tidak valid


64

3.4.4.4 Diagram Aktifitas Update Data Pengirim Penerima

Gambar 3.21 Diagram Aktifitas Update Data Pengirim Penerima

Pilih Menu Pengirim

Penerima

Menampilkan tabel Data

Pengirim Penerima

Diagram Aktifitas Update Data Pengirim Penerima

Start

Staff Bagian Distribusi Sistem

Kilik data pengirim

penerima yang akan di-

update

Menampilkan form data

pengirim penerima

cek data pengirim

penerima

data valid


Ubah data yang akan di-

update dan klik simpan

perubahan

simpan data update

pengirim penerima ke

tabel pengirimpenerima

konfirmasi data valid dan

disimpan


65

3.4.4.5 Diagram Aktifitas Input Data Pengirim Penerima

Gambar 3.22 Diagram Aktifitas Input Data Pengirim Penerima

Pilih Menu Pengirim

Penerima


Pengirim Penerima

Diagram Aktifitas Input Data Pengirim Penerima

Start


Kilik tombol pengirim

penerima baru

Menampilkan form isian

data pengirim penerima

cek data pengirim

penerima

data valid


isi data pengirim

penerima dan klik simpan

simpan data update

pengirim penerima ke


konfirmasi data valid dan

disimpan


66

3.4.4.6 Diagram Aktifitas Hapus Data Pengirim Penerima

Gambar 3.23 Diagram Aktifitas Hapus Data Pengirim Penerima

Pilih Menu Pengirim

Penerima


Pengirim Penerima

Diagram Aktifitas Hapus Data Pengirim Penerima

Start


Kilik data pengirim

penerima yang akan

dihapus


pengirim penerima

konfirmasi data akan

benar dihapus

menghapus data

pengirimpenerima dari


klik tombol hapus

klik ya

klik batal


67

3.4.4.7 Diagram Aktifitas Ubah Kondisi Pengiriman

Gambar 3.24 Diagram Aktifitas Ubah Kondisi Pengiriman

3.4.4.8 Diagram Aktifitas Perhitungan Pencarian Rute

Gambar 3.25 Diagram Aktifitas Perhitungan Pencarian Rute

Pilih Menu Daftar

Pengiriman


Pengirim Penerima

Diagram Aktifitas Ubah Kondisi Pengiriman

Start


Kilik data pengirim

penerima yang akan di

ubah kondisi


pengirim penerima

mengupdate kondisi

pengiriman pada tabel

pengirim penerima

ubah kondisi pengiriman,

dan klik simpan

Pilih Menu Daftar

Pengiriman


Pengirim Penerima, dan

sudah kondisi kirim

Diagram Aktifitas Perhitungan Pencarian Rute Pengiriman

Start


Kilik lihat peta

pengiriman

Memproses rute

pengiriman dan

menampilkan peta

pengiriman


68

3.5 Perancangan Basis Data

3.5.1 Entity Relationship Diagram

Sebelum melakukan penyusunan basis data perlu dibuat Entity

Relationship Diagram (ERD) dari entitas yang terlibat dalam sistem pencarian

rute P.T. Pos Indonesia. Entity – Relationship adalah suatu hubungan antara dua

file atau lebih yang saling berkaitan. Entitas yang saling berhubungan antara satu

dengan yang lain akan membentuk suatu relasi dan isi masing-masing entitas

tersebut saling melengkapi.

ERD adalah model konseptual yang mendeskripsikan hubungan antar

penyimpanan (dalam DFD). ERD digunakan untuk memodelkan struktur data dan

hubungan antar data. Dengan ERD kita dapat menguji model dengan

mengabaikan proses yang harus dilaksanakan. ERD menggunakan notasi dan

sumber untuk menggambarkan struktur dan hubungan antar data


69

ERD dapat digambarkan pada gambar 3.26 berikut.

Gambar 3.26 ERD Database System

pengirim_penerima

id_

pe

ng

irim

pe

ne

rim

a

na

ma

_p

eng

irim

no

de

telp

f_p

eng

irim

ala

ma

t_p

eng

irim

nil_

X

nil_

Y

idJa

lan

telp

f_p

ene

rim

a

alamat_penerima

tgl_kirim

status

tgl_terima

na

ma

_p

ene

rim

a

kecamatan

id_

ke

ca

ma

tan

na

ma

_ke

ca

ma

tan

id_

ka

bup

ate

nkabupaten

id_

ka

bup

ate

n

na

ma

_ka

bup

ate

n

pro

pin

si

hitungKepadatan

idH

itung

Ke

pa

da

ta

n

na

ma

Po

si

si

ke

ce

pa

tan_

pa

gi

ke

ce

pa

tan_

pa

gi_

sia

ng

ke

ce

pa

tan_

sia

ng

ke

ce

pa

tan_

sia

ng

_so

re

ke

ce

pa

tan_

so

re

gmbrjalur

id koordinatnamaJala

n

namaFilenamaActi

on

jalanid

Ja

lan

na

ma

Ja

lan

wila

yah

jara

k

koordinatX

koordinatY

id_

Ke

lura

ha

n

idH

itung

Ke

pa

da

tan

wa

ktu

_p

ag

i

wa

ktu

_p

ag

i_sia

ng

wa

ktu

_sia

ng

_so

re

waktu_sore

kondisi

wa

ktu

_sia

ng

kelurahan

id_

ke

lura

ha

n

na

ma

_ke

lura

ha

n

id_

ke

ca

ma

tan

user

id_

use

r

na

ma

_use

r

pa

ssw

ord

log

ina

s

punyaN 1

punya1 N

punyaN 1punyaN 1

punya

N

1


70

3.5.2 Perancangan Fisikal

Perancangan fisik basis data merupakan proses untuk

mengimplementasikan hasil perancangan logika kedalam sistem komputer secara

fisik. Pada penelitian ini, aktivitas perancangan fisik yang dikerjakan dibatasi

hanya penentuan struktur setiap tabel yang meliputi nama atribut, jenis, lebar

atribut, dan penentuan batasan integritas (integrity contraints). Secara rinci hasil

dari perancangan fisikal dalam penelitian ini adalah:

a. Tabel Pengirim dan Penerima

Digunakan untuk menyimpan data pengirim dan data penerima.

Nama Tabel : pengirim_penerima

Primary Key: id_pengirimpenerima

Foreign Key: idJalan

No Nama Atribut Jenis Lebar Keterangan

1 Id_pengirimpeneri

ma

int 11 Primary key

2 Nama_pengirim varchar 50 Nama pengirim

3 Node varchar 11 Node tujuan penerima

4 telpf_pengirim varchar 20 Data telpon pengirim

5 alamat_pengirim varchar 200 Data alamat pengirim

6 nil_X int 11 Nilai koordinat X penerima dipeta

7 nil_Y int 11 Nilai koordinat Y penerima dipeta

8 idJalan int 11 Foreign key dari tabel jalan

9 nama_penerima varchar 50 Nama penerima

10 telpf_penerima varchar 20 Data telpon penerima

11 alamat_penerima varchar 500 Data alamat penerima

12 tgl_kirim varchar 50 Data tanggal kirim pengiriman

13 status varchar 50 Data status pengiriman

14 tgl_terima varchar 50 Data tanggal terima pengiriman

b. Tabel Hitung Kepadatan

Digunakan untuk menyimpan data kepadatan untuk dihitung bobot waktunya.


71

Nama Tabel : hitungkepadatan

Primary Key: idHitungKepadatan

Foreign Key: -


1 idHitungKepadata

n

int 11 Primary key

2 namaPosisi varchar 60 Nama ruas jalan yang menjadi

patokan hitung kepadatan

3 kecepatan_pagi double - waktu kecepatan rata-rata pada

waktu pagi hari

4 kecepatan_pagi_si

ang

double - waktu kecepatan rata-rata pada

waktu pagi menjelang siang hari

5 kecepatan_siang double - waktu kecepatan rata-rata pada

waktu siang hari

6 kecepatan_siang_s

ore

double - waktu kecepatan rata-rata pada

waktu siang menjelang sore hari

7 kecepatan_sore double - waktu kecepatan rata-rata pada

waktu sore hari

c. Tabel Jalan

Digunakan untuk menyimpan data hasil penghitungan bobot waktu.

Nama Tabel : jalan

Primary Key: idJalan

Foreign Key: idHitungKepadatan, id_Kelurahan


1 idJalan int 11 Primary key

2 namaJalan varchar 50 Nama ruas jalan

3 wilayah int 11 No wilayah jalan

4 jarak double - Jarak tiap jalan

5 koordinatX varchar 20 Node awal jalan

6 koordinatY varchar 20 Node akhir jalan


72

7 id_Kelurahan int 11 Foreign key dari tabel kelurahan

8 idHitungKepadata

n

int 11 Foreign key dari table hitung

kepadatan

9 waktu_pagi double - Waktu tempuh rata-rata jalan pada

pagi hari

10 waktu_pagi_siang double - Waktu tempuh rata-rata jalan pada

pagi menjelang siang hari

11 waktu_siang double - Waktu tempuh rata-rata jalan pada

siang hari

12 waktu_siang_sore double - Waktu tempuh rata-rata jalan pada

siang menjelang sore hari

13 waktu_sore double - Waktu tempuh rata-rata jalan pada

sore hari

14 kondisi varchar 20 Kondisi jalan apakah bisa dilewati

atau tidak

d. Tabel Kabupaten

Digunakan untuk menyimpan data kabupaten.

Nama Tabel : kabupaten

Primary Key: idKabupaten

Foreign Key: -


1 id_kabupaten int 11 Primary key

2 nama_kabupaten varchar 200 Nama kabupaten

3 propinsi varchar 100 Nama propinsi

e. Tabel Kecamatan

Digunakan untuk menyimpan data kecamatan.

Nama Tabel : kecamatan

Primary Key: idKecamatan

Foreign Key: idKabupaten


1 id_kecamatan int 11 Primary key

2 nama_kecamatan varchar 100 Nama kecamatan


73

3 id_kabupaten int 11 Foreign key dari tabel kabupaten

f. Tabel kelurahan

Digunakan untuk menyimpan data kelurahan.

Nama Tabel : kelurahan

Primary Key: id_kelurahan

Foreign Key: id_kecamatan


1 id_kelurahan int 11 Primary key

2 nama_kelurahan varchar 100 Nama kelurahan

3 id_kecamatan int 11 Foreign Key dari tabel kecamatan

g. Tabel user

Digunakan untuk menyimpan data user.

Nama Tabel : user

Primary Key: id_user

Foreign Key: -


1 id_user int 11 Primary key

2 nama_user varchar 30 Nama user untuk login

3 password varchar 200 Password user

loginas varchar 50 Login sebagai

h. Tabel gambar jalur

Digunakan untuk menyimpan data gambarjalur.

Nama Tabel : gmbrjalur

Primary Key: id

Foreign Key: -



74

1 id int 11 Primary key

2 koordinat varchar 200 Koordinat jalan

3 namaJalan varchar 100 Nama jalan

4 namaFile varchar 100 Nama file gambar

5 namaAction varchar 100 Nama action gambar jalan

3.6 Diagram Kelas Analisis dan Diagram Sekuen

3.6.1 Diagram Kelas Analisis dan Diagram Sekuen Use Case Login

No Nama Kelas Tipe Deskripsi

1 loadPeta Control Kelas ini berfungsi untuk memanggil

data peta yang berupa text ke dalam

program.

2 loginFrame Interface /

Boundary

Kelas ini menyediakan fungsi untuk

menyediakan fungsi penampilan form

login.

3 authentfikasiL

ogin

Control Kelas ini menyediakan fungsi untuk

mengauthentifikasi / memvalidasi

username dan password

4 userData Entity Kelas ini menyediakan fungsi untuk

menyimpan data-data user (username

dan password).

5 adminMainFram

e

Interface /

Boundary


menampilkan halaman utama

administrator.

6 staffBagianDistr

ibusiMainFrame

Interface /

Boundary


menampilkan halaman utama staff

bagian distribusi.


75

Gambar 3.27 Diagram Kelas Analisis Use Case Login

Gambar 3.28 Diagram Sekuen Login

3.6.2 Diagram Kelas Analisis dan Diagram Sekuen Use Case Logout

loadPeta loginFrame authentifikasiLogin staffBagianDistribusiMainframe

userData adminMainFrame

staffBagi

anDistrib

usi

administ

rator

<<Controller>>

loadPeta

<<Boundary>>

loginFrame

<<Controller>>

authentifikasiLogin

<<Entity>>

userData

<<Boundary>>

staffBagianDistribusiMainFrame

<<Boundary>>

adminMainFrame

1. Aktor mulai

2. Sistem menampilkan

form login

3. Mengisi username

dan password

4. Menekan

tombol login

5. Mengidentifikasi

username dan

password

6. Menampilkan form

staffBagianDistribusi

Skenario Alternatif

1. Aktor mulai

2. Sistem menampilkan

form login

3. Mengisi username

dan password

4. Menekan

tombol login

5. Mengidentifikasi

username dan

password

6. Menampilkan form

administrator

klik eksesusi penerapan()

show()


login key

show()

authentik(string,

string, string)

klik eksesusi penerapan()

show()


login key

authentik(string,

string, string)

getPassUsername

(string)

getPassUsername

(string)

show()


1 controlPengiri

mPenerima

Control Kelas ini berfungsi untuk mengatur

tampilan ketika action dijalankan oleh


2 loginFrame Interface / Kelas ini menyediakan fungsi untuk


76

Gambar 3.29 Diagram Kelas Analisis Use Case Logout

Gambar 3.30 Diagram Sekuen Logout


adminMainFrame

controlPengirimPenerima

adminControl

loginFrame

staffBagi

anDistrib

usi

administ

rator

<<Boundary>>

adminMainFrame

<<Boundary>>


<<Controller>>


<<Controller>>

adminControl

<<Boundary>>

loginFrame

1. Administator menekan

tombol logout

2. set dispose lalu

menampilkan form login

Skenario Alternatif

1. Staff Bagian Distribusi

menekan tombol logout

2. set dispose lalu

menampilkan form login

show()

memilih menu logout

memilih menu logout

tampilmenu(integer)

tampilmenu(integer)

show()

Boundary menyediakan fungsi penampilan form

login.

3 adminControl Control Kelas ini menyediakan fungsi untuk

mengatur tampilan ketika action

dijalankan oleh adminMainFrame

4 adminMainFra

me

Interface /

Boundary



administrator.

5 staffBagianDistr

ibusiMainFrame

Interface /

Boundary



bagian distribusi.


77

3.6.3 Diagram Kelas Analisis dan Diagram Sekuen Use Case Mengubah

Account


1 controlPengiri

mPenerima




2 adminControl Control Kelas ini menyediakan fungsi untuk

mengatur tampilan ketika action

dijalankan oleh adminMainFrame

3 adminMainFra

me

Interface /

Boundary



administrator.

4 staffBagianDistr

ibusiMainFrame

Interface /

Boundary



bagian distribusi.

5 updateAccountC

ontrol


semua action yang dilakukan

ubahAccountFrame

6 ubahAccountFra

me

Interface /

Boundary


menampilkan halaman untuk mengubah


7 userData Entity Kelas ini berfungsi untuk menyimpan

data –data user (username dan

password)


78

Gambar 3.31 Diagram Kelas Analisis Use Case Mengubah Account

Gambar 3.32 Diagram Sekuen Mengubah Account

3.6.4 Diagram Kelas Analisis dan Diagram Sekuen Use Case Mengisi data

pengirim penerima

adminMainFrame

ubahAccountFrame

staffBagianDistribusiMainFrame controlPengirimPenerima

adminControl

updateAccountControl userData

staffBagi

anDistrib

usi

administ

rator

<<Boundary>>

adminMainFrame

<<Boundary>>


<<Controller>>


<<Controller>>

adminControl

<<Boundary>>

ubahAccountFrame

1. Memilih menu ubah

account

2. Menampilkan form

ubah account

Skenario Alternatif

show()

memilih menu ubah

account

mengisi username dan password baru

tampilmenu(integer)

<<Controller>>

updateAccountControl

<<Entity>>

userData

3. Mengisi username

dan password baru

4. menekan tombol

simpan

5. Memvalidasi username dan password

6. mengupdate username dan password

1. Memilih menu ubah

account

2. Menampilkan form

ubah account

3. Mengisi username

dan password baru

4. menekan tombol

simpan

5. Memvalidasi username dan password

6. mengupdate username dan password

menekan tombol simpan updateAccount

(string, string,

string, string) updateAccount

(string, string,

string)

memilih menu ubah accounttampilmenu

(integer)

show()

mengisi username dan password baru

menekan tombol simpanupdateAccount

(string, string,

string, string) updateAccount

(string, string,

string)


1 controlPengiri

mPenerima





79

2 pengirimPeneri

maInternalFra

me

Interface /

Boundary

Kelas ini berfungsi untuk menampilkan

halaman pengirim penerima, dan tempat

user untuk menambah menghapus, dan

mengubah data pengirim dan penerima.

3 staffBagianDistr

ibusiMainFrame

Interface /

Boundary



bagian distribusi.

4 PilihNodeFrame Interface /

Boundary

Kelas ini berfungsi untuk mengatur

menampilkan peta yang digunakan oleh

user untuk memilih letak dari penerima

sesuai dengan alamatnya.

5 pengirimPeneri

maData

Entity Kelas ini menyediakan fungsi untuk

menangani inputan, hapus, ubah dari

tabel pengirim_penerima.

6 kabupatenData Entity Kelas ini berfungsi untuk mengelola

tabel kabupaten, baik itu insert, update,

maupun delete.

7 kecamatanData Entity Kelas ini berfungsi untuk mengelola

tabel kecamatan, baik itu insert, update,

maupun delete.

8 kelurahanData Entity Kelas ini berfungsi untuk mengelola

tabel kelurahan, baik itu insert, update,

maupun delete.

9 jalanData Entity Kelas ini berfungsi untuk mengelola

tabel jalan, baik itu insert, update,

maupun delete.


80

Gambar 3.33 Diagram Kelas Analisis Use Case Mengisi data Pengirim dan

Penerima

Gambar 3.34 Diagram Sekuen Mengisi data Pengirim dan Penerima

3.6.5 Diagram Kelas Analisis dan Diagram Sekuen Use Case Mengubah



pengirimPenerimaInternalFrame

pilihNodeFrame


kabupatenData

kecamatanData

kelurahanData

pengirimPenerimaData

jalanData

staffBagi

anDistrib

usi

<<Boundary>>


<<Controller>>


<<Boundary>>


<<Entity>>


<<Entity>>

kabupatenData

<<Entity>>

kecamatanData

<<Entity>>

kelurahanData

<<Entity>>

jalanData

<<Boundary>>

pilihNodeFrame

memilih menu

pengirim &

penerima

tampilMenu(integer)

pengirimPenerimaData()

1. Memilih menu pengirim & penerima

2. Menampilkan


3. Menekan tombol

pengirimPenerimaBaru

4. Mengisi data pengirim Penerima

7. Menekan tombol simpan

selectKabupaten(string)

selectKecamatan(string)

selectKelurahan(string)

selectJalan(string)

show()

menekan tombol pengirim penerima baru


mengisi data pengirim penerima

cariKoordinatAlamatPenerima(string, string,

string, string, string, string, string, string)

getCriKoordinatJalan(string, string)

show()

show()

pilih lokasi penerima

setLocation(int, int)

tekan tombol pilih

setKoordinat(string, string, string)

menekan tombol simpan

cekEmpty()

insertDataPengirimPenerima(string, string, string, string, int, int, string, string, string, string, string, string, string, string)konfirmasi()

5. Menampilkan animasi peta lokasi

yang di pilih user

6. Memilih lokasi peta penerima

8. insert data pengirim dan penerima

9. mendapatkan hasil konfirmasi



81

1 controlPengiri

mPenerima




2 pengirimPeneri

maInternalFra

me

Interface /

Boundary





3 staffBagianDistr

ibusiMainFrame

Interface /

Boundary



bagian distribusi.

4 PilihNodeFrame Interface /

Boundary

Kelas ini berfungsi untuk mengatur

menampilkan peta yang digunakan oleh

user untuk memilih letak dari penerima

sesuai dengan alamatnya.

5 pengirimPeneri

maData






maupun delete.



maupun delete.



maupun delete.



maupun delete.


82

Gambar 3.35 Diagram Kelas Analisis Use Case Mengubah Data Pengirim dan

Penerima

Gambar 3.36 Diagram Sekuen Mengubah Data Pengirim dan Penerima

3.6.6 Diagram Kelas Analisis dan Diagram Sekuen Use Case Menghapus




pilihNodeFrame


kabupatenData

kecamatanData

kelurahanData


jalanData

staffBagi

anDistrib

usi

<<Boundary>>


<<Controller>>


<<Boundary>>


<<Entity>>


<<Entity>>

kabupatenData

<<Entity>>

kecamatanData

<<Entity>>

kelurahanData

<<Entity>>

jalanData

<<Boundary>>

pilihNodeFrame

memilih menu

pengirim &

penerima

tampilMenu(integer)



3. Menampilkan


4. Memilih pengirim&penerima

yang akan diubah

5. Mengisi data pengirim Penerima

10. Menekan tombol simpan perubahan




selectJalan(string)

show()

memilih data pengirim dan penerima yang akan di ubah


mengisi data pengirim penerima

cariKoordinatAlamatPenerima(string, string,

string, string, string, string, string, string)

getCriKoordinatJalan(string, string)

show()

pilih lokasi penerima

setKoordinat(string, string, string)

menekan tombol simpan Perubahan

cekEmpty()

updateDataPengirimPenerima(int, string, string, string, string, int, int, string, string, string, string, string, string, string, string)konfirmasi()

6. Mencari koordinat alamat penerima

8. Memilih lokasi peta penerima

11. mengecek inputan

13. Sistem memberikan konfirmasi bahwa

data telah tersimpan

2. Memasukkan data kabupaten,

kecamatan, kelurahan, jalan

7. Menampilkan peta awal dan yang

dipilih

9. Memasukkan koordinat yang telah dipilih

ke pengirimPenerimaInternalFrame

12. Menyimpan update data pengirim penerima



83

1 controlPengiri

mPenerima




2 pengirimPeneri

maInternalFra

me

Interface /

Boundary





3 staffBagianDistr

ibusiMainFrame

Interface /

Boundary



bagian distribusi.

4 pengirimPeneri

maData






maupun delete.



maupun delete.



maupun delete.



maupun delete.


84

Gambar 3.37 Diagram Kelas Analisis Use Case Menghapus Data Pengirim dan

Penerima

Gambar 3.38 Diagram Sekuen Menghapus Data Pengirim dan Penerima

3.6.7 Diagram Kelas Analisis dan Diagram Sekuen Use Case Melihat

Daftar Pengiriman




kabupatenData

kecamatanData

kelurahanData


jalanData

staffBagi

anDistrib

usi

<<Boundary>>


<<Controller>>


<<Boundary>>


<<Entity>>


<<Entity>>

kabupatenData

<<Entity>>

kecamatanData

<<Entity>>

kelurahanData

<<Entity>>

jalanData

memilih menu

pengirim &

penerima

tampilMenu(integer)



3. memilih data pengirim penerima

yang akan dihapus

4. Menekan tombol hapus

6. menekan tombol ya




selectJalan(string)

show()

memilih data pengirim dan penerima yang akan di hapus

menekan tombol hapus

konfirmasi ya atau tidak

hapusPengirimPenerima()

konfirmasi()

7. Menghapus data pengirim_penerima

dari database

2. Menampilkan


8. Konfirmasi data telah dihapus

memilih tombol ya

hapusData(integer)

5. menampilkan konfirmasi data akan

dihapus atau tidak


1 controlPengiri Control Kelas ini berfungsi untuk mengatur


85

Gambar 3.39 Diagram Kelas Analisis Use Case Melihat Daftar Pengiriman


daftarPengirimanInternalFrame

controlDaftarPengiriman


daftarPengirimanData

mPenerima tampilan ketika action dijalankan oleh


2 controlDaftarP

engiriman

Control Kelas ini berfungsi untuk menangani

action dari


3 staffBagianDistr

ibusiMainFrame

Interface /

Boundary



bagian distribusi.

4 daftarPengirima

nInternalFrame

Interface /

Boundary


menampilkan daftar pengiriman

pengirim dan penerima, dan digunakan

actor untuk memilih daftar pengirim dan

penerima yang akan dikirimkan.

5 pengirimPeneri

maData

Entity Kelas ini berfungsi untuk menangani

inputan, hapus, ubah dari tabel

pengirim_penerima.


86

Gambar 3.40 Diagram Sekuen Melihat Daftar Pengiriman

3.6.8 Diagram Kelas Analisis dan Diagram Sekuen Use Case Mengupdate

Kondisi Jalan

staffBagi

anDistrib

usi

<<Boundary>>


<<Controller>>

daftarPengirimanControl

<<Boundary>>


<<Entity>>

daftarPengirimanData

<<Entity>>


memilih menu

daftar

Pengiriman

tampilMenu(integer)

show()

1. Memilih menu daftar pengiriman

3. Memilih tanggal Pengiriman

4. Menampilkan daftar pengiriman

pengirimanData()

daftarPengirimanTable.setModel(Default Table Model)

2. Menampilkan


pilih tanggal pengiriman

pengiriman()

viewPengirimPenerima(integer)


1 adminMainFram

e

Interface /

Boundary


menampilkan halaman utama admin.

2 kondisiJalanInte

rnalFrame

Interface /

Boundary


menampilkan halaman yang digunakan

user untuk mengubah kondisi jalan yang

bisa dilewati maupun tidak.

3 adminControl Control Kelas ini berfungsi untuk mengatur


adminMainFrame



maupun delete.


87

Gambar 3.41 Diagram Kelas Analisis Use Case Mengupdate Kondisi Jalan

Gambar 3.42 Diagram Sekuen Mengupdate Kondisi Jalan

3.6.9 Diagram Kelas Analisis dan Diagram Sekuen Use Case Ubah

Kecepatan Jalan

adminMainFrame

kondisiJalanInternalFrame

adminControljalanData

Administ

rator

<<Boundary>>


<<Boundary>>

kondisiJalanInternalFrame

<<Controller>>

adminControl

<<Entity>>

jalanData

memilih menu

ubah kondisi

jalan

tampilMenu(integer)

ubahKondisiJalan(integer)

1. Memilih menu ubah kondisi jalan

3. Mengganti status jalan yang

tidak bisa dilewati pada tabel


ubahKondisiJalan(integer)

2. Menampilkan form ubah kondisi jalan

mengganti status jalan

simpan()

show()


5. Menyimpan data kedalam database


1 adminMainFram

e

Interface /

Boundary


menampilkan halaman utama admin.

2 satuanPerhitung

anForm

Interface /

Boundary


menampilkan frame yang digunakan user

untuk mengubah data kecepatan tiap

jalan.

3 adminControl Control Kelas ini berfungsi untuk mengatur


adminMainFrame


88

Gambar 3.43 Diagram Kelas Analisis Use Case Ubah Kecepatan Jalan

Gambar 3.44 Diagram Sekuen Ubah Kecepatan Jalan

adminMainFrame

satuanPerhitunganFrame

adminControl

hitungKepadatanData

jalanData

Administ

rator

<<Boundary>>

adminMainFrame

<<Controller>>

adminControl

<<Boundary>>

satuanPerhitunganForm

<<Entity>>

hitungKepadatanData

memilih menu

ubah bobot

tampilMenu(integer)

tampilData(integer)

1. Memilih menu ubah bobot

3. Memilih data jalan yang akan

diubah

4. Menampilkan data jalan yang diubah

dalam field

updateKecWaktu(double, double, double, double, double)

2. Menampilkan form ubah bobot

memilih data jalan yang mau di ubah

validasiUpdate()

show()


5. Menekan tombol ubah

<<Entity>>

jalanData

selectionListener()

valueChanged()

menekan tombol ubah

getEnableAll(boolean)

setEnableAll(boolean)

merubah data yang mau di ubah

konfirmasi()

updateJalan(integer, double, double, double, double, double)

6. Menset enable pada field dan

merubah tombol ubah menjadi simpan

7. Merubah data yang mau di ubah


9. Memvalidasi data yang telah di

update

10. Menyimpan data yg telah

di ubah ke dalam database

11. Menampilkan konfirmasi



maupun delete.

5 hitungKepadata

nData

Entity Kelas ini berfungsi untuk mengelola

tabel hitungKepadatan, baik itu insert,

update, maupun delete.


89

3.7 Diagram Kelas Disain

Gambar 3.45 berikut ini merupakan diagram kelas yang akan

digunakan pada sistem yang akan dibangun. Seluruh kelas memiliki hubungan

asosiasi antara kelas yang satu dengan kelas yang lainnya.

Gambar 3.45 Diagram Kelas Keseluruhan


90



91



92



93

3.8 Perancangan Struktur Data

Dalam proses pembentukan rute terpendek hasil algoritma yaitu berupa

peta. Pembentukan data yang ada pada peta tersebut akan disimpan dalam Vector.

Vector merupakan suatu bentuk array dinamis yang merupakan turunan dan

implement yang sama dari arrayList. Dalam vector tidak diperlukan

pendeklarasian jumlah kuota yang harus disediakan untuk menampung data.

Kapasitas dari vector akan bertambah secara otomatis sesuai dengan jumlah data

yang disimpan. Dalam penelitian ini data yang data yang akan disimpan dalam

vector meliputi vertexlist. Sedangkan data yang disimpan dalam arrayList adalah ,

bobot waktu, tau, rute yang dilewati. Berikut ini merupakan penjelasan dari

masing-masing vector dan arrayList tersebut:

Nama Vector atau

arrayList

Keterangan

vertexlist Digunakan untuk menampung vertexList

bobot waktu Digunakan untuk menampung data bobot waktu array 2

dimensi

tau Digunakan untuk menampung data perubahan tau.

rute yang dilewati Digunakan untuk menampung vertexList yang menjadi

bagian rute yang telah dilewati


94

3.9 Perancangan Antarmuka Sistem

Gambar 3.46 Gambar Halaman Utama Staff Bagian Distribusi

Gambar 3.47 Gambar Halaman Daftar Pengiriman

Window

APLIKASI PERHITUNGAN JARAK PENGIRIMAN PAKET PT. POS INDONESIA

File Akun About

Pengirim & Penerima

Daftar Pengiriman

Logout

ubah Akun about

Window

pembanding random (q0)

konstanta rho

jumlah iterasi

Tabel

TextStatus

TextidPengirimPenerima

Simpan

Lihat Rute Pengiriman

konstanta beta

konstanta alpha

Text

Text

Text

Text

Text


95

Gambar 3.48 Gambar Halaman Hasil Rute Pengiriman

Gambar 3.49 Gambar Halaman Utama Administrator

Window

Peta Pengiriman

Rute Pengiriman

Bobot waktu

Jarak Tempuh

Window

Halaman Administrator

File Akun About

ubah bobot

Ubah Kondisi Jalan

Ubah Akun

Logout about


96

Gambar 3.50 Gambar Ubah Kondisi Jalan

Window

Table Peta kondisi

Kondisi Text

Simpan


97

BAB IV

IMPLEMENTASI PROGRAM

Pada bab ini akan dijelaskan lebih lanjut mengenai implementasi dari

perancangan “Penerapan Algoritma Ants Colony System pada Travelling

Salesman Problem” yang telah dibuat pada bab sebelumnya.

4.1. Perangkat Kebutuhan Sistem

Dalam pengujian sistem diperlukan sistem penunjang, diantaranya

sebagai berikut:

a. Microsoft Windows XP Professional SP 1

b. Mysql untuk databasenya

c. Java Runtime Environment

4.2. Uji Validasi Sistem

Pada penelitian ini dilakukan uji validasi sistem untuk memastikan bahwa

sistem yang dibangun menghasilkan keluaran yang benar. Hal yang diuji pada

penelitian ini yaitu path Search Destination dan pembentuk peta.

4.3. Implementasi Antar Muka dengan Pengguna

Antar muka merupakan tampilan yang nantinya akan berinteraksi

langsung dengan pengguna.

1. Halaman Login

Gambar dibawah ini merupakan halaman login. Terdapat dua

pilihan login sebagai Staff Bagian Distribusi atau login sebagai

Administrator. Jika ingin login isikan dahulu user name dan password

kemudian klik Ok.


98

Gambar 4.1 Halaman Login

Adapun proses login setelah klik ok akan masuk ke authentifikasi

login untuk pengecekan username dan password dengan kode program

authentifikasiLogin.java sebagai berikut:

public boolean autentik(String user, String pass, String

stts) {

userData ld = new userData();

String passenkripsi = ld.passEncrypt(pass);

String userEnkripsi = user;

String status = stts;

ld.getPassUsername(status);

String passHasil = ld.getPasswordHasil();

String userHasil = ld.getNama_userHasil();

String statusHasil = ld.getStatusHasil();

if (userEnkripsi.equals(userHasil) &&

passenkripsi.equals(passHasil) && status.equals("Staff Bagian

Distribusi")) {

staffBagianDistribusiMainFrame stf = new

staffBagianDistribusiMainFrame();

stf.show();

return true;

// this.dispose();


99

} else if (userEnkripsi.equals(userHasil) &&

passenkripsi.equals(passHasil) && status.equals("Administrator")) {

adminMainFrame adm = new adminMainFrame();

adm.show();

return true;

// this.dispose();

} else {

JOptionPane.showMessageDialog(null, "Username

dan pasword yang Anda \n masukkan salah silahkan sek kembali");

return false;

}

}

Apabila nama user dan password salah akan ada pesan kesalahan,

dan bila sudah benar akan langsung masuk halaman Administrator ataupun

halaman Staff bagian Distribusi.

Gambar 4.2 Tampilan Jika Login Salah

2. Halaman Utama Staff Bagian Distribusi

Gambar dibawah ini merupakan halaman utama pengguna setelah

login sebagai Staff Bagian Distribusi. Pada halaman ini terdapat 3 buah

menu yaitu menu File, Akun dan About. Menu File mempunyai submenu

Pengirim dan Penerima untuk pengolahan data pengirim dan penerima

yang akan mengirimkan paket, Daftar Pengiriman untuk pengolahan data

pengiriman yang akan diproses untuk pembentukan rute jalan, dan Logout.

Sedangkan Menu Akun mempunyai submenu Ubah Akun untuk ubah akun

user name dan password pada Staff Bagian Distribusi. Berikut gambar 4.3

merupakan halaman utama staff bagian distribusi.


100

Gambar. 4.3 Halaman Utama Staff Bagian Distribusi

3. Halaman Pengirim dan Penerima

Gambar dibawah ini merupakan halaman pengolahan data

pengirim dan penerima. Pada halaman ini terdapat daftar data pengirim

dan penerima yang telah diinputkan. Fungsi-fungsi yang ada pada halaman

ini adalah input, update, delete dan search by kategori. Berikut gambar 4.4

merupakan halaman pengirim dan penerima.


101

Gambar 4.4 Halaman Pengirim dan Penerima

Adapun proses inputkan data baru maka klik pengirim dan

penerima baru, isikan semua data-data pengirim dan penerima kemudian

klik simpan. Kemudian jika ingin mengubah data yang sudah ada adalah

klik dahulu daftar data yang akan diubah kemudian klik ubah dan ganti

kolom isian yang akan di perbaharui. Untuk menghapus data pilih data

yang akan dihapus kemudian klik hapus maka data akan terhapus. Proses-

proses tersebut berada pada kode program pengirimPenerimaData.java

sebagai berikut:

public boolean hapusData(int idhapus) {

Connection con = kon.getKon();

String query = "delete from pengirim_penerima where

id_pengirimpenerima=" + idhapus;

try {

PreparedStatement pre =

con.prepareStatement(query);

int j = pre.executeUpdate();

return true;

} catch (Exception e) {

System.out.println(e);

return false;

}

}


102

public void insertDataPengirimPenerima(String

nmPenerima, String node, String telpfPenerima, String

alamatPenerima, int koorX, int koorY, String namaJalan, String

kelurahan, String nmPengirim, String telpfPengirim, String

alamatPengirim, String tglKirim, String status) {

String query = "call

insertPengirimPenerima(?,?,?,?,?,?,?,?,?,?,?,?,?)";


try {

CallableStatement clls = con.prepareCall(query);

clls.setString(1, nmPenerima);

clls.setString(2, node);

clls.setString(3, telpfPenerima);

clls.setString(4, alamatPenerima);

clls.setInt(5, koorX);

clls.setInt(6, koorY);

clls.setString(7, namaJalan);

clls.setString(8, kelurahan);

clls.setString(9, nmPengirim);

clls.setString(10, telpfPengirim);

clls.setString(11, alamatPengirim);

clls.setString(12, tglKirim);

clls.setString(13, status);

clls.execute();



}

}

public boolean updateDataPengirimPenerima(int idPP,

String nmPenerima, String node, String telpfPenerima, String

alamatPenerima, int koorX, int koorY, String namaJalan, String

kelurahan, String nmPengirim, String telpfPengirim, String

alamatPengirim, String tglKirim, String status) {

String query = "call

updatePengirimPenerima(?,?,?,?,?,?,?,?,?,?,?,?,?,?)";


try {

CallableStatement clls = con.prepareCall(query);

clls.setInt(1, idPP);

clls.setString(2, nmPenerima);


103

clls.setString(3, node);

clls.setString(4, telpfPenerima);

clls.setString(5, alamatPenerima);

clls.setInt(6, koorX);

clls.setInt(7, koorY);

clls.setString(8, namaJalan);

clls.setString(9, kelurahan);

clls.setString(10, nmPengirim);

clls.setString(11, telpfPengirim);

clls.setString(12, alamatPengirim);

clls.setString(13, tglKirim);

clls.setString(14, status);

clls.execute();

return true;



return false;

}

}

4. Halaman Daftar Pengiriman

Gambar dibawah ini merupakan halaman pengolahan daftar

pengiriman. Pada halaman ini terdapat daftar data pengirim dan penerima

yang telah diinputkan berdasarkan tanggal. Fungsi-fungsi yang ada pada

halaman ini adalah proses untuk tampil jalur pengiriman. Sebelum nya

ubah dulu mode status belum menjadi kirim untuk data pengirim dan

penerima yang akan diproses. Kemudian inputkan parameter yang sesuai

dengan perhitungan algoritma semut yaitu parameter q, t0, q0, p, b, a.

Berikut gambar 4.5 merupakan halaman daftar pengiriman.


104

Gambar 4.5 Halaman Daftar Pengiriman

Jika ingin mengubah kondisi paket yang akan dikirimkan dari

pengirim ke penerima makan klik kolom yang akan di ubah, kemudian

ganti status belum menjadi kirim kemudian simpan. Kode program

tersebut ada pada pengirimPenerimaData.java.

public boolean updateStatus(String stts,int idPP){


String query = "update pengirim_penerima set

status=? where id_pengirimpenerima=?";

try {

PreparedStatement pre =

con.prepareStatement(query);

pre.setString(1, stts);

pre.setInt(2, idPP);

int a = pre.executeUpdate();

return true;



return false;

}

// return false;

}


105

Kemudian setelah dipastikan paket tersebut akan dikirim maka klik

tampil jalur pengiriman. Untuk menghasilkan peta secara visual dan jalur

yang akan dilewati serta waktu tempuh. Kode program ini terbagi atas

pathSearchDestination.java, graph.java, graphTengah.java.

5. Halaman Ubah Akun

Gambar dibawah ini merupakan halaman ubah akun. Pada halaman

ini berfungsi untuk mengganti username dan password sebelumnya. Untuk

mengganti password inputkan username, password baru, dan ulangi

password baru kemudian klik setuju. Perlu di ingat ini hanyak untuk

mengubah akun Staff Bagian Distribusi. Berikut gambar 4.6 merupakan

halaman ubah akun.

Gambar 4.6 Halaman Ubah Akun

Adapun untuk ubah akun akan melewati proses

updateAccountControl.java dengan kode program sebagai berikut:


106

public void updateAccount(String username,String

pass1,String pass2,String loginas){

if(pass1.equals(pass2)){

userData ud=new userData();

ud.updateUserData(username, pass2, loginas);


dan password telah

diubah","INFORMASI",JOptionPane.INFORMATION_MESSAGE);

}

else {

JOptionPane.showMessageDialog(null, "Password

pada field satu berbeda dengan \n pada field dua silahkan ulangi

lagi","Peringatan",JOptionPane.ERROR_MESSAGE);

}

}

6. Halaman Utama Administrator

Gambar dibawah ini merupakan halaman utama pengguna setelah

login sebagai Administrator. Pada halaman ini terdapat 3 buah menu yaitu

menu File, Ubah dan About. Menu File mempunyai submenu Logout.

Sedangkan Menu Ubah mempunyai submenu Ubah Bobot untuk ubah

bobot kecepatan dan Ubah Kondisi Jalan untuk mengubah kondisi jalan

baik atau buruk serta Ubah Akun sebagai Administrator. Berikut gambar

4.7 merupakan halaman utama administrator.


107

Gambar 4.7 Halaman Utama Administrator

7. Halaman Ubah Bobot

Gambar dibawah ini merupakan halaman ubah nilai bobot

kecepatan pagi, pagi menjelang siang, siang, siang menjelang sore dan

sore. Pada halaman ini terdapat daftar bobot kecepatan tersebut. Untuk

ubah pilih daftar bobot kecepatan kemudian klik ubah kemudian isikan

kecepatan pagi, pagi menjelang siang, siang, siang menjelang sore dan

sore dan klik simpan. Setelah di ubah klik simpan ke text supaya nilai yang

telah diubah dapat dieksport ke text supaya dapat diproses pembentukan

peta. Berikut gambar 4.8 merupakan halaman ubah bobot.


108

Gambar 4.8 Halaman Ubah Bobot

Adapun untuk ubah bobot kecepatan proses dari klik simpan

tersebut akan melewati proses updateKecWaktu pada adminControl.java

dengan kode program sebagai berikut:

public void updateKecWaktu(double kec1, double kec2,

double kec3, double kec4, double kec5, int kondisi) {

hitungKepadatanData hit = new hitungKepadatanData();

boolean ck = hit.updateDataHitung(kec1, kec2, kec3,

kec4, kec5, kondisi);

if (ck == true) {

jalanData jd = new jalanData();

ResultSet nilJarak =

jd.cariHitungJalan(kondisi);

try {

while (nilJarak.next()) {

int idJl = nilJarak.getInt(1);

double jrk = nilJarak.getDouble(2);

double wkt1 = jrk / kec1;





jd.updateJalan(idJl, wkt1, wkt2, wkt3,

wkt4, wkt5);

}


109



JOptionPane.showMessageDialog(null, "Data

Gagal disimpan ", "Peringatan", JOptionPane.ERROR_MESSAGE);

}

} else {

JOptionPane.showMessageDialog(null, "Data Gagal

disimpan ", "Peringatan", JOptionPane.ERROR_MESSAGE);

}

}

Dari updateKecWaktu akan melakukan kueri updateDataHitung

dari hitungKepadatanData.java, cariHitungJalan dan updateJalan pada

JalanData.java.

public boolean updateDataHitung(double kec1,double kec2,double

kec3,double kec4,double kec5,int kondisi){

boolean stts=false;

String query = "update hitungkepadatan set

kecepatan_pagi=?," +

"kecepatan_pagi_siang=?,kecepatan_siang=?," +

"kecepatan_siang_sore=?,kecepatan_sore=? where

idHitungKepadatan=?";


try {

PreparedStatement state = con.prepareStatement(query);

state.setDouble(1, kec1);





state.setInt(6, kondisi);

int a = state.executeUpdate();

stts=true;



stts=false;

}

return stts;

}


110

public ResultSet cariHitungJalan(int fkIdHit){

ResultSet hasil=null;

String query="select idJalan,jarak from jalan where

idHitungKepadatan="+fkIdHit;

Connection con=kon.getKon();

try {

Statement state=con.createStatement();

ResultSet rst=state.executeQuery(query);

hasil=rst;



}

return hasil;

}

public void updateJalan(int kondisi, double waktu1, double

waktu2, double waktu3, double waktu4, double waktu5) {

String query = "update jalan set waktu_pagi=?," +

"waktu_pagi_siang=?,waktu_siang=?,waktu_siang_sore=?," +

"waktu_sore=? where idJalan=?";


try {

PreparedStatement state = con.prepareStatement(query);

state.setDouble(1, waktu1);






111

state.setInt(6, kondisi);

int a = state.executeUpdate();



}

}

8. Halaman Ubah Kondisi Jalan

Gambar dibawah ini merupakan halaman ubah kondisi jalan baik

atau buruk. Pada halaman ini terdapat daftar nama jalan serta kondisi nya.

Untuk ubah pilih daftar kondisi jalan kemudian ganti kondisi ke baik atau

buruk kemudian klik simpan. Berikut gambar 4.9 merupakan halaman

ubah kondisi jalan.

Gambar 4.9 Halaman Ubah Kondisi Jalan

Adapun untuk ubah kondisi jalan akan melalui proses

updateKondisiJalan pada kode program jalanData.java sebagai berikut:

public void updateKondisiJalan(int id,String kondisi){

Connection con=kon.getKon();

String query="update jalan set kondisi=? where

idJalan=?";

try {


112

PreparedStatement

prep=con.prepareStatement(query);

prep.setString(1, kondisi);

prep.setInt(2, id);

int i=prep.executeUpdate();



}

}

9. Halaman Ubah Akun Administrator

Gambar dibawah ini merupakan halaman ubah akun administrator.

Pada halaman ini berfungsi untuk mengganti username dan password

sebelumnya. Untuk mengganti password inputkan username, password

baru, dan ulangi password baru kemudian klik setuju. Perlu di ingat ini

hanya untuk mengubah akun Administrator. Berikut gambar 4.10

merupakan halaman ubah akun.

Gambar 4.10 Halaman Ubah Akun Administrator


113

Adapun untuk ubah akun akan melewati proses

updateAccountControl.java dengan kode program sebagai berikut:

public void updateAccount(String username,String

pass1,String pass2,String loginas){

if(pass1.equals(pass2)){

userData ud=new userData();

ud.updateUserData(username, pass2, loginas);


dan password telah

diubah","INFORMASI",JOptionPane.INFORMATION_MESSAGE);

}

else {

JOptionPane.showMessageDialog(null, "Password

pada field satu berbeda dengan \n pada field dua silahkan ulangi

lagi","Peringatan",JOptionPane.ERROR_MESSAGE);

}

}

4.4. Implementasi Diagram Kelas

Sistem dibangun dengan berbasis objek, sehingga dalam implementasi

dibutuhkan kelas – kelas untuk mendefinisikan objek yang akan dipakai untuk

membangun sistem. Dalam sistem yang dibangun ini kelas-kelas yang dibentuk

dibagi dalam 4 package yaitu package Entity, Boundary, Controller dan Tools.

Karena banyaknya metode dalam pembuatan sistem, maka yang disajikan pada

penelitian ini hanya metode yang berperan penting dalam penelitian yaitu metode

Ants Colony System (ACS), Sedangkan untuk penyajian metode secara lengkap

terlampir pada lampiran 1. Berikut ini disajikan penjabaran metode ACS yang

dibangun dalam penelitian.

Nama Paket : Control

Nama Kelas : pathSearchDestination

Nama Metode : cariRuteTerpendek(int waktuMulai, double to, double qo,

double p, double b, double a, double q, int nSemut)


114

Fungsi Metode :

Berfungsi untuk melakukan proses algoritma ants colony system. Hasil dari

metode ini berupa rute peta pengiriman.

Listing Program :

//mencari bobot waktu yang sesuai dengan inputan waktu mulai ========

List waktu = preJalurTerpendek(waktuMulai);

int zone = (Integer) waktu.get(0);

List wktuZona = (List) urutanWaktu.get(zone);

//mancari urutan vertexlist yang akan di cari node nya terlebih dahulu===

List baru = new ArrayList();

List hrf = mencariUrutanCluster("vertexlist3", to, q, qo, b, p);

//mengubah dari nama cluster menjadi id di Object nameMap =========

System.out.println(" Urutan Cluster dalam Angka");

for (int i = 0; i < hrf.size(); i++) {

int angTmp = (Integer) ubahKeAngka((String) hrf.get(i));

baru.add(angTmp);

System.out.print(baru.get(i) + " ");

}

System.out.println("");

for (int semut = 0; semut < nSemut; semut++) {

gabungPath = new ArrayList();

//mengubah matriks dan invers pada Urutan Cluster ke – 0 ============

vertex[] vr = (vertex[]) listVertexPerMap.get((Integer) baru.get(0));

double[][] amNew = (double[][]) wktuZona.get((Integer) baru.get(0));

List vNew = ubahMatrik(getNodeAwal(), amNew, vr);

vertex[] vrTmp = (vertex[]) vNew.get(0);

double[][] amNewTmp = (double[][]) vNew.get(1);

double[][] amBobot = (double[][]) vNew.get(2);


115

if (semut == 0) {

//pheromone awal dalam bentuk matriks ==================

List tMatrik = ubahMatrikPheromone(to, amNewTmp);

tMatAwal = (double[][]) tMatrik.get(0);

}

if (semut > 0) {

tMatAwal = finalTau;

}

//pencarian graph Cluster ke – 0 ===========================

graph gpCluster = new graph(vrTmp, amNewTmp, vrTmp.length,

vrTmp.length, tMatAwal,

q, qo, b, p, (Integer) baru.get(1), amBobot);

List hsl = gpCluster.ssnJalan();

finalPath = new ArrayList();

finalPath = (List) hsl.get(0);

finalBobot = (Double) hsl.get(1);

finalTau = (double[][]) hsl.get(2);

//menambahkan final tau pada gabung final tau untuk di bandingkan

pada update pheromone global ==============================

gabungFT.add(finalTau);

gabungFP.add(finalPath);

gabungVerUrut.add(vrTmp);

//tampil jalur vertex cluster 0 ============================

//System.out.println("Coba tampil jalur vertex Awal : "+ (Integer)

baru.get(0));

for (int i = 0; i < finalPath.size()-1; i++) {

// System.out.print(finalPath.get(i).toString()+ "--->");

gabungPath.add(finalPath.get(i));

}


116

gabungBobot = finalBobot;

int v=0;

//Ulang sampai pencarian graph dr Cluster 0 - Akhir selesai========

for (int i = 1; i < baru.size() - 1; i++) {

//mengubah matriks pada Urutan Cluster ke - i==============

vertex[] vrIn = (vertex[]) listVertexPerMap.get((Integer) baru.get(i));

double[][] amIn = (double[][]) wktuZona.get((Integer) baru.get(i));

if (semut == 0) {

//pheromone awal dalam bentuk matriks===============

List tMatrik2 = ubahMatrikPheromone(to, amIn);

tMatAwal2 = (double[][]) tMatrik2.get(0);

}

if (semut >0) {

for (int j = v; j <= 5; j++) {

tMatAwal2 = (double[][]) tauTemp.get(j);

break;

}

v++;

}

//pencarian graph Cluster ke – I =================

int h = i;

graphTengah gpClusterIn = new graphTengah(vrIn, amIn, vrIn.length,

vrIn.length,

finalPath, finalBobot, tMatAwal2, q, qo, b, p, (Integer) baru.get(h

+ 1));

List tmpIncluster = gpClusterIn.cariPath();


finalPath = (List) tmpIncluster.get(0);

finalBobot = (Double) tmpIncluster.get(1);

finalTau = (double[][]) tmpIncluster.get(2);


117

vertex[] testvertexbaru = (vertex[]) tmpIncluster.get(3);

tauTemp.add(finalTau);



gabungVerUrut.add(testvertexbaru);

//tampil jalur vertex cluster ke – I ===============

for (int d = 0; d < finalPath.size()-1; d++) {

//gabung path ==================

gabungPath.add(finalPath.get(d));

}

//gabung bobot ===============================

gabungBobot = gabungBobot + finalBobot;

}

//mengubah matriks pada Urutan Cluster Akhir ========

vertex[] vrAkhir = (vertex[]) listVertexPerMap.get((Integer)

baru.get(baru.size()-1));

double[][] amAkhir = (double[][]) wktuZona.get((Integer)


if (semut == 0) {

//pheromone awal dalam bentuk matriks ==============

List tMatAkhir = ubahMatrikPheromone(to, amAkhir);

tMatrikAkhir = (double[][]) tMatAkhir.get(0);

}

if (semut > 0) {

tMatrikAkhir = finalTau;

}

//pencarian graph Cluster ke – I ======================

graphTengah gpAkhir = new graphTengah(vrAkhir, amAkhir,

vrAkhir.length, vrAkhir.length,

finalPath, finalBobot, tMatrikAkhir, q, qo, b, p);


118

List tmpAkhcluster = gpAkhir.pathAkhir();


finalPath = (List) tmpAkhcluster.get(0);

finalBobot = (Double) tmpAkhcluster.get(1);

finalTau = (double[][]) tmpAkhcluster.get(2);

vertex[]testvertexakhir = (vertex[]) tmpAkhcluster.get(3);



gabungVerUrut.add(testvertexakhir);

//tampil jalur vertex cluster ke – I ==========

for (int d = 0; d < finalPath.size(); d++) {


}


//gabung path ========================================

System.out.println("Gabung Path");

//tampil jalur vertex cluster ke – I =====================

for (int d = 0; d < gabungPath.size(); d++) {

System.out.print(gabungPath.get(d).toString()+ "--->");

}

System.out.println("bobot gabung : "+gabungBobot);

bandingBobot.add(gabungBobot);

bandingPath.add(gabungPath);

//set desstination baru ===============================

for (int j = 0; j < listVertexPerMap.size(); j++) {

vertex[] vere = (vertex[])listVertexPerMap.get(j);

for (int k = 0; k < vere.length; k++) {

if (vere[k].isIsInDestinationNext() == true) {

vere[k].setIsInDestination(true);


119

}

}

}

}

//path dan bobot waktu terbaik ===================

double bbtTerbaik = (Double)bandingBobot.get(0);

List pathTerbaik = (List) bandingPath.get(0);

int nilaiI = 0;

for (int i = 1; i < bandingBobot.size(); i++) {

if (bbtTerbaik > (Double)bandingBobot.get(i)) {

bbtTerbaik=(Double)bandingBobot.get(i);

pathTerbaik=(List) bandingPath.get(i);

nilaiI = i;

}

}

List global = updatePheromoneGlobal (gabungFT, a, bbtTerbaik,

gabungFP, gabungVerUrut, hrf.size(), nSemut, nilaiI);

List hasilAkhir = new ArrayList();

hasilAkhir.add(bandingPath);

hasilAkhir.add(bandingBobot);

hasilAkhir.add(pathTerbaik);

hasilAkhir.add(bbtTerbaik);

return hasilAkhir;


120

BAB V

ANALISIS HASIL IMPLEMENTASI

Tahap akhir dari penelitian ini adalah rute pengiriman, waktu tempuh dan

jarak tempuh. Sistem yang dibangun ditahap sebelumnya mengimplementasikan

algoritma Ant Colony system (ACS) dan telah berhasil diimplementasikan kedalam

sebuah program. Dalam tahap analisis akan ada perubahan parameter untuk mencapai

hasil yang berbeda. Nilai default dari masing-masing parameter adalah:

parameter nilai

t0 0.01

q0 0.1

p 0.1

b 2

a 0.1

m 1

1. Perubahan nilai q0 dan t0

t0 (0.0001)

t0 (0.009) t0 (0.01) t0 (0.5) t0 (1)

q0 (0.25) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.75) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.9) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.99) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (1) 25.11783 25.11783 25.11783 25.11783 25.11783

2. Perubahan nilai q0 dan p

p (0.005) p (0.1) p (0.4) p (0.8) p (1)

q0 (0.25) 25.11783 25.11783 25.11783 25.11783 25.11783


121

q0 (0.75) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.9) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.99) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (1) 25.11783 25.11783 25.11783 25.11783 25.11783

3. Perubahan nilai q0 dan B

b (0.01) b (0.5) b (2) b (5) b (10)

q0 (0.25) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.75) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.9) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.99) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (1) 25.11783 25.11783 25.11783 25.11783 25.11783

4. Perubahan nilai q0 dan a

a (0.03) a (0.4) a (0.6) a (0.9) a (1)

q0 (0.25) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.75) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.9) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (0.99) 25.11783 25.11783 25.11783 25.11783 25.11783

q0 (1) 25.11783 25.11783 25.11783 25.11783 25.11783

5. Perubahan nilai q0 dan m semut

m (1) m (5) m (10) m (25) m (50) m (100)

q0 (0.25) 25.11783 24.33635 16.07243 5.279087 error error

q0 25.11783 24.33635 16.07243 5.279087 error error


122

(0.75)

q0 (0.9) 25.11783 24.33635 16.07243 5.279087 error error

q0 (0.99) 25.11783 24.33635 16.07243 5.279087 error error

q0 (1) 25.11783 24.33635 16.07243 5.279087 error error

6. Perubahan nilai t0 dan p

p (0.005) p (0.1) p (0.4) p (0.8) p (1)

t0 (0.0001) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (0.009) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (0.01) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (0.5) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (1) 25.11783 25.11783 25.11783 25.11783 25.11783

7. Perubahan nilai t0 dan b

b (0.01) b (0.5) b (2) b (5) b (10)

t0 (0.0001) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (0.009) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (0.01) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (0.5) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (1) 25.11783 25.11783 25.11783 25.11783 25.11783

8. Perubahan nilai t0 dan a

a (0.03) a (0.4) a (0.6) a (0.9) a (1)

t0 (0.0001) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (0.009) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (0.01) 25.11783 25.11783 25.11783 25.11783 25.11783


123

t0 (0.5) 25.11783 25.11783 25.11783 25.11783 25.11783

t0 (1) 25.11783 25.11783 25.11783 25.11783 25.11783

9. Perubahan nilai t0 dan m semut

m (1) m (5) m (10) m (25) m (50) m (100)

t0 (0.0001) 25.11783 25.11783 25.11783 23.16756 22.99762 22.99762

t0 (0.009) 25.11783 25.11783 16.01538 14.36957 error error

t0 (0.01) 25.11783 24.33635 16.07243 5.279087 error error

t0 (0.5) 25.11783 19.26376 18.25726 7.627835 error error

t0 (1) 25.11783 19.26376 18.25726 8.486218 error error

10. Perubahan nilai p dan b

b (0.01) b (0.5) b (2) b (5) b (10)

p (0.005) 25.11783 25.11783 25.11783 25.11783 25.11783

p (0.1) 25.11783 25.11783 25.11783 25.11783 25.11783

p (0.4) 25.11783 25.11783 25.11783 25.11783 25.11783

p (0.8) 25.11783 25.11783 25.11783 25.11783 25.11783

p (1) 25.11783 25.11783 25.11783 25.11783 25.11783

11. Perubahan nilai p dan a

a (0.03) a (0.4) a (0.6) a (0.9) a (1)

p

(0.005) 25.11783 25.11783 25.11783 25.11783 25.11783

p (0.1) 25.11783 25.11783 25.11783 25.11783 25.11783

p (0.4) 25.11783 25.11783 25.11783 25.11783 25.11783

p (0.8) 25.11783 25.11783 25.11783 25.11783 25.11783


124

p (1) 25.11783 25.11783 25.11783 25.11783 25.11783

12. Perubahan nilai p dan m semut

m (1) m (5) m (10) m (25) m (50) m (100)

p (0.005) 25.11783 25.11783 25.11783 20.11139 19.07446 17.19837

p (0.1) 25.11783 24.33635 16.07243 5.279087 error error

p (0.4) 25.11783 16.08433 error error error error

p (0.8) 25.11783 error error error error error

p (1) 25.11783 error error error error error

13. Perubahan nilai b dan a

a (0.03) a (0.4) a (0.6) a (0.9) a (1)

b (0.01) 25.11783 25.11783 25.11783 25.11783 25.11783

b (0.5) 25.11783 25.11783 25.11783 25.11783 25.11783

b (2) 25.11783 25.11783 25.11783 25.11783 25.11783

b (5) 25.11783 25.11783 25.11783 25.11783 25.11783

b (10) 25.11783 25.11783 25.11783 25.11783 25.11783

14. Perubahan nilai b dan m semut

m (1) m (5) m (10) m (25) m (50) m (100)

b (0.01) 25.11783 13.83106 13.83106 error error error

b (0.5) 25.11783 13.83106 13.83106 error error 17.28792

b (2) 25.11783 24.33635 16.07243 5.279087 error error

b (5) 25.11783 25.11783 25.11783 24.50283 17.28792 error

b (10) 25.11783 25.11783 19.07446 17.28792 17.28792 17.28792


125

15. Perubahan nilai a dan m semut

m (1) m (5) m (10) m (25) m (50) m (100)

a (0.03) 25.11783 24.33635 16.07243 error error error

a (0.4) 25.11783 24.33635 16.07243 5.279087 error error

a (0.6) 25.11783 24.33635 16.07243 5.279087 error error

a (0.9) 25.11783 24.33635 16.07243 5.279087 error error

a (1) 25.11783 24.33635 16.07243 5.279087 error error


126

BAB VI

PENUTUP

6.1. Kesimpulan

Setelah dilakukan penelitian, perancangan, implementasi dan analisis

hasil implementasi dari aplikasi sistem, maka dapat diambil kesimpulan

sebagai berikut:

1. Algoritma ACS dapat diterapkan untuk penentuan rute terpendek

pengiriman barang pada P.T. Pos Indonesia ini.

2. Sistem aplikasi penerapan algoritma ACS dalam menentukan rute

terpendek pada P.T. Pos Indonesia ini memudahkan Staff bagian

Distribusi P.T. Pos Indonesia dalam mendistribusikan paket nya.

3. Perubahan parameter q0, t0, p, b, a tidak banyak berpengaruh kepada hasil

algoritma ACS jika tidak disertai perubahan nilai m semut.

4. Perubahan nilai m semut paling baik antara nilai 5 sampai 50, jika nilai m

semut lebih dari 100 maka akan menghasilkan algoritma ACS yang buruk.

5. Waktu terpendek dari 4 titik tglu3, wch2, kb35, gkan5 adalah 25 menit

dengan jarak 70 km dengan penggunaan parameter q0 adalah 0.1, t0

adalah 0.01, p adalah 0.1, b adalah 2 dan a adalah 0.1.

6.2. Saran

Walaupun sistem aplikasi ini sudah berjalan dengan sebagaimana

mestinya, namun masih terdapat banyak kekurangan, beberapa saran yang

bisa dilakukan dan digunakan untuk pengembangan lebih lanjut, yaitu :

1. Dilakukan implementasi di kantor pos tersebut untuk menguji unjuk kerja

sistem.


127

2. Penambahan beberapa fasilitas atau menu pendukung yang lebih menarik

dan lengkap, misal cetak pdf dan aplikasi versi mobile.


128

DAFTAR PUSTAKA

Dorigo, Marco., Gambardella, Luca Maria. (1997). “Ant Colonies for the travelling

salesman problem”.

Dorigo, Marco., Gambardella, Luca Maria. (1997). “Ant Colony System: A

Cooperative Learnng Approach to the Travelling Salesman Problem”.

Stutzle, Thomas.,et.al. (2010). “Parameter Adaptation in Ant Colony

Optimization”.IRIDA, Belgia.

Catur, Nikolas (2010). “Optimasi Distribusi Majalah Dengan Menggunakan Metode

Djikstra”.

Mindaputra, Eka (2009). “Penggunaan Algoritma Ant Colony System dalam

Travelling Salesman Problem (TSP) pada P.T. Eka Jaya Motor”.

http://dishub-diy.net/dinas/survey-lalu-lintas.html. Diakses pada tanggal, 19

Desember 2012.


http://dishub-diy.net/dinas/survey-lalu-lintas.html

129

Lampiran 1

ATRIBUT DAN METHOD ALGORITMA ACS

1.1 pathSearchDestination

Atribut

double maping[][];

vertex nameMap[];

List listVertexPerMap;

List bobotWaktu1 = new ArrayList();

List bobotWaktu2;

List bobotWaktu3;

List bobotWaktu4;

List bobotWaktu5;

List rentangWaktu;

List urutanWaktu;

List finalPath = new ArrayList();

List gabungPath = new ArrayList();

List tauTemp = new ArrayList();

double finalTau[][];

double tMatAwal [][];

double tMatAwal2 [][];

double tMatrikAkhir [][];

double finalBobot;

double gabungBobot;

List bandingBobot = new ArrayList();

List bandingPath = new ArrayList();

String nodeAwal;

List gabungFT = new ArrayList();

List gabungFP = new ArrayList();

List gabungVerUrut = new ArrayList();


130

Method

cariJalur()

Input:

AbstractTabelModel abm

int waktuBerangkat

double t0

double q0

double p

double b

double a

double q

double smt

Output:

void

Algoritma:

1. setNodeAwal("riut18");

2. addDesination("riut18");

3. List krdinatDest = new ArrayList();

4. int total = abm.getRowCount();

5. int indek = 0;

6. for int i = 0; i < total

String statusPesanan = String.valueOf(abm.getValueAt(i, 3));

if statusPesanan.equals("kirim")

int[] as = new int[2];

int agnI = (Integer) abm.getValueAt(i, 0);


131

pengirimPenerimaData ad = new pengirimPenerimaData();

ad.pengirimPenerimaLengkap(agnI);

addDesination(ad.getNode());

as[0] = ad.getKoordinatX();

as[1] = ad.getKoordinatY();

krdinatDest.add(as);

indek++;

end for

7. if indek > 0

List tmp = cariRuteTerpendek(waktuBerangkat, to, qo, p, b, a, q, smt);

List pathAlt = (List)tmp.get(0);

List bobotAlt = (List) tmp.get(1);

for int i = 0; i < pathAlt.size();

List Alternatif = new ArrayList();

List pathPerBag = (List)pathAlt.get(i);

double bobotPerBag = (Double) bobotAlt.get(i);

Alternatif.add(pathPerBag);

Alternatif.add(bobotPerBag);

jalanYangDilewati(Alternatif, krdinatDest);

end for

List Terbaik = new ArrayList();

List pathTerbaik = (List)tmp.get(2);

double bobotTerbaik = (Double) tmp.get(3);

Terbaik.add(pathTerbaik);


132

Terbaik.add(bobotTerbaik);

jalanYangDilewati(Terbaik, krdinatDest);

end if

cariRuteTerpendek()

Input:

int waktuBerangkat

double t0

double q0

double p

double b

double a

double q

double smt

Output:

List

Algoritma:

1. List waktu = preJalurTerpendek(waktuMulai);

2. int zone = (Integer) waktu.get(0);

3. List wktuZona = (List) urutanWaktu.get(zone);

4. List baru = new ArrayList();

5. List hrf = mencariUrutanCluster("vertexlist3", to, q, qo, b, p);

6. for int i = 0; i < hrf.size();

int angTmp = (Integer) ubahKeAngka((String) hrf.get(i));

baru.add(angTmp);


133

end for

7. for int semut = 0; semut < nSemut;

gabungPath = new ArrayList();

vertex[] vr = (vertex[]) listVertexPerMap.get((Integer) baru.get(0));

double[][] amNew = (double[][]) wktuZona.get((Integer) baru.get(0));

List vNew = ubahMatrik(getNodeAwal(), amNew, vr);

vertex[] vrTmp = (vertex[]) vNew.get(0);

double[][] amNewTmp = (double[][]) vNew.get(1);

double[][] amBobot = (double[][]) vNew.get(2);

if (semut == 0)

List tMatrik = ubahMatrikPheromone(to, amNewTmp);

tMatAwal = (double[][]) tMatrik.get(0);

end if

if (semut > 0)

tMatAwal = finalTau;

end if

graph gpCluster = new graph(vrTmp, amNewTmp, vrTmp.length,

vrTmp.length, tMatAwal, q, qo, b, p, (Integer) baru.get(1), amBobot);

List hsl = gpCluster.ssnJalan();


finalPath = (List) hsl.get(0);

finalBobot = (Double) hsl.get(1);

finalTau = (double[][]) hsl.get(2);



gabungVerUrut.add(vrTmp);

for int i = 0; i < finalPath.size()-1;

gabungPath.add(finalPath.get(i));

end for


134

gabungBobot = finalBobot;

int v=0;

for (int i = 1; i < baru.size() - 1; i++)

vertex[] vrIn = (vertex[]) listVertexPerMap.get((Integer)

baru.get(i));

double[][] amIn = (double[][]) wktuZona.get((Integer) baru.get(i));

if (semut == 0)

List tMatrik2 = ubahMatrikPheromone(to, amIn);

tMatAwal2 = (double[][]) tMatrik2.get(0);

end if

if (semut >0)

tMatAwal2 = (double[][]) tauTemp.get(v);

v++;

end if

int h = i;

graphTengah gpClusterIn = new graphTengah(vrIn, amIn,

vrIn.length, vrIn.length, finalPath, finalBobot, tMatAwal2, q, qo, b, p,

(Integer) baru.get(h + 1));

List tmpIncluster = gpClusterIn.cariPath();


finalPath = (List) tmpIncluster.get(0);

finalBobot = (Double) tmpIncluster.get(1);

finalTau = (double[][]) tmpIncluster.get(2);

vertex[] testvertexbaru = (vertex[]) tmpIncluster.get(3);

tauTemp.add(finalTau);



gabungVerUrut.add(testvertexbaru);

for (int d = 0; d < finalPath.size()-1; d++)


135


end for


end for

vertex[] vrAkhir = (vertex[]) listVertexPerMap.get((Integer)


double[][] amAkhir = (double[][]) wktuZona.get((Integer)


if (semut == 0)

List tMatAkhir = ubahMatrikPheromone(to, amAkhir);

tMatrikAkhir = (double[][]) tMatAkhir.get(0);

end if

if (semut > 0)

tMatrikAkhir = finalTau;

end if

graphTengah gpAkhir = new graphTengah(vrAkhir, amAkhir,

vrAkhir.length, vrAkhir.length, finalPath, finalBobot, tMatrikAkhir, q, qo, b,

p);

List tmpAkhcluster = gpAkhir.pathAkhir();


finalPath = (List) tmpAkhcluster.get(0);

finalBobot = (Double) tmpAkhcluster.get(1);

finalTau = (double[][]) tmpAkhcluster.get(2);

vertex[]testvertexakhir = (vertex[]) tmpAkhcluster.get(3);



gabungVerUrut.add(testvertexakhir);

for (int d = 0; d < finalPath.size(); d++) {



136

}


bandingBobot.add(gabungBobot);

bandingPath.add(gabungPath);

for (int j = 0; j < listVertexPerMap.size(); j++) {

vertex[] vere = (vertex[])listVertexPerMap.get(j);

for (int k = 0; k < vere.length; k++) {

if (vere[k].isIsInDestinationNext() == true)

vere[k].setIsInDestination(true);

end if

end for

end for

end for

8. double bbtTerbaik = (Double)bandingBobot.get(0);

9. List pathTerbaik = (List) bandingPath.get(0);

10. int nilaiI = 0;

11. for (int i = 1; i < bandingBobot.size(); i++)

if (bbtTerbaik > (Double)bandingBobot.get(i))

bbtTerbaik=(Double)bandingBobot.get(i);

pathTerbaik=(List) bandingPath.get(i);

nilaiI = i;

end if

end for

12. List global = updatePheromoneGlobal (gabungFT, a, bbtTerbaik,

gabungFP, gabungVerUrut, hrf.size(), nSemut, nilaiI);

13. List hasilAkhir = new ArrayList();

14. hasilAkhir.add(bandingPath);

15. hasilAkhir.add(bandingBobot);

16. hasilAkhir.add(pathTerbaik);


137

17. hasilAkhir.add(bbtTerbaik);

18. return hasilAkhir;

mencariUrutanCluster()

Input:

String StartVertex;

double to;

double q;

double qo;

double b;

double p;

Output:

List

Algoritma:

1. int jmlNameMaping = 0;

2. for (int i = 0; i < nameMap.length; i++)

if (nameMap[i].isIsInDestination())

jmlNameMaping++;

end if

end for

3. List mapingBaru = ubahMatrik(StartVertex, maping, nameMap);

4. vertex[] VlistBaru = (vertex[]) mapingBaru.get(0);

5. double[][] adListBaru = (double[][]) mapingBaru.get(1);

6. List tMatrik = ubahMatrikPheromone(to, adListBaru);

7. double[][] tMatrik2 = (double[][]) tMatrik.get(0);

8. graph gpCluster = new graph(VlistBaru, adListBaru, VlistBaru.length,

VlistBaru.length, tMatrik2, q, qo, b, p, nameMap);

9. List nn = gpCluster.ssnMaping();


138

10. return nn;

jalanYangDilewati()

Input:

List jalur;

List tujuan;

Output:

void

Algoritma:

1. controlPengirimPenerima ca = new controlPengirimPenerima();

2. jalanData jd = new jalanData();

3. List pathJalurAkhir = (List) jalur.get(0);

4. double bobotAkhir = (Double) jalur.get(1);

5. String jalurTmpFile = "";

6. for (int j = 0; j < pathJalurAkhir.size(); j++)

if (j != pathJalurAkhir.size() - 1)

String vrt = (String) pathJalurAkhir.get(j);

int a = j;

String vrt2 = (String) pathJalurAkhir.get(a + 1);

String tmpHasil = jd.namaJalanKoordinat(vrt.toString(),

vrt2.toString());

jalurTmpFile = jalurTmpFile + "\n" + tmpHasil;

end if

String ver = (String) pathJalurAkhir.get(j);

End for

7. double jarak= createXml(pathJalurAkhir);

8. petaPengirimanFrame pp = new petaPengirimanFrame();

9. String tmpbbt = String.valueOf(bobotAkhir);

10. pp.setJalur(jalurTmpFile);


139

11. pp.setTotalPengiriman(tmpbbt);

12. pp.setTotalJarak(String.valueOf(jarak));

13. pp.setKrr(tujuan);

14. pp.show();

15. pp.addJalan();

16. pp.repaint();

preJalurTerpendek()

Input:

double waktuMulai

Output:

List

Algoritma:

1. List ckList = new ArrayList();

2. int timezone = 1000000;

3. for (int i = 0; i < rentangWaktu.size(); i++)

double[] tmp = (double[]) rentangWaktu.get(i);

if (tmp[0] <= waktuMulai && tmp[tmp.length - 1] > waktuMulai)

timezone = i;

end if

end for

4. ckList.add(timezone);

5. return ckList;

ubahKeAngka()

Input:

String vList;

Output:

int


140

Algoritma:


if (nameMap[i].getLabel().equals(vList))

return i;

end if

end for

2. return 0;

ubahMatrik()

Input:

String startAt;

double[][] aMat;

vertex[] vrtList;

Output:

List

Algoritma:

1. int koordinat = 0;

2. for (int k = 0; k < vrtList.length; k++)

vertex vrt = vrtList[k];

if (vrt.getLabel().equals(startAt))

koordinat = k;

end if

end for

3. vertex[] vrtListBaru = new vertex[vrtList.length];

4. int k = 0;

5. for (int i = koordinat; i < vrtList.length; i++)

vrtListBaru[k] = vrtList[i];

k++;

end for


141

6. for (int i = 0; i < koordinat; i++)

vrtListBaru[k] = vrtList[i];

k++;

end for

7. double test2[][] = new double[aMat.length][aMat.length];

8. int a = 0;

9. int b;

10. for (int i = koordinat; i < aMat.length; i++)

b = 0;

for (int j = koordinat; j < aMat.length; j++)

test2[a][b] = aMat[i][j];

b++;

end for

for (int j = 0; j < koordinat; j++)


b++;

end for

a++;

end for

11. for (int i = 0; i < koordinat; i++)

b = 0;

for (int j = koordinat; j < vrtList.length; j++)


b++;

end for

for (int j = 0; j < koordinat; j++)


b++;

end for


142

a++;

end for

12. double aIMat[][] = new double [aMat.length][aMat.length];

13. for (int i = 0; i < aMat.length; i++)

for(int j = 0; j < aMat.length; j++)

aIMat[i][j]= 1 / test2[i][j];

end for

end for

14. List masuk = new ArrayList();

15. masuk.add(vrtListBaru);

16. masuk.add(aIMat);

17. masuk.add(test2);

18. return masuk;

ubahMatrikPheromone()

Input:

double to;

double [][] aMat;

Output:

List

Algoritma:

1. double aIMat[][] = new double [aMat.length][aMat.length];

2. for (int i = 0; i < aMat.length; i++)

for(int j = 0; j < aMat.length; j++)

aIMat[i][j]= to;

end for

end for


4. masuk.add(aIMat);


143

5. return masuk;

ubahPheromoneGlobal()

Input:

List tMatrik;

double a;

double Lgb;

List rute;

List InvVertex;

int cluster;

int semut;

int I;

Output:

List

Algoritma:

1. int bagi= tMatrik.size()/semut;

2. List baruTau = new ArrayList();

3. List baruVert = new ArrayList();

4. List baruRut = new ArrayList();

5. List finalHasilGlobal = new ArrayList();

6. int q = 0;

7. for (int i = 0; i < tMatrik.size(); i++)

for (int j = 0; j < semut; j++)

if (cluster == semut)

for (int k = q; k < bagi; k++)

baruTau.add(tMatrik.get(k));

baruVert.add(InvVertex.get(k));

baruRut.add(rute.get(k));

end for


144

end if

q = bagi;

bagi = bagi * semut;

end for

end for

8. for (int i = 0; i < baruTau.size(); i++)

double[][] percluster = (double[][])baruTau.get(i);

vertex[] perVert = (vertex[]) baruVert.get(i);

String[] perRut = (String[]) baruRut.get(i);

double[][] hasilGlobal = new

double[percluster.length][percluster.length];

double deltaT1 = 1/Lgb;

double deltaT2 = 0;

for(int j=0; j<percluster.length; j++)

for(int k=0; k<percluster.length; k++)

for (int l = 0; l < perRut.length-1; l++)

if(perVert[j].toString().equals(perRut[l].toString()) &&

perVert[k].toString().equals(perRut[l+1].toString()))

hasilGlobal[j][k] = ((1-a) * percluster[j][k]) + (a*deltaT1);

end if

else

hasilGlobal[j][k] = ((1-a) * percluster[j][k]) + (a*deltaT2);

end else

end for

end for

end for

finalHasilGlobal.add(hasilGlobal);

end for



145

10. masuk.add(finalHasilGlobal);

11. masuk.add(baruVert);

12. masuk.add(baruRut);

13. return masuk;

addDestination()

Input:

String dest;

Output:

boolean

Algoritma:


vertex[] vertexList = (vertex[]) listVertexPerMap.get(i);

for (int j = 0; j < vertexList.length; j++)

if (dest.equals(vertexList[j].getLabel()))

vertexList[j].setIsInDestination(true);

vertexList[j].setIsInDestinationNext(true);

System.out.println("nama map " + nameMap[i].getLabel());

vertex vr = nameMap[i];

vr.setIsInDestination(true);

cobaTampilHasilSet(vertexList[j]);

System.out.println("pada bagian vertex " + i);

return true;

end if

end for

end for

2. return false;

1.2 graph


146

Atribut

private List bobot = new ArrayList();

private List susunanJalan = new ArrayList();

private String sudahPernahJalan [];

private List daftarPernahJalan = new ArrayList();

private List tLokal = new ArrayList();

private String lewatJalan = new String();

private String nodeInfinity = new String();

private vertex vertexList[];

private double adjMat[][];

private vertex nmMap [];

private double tMatriks [][];

private double adBobot [][];

private double hasil [][];

private double INFINITY;

private int nVerts;

private double nilaiQ;

private double nilaiQ0;

private double nilaiB;

private double nilaiP;

private double max;

int angkaJalanAwal =0;;

int nextAngkaJalan;

String jalanPresent = new String();

String nextJalan = new String();

private int next;

private boolean statusDest;

private double bw;


147

Method

path2()

Input:

-

Output:

void

Algoritma:

1. int jumlahtitik = 0;

2. for (int i = 0; i < vertexList.length; i++)

if (vertexList[i].isIsInDestination())

jumlahtitik++;

end if

end for

3. jalanPresent = vertexList[angkaJalanAwal].getLabel();

4. susunanJalan.add(jalanPresent);

5. vertexList[angkaJalanAwal].setIsInTree(true);

6. while (jumlahtitik > 1)

statusDest = false;

if(nilaiQ <= nilaiQ0)

List pers1 = inisialisasiStatus1();

hasil = (double[][]) pers1.get(0);

INFINITY = cekInvinity();

end if

if(nilaiQ > nilaiQ0)



double jumlah = Double.parseDouble(pers2.get(1).toString()) ;

INFINITY = cekInvinity2(jumlah);


148

end if

max = INFINITY;

for (int j = 1; j < nVerts; j++)

if (!vertexList[j].isIsInTree() && hasil[angkaJalanAwal][j] >

max && vertexList[j].isIsInDestination())

max = hasil[angkaJalanAwal][j];

nextAngkaJalan=j;

statusDest = true;

end if

end for

if (max == INFINITY)

for (int i = 1; i < nVerts; i++)

if (!vertexList[i].isIsInTree() && hasil[angkaJalanAwal][i] >

max )

max = hasil[angkaJalanAwal][i];

nextAngkaJalan = i;

end if

end for

end if

nextJalan = vertexList[nextAngkaJalan].getLabel();

vertexList[nextAngkaJalan].setIsInTree(true);

susunanJalan.add(nextJalan);

angkaJalanAwal = nextAngkaJalan;

if (statusDest == true)

jumlahtitik--;

end if

end while

7. for (int i = 0; i < nVerts; i++)

vertexList[i].setIsInDestination(false);


149

end for

8. clusterSetTrue("vertexlist3");

9. clusterSetTrue(nextJalan);

10. vertexList[0].setIsInTree(false);

11. jumlahtitik = 1;

12. while (jumlahtitik > 0)

statusDest = false;





end if






end if

max = INFINITY;


if (!vertexList[j].isIsInTree() && hasil[angkaJalanAwal][j] >

max && vertexList[j].isIsInDestination())


nextAngkaJalan = j;

statusDest = true;

end if

end for




150

if (!vertexList[i].isIsInTree() && hasil[angkaJalanAwal][i] >

max)


nextAngkaJalan = i;

end if

end for

end if


vertexList[nextAngkaJalan].setIsInTree(true);




jumlahtitik--;

end if

end while

path3()

Input:

-

Output:

void

Algoritma:




jumlahtitik++;

end if

end for

3. angkaJalanAwal =0;


151


5. lewatJalan = vertexList[angkaJalanAwal].getLabel();


7. sudahPernahJalan = new String[2];

8. sudahPernahJalan[0] =lewatJalan;

9. while (jumlahtitik >= 0)

statusDest = false;





end if






end if

max = INFINITY;


if (susunanJalan.size()>=2)

if

(!vertexList[j].getLabel().equals(susunanJalan.get(susunanJalan.size()-

2).toString()) && !vertexList[j].getLabel().equals(nodeInfinity) &&

hasil[angkaJalanAwal][j] > max && nodePernahJalan(jalanPresent,

vertexList[j].getLabel()) && vertexList[j].isIsInDestination())


nextAngkaJalan = j;

statusDest = true;


152

end if

end if

else

if (!vertexList[j].getLabel().equals(nodeInfinity) &&


vertexList[j].getLabel()) &&

vertexList[j].isIsInDestination() )\


nextAngkaJalan = j;

statusDest = true;

end if

end else

end if



if (susunanJalan.size() >= 2)

if (

!vertexList[i].getLabel().equals(susunanJalan.get(susunanJalan.size()-

2).toString()) &&

!vertexList[i].getLabel().equals(nodeInfinity) &&

hasil[angkaJalanAwal][i] > max &&

nodePernahJalan(jalanPresent, vertexList[i].getLabel()))


nextAngkaJalan = i;

end if

end if

else

if (hasil[angkaJalanAwal][i] > max &&



153



nextAngkaJalan = i;

end if

end else

end for

end if

if (max != INFINITY)

lewatJalan = vertexList[nextAngkaJalan].getLabel();

sudahPernahJalan[1] = lewatJalan;

daftarPernahJalan.add(sudahPernahJalan);

sudahPernahJalan = new String[2];

end if




bobot.add(max);

updatePheromoneLokal();


jalanPresent = nextJalan;

end if

else

nodeInfinity = null;

nodeInfinity = nextJalan;

susunanJalan.remove(susunanJalan.size()-1);

bobot.remove(bobot.size()-1);



154

if

(vertexList[i].getLabel().equals(susunanJalan.get(susunanJalan.size()-

1).toString()))

angkaJalanAwal = i;

end if

end for

jalanPresent = vertexList[angkaJalanAwal].getLabel();

nextJalan = jalanPresent;

end else


vertexList[nextAngkaJalan].setIsInDestination(false);

jumlahtitik--;

end if

if (jumlahtitik ==0 && vertexList[nextAngkaJalan].isIsInPersimpangan()

== next)

jumlahtitik--;

end if

sudahPernahJalan[0] = jalanPresent;

end while

path4()

Input:

-

Output:

void

Algoritma:


if (vertexList[i].getLabel().equals("riut18"))

vertexList[i].setIsInDestination(true);


155

end if

end for




jumlahtitik++;

end if

end for

4. angkaJalanAwal =0;


6. lewatJalan = vertexList[angkaJalanAwal].getLabel();


8. sudahPernahJalan = new String[2];

9. sudahPernahJalan[0] =lewatJalan;

10. while (jumlahtitik >= 1)

statusDest = false;





end if






end if

max = INFINITY;



156

if (susunanJalan.size()>=2)

if

(!vertexList[j].getLabel().equals(susunanJalan.get(susunanJalan.size()-

2).toString()) &&!vertexList[j].getLabel().equals(nodeInfinity) &&


vertexList[j].getLabel()) &&vertexList[j].isIsInDestination())


nextAngkaJalan = j;

statusDest = true;

end if

end if

else

if (!vertexList[j].getLabel().equals(nodeInfinity) &&


vertexList[j].getLabel()) && vertexList[j].isIsInDestination() )


nextAngkaJalan = j;

statusDest = true;

end if

end else

end for



if (susunanJalan.size() >= 2)

if (

!vertexList[i].getLabel().equals(susunanJalan.get(susunanJalan.size()-

2).toString()) &&!vertexList[i].getLabel().equals(nodeInfinity) &&

hasil[angkaJalanAwal][i] > max && nodePernahJalan(jalanPresent,

vertexList[i].getLabel()))


157


nextAngkaJalan = i;

end if

end if

else

if (hasil[angkaJalanAwal][i] > max &&




nextAngkaJalan = i;

end if

end else

end for

end if


lewatJalan = vertexList[nextAngkaJalan].getLabel();

sudahPernahJalan[1] = lewatJalan;

daftarPernahJalan.add(sudahPernahJalan);

sudahPernahJalan = new String[2];

end if




bobot.add(max);

double[][] tMat = updatePheromoneLokal();


jalanPresent = nextJalan;

end if

else


158

nodeInfinity = null;

nodeInfinity = nextJalan;

susunanJalan.remove(susunanJalan.size()-1);

bobot.remove(bobot.size()-1);


if

(vertexList[i].getLabel().equals(susunanJalan.get(susunanJalan.size()-

1).toString()))

angkaJalanAwal = i;

end if

end for

jalanPresent = vertexList[angkaJalanAwal].getLabel();

nextJalan = jalanPresent;

end else


vertexList[nextAngkaJalan].setIsInDestination(false);

jumlahtitik--;

end if

sudahPernahJalan[0] = jalanPresent;

end while

inisialisasiStatus1()

Input:

-

Output:

List

Algoritma:

1. double[][] krMatrik = new double [adjMat.length][adjMat.length];

2. for (int i = 0; i < adjMat.length; i++)


159

for(int j = 0; j < adjMat.length; j++)

krMatrik[i][j]= adjMat[i][j];

end for

end for

3. for(int x = 1; x<nilaiB; x++)

for (int i = 0; i < adjMat.length; i++)


krMatrik[i][j]= krMatrik[i][j] * adjMat[i][j];

end for

end for

end for

4. double[][] baru = new double [adjMat.length][adjMat.length];

5. for (int i = 0; i < adjMat.length; i++){

for(int j = 0; j < adjMat.length; j++){;

baru[i][j]= tMatriks[i][j] * krMatrik[i][j];

end for

end for


7. masuk.add(baru);

8. return masuk;

inisialisasiStatus2()

Input:

-

Output:

List

Algoritma:


160

1. double[][] krMatrik = new double [adjMat.length][adjMat.length];


System.arraycopy(adjMat[i], 0, krMatrik[i], 0, adjMat.length);

end for

3. for(int x = 1; x<nilaiB; x++)

for (int i = 0; i < adjMat.length; i++)


krMatrik[i][j]= krMatrik[i][j] * adjMat[i][j];

end for

end for

end for

4. double[][] baru = new double [adjMat.length][adjMat.length];



baru[i][j]= tMatriks[i][j] * krMatrik[i][j];

end for

end for

6. double jumlah = 0.0;

7. for(int k=0; k<baru.length; k++)

jumlah = jumlah + baru[angkaJalanAwal][k];

end for

8. for(int m=0; m < baru.length; m++)

baru[angkaJalanAwal][m] = baru[angkaJalanAwal][m] / jumlah;

end for


10. masuk.add(baru);

11. masuk.add(jumlah);

12. return masuk;


161

updatePheromoneLokal()

Input:

-

Output:

double[][]

Algoritma:

1. double Lnn = 0;

2. int c = adjMat.length;

3. for(int i=0; i<adjMat.length; i++)

for(int j=0; j<adjMat.length; j++)

if(vertexList[i].getLabel().equals(jalanPresent) &&

vertexList[j].getLabel().equals(nextJalan))

Lnn = adjMat[i][j];

end if

end for

end for

4. double deltaT = 1 / (Lnn * c);

5. for(int i=0; i<tMatriks.length; i++)

for(int j=0; j<tMatriks.length; j++)

if (vertexList[i].getLabel().equals(jalanPresent) &&

vertexList[j].getLabel().equals(nextJalan))

tMatriks[i][j] = ((1-nilaiP) * tMatriks[i][j]) + (nilaiP*deltaT);

end if

end for

end for

6. return tMatriks;

1.3 graphTengah


162

Atribut

vertex vertexList[];

double adjMat[][];

List nextAwal;

double bobotBefore;

int next;

double[][] tMatriks;

double nilaiQ;

double nilaiQ0;

double nilaiB;

double nilaiP;

Method

cariPath()

Input:

-

Output:

List

Algoritma:

1. List gabunganPath = new ArrayList();

2. List correctAwal = new ArrayList();

3. List bbtAwal = new ArrayList();

4. List pathPilihan = new ArrayList();

5. double bobotPilihan = 0;

6. double[][] tauPilihan;

7. for (int i = 0; i < nextAwal.size(); i++)

if (CariNode(nextAwal.get(nextAwal.size()-1).toString()))

correctAwal.add(nextAwal.get(i));


163

bbtAwal.add(bobotBefore);

end if

end for

8. List awalBaru2 = ubahMatrik(nextAwal.get(nextAwal.size()-1).toString(),

adjMat, vertexList);

9. vertex[] vListBaru2 = (vertex[]) awalBaru2.get(0);

10. double[][] adMatBaru2 = (double[][]) awalBaru2.get(1);

11. double[][] amBobot = (double[][]) awalBaru2.get(2);

12. graph grpIncluster2 = new graph(vListBaru2, adMatBaru2,

vListBaru2.length, vListBaru2.length, tMatriks, nilaiQ, nilaiQ0, nilaiB,

nilaiP, next, amBobot);

13. List clsterlanjut = grpIncluster2.ssnJalan();

14. pathPilihan = new ArrayList();

15. pathPilihan = (List) clsterlanjut.get(0);

16. bobotPilihan = (Double) clsterlanjut.get(1);

17. tauPilihan = (double[][]) clsterlanjut.get(2);

18. for (int i = 0; i < vListBaru2.length; i++) {

for (int j = 0; j < pathPilihan.size(); j++) {

if (vListBaru2[i].getLabel().equals(pathPilihan.get(j).toString()))

break;

end if

end for

end for

19. awalBaru2 = null;

20. adMatBaru2 = null;

21. gabunganPath.add(pathPilihan);

22. gabunganPath.add(bobotPilihan);

23. gabunganPath.add(tauPilihan);

24. gabunganPath.add(vListBaru2);


164

25. vListBaru2 = null;

26. return gabunganPath;

pathAkhir()

Input:

-

Output:

List

Algoritma:

1 List gabunganPath = new ArrayList();

2 List correctAwal = new ArrayList();

3 List bbtAwal = new ArrayList();

4 List pathPilihan = new ArrayList();

5 double bobotPilihan = 0;

6 double[][] tauPilihan;

7 for (int i = 0; i < nextAwal.size(); i++)

if (CariNode(nextAwal.get(i).toString()))

correctAwal.add(nextAwal.get(i));

bbtAwal.add(bobotBefore);

end if

end for

8 List awalBaru2 = ubahMatrik((String) correctAwal.get(0), adjMat,

vertexList);

9 vertex[] vListBaru2 = (vertex[]) awalBaru2.get(0);

10 double[][] adMatBaru2 = (double[][]) awalBaru2.get(1);

11 double[][] amBobot2 = (double[][]) awalBaru2.get(2);

12 graph grpIncluster2 = new graph(vListBaru2, adMatBaru2,

vListBaru2.length, vListBaru2.length, tMatriks, nilaiQ, nilaiQ0, nilaiB,

nilaiP, amBobot2);


165

13 List clusterAkhir = grpIncluster2.ssnJalan();

14 pathPilihan = new ArrayList();

15 pathPilihan = (List) clusterAkhir.get(0);

16 bobotPilihan = (Double) clusterAkhir.get(1);

17 tauPilihan = (double[][]) clusterAkhir.get(2);

18 awalBaru2 = null;

19 adMatBaru2 = null;

20 gabunganPath.add(pathPilihan);

21 gabunganPath.add(bobotPilihan);

22 gabunganPath.add(tauPilihan);

23 gabunganPath.add(vListBaru2);

24 vListBaru2 = null;

25 return gabunganPath;


plagiat merupakan tindakan tidak … graf .....7 2.1.1 definisi graf .....7 2.1.2 definisi walk,...

Documents

Konsep Dasar Graf

APLIKASI TEORI GRAF

Graf · contoh graf sederhana 2. Graf tak-sederhana (unsimple-graph ). Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph ). G 2 dan G 3 pada

Multi Graf Ida

Dasar-dasar Teori Graf - Gunadarmasabri.staff.gunadarma.ac.id/Downloads/files/71023/02...Definisi Graf 𝐺( ,𝐺)adalah struktur diskrit yang terdiri dari: 1. Himpunan yang anggotanya

graf theory

`BAB II LANDASAN TEORIGambar 2.3 (1 ) Graf Kosong dan (2 ) G raf tidak Kosong Definisi 2.2 (R inaldi Munir, 2007) Derajat (Degree) suatu simpul pada graf tak- berarah adalah jumlah

LOGIKA DAN ALGORITMA - febianto.staff.gunadarma.ac.idfebianto.staff.gunadarma.ac.id/Downloads/files/47036/Bab+1+-+Dasar...Dasar Teori Graf • Definisi Graf Graf G (V, E), adalah koleksi

Paper Graf Is

Teori Graf

Angio Graf i

pewarnaan graf

Graf Miliequivalen(2)

PEMBERIAN NOMOR VERTEX PADA TOPOLOGI JARINGAN GRAF … filejaringan graf yang berbentuk graf wheel , graf helm dan graf lollipop . Didapatkan hasil penelitian berupa penomoran vertex

Makalah Teori Graf(Graf Berarah)

Graf Berarah

BAB II STUDI LITERATUR garis besar, bab dua berisi berbagai studi literatur mengenai teori graf, social network dan text classification. Pembahasan mengenai teori graf mencakup definisi

Interpolasi, Definisi, dan Macam-macamnya

AUTOMORFISME GRAF BINTANG DAN GRAF LINTASAN …etheses.uin-malang.ac.id/6709/1/07610029.pdf · 2.8.1 Graf Lintasan (Path Graph) ... 2.9. Isomorfisme Graf..... 25 2.10. Automorfisme

Graf (Bagian 1)

PELABELAN JUMLAH EKSKLUSIF PADA GRAF MATAHARI, GRAF …lib.ui.ac.id/file?file=digital/20299156-S1957-Pelabelan jumlah.pdfpelabelan jumlah eksklusif pada graf matahari, graf korona,

TEORI GRAF - ilhamsaifudin12.files.wordpress.com · 4 Contoh Aplikasi Graf Terminologi Graf 5 6 Graf-graf Khusus Representasi Graf 7 8 Graf Isomorfik . OUTLINE 1. PENDAHULUAN 1. PENDAHULUAN

DIMENSI PARTISI GRAF HASIL OPERASI COMB GRAF …

Karto Graf i

pemberian nomor vertex pada topologi jaringan graf wheel, graf

BAB II TINJAUAN PUSTAKA 2.1 Pewarna Definisi dan Macam Pewarna

Makalah Graf

Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

Graf Pohon

Graf Bagian 1

Graf - dinus.ac.id · contoh graf sederhana 2. Graf tak-sederhana (unsimple-graph ). Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph ). G

febianto.staff.gunadarma.ac.idfebianto.staff.gunadarma.ac.id/.../47041/Teori+Graf.doc · Web viewTeori Dasar Graf. Kelahiran Teori Graf . Teori Graf mulai dikenal pada saat seorang

Oceano Graf i

Teori Graf

Pengantar Graf