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

e6

e7

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).

( ) ( )22jijiij 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

vkik0 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)