bab 2 landasan teori 2.1 teori graf 2.1.1 pengenalan...
Embed Size (px)
TRANSCRIPT
-
BAB 2
LANDASAN TEORI
2.1 Teori Graf
2.1.1 Pengenalan Teori Graf
Teori graf adalah cabang ilmu yang mempelajari sifat-sifat graf, yang pertama
kali diperkenalkan pada tahun 1736. Baru pada sekitar tahun 1920 teori graf berkembang
pesat terutama di bidang ilmu komputer, kimia, bahasa, ekonomi, dan riset operasi.
Gambar 2.1 Jembatan utama di Königsberg (Sumber: Rinardi Munir, 2005, p.355)
Menurut catatan sejarah, masalah jembatan Königsberg adalah masalah yang
pertama kali menggunakan graf (tahun 1739) [Rinardi Munir, 2005, p.354]. Di kota
Königsberg (sebelah timur negara bagian Prussia, Jerman), sekarang bernama kota
Kaliningrad, terdapat sungai Pregal yang mengalir mengitari Pulau Kneiphof lalu
bercabang menjadi dua buah anak sungai yang diperlihatkan oleh gambar 2.1.
Permasalahannya ialah menemukan pejalanan atau rute dari suatu kota melalui ketujuh
-
11
buah jembatan masing-masing tepat satu kali, kemudian kembali lagi ke tempat awal.
Pulau tersebut tidak dapat dicapai oleh rute apapun selain melalui jembatan-jembatan
tersebut.
Tahun 1736, Leonhard Euler adalah orang pertama yang berhasil menemukan
jawaban masalah tersebut dengan pembuktian yang sederhana (melalui karya tulisannya
Seven Bridges of Königsberg). Daratan (titik-titik yang dihubungkan oleh jembatan)
dinyatakan sebagai titik disebut verteks dan jembatan dinyatakan sebagai edge. Dari
analisa Euler pada jembatan Königsberg menghasilkan sebuah model graf, seperti yang
diperlihatkan pada gambar 2.2. Analisis Euler mengenai permasalahan jembatan di
Königsberg tidak menghasilkan solusi. Karena orang tidak mungkin melalui ketujuh
jembatan masing-masing tepat satu kali dan kembali lagi ke tempat awal keberangkatan
jika derajat (banyaknya garis yang bersisian dengan titik) setiap verteks tidak seluruhnya
genap. Penemuan Euler adalah kunci yang menandai perkembangan topologi, di mana
perbedaan antara layout sebenarnya dan graf scematic adalah contoh yang bagus untuk
gagasan bahwa topologi tidak dibatasi dengan bentuk kaku dari objek-objek tertentu.
Gambar 2.2 Graf yang merepresentasikan jembatan Königsberg (Sumber: Rinardi Munir, 2005, p.355)
C
B
AD
-
12
2.1.2 Definisi Graf
Graf adalah kumpulan verteks atau node yang dihubungkan satu sama lain
melalui sisi/rusuk/busur/edge, yang digunakan untuk merepresentasikan objek-objek
diskrit dan hubungan antara objek-objek tersebut. Graf G didefinisikan sebagai pasangan
himpunan (V,E), ditulis dengan notasi G(V,E), yang dalam hal ini.
i. V adalah himpunan tidak kosong dari simpul-simpul (titik/verteks/node).
ii. E adalah himpunan sisi (rusuk/edge) yang menghubungkan sepasang simpul.
Verteks-verteks pada graf dapat merupakan obyek sembarang seperti kota, atom-
atom suatu zat, nama anak, jenis buah, komponen alat elektronik dan sebagainya. Edge
dapat menunjukkan hubungan sembarang seperti rute penerbangan, jalan raya,
sambungan telepon, ikatan kimia, dan lain-lain. Jika terdapat sebuah rusuk e yang
menghubungkan verteks v dan w, ditulis edge (v, w).
2.1.3 Jenis Graf
Graf dapat dibagi menjadi 2 jenis berdasarkan arahnya, yaitu sebagai berikut.
1. Graf tidak berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah. Edge (v, w) = edge (w, v)
adalah sisi yang sama, di tampilkan pada gambar 2.3 di mana V = {A, B, C,
D} dan e = {e1, e2, e3, e4}.
-
13
Gambar 2.3 Graf tidak berarah
2. Graf berarah (directed graph)
Graf yang setiap sisinya diberikan orientasi arah, Edge (v, w) ≠ edge (w, v),
yang di tampilkan pada gambar 2.4 di mana V = {A, B, C, D} dan e = {e1, e2,
e3, e4, e5, e6, e7}.
Gambar 2.4 Graf berarah (Sumber: Seymour Lipschutz, 1985, p.119)
Sebuah struktur graf bisa dikembangkan dengan memberi bobot atau nilai pada
tiap edge di mana merupakan suatu nilai yang dapat berupa biaya atau jarak, graf
semacam ini disebut graf berbobot (weighted graph). Dalam pengajaran teori graf
[Seymour Lipschutz, 1985, p.85], terdapat graf khusus beberapa diantaranya adalah
sebagai berikut.
e4
e3
e2
e1
edge
node
D
C
A
B
A
B
De1
e2 e3 e4 e6
e5
e7 C
-
14
a) Complete graph ialah graf di mana setiap verteks berhubungan dengan semua
verteks yang lain (semua verteks saling berhubungan). Biasanya
direpresentasikan dengan simbol Kn, dimana K adalah complete graph dan n
jumlah verteks. Sebuah complete graph dengan n verteks akan mempunyai rusuk
sebanyak n(n-1)/2.
Gambar 2.5 Contoh model complete graph (K5) (Sumber: Seymour Lipschutz, 1985, p.85)
b) Bipartite graph adalah graf dimana satu verteksnya dibagi kedalam dua subset
verteks m dan n, sedemikian sehingga tidak ada rusuk yang menyebabkan
verteks-verteks dalam subset yang sama. Biasanya direpresentasikan dengan
simbol Km,n , di mana K adalah bipartite graph, dan m adalah jumlah sunset
verteks m, dan n adalah jumlah subset n.
Gambar 2.6 Contoh model bipartite graph (K3,3) (Sumber: Seymour Lipschutz, 1985, p.86)
-
15
c) Complete bipartite graph adalah bipartite graph di mana setiap verteks dari m
harus memiliki rusuk yang berhubungan ke semua verteks dari n. Biasanya
direpresentasikan dengan simbol Km,n , sama seperti bipartite graph.
Gambar 2.7 Contoh model bipartite graph (K2,3) (Sumber: Seymour Lipschutz, 1985, p.86)
d) Regular graph adalah graf dimana setiap verteksnya memiliki derajat yang
sama.
Gambar 2.8 Contoh model regular graph berderajat 2 (Sumber: Seymour Lipschutz, 1985, p.85)
e) Tree adalah graf yang tidak memiliki cycle. Jika jumlah verteks pada tree adalah
n, maka jumlah rusuk pada tree adalah n-1.
Gambar 2.9 Contoh model tree graph (Sumber: Seymour Lipschutz, 1985, p.86)
-
16
2.1.4 Teori Lintasan dan Siklus
Misalkan vo dan vn adalah verteks-verteks dalam sebuah graf [Richard
Johnsonbaugh, 2002, p.12]. Sebuah lintasan dari vo ke vn dengan panjang n adalah sebuah
barisan berselang-seling dari (n+1) verteks dan n edge yang berawal dengan verteks vo
dan berakhir dengan verteks vn,
(v0, e1, v1, e2, v2, …, vn-1, en, vn)
Dengan rusuk ei insiden pada verteks vi-1 dan vi ( i= 1, 2, …, n).
Sebuah siklus adalah sebuah litasan yang mempunyai panjang lintasan tidak nol
dari kota pertama sampai kota terakhir yang merupakan kota pertama, di mana tidak
terdapat rusuk yang dilalui lebih dari sekali.
Sebuah siklus sederhana adalah siklus dari kota pertama sampai kota terakhir
yang merupakan kota terakhir juga pada suatu graf, yang kecuali kota pertama dan kota
terakhir yang sama, tidak terdapat verteks yang berulang
Untuk mengamati perbedan anatara lintasan, siklus, siklus sederhana, dengan
contoh graf pada gambar 2.10 dapat dilihat yang akan disajikan dalam bentuk tabel.
Gambar 2.10 Graf tidak berarah (Sumber: Richard Johnsonbaugh, 2002, p.12)
1
23
4
5
6
7
-
17
Tabel 2.1 Perbedaan Lintasan, Siklus, dan Siklus Sederhana (Sumber: Richard Johnsonbaugh, 2002, p.16)
Lintasan Lintasan Sederhaa Siklus Siklus Sederhana
( 5, 6, 2, 5) Tidak Ya Ya ( 2, 6, 5, 2, 4, 3, 2) Tidak Ya Tidak ( 6, 5, 2, 4) Ya Tidak Tidak ( 6, 5, 2, 4, 3, 2, 1) Tidak Tidak Tidak
2.1.5 Representasi Graf
Misalkan G adalah sebuah graf dengan verteks-verteks v1, v2, …, vn dan edge e1,
e2, …, en maka didefinisikan dua macam matriks yang berhubungan dengan sebuah graf
G [Seymour Lipschutz, 1985, p.87].
1. Matriks adjacency
Misalkan A=(aij) adalah matriks m x n yang didefinisikan oleh:
jika {u, v} adalah edge, yaitu vi adjacent terhadap vj
lainnya
2. Matriks incident
Misalkan M=(mij) adalah matriks m x i didefinisikan oleh:
verteks vi adalah incident pada edge ei
lainnya
Contoh:
Diketahui graf G:
v1
v2 v3
v4
v5
e1
e2
e3
e4
e5
e6e7
e8
⎩⎨⎧
=01
ija
⎩⎨⎧
=01
m
-
18
maka:
v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
0110110101110110010111110
5
4
3
2
1
vvvvv
A
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
0110001010110000110011000000100100010111
5
4
3
2
1
vvvvv
m
(a) (b)
Gambar 2.11 matriks adjecency (a) dan matriks incidence (b) (Sumber: Seymour Lipschutz, 1985, p.87)
2.1.6 Graf Hamiton
Lintasan Hamilton ialah lintasan yang melalui tiap verteks di dalam graf tepat satu
kali [Rinardi Murni, 2005, p. 408]. Sirkuit Hamilton ialah sirkuit yang melalui tiap
verteks di dalam graf tepat satu kali, kecuali verteks asal (sekaligus verteks akhir) yang
dilalui dua kali. Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton,
sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.
Gambar 2.12 Penggambaran Graf Hamilton (Sumber: Rinardi Murni, 2005, p. 409)
Keterangan gambar 2.12:
a. Graf yang memiliki lintasan Hamilton (3, 2, 1, 4)
(a) (b) (c)
1 2
3 4
1 2
3 4
1 2
3 4
-
19
b. Graf yang memiliki lintasan Hamilton (1, 2, 3, 4, 1)
c. Graf yang tidak memiliki lintasan maupun sirkuit Hamilton
2.2 Algoritma
Secara umum algoritma ialah sejumlah langkah komputasi yang mengubah
masukan (input) menjadi keluaran (output) yang benar [Thompson S. Ngoen, 2004, p.4].
Menurut Donald E. Knuth sebuah algoritma harus memenuhi persyaratan:
• Finitness: algoritma harus berakhir setelah melakukan sejumlah langkah proses
• Definitness: setiap langkah algoritma harus didefinisikan dengan tepat dan tidak
menimbulkan makna ganda (ambiguous).
• Input: setiap algoritma memerlukan data sebagai masukan untuk diolah
• Output: setiap algoritma memberikan satu atau beberapa hasil keluaran.
• Effectiveness: langkah-langkah algoritma dikerjakan dalam waktu yang wajar
Terdapat beberapa pengertian algoritma sebagai berikut.
• Pada Merriam-Webster’s Collegiate Dictionary istilah algorithm diartikan
sebagai prosedur langkah demi langkah untuk memecahkan masalah atau
menyeleseikan suatu tugas khususnya dengan menggunakan bantuan komputer.
• Algoritma [Moh. Sjukani, 2004, p.1] adalah alur pikiran dalam menyelesaikan
suatu pekerjaan, yang dituangkan dalam bentuk tertulis yang dapat dimengerti
oleh orang lain.
-
20
2.3 Optimisasi
2.3.1 Definisi Optimisasi
Optimisasi ialah suatu proses untuk mencapai hasil yang ideal atau optimal (nilai
efektif yang dapat dicapai) [Ibnu Sina Wardy, 2008, p.2]. Dalam 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. Nilai optimal adalah nilai yang didapat melalui
suatu proses dan dianggap menjadi suatu solusi jawaban yang paling baik dari semua
solusi yang ada.
2.3.2 Macam-Macam Permasalahan Optimisasi
Persoalan yang berkaitan dengan optimisasi sangat kompleks dalam kehidupan
sehari-hari. Nilai optimal yang didapat dalam optimisasi dapat berupa besaran panjang,
waktu, jarak, dan lain-lain. Berikut ini adalah beberapa persoalan yang memerlukan
optimisasi:
a. Menentukan lintasan terpendek dari suatu tempat ke tempat yang lain.
b. Menentukan jumlah pekerja seminimal mungkin untuk melakukan suatu proses
produksi agar pengeluaran biaya pekerja dapat diminimalkan dan hasil produksi
tetap maksimal.
c. Mengatur jalur kendaraan umum agar semua lokasi dapat dijangkau.
d. Mengatur routing jaringan kabel telepon agar biaya pemasangan kabel tidak
terlalu besar dan penggunaannya tidak boros.
-
21
Selain beberapa contoh di atas, masih banyak persoalan lainnya yang terdapat
dalam kehidupan sehari-hari.
2.3.3 Penyelesaian Masalah Optimisasi
Secara umum, penyelesaian masalah pencarian jalur terpendek dapat dilakukan
dengan menggunakan dua metode, yaitu:
1. Metode Konvensional
2. Metode Heuristik
2.3.3.1 Metode Konvensional
Metode konvensional ialah metode yang menggunakan perhitungan matematis
biasa. Semua kemungkinan yang ada dicoba dengan mencatat nilai yang didapat, cara ini
kurang efektif karena optimasi akan berjalan secara lambat (polynomial time).
A. Dynamic Programming
Dynamic Programming (DP) adalah prosedur matematika yang didesain utama
untuk meningkatkan efisien komputerisasi dalam memilih permasalahan-permasalahan
pemograman matematika dengan memecah permasalahan tersebut menjadi bagian-bagian
lebih kecil [Hamdy A. Taha, 1995, p.345]. Setiap bagian-bagian tersebut menghasilkan
satu variabel optimasi. Hasil komputasi untuk bagian-bagian yang berbeda dihubungkan
dengan recursive computations yang akan menghasilkan solusi optimal yang feasible
untuk semua permasalahan.
-
22
B. Branch and Bound
Teknik branch and bound (B&B) terdiri dari dua prosedur dasar. Branching
adalah proses mempartisi masalah yang besar menjadi dua atau lebih masalah kecil.
Bounding adalah proses menghitung batas bawah pada solusi optimal dari masalah kecil
tersebut. Bounding function yang digunakan yaitu pemrosesan hanya dilakukan pada
branch yang baik; yang buruk tidak akan diproses. Diharapkan bahwa branch yang baik
akan memberikan hasil yang optimal pada proses selanjutnya.
C. Branch and Cut
Teknik branch and cut merupakan teknik yang menggunakan branch dan bound
dengan penambahan algoritma cutting pada solusi yang didapatkan. Proses yang
dilakukan ialah dengan mengaplikasikan branch and bound pada solusi yang nantinya
akan dipotong dengan algoritma tertentu untuk mendapatkan hasil yang lebih baik. Proses
tersebut akan diulang sampai tidak ada pemotongan lagi.
2.3.3.2 Metode Heuristik
Metode heuristik adalah subbidang dari kecerdasan buatan yang digunakan untuk
melakukan pencarian dan optimasi. Menurut Judea Peral (April, 1984), metode heuristik
berkerja berdasarkan strategi pencarian pintar pada pemecahan masalah dengan
komputer, dengan menggunakan beberapa pendekatan [http://en.wikipedia.org/wiki/
Heuristic _algorithm].
Dua tujuan dasar dalam pemecahan masalah optimisasi pada ilmu komputer
adalah mencari algoritma yang cepat menyelesaikan masalah dan memperoleh hasil yang
-
23
optimal. Metode heuristik ialah metode yang menghilangkan salah satu atau dua dari
tujuan tersebut. Misalnya, pada pemecahan masalah optimisasi, dihasilkan solusi yag
cukup optimal, tetapi secara manual, belum tentu solusi yang lebih optimal dapat
diperoleh karena kompleksnya permasalahan yang ada. Atau, solusi yang didapat
dihasilkan dengan waktu yang sangat cepat, namun secara manual masih dapat ditemukan
hasil yang lebih optimal.
Jadi, hasil yang diperoleh belum tentu yang paling optimal. Tetapi penggunaan
metode heuristik yang umum tetap diterapan di dunia nyata. Karena terdapat beberapa
masalah, di mana hanya metode heuristik yang memungkinkan untuk memperoleh solusi
yang optimal dalam waktu yang sangat singkat.
Gambar 2.13 Sistem yang menggunakan kecerdasan buatan (Sumber: Sri Kusumadewi, 2005, p.1)
Pada gambar 2.14 [Sri Kusumadewi dan H. Purnomo, 2005, p.1], input yang
diberikan pada sistem yang menggunakan kecerdasan buatan adalah masalah. Sistem
harus dilengkapi dengan sekumpulan pengetahuan yang ada pada basis pengetahuan.
Sistem harus memiliki inference engine agar mampu mengambil kesimpulan berdasarkan
fakta atau pengetahuan. Output yang diberikan berupa hasil masalah sebagai hasil dari
inferensi.
Basis Pengetahuan
Inference Engine
Sistem yang menggunakan AI
MASALAH SOLUSI
-
24
A. Algoritma Generate and Test
Pada prinsipnya metode ini merupakan penggabungan antara depth-first search
dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu
keadaaan awal. Nilai pengujian berupa jawaban ‘ya’ atau ‘tidak’. Algoritmanya adalah
sebagai berikut.
1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik atau lintasan
tertentu dari keadaan awal).
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusi dengan
cara membandingkan verteks tersebut atau verteks akhir dari suatu lintasan yang
dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
B. Simulated Annealing
Simulated Annealing (SA) adalah metode pencarian lokal yang acak, di mana
solusi sementara dimodifikasi sehingga mengarah pada hasil yang lebih baik, dengan
beberapa kemungkinan. Mekanisme ini dapat mengantisipasi local optima yang buruk
Ide dasar SA terbentuk dari pemrosesan logam. Annealing (memanaskan
kemudian mendinginkan) dalam pemrosesan logam ini adalah suatu proses bagaimana
membuat bentuk cair berangsur-angsur menjadi bentuk yang lebih padat seiring dengan
penurunan temperature. SA biasanya digunakan untuk penyelesaian masalah yang mana
perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang
sangat luas.
-
25
Pada SA, ada 3 parameter yang sangat menentukan adalah tetangga, gain, dan
temperatur. Tetangga akan sangat berperan dalam bentuk perubahan pada solusi.
Pembangkitan bilangan random akan berimplikasi adanya probabilitas.
C. Tabu Search
Tabu Search (TS) merupakan suatu metode optimisasi yang menggunakan short-
term memori atau memori jangka pendek untuk menjaga agar proses pencarian tidak
terjebak pada nilai optimum lokal. Metode ini menggunakan Tabu List untuk
menyimpan sekumpulan solusi yang telah dievaluasi. Pada setiap iterasi, solusi yang akan
dievaluasi akan dicocokkan terlebih dahulu dengan tabu list untuk melihat apakah solusi
tersebut sudah ada pada tabu list. Apabila solusi tersebut sudah ada pada tabu list, maka
solusi tersebut tidak akan dievaluasi lagi pada iterasi berikutnya. Apabila sudah tidak ada
lagi solusi yang tidak menjadi anggota tabu list, maka nilai terbaik yang baru saja
diperoleh merupakan solusi yang sebenarnya.
D. Algoritma Genetika
Genetic Algorithm (GA) pertama kali dikembangkan oleh John Holland dari
universitas Michigan (1975). GA adalah algoritma heuristik yang didasarkan atas
mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah variasi dari
kromosom antar individu organisme. Individu yang lebih kuat (fit) akan memiliki tingkat
survival dan reproduksi yang lebih tinggi jika dibandingkan dengan individu yang kurang
fit. Pada dasarnya ada 4 kondisi yang sangat mempengaruhi proses evalusi adalah sebagai
berikut.
-
26
• Kemampuan organisme untuk melakukan reproduksi
• Keberadaan populasi organisme yang bisa melakukan reproduksi
• Keberagaman organisme dalam suatu populasi
• Perbedaan kemampuan untuk survive
Pada GA, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang
mungkin dikenal dengan istilah populasi. Individu yang terdapat dalam satu populasi
disebut dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih
berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya
merupakan hasil evaluasi kromosom-kromosom melalui iterasi yang disebut dengan
istilah generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi dengan
menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dalam kromosom
menunjukkan kualitas kromosom dalam populasi tersebut. Generasi berikutnya dikenal
dengan istilah anak (off-spring) terbentuk dari gabungan 2 kromosom yang bertindak
sebagai induk (parent) dengan operator penyilangan. Selain operator penyilangan, suatu
kromosom dapat dimodifikasi dengan menggunakan operator mutasi.
E. Harmony Search
Harmony search (HS) ialah algoritma metaheuristic (algoritma soft computing
atau algoritma evolusioner) meniru proses improvisasi musisi
[http://en.wikipedia.org/wiki/Harmony_search]. Setiap musisi memainkan nada untuk
mencari harmoni yang terbaik bersama-sama, sama seperti setiap variabel keputusan
dalam proses optimasi memiliki nilai untuk menemukan vektor terbaik serentak. HS
mencoba mencari vektor x yang meminimalkan beberapa pengeluaran fungsi.
-
27
F. Particle Swarm Optimization
Particle Swarm Optimization (PSO) merupakan teknik komputasi heuristik
berbasis populasi parallel yang diajukan oleh Kennedy dan Eberhart (1995), yang
dimotivasikan dari perilaku organisme seperti populasi ikan atau populasi burung.
Andaikan ada sejumlah burung yang sedang mencari makanan di sebuah daerah secara
acak [http://www.swarmintelligence.org/tutorials.php]. Di daerah tersebut hanya ada satu
potong makanan. Semua burung tidak mengetahui posisi makanan berada. Tetapi mereka
tahu seberapa jauh makanan tersebut dengan setiap perulangan. Jadi strategi yang baik
untuk menemukan makanan tersebut adalah mengikuti posisi burung yang terdekat
dengan makanan.
2.4 Travelling Salesman Problem
Traveling Salesman Problem (TSP) adalah permasalahan pada matematika diskrit
dan optimalisasi kombinatorial [http://www.tsp.gatech.edu/history/index.html]. TSP
pertama kali dikemukakan pada tahun 1800-an oleh seorang matematikawan asal
Irlandia, sir William Howard Hamilton dan seorang matematikawan asal inggris, Thomas
Penyngton Kirkman. Bentuk umum dari TSP pertama dipelajari oleh para
matematikawan mulai tahun 1930. Diawali oleh Karl Menger di Vienna dan Harvard,
permasalahan TSP dipublikasikan oleh Hassler Whitney dan Merrill Flood di Princeton.
TSP memerlukan keputusan dari siklus biaya atau panjang yang minimal, melalui
penerusuran setiap node pada graf yang relevan [Thammapimookkul dan Chamsethikul,
2001, p.5]. Jika biaya antar dua lokasi tidak tergantung pada arah lintasan, maka TSP
-
28
jenis ini bersifat simetris. Sedangkan TSP yang bersifat asimetris, yang disebut direcred
TSP.
TSP sebagai salah dari NP-complete problems dapat diselesaikan dengan
Pendekatan heuristik yang terbagi dalam tiga kelas, sebagai beikut.
• Tour construction procedures, menghasilkan perkiraan perjalanan optimal dari
jarak matriks. Seperti prosedur Nearest Neighbor, Clarke and Wright Saving,
prosedur Insertion, Minimal Spanning Tree, dan Christofides heuristic.
• Tour improvement procedures, berusaha mencari perjalanan yang lebih baik dari
perjalanan awal. Seperti 2-opt dan 3-opt heuristik dan prosedur k-opt.
• Tour composite procedures, membuat perjalanan awal dari salah satu composite
procedures dan kemudian mencari perjalanan yang lebih baik menggunakan satu
atau lebih dengan tour improvement procedures.
Gambar 2.14 Solusi TSP dengan 91 verteks (Sumber: http://www.visualbots.com/tsp_project.htm)
2.5 Multi Travelling Salesman Problem
Multi Travelling Salesman Problem (M-TSP) adalah generalisasi dari TSP, yang
merupakan persoalan yang lebih mendekati permasalahan dalam dunia nyata. Dalam
-
29
masalah ini diperlukan lebih dari satu kendaraan pengangkut untuk pendistribusian
barang. Pada M-TSP, keadaan pengangkut berjumlah m akan mengunjungi semua verteks
yang ada dengan total jarak yang minimum. M-TSP dapat selalu dikonversikan ke dalam
TSP yang sama dengan membuat perbanyak sebanyak m kali dari lokasi yang sama,
tetapi tidak berhubungan satu sama lain. Bebearapa formula M-TSP diturunkan secara
independent oleh Bellmore dan Hong (1974), Orloff (1974), Svetska dan Huckfeltz
(1973).
Pada M-TSP harus terdapat m ≥ 2 salesman yang mengunjungi n kota secara
bebas. Tidak ada kota yang dikunjungi oleh lebih dari satu salesman dan setiap m
salesman dapat memulai dari kota awal yang berbeda atau yang sama dan berakhir pada
kota yang sama dengan kota awal pada masing-masing salesman.
2.6 Vehicle Routing Problem
Vehicle Routing Problem (VRP) adalah salah satu problem atau permasalahan dari
combinatorial optimization di mana sebuah set rute akan dibentuk dari sejumlah kota atau
pelanggan didasarkan atas satu atau beberapa depot. Setiap kota atau pelanggan akan
dilayani oleh satu kendaraan dengan batasan-batasan tertentu; rute tersebut di awali dan
diakhiri di depot [http://neo.lcc.uma.es/radi-aeb/WebVRP].
Permasalahan ini pertama kali diformulasikan oleh Dantzing dan Ramser pada
tahun 1959 sebagai pusat permasalahan utama dalam bidang transportasi, distribusi, dan
logistik. Dalam beberapa sektor pasar, transportasi memiliki nilai persentase yang tinggi
yang dimasukkan dalam keuntungan. Setelah itu dikembangkan metode komputerisasi
untuk transportasi yang menghasilkan penghematan total biaya yang signifikan.
-
30
VRP adalah generalisasi dari TSP. Maka, TSP adalah sebuah VRP tanpa batasan
seperti depot, pelanggan dan permintaan. M-TSP adalah VRP dengan sebuah depot dan m
kendaraan pengangkut, termasuk bila tidak ada permintaan dari pelanggan. MTSP adalah
transformasi dari TSP dengan memperbanyak jumlah depot.
Gambar 2.15 Contoh visualisasi input dari Vehicle Routing Problem (Sumber: http://neo.lcc.uma.es/radi-aeb/WebVRP/)
Gambar 2.16 Salah satu output dari VRP dari input gambar 2.15 (Sumber: http://neo.lcc.uma.es/radi-aeb/WebVRP/)
Depot
Pelanggan
Rute
Depot
Pelanggan
-
31
Tujuan dari Vehicle Routing Problem ialah untuk meminimalkan jarak yang
dilalui oleh armada kendaraan yang melayani sekumpulan pelanggan seperti pada gambar
2.18 dan menghasilkan salah satu rute seperti pada gambar 2.19 dengan banyaknya
kendaraan yang disediakan atau digunakan.
Pada perkembangannya [Titiporn Thammapimookkul, 2001, p.3], VRP memiliki
beberapa karateristik sehingga dapat dibagi-bagi dalam beberapa kategori masalah,
seperti yang dapat ditunjukkan dalam tabel 2.2. Kategori ini dibuat oleh Bodin dan
Golden (1981), yang memaparkan berbagai karakteristik umum, yang membedakan VRP.
Keseluruhan tabel memberikan gambaran singkat tentang masalah routing.
Tabel 2.2 Kategori masalah dalam VRP (Sumber: Titiporn Thammapimookkul, 2001, p.3)
No Karateristik Varian yang mungkin 1 Jumlah kendaraan
pengangkut Satu kendaraan pengangkut Multi kendaraan pengangkut
2 Tipe kendaraan pengangkut
Homogen (satu tipe) Heterogen (multi tipe) Tipe khusus
3 Tipe permintaan Permintaan deterministik (telah dikethui sebelumnya)
Permintaan stokastik Permintaan kepuasan sebagian
4 Lokasi permintaan Simpul Garis campuran
5 Tenpat asal kendaraan (pusat)
Satu pusat Multi pusat
6 Jaringan yang mendasari Tidak berarah Berarah Campuran Euclid
7 Batasan kapasitas kendaraan pengangkut
Semuanya sama Jalur yang berbeda Kapasitas tak terbatas
-
32
8 Rute maksimum Sama untuk semua rute Berbeda untuk setiap rute Tidak ditentukan
9 Sistem pengoperasian Pengambilan saja Pengiriman saja Pengambilan dan pengantaran
10 Biaya Variable atau biaya rute Biaya tetap pengoperasian atau biaya tetap
kendaraan pengangkut Biaya pengangkut umum
11 Tujuan Meminimalkan biaya total rute Meminimalkan jumlah kendaraan yang diperlukan Meminimalkan fungsi kegunaan berdasarkan pada
pelayanan dan kenyamanan Meminimalkan fungsi kegunaan berdasarkan pada
prioritas pelanggan
Jika VRP salah satu permasalahan kombinatorial direpresentasikan dalam sebuah
graf G = (V, E) [http://neo.lcc.uma.es/radi-aeb/WebVRP], maka notasi yang digunakan
ialah sebagai berikut.
• V = {v0, v1, …, vn} ialah set atau sekumpulan verteks yang menggambarkan depot,
pelanggan ataupun persimpangan jalan, di mana:
o v0 sebagai depot.
o v1, …, vn sebagai pelanggan
o Misalakan V` = V tanpa elemen {v0} digunakan sebagai himpunan n kota
• C ialah matriks cij sebagai biaya atau jarak antara pelanggan vi dan vj yang bernilai
non-negatif.
• A = {(vi, vj) | vi, vj Є V; i ≠ j} adalah himpunan rusuk atau edge. Edge dapat yang
berarah (i, j) Є A dan tidak berarah e Є E
• d ialah vektor dari permintaan / demand pelanggan.
• Ri ialah rute dari kendaraan ke-i.
-
33
• k ialah banyaknya kendaraan (semuanya identik) dengan kapasitas Q. Satu rute
untuk tiap kendaraan.
Dengan setiap verteks vi dalam V’ diasosiasikan dengan sejumlah barang qi, yang
akan diantarkan oleh satu kendaraan. VRP bertujuan untuk menentukan sejumlah k rute
kendaraan dengan total biaya yang minimum, bermula dan berakhir di sebuah depot,
yang setiap verteks dalam V’ dikunjungi tepat sekali oleh satu kendaraan. Akhirnya,
biaya dari solusi permasalahan ini S adalah: ∑=
=k
iiVRP RCSF
1)()(
2.7 Local Search
Local search (LS) ialah metaheuristik untuk menyelesaikan permasalahan
perhitungan optimisasi yang berat. LS dapat digunakan pada permasalahan yang
bertujuan memaksimalkan solusi yang standar di antara banyaknya kandidat solusi
[http://en.wikipedia.org/wiki/Local_search_(optimization)]. Algoritma LS berpindah dari
solusi ke solusi dalam kandidat solusi sampai dianggap solusi tersebut optimal. Algoritma
LS dipergunakan secara luas untuk permasalahan perhitungan yang berat, meliputi
permasalahan computer science (artificial intelligence), matematika, operations research,
engineering, and bioinformatics.
Dalam algoritma LS yang paling dasar, dilakukan penyelusuran dalam
neighborhood terhadap perjalanan tertentu untuk kemajuan perjalanan. Jika perjalanan
tersebut ditemukan maka rute tersebut menggantikan yang lama dan proses tersebut akan
diteruskan sampai kemajuan perjalanan tidak dapat ditemukan lagi. Hal ini disebut
iterative improvement algorithm. Algoritma tersebut dapat diterapkan dalam hal-hal
sebagai berikut.
-
34
A. 2-Opt
2-Opt ialah algoritma LS yang pertama kali diusulkan oleh Croes pada tahun 1958
untuk menyeleseikan TSP. Ide dasar dibelakang algoritma tersebut ialah memindahkan
atau menghapus pasangan rute yang bersilangan dan mengembalikan suatu perjalanan
yang memungkinkan [http://en.wikipedia.org/wiki/2-opt].
Gambar 2.17 2-Opt move (a) dan 2-Opt optimal (b) (Sumber: http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf)
B. 3-Opt
Analisis 3-Opt meliputi penghapusan tiga edge dalam perjalanan, kemudian
menghubungkan kembali perjalanan tersebut ke dalam perjalanan yang memungkinkan
dan kemudian mengevaluasi tiap metode pengembalian untuk mencari yang paling
optimum. Proses ini kemudian diulang untuk set tiga set koneksi yang berbeda [http://en.
wikipedia.org/wiki/3-opt].
Menghapus 2 edge reconnect
(a) (b)
-
35
Gambar 2.18 3-Opt move (Sumber: http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf)
2.8 Algoritma Ant Colony Optimization
Algoritma Ant Colony Optimization merupakan teknik probabilistik untuk
menjawab masalah komputasi yang bisa dikurangi dengan menemukan jalur yang baik
dengan graf. ACO pertama kali dikembangkan oleh Marco Dorigo pada tahun 1991.
Sesuai dengan nama algoritmanya, ACO di inspirasi oleh koloni semut karena
tingkah laku semut yang menarik ketika mencari makanan [Heitor S. Lopes et al., 2005,
p.2]. Semut-semut menemukan jarak terpendek antara sarang semut dan sumber
makanannya. Ketika berjalan dari sumber makanan menuju sarang mereka, semut
memberikan tanda dengan zat feromon sehingga akan tercipta jalur feromon. Feromon
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, feromon menyebar ke luar tubuh dan hanya dapat
mempengaruhi dan dikenali oleh individu lain yang sejenis, proses peninggalan feromon
ini dikenal sebagai stigmergy. Semut dapat mencium feromon dan ketika mereka memilih
Menghapus 3 edge reconnect
-
36
jalur mereka, mereka cenderung memilih jalur yang ditandai oleh feromon dengan
konsentrasi yang tinggi. Apabila semut telah menemukan jalur yang terpendek maka
semut-semut akan terus melalui jalur tersebut. Jalur lain yang ditandai oleh feromon lama
akan memudar atau menguap, seiring berjalannya waktu. Jalur-jalur yang pendek akan
mempunyai ketebalan feromon dengan probabilitik yang tinggi dan membuat jalur
tersebut akan dipilih dan jalur yang panjang akan ditinggalkan. Jalur feromon membuat
semut dapat menemukan jalan kembali ke sumber makanan atau sarang mereka.
Algoritma ACO telah banyak digunakan untuk menghasilkan penyelesaian yang
mendekati optimal [Bernd Bullnheimer et al., 1997, p.1]. Aplikasi algoritma semut dalam
kehidupan sehari-hari mencakup beberapa persoalan sebagai berikut.
a. Traveling Salesman Problem (TSP), yaitu mencari jalur terpendek dalam sebuah
graf menggunakan jalur Hamilton.
b. Quadratic Assignment Problem (QAP) yang berusaha menempatkan sejumlah
sumber n ditempatkan pada sejumlah m lokasi dengan meminimalkan biaya
assignment.
c. Job-shop Scheduling Problem (JSP), juga salah satu contoh aplikasi algoritma
semut untuk menjadwalkan sejumlah j pekerjaan menggunakan sejumlah m mesin
sehingga seluruh pekerjaan diselesaikan dalam waktu yang minimal.
d. Vehicle Routing Problem (VRP), pengaturan jalur kendaraan
e. Pewarnaan graf
Koloni semut yang nyata dan artificial terdapat banyak kemiripan [Marco Dorigo
et al., 2006, p.3]. Keduanya terbentuk dari sebuah populasi yang terdiri dari individu-
individu yang berkerja sama untuk mencapai tujuan. Semut artificial hidup di dunia
-
37
virtual, karenanya mereka hanya memodifikasi nilai numerik (disebut analogi artificial
pheromones) yang berhubungan dengan keadaan-keadaan permasalahan yang berbeda.
Sebuah rangkaian dari nilai-nilai feromon yang berhubungan dengan keadaan
permasalahan disebut pheromone trail atau jejak feromon. Mekanisme untuk evaporation
atau penguapan feromon pada koloni semut nyata yang membuat semut artificial dapat
melupakan sejarah (jalur-jalur yang pernah diambil) dan fokus pada arah pencarian baru
yang menjanjikan.
Seperti semut-semut nyata, semut-semut artificial membuat solusi secara berurut
dengan bergerak dari satu keadaan permasalahan ke lainnya. Semut-semut nyata hanya
berjalan, memilih arah berdasarkan konsentrasi feromon lokal dan kebijakan keputusan
stokastik. Semut artificial membuat solusi sedikit demi sedikit, dan bergerak dari
keadaan permasalahan yang tersedia dan membuat keputusan stokastik setiap langkah.
Meskipun begitu, terdapat perbedaan antara yang nyata dan semut artificial sebagai
berikut.
• Semut artificial hidup di dunia dan pada waktu diskrit, mereka berpindah secara
sekuen melewati set batasan dari permasalahan.
• Update feromon (penumpukan dan penguapan feromon) tidak dilakukan dengan
jalan yang sama pada semut yang nyata dan semut arficial. Update feromon
dilakukan oleh beberapa dari semut artificial dan terkadang dilakukan saat solusi
telah dibangun.
• Beberapa implementasi dari semut artificial menggunakan mekanisme tambahan
yang tidak ada pada semut-semut nyata, seperti local search, backtracking, dan
lain-lain.
-
38
2.8.1 Algoritma Elitist Ant System
Ant System (AS) adalah bentuk awal dari algoritma ACO yang telah dimodifikasi
oleh para peneliti sampai saat ini [Ayan Acharya et al., 2008, p.1]. Algoritma Elitist Ant
System (EAS) adalah salah satu dari model yang dikembangkan dari algoritma AS.
Strategi dari EAS mirip dengan AS tetapi berbeda dalam penerapan memberikan jejak
feromon karena elite ant atau best ant disertakan sebagai feromon tambahan dalam meng-
update jejak semut. Aturan dasar meng-update jejak feromon dalam algoritma AS adalah
sebagai berikut.
∑=
Δ+−=m
k
kij
oldij
newij
1)1( ττρτ ……………..……….….…… (1)
Sedangkan aturan dalam meng-update feromon dengan algoritma elitist ant
system adalah sebagai berikut.
∑=
Δ+Δ+−=m
k
bsij
kij
oldij
newij e
1)1( τττρτ ………..…………..…… (2)
dengan kijτΔ adalah perubahan harga intensitas jejak semut antar kota setiap
semut yang dihitung berdasarkan persamaan 3 sebagai berikut.
untuk (i,j) ∈ kota asal dan tujuan dalam tabuk,v
lainnya
e adalah parameter yang mendefinisikan bobot yang diberikan pada rute yang
terbaik pada tabubs dengan panjang Lbs.
untuk (i,j) ∈ kota asal dan tujuan dalam tabubs
lainnya
⎩⎨⎧
=Δ0
1 kkij
Lτ
⎩⎨⎧
=Δ0
1 bsbsij
Lτ
-
39
2.9 Capacitated Vehicle Routing Problem dengan Algoritma Elitist Ant System
Capacitated Vehicle Routing Problem (CVRP) dapat didefinisikan sebagai
pemberangkatan armada dari pusat depot, dengan sejumlah pelanggan yang mesti
dilayani, dengan permintaan yang berbeda untuk produk sejenis [Heitor S. Lopes et al.,
2005, p.3]. Armada kendaraan terbatas dan mempunyai kapasitas yang sama. Batasan-
batasan pada CVRP adalah sebagai berikut.
• Setiap pelanggan hanya dilayani oleh satu pelanggan saja
• Total permintaan yang dilayani kendaraan tidak boleh melebihi kapasitas
kendaraan.
• Masing-masing perjalanan kendaraan dimulai dan diakhiri di depot
• Total panjang perjalanan tidak boleh melebihi batas otonomi kendaraan.
CVRP ialah permasalahan yang lebih rumit dari TSP, karena memerlukan dua
tahap penyelesaian. Pada tahap awal, setiap semut menyusun beberapa perjalanan yang
independen, dan set-set perjalanan melayani semua pelanggan. Pada tahap kedua, setiap
perjalanan disampaikan pada sebuah populasi baru, yang sistemnya sama dalam
algoritma Ant System (AS) untuk TSP. Pada tahap ini, algoritma berkerja untuk
menetapkan banyaknya siklus, yang mengarah pada optimisasi lokal perjalanan. Dua
tahap proses tersebut, diulang sampai kriteria pemberhentian dipenuhi. Dengan keadaan
total permintaan semua pelanggan yang dilayani tidak melebihi batas kendaraan yang
digunakan pada rute Ri, Notasinya adalah sebagai berikut.
∑=
≤m
ii Qd
1
…………………..………….….…… (4)
-
40
Dalam algoritma EAS untuk CVRP, diperlukan langkah-langkah untuk
menentukan jalur terpendek sebagai berikut.
i. Inisialisasi
Parameter-parameter yang di inisialisasi adalah:
Intensitas jejak semut antar antar kota dan perubahannya (τij).
Banyak pelanggan (n) termasuk koordinat pelanggan (x, y).
Jarak antar pelanggan (dij).
( ) ( )22 jijiij yyxxd −+−= ……………………………… (5)
Permintaan atau demand pelanggan (qn).
Banyak kendaraan (v) dengan kapasitas kendaraan (Q).
Banyak semut (k).
Tetapan pengendali intensitas jejak semut (α), nilai α ≥ 0.
Tetapan pengendali visibilitas (β), nilai β ≥ 0.
Tetapan penguapan jejak semut (ρ), nilai harus 0 > ρ > 1 untuk mencegah
jejak feromon yang tak hingga.
Visibilitas antar kota (ηij).
ijij d
1=η ………………………………………… (6)
Jumlah siklus maksimum (NCmax).
-
41
ii. Proses iterasi sampai NCmax
a. Untuk setiap semut k = 1, …, n menbangun solusi yang baru.
Pengisian depot dan kota pertama k semut ke dalam tabu list semut
kendaraan awal. Tabu list semut ditulis sebagai tabuk,v di mana tabuk,v
digunakan menyimpan rute semut k pada kendaraan v.
Penyusunan rute kunjungan semut ke setiap kota.
Perjalanan koloni semut berlangsung terus-menerus sampai semua
kota telah dikunjungi dan tidak melebihi batas kapasitas kendaraan yang
sesuai dengan rumus 4. Untuk menentukan kota tujuan digunakan
persamaan probabilitas kota untuk dikunjungi sebagai berikut.
[ ] [ ][ ] [ ]∑ Ω∈
=h ijij
ijijkijp βα
βα
ητητ
untuk vj ∈Ω ……………….……… (7)
0=kijp untuk lainnya ………………………………… (8)
Dengan Ω = {vj ∈ V : vj yang boleh dikunjungi} ∪ {v0}, kota vj
dipilih untuk dikunjungi setelah kota vi. Bila kendaraan v pada semut k
telah melebihi batas dari kapasitas kendaraan Q maka semut k akan
menggunakan kendaraan selanjutnya.
b. Perbaiki semua rute kendaraan menggunakan 2-opt heuristik.
c. Perhitungan panjang rute kendaraan untuk setiap semut.
Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap
semut dilakukan setelah satu siklus diselesaikan oleh semua semut.
Perhitungan ini dilakukan berdasarkan tabuk,v masing-masing dengan
persamaan sebagai berikut.
-
42
∑∑= =
+=v
i
n
jtabutabuk jdjdL vkik
0 0)1(),(
,, ……………….……… (9)
d. Pencarian rute terpendek.
Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang
rute tertutup setiap siklus atau Lbs dan harga minimal panjang rute tertutup
secara keseluruhan adalah Lmin.
e. Update jejak feromon.
Koloni semut akan meninggalkan jejak-jejak pada lintasan antar kota
yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat,
menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak semut
antar kota. Aturan dasar dalam meng-update jejak feromon dengan algoritma
Elitist Ant System yaitu dengan persamaan 2 yang telah disebutkan terdahulu.
2.10 Flowcart
Salah satu bentuk untuk menyatakan alur pikiran dalam menyelesaikan suatu
pekerjaan adalah dalam bentuk gambar atau bagan yang disebut program flowchart atau
bagan alir suatu program [Moh. Sjukani, 2004, p.5]. Berikut adalah simbol-simbol yang
digunakan untuk menggambarkan diagram alur.
Tabel 2.3 Tabel simbol flowchart (Sumber: Moh. Sjukani, 2004, p.9)
Notasi Arti notasi Terminal, untuk menyatakan mulai dan selesei sebagai tanda, tidak melakukan suatu pekerjaan khusus.
-
43
Process, untuk menyatakan assignment statement
Input/Output operation, untuk menyatakan proses baca dan proses tulis
Decision, untuk menyatakan pengambilan keputusan sesuai dengan suatu kondisi
Garis, untuk menyatakan pelaksanaan, atau alur proses
Preparation, pemberi nilai awal suatu variabel
Call, memanggil suatu subprogram
Titik connector yang berada pada halaman yang sama.
Titik connector yang berada pada halaman yang lain.
2.11 State Transition Diagram
State Transition Diagram (STD) adalah kumpulan keadaan/atribut yang
menggambarkan seseorang atau suatu benda pada waktu tertentu, bentuk keberadaan atau
kondisi tertentu, seperti menunggu instruksi berikutnya, menunggu pengisian password,
dan lain-lain.
STD merupakan modeling tools yang sangat kuat untuk mendekripsikan kelakuan
yang dibutuhkan pada sistem yang mempunyai sifat real-time, dan juga bagian interface
manusia pada berbagai sistem online (Yourdan, 1989, p.270). Cara kerja sistem ini ada
dua macam sebagai berkut.
-
44
Passive
Sistem ini melakukan kontrol terhadap lingkungan, tetapi lebih bersifat
memberikan atau menerima data. Kontrol suatu sistem bertugas
mengumpulkan/menerima data melalui sinyal yang dikirim oleh satelit.
Active
Sistem ini melakukan kontrol terhadap lingkungan secara aktif dan dapat
menberikan respon terhadap lingkungan sesuai dengan program yang ditentukan.
Komponen-komponen utama STD sebagai berikut.
1. State, yang disimbolkan dengan
State adalah kumpulan atribut yang mencirikan seseorang atau suatu
benda pada waktu atau kondisi tertentu.
2. Transition State, yang disimbolkan dengan
Transition State yang diberi label dengan ekspresi atau arah, label tersebut
menunjukkan kejadian yang menyebabkan transisi terjadi.
3. Condition dan Action
Condition adalah suatu peristiwa pada lingkungan eksternal yang dapat
dideteksi oleh sistem. Dan action adalah apa yang dilakukan oleh sistem apabila
terjadi perubahan state, atau bisa juga dikatakan sebagai reaksi sistem terhadap
suatu kondisi, aksi akan menghasilkan keluaran/tampilan.
Gambar 2.19 Contoh STD (Sumber: Yourdan, 1989, p.265)