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 (41)!

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 0q1, q0

adalah sebuah parameter yaitu Probabilitas semut melakukan eksplorasi

pada setiap tahapan, dimana (0 q01) 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



1. Sistem menampilkan tabel data

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

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

Documents

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

Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

Makalah Teori Graf(Graf Berarah)

Multi Graf Ida

pewarnaan graf

Makalah Graf

Graf Pohon

GRAF BERARAH

Konsep Dasar 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

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 Complete

Paper Graf Is

Graf (bagian 5 )

Teori Dasar Graf

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

APLIKASI TEORI GRAF

Pengantar Graf

Radio Graf i

Tm Graf Kelvin

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

Graf Miliequivalen(2)

Video Graf i

The Use of Mixed Eulerian Lagrangian Displacement in ...ftsl.itb.ac.id/wp-content/uploads/sites/8/2016/09/6.-Binsar-The-Use-Of-Mixed-Eulerian... · The paper deals with the use of

sirkuit eulerian

Angio Graf i

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

pemberian nomor vertex pada topologi jaringan graf wheel, graf

SIFAT-SIFAT GRAF KOSET DAN GRAF …repository.uin-malang.ac.id/1774/7/1774.pdfLAPORAN PENELITIAN PENGUATAN PROGRAM STUDI SPEKTRUM GRAF KONJUGASI DAN GRAF KOMPLEMEN GRAF KONJUGASI DARI

TEORI GRAF

SKRIPSI - etheses.uin-malang.ac.idetheses.uin-malang.ac.id/6758/1/08610057.pdf · BAB II: KAJIAN PUSTAKA ... 2.7 Macam-Macam Graf Khusus ... Di dalam teori graf terdapat beberapa

DIMENSI PARTISI GRAF HASIL OPERASI COMB GRAF …

PEMBERIAN NOMOR VERTEX PADA TOPOLOGI JARINGAN GRAF … filejaringan graf yang berbentuk graf wheel , graf helm dan graf lollipop . Didapatkan hasil penelitian berupa penomoran vertex

graf theory

Teori Graf