tsp

LAPORAN OBSERVASI

Penerapan Travelling Salesman Problem (TSP)

untukPencarianLintasanTerpendekPendistribusian Air Mineral di UD. Q-A

Jl. Ciamis No. 4 Malang, JawaTimur

Oleh:

Dessy Rochmatussa’diah (409312413117)

Nina Milana (409312419794)

Lina Rahmawati (409312419797)

UNIVERSITAS NEGERI MALANG

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

JURUSAN MATEMATIKA

FEBRUARI 2012

DAFTAR ISI

Halaman

HALAMAN JUDUL……………..……………..……………..………………….. i

ABSTRAK……………………………………………………... ……………… … ii

DAFTAR ISI ……………………………………………………........................... iii

DAFTAR LAMPIRAN…………………………………………………………… iv

BAB I PENDAHULUAN……………..……………..……………..……………... 1

1.1 Latar Belakang……………..……………..……………..………………….. … 1

1.2 TujuanObservasi……………..……………..……………..………………….... 2

1.3 ManfaatObservasi……………..……………..……………..………………….. 2

1.4 BatasanMasalah……………..……………..……………..……………………. 3

1.5 Alasan Pemilihan Lokasi……………..……………..……………..………….. 3

BAB II KAJIAN TEORI……………..……………..……………..…………… … 4

2.1 Definisi Travelling Salesman Problem……………..……………..…………… 4

2.2Definisi Graph……………..……………..……………..……………………… 4

2.3Definisi Subgraph……………..……………..……………..………………….. 5

2.4DefinisiGraph Berbobot……………..……………..……………..…………… 5

2.5 DefinisiLintasan……………..……………..……………..…………………… 5

2.5Definisi Cycle……………..……………..……………..……………………… 5

2.6 Definisi Trail……………..……………..……………..………………………. 5

2.6 Graph Hamiltonian……………..……………..……………..………………… 5

1. Algoritma-algoritmauntuk TSP……………..……………..………………

2. Nearest NeightbourHeuristik……………..……………..………………..

3. Cheapest Insertion Heuristik……………..……………..……………..…

4. Metode Koloni Semut……………..……………..……………..………

5. Cheapest Link……………..……………..……………..………………….

6. Algoritma Brute Force ……………..……………..……………..………..

7. Algoritma DFS……………..……………..……………..………………….

8. Algoritma Branch and Bound……………..……………..……………..…

9. Algoritma Heuristik……………..……………..……………..…………..

10. Algoritma Genetika……………..……………..……………..………….

11. Fartest insertion Heuristik

12. Nearest Insertion Heuristik……………..……………..……………..…..

13. Algoritma Tabu Search. ……………..……………..……………..……..

14. Simulated Annealing……………..……………..……………..………..

15. Complete Enumeration……………..……………..……………..……..

16. Jaringan Saraf Kahonen Self Organizer……………..……………..…..

17. Algoritma Metode Arbitrary Insertion Heuristik……………..………..

18. Algoritma Two way Exchange Heuristik……………..……………….

19. Algoritma Kolesar……………..……………..……………..…………

20. Program Dinamik (Dynamic Program) ……………..………………….

21. Algoritma Runut Balik……………..……………..……………..……

22. Linear Programming……………..……………..……………..………

BAB III METODOLOGI……………..……………..……………..…………

BAB IV PEMBAHASAN……………..……………..……………..………

4.1 Permasalahan……………..……………..……………..………………….

4.2 PenyelesaianMasalahdenganAlgorima……………..…………………….

4.3 PenyelesaianMasalahdenganAlat Bantu……………..……………..……

4.4 AnalisaHasil……………..……………..……………..…………………..

BAB V KESIMPULAN……………..……………..……………..…………

PengalamanSurvei……………..……………..……………..…………………..

DAFTAR PUSTAKA……………..……………..……………..…………………..

ABSTRAK

Permasalahan TSP (Traveling Salesman Problem ) adalah permasalahan dimana

seorang salesman harus mengunjungi semua kota dimana tiap kota hanyadikunjungi sekali,

dan dia harus mulai dari dan kembali ke kota asal. Tujuannya adalah menentukan rute dengan

jarak total terpendek.

Permasalahan TSP ( Travelling Salesman Problem) dapat diselesaikan dengan

beberapa algortima, diantaranya: AlgoritmaNearest Neightbour Heuristik, Algoritma Chepest

Link, Algoritma Genetik, Algoritma Koloni Semut(Ant Colony) ,dan beberapa algoritma lain.

Permasalahan Travelling Salesman Problem mudah untuk diselesaikan dengan

Algoritma Nearest Neightbour Heuristik, Algoritma Cheapest Link, Algoritma Branch and

Bound dan Algoritma Cheapest Insertion Heuristik. Algoritma-algortima ini pencarian rute

terpendeknya dengan menentukan sebuah titik awal dan sekaligus sebagai titik akhir, lalu

mencari jarak minimum dari titik satu ketitik lainya yang terhubung langsung.

Dan untuk permasalahan TSP ( Travelling Salesman Problem ) juga dapat

diselesaikan denganalat bantu. Alatbantu yang menyediakan Algoritma Nearest Neightbour

Heuristik, Algoritma Branch and Bound dan Cheapest Insertion Heuristik sebagai salah satu

solusinya adalah alat bantu yang bernama WINQSB.

Kata Kunci: Travelling Salesman Problem (TSP), Nearest NeightbourHeuristik, Cheapest

Link, Algoeirma Branch, Bound dan Algoritna Cheapest Insertion Heuristik, WINQSB,

BAB I

PENDAHULUAN

1.1 Latar Belakang

Dalam kehidupan sehari – hari banyak permasalahan yang dapat diselesaikan dengan

bantuan Matematika.Teori Graph merupakan salah satu cabang dari ilmu Matematika yang

dapat digunakan untuk memecahkan suatu masalah yang terjadi dalam kehidupan sehari-

hari.Salah satu terapan dari Teori Graph adalah Travelling Salesman Problem (TSP).

Nama persoalan TSP diilhami oleh masalah seorang pedagang yang akan

mengunjungi sejumlah kota. Uraian persoalannya, diberikan sejumlah kota dan jarak antar

kota. Akan ditentukan sikel (lintasan tertutup) terpendek yang harus dilalui oleh seorang

pedagang bila pedagang itu berangkat dari kota asal dan menyinggahi setiap kota tepat satu

kali dan kembali lagi ke kota asal. Kota dapat dinyatakan sebagai titik Graph sedangkan sisi

menyatakan jalan yang menghubungkan antara dua buah kota. Persoalan perjalanan pedagang

tidak lain adalah menentukan sikel Hamilton yang memiliki bobot minimum pada Graph

terhubung.

Permasalahan TSP dapat di temukan pada perusahaan yang bergerak di bidang jasa

distribusi.Salah satunya adalah pendistribusian air mineral di UD.Q-A Jl. Ciamis No 4

Malang. UD.Q-A selalu berusaha untuk memberikan yang terbaik bagi setiap pelanggannya,

yaitu dengan cara selalu memperhatikan setiap pesanan (order) para pelanggannya agar

barang dapat sampai di tujuan dalam keadaan baik dan dapat sampai tepat waktu, dengan

biaya operasional yang murah.

Namun saat ini salesman mengalami kesulitan, yang disebabkan oleh padatnya jalan

raya dan dengan harga BBM yang semakin mahal, akan menambah beban operasional

perusahaan. Oleh karena itu, dengan menggunakan Algoritma Travelling Salesman Problem

(TSP) pada mata kuliah Teori Graph, akan ditemukan solusi dari permasalahan-permasalahan

tersebut dengan cepat dan mudah.

1.2 Tujuan Observasi

1. Menambahwawasan pengetahuan dan ketrampilan yang berkaitan dengan

perkuliahan bidang keahlian yang sesuai.

2. Menerapkan pengetahuan dan keterampilan yang di peroleh di perkuliahan dengan

bidang keahlian yang sesuai.

3. Memberikan pengalaman profesional mahasiswa untuk bekerja secara nyata.

4. Membuka peluang kerja dengan instansi tempat pelaksanaan kegiatan observasi.

5. Secara khusus, tujuan dari kegiatan observasi kami adalah:

a.Identifikasi permasalahan pendistribusian.

b.Menerapkan Traveling Salesman Problem untuk mengetahui jarak tempuh terpendek

yang dilalui salesman dalam mendistribusikan barang.

c. Memberikan solusi alternatif.

1.3 Manfaat Observasi

Adapun manfaat dari pelaksanaan observasi adalah :

a. Dapat mengenal lebih jauh realita ilmu yang telah diterima dibangku

kuliahmelalui kenyataan yang ada di lapangan.

b. Memperdalam dan meningkatkan ketrampilan kerja yang sesuai dengan ilmu

yang dimiliki.

c. Dapat mempersiapkan langkah-langkah yang diperlukan untuk menyesuaikan

diri dengan lingkungan kerjanya di masa mendatang.

d. Menambah wawasan, pengetahuan dan pengalaman mahasiswauntuk siap

terjun langsung di masyarakat khususnya di lingkungan mahasiswa.

1.4 Batasan Masalah

a. Permasalahan yang akan dibahas dalam Laporan Observasi ini adalah

permasalahan yang dihadapi oleh salesman yang mendistribusikan air mineral

kepada pelanggan atau agen yang telah ditentukan.

b. Wilayah pendistribusian air mineral yang akan dibahas pada Laporan Observasi

ini adalah meliputi wilayah Malang Raya.

c. Hasil Laporan Observasi ini hanya mempertimbangkan jarak tempuh

pendistribusian air mineral ke pelanggan atau agen-agen yang telah ditentukan

tanpa melihat omset.

1.5 Alasan Pemilihan Lokasi Observasi

Adapun alasan pemilihan UD.Q-A untuk pelaksanaan observasi adalah :

1. Lokasi mudah dijangkau (strategis).

2. Merupakan salah satu instasi yang bergerak di bidang pendistribusian.

BAB II

KAJIAN TEORI

2.1 Pengertian Travelling Salesman Problem

Traveling Salesman Problem (TSP) adalah permasalahan untuk mencari rute

terpendek yang dapat dilalui untuk mengunjungi beberapa kota tanpa harus mendatangi

kota yang sama lebih dari satu kali.

2.2 Graph

Graph adalah suatu diagram yang terdiri dari titik, gabungan garis yang disebut sisi,

dimana setiap sisi menggabungkan tepat dua titik. Suatu graph tanpa sisi ganda atau loop

disebut graph sederhana.

Himpunan dari titik-titik pada graph G disebut himpunan titik G, dinotasikan dengan

V(G), dan daftar dari sisi-sisi disebut daftar sisi G, dinotasikan dengan E(G) (Wilson,

1990:10).

Banyaknya titik pada graph G dinotasikan dengan | )(GV | dan banyaknya sisi pada

graph G dinotasikan dengan |E(G)|

.

Dari Gambar diatas dapat dilihat bahwa },,,,,{)( EDCBAGV dan E(G)={e1, e2, e3,

e4, e5, e6, e7, e8, e9, e10} sehingga 5|)(| GV dan 10|)(| GE .

2.3 Subgraph

Subgraph dari suatu graph G adalah semua titik-tik adalah titik-titik dari dari graph G

dan semua sisi-sisi adalah sisi-sisi dari G.

2.4 Graph Berbobot

Graph berbobot adalah graph yang sisi-sisnya di beri sebuah bobot. Yang mana bobot

pada setiap sisinya dapat berbeda-beda tergantung pada permasalahan.

Contoh:

2.5 Lintasan (Path)

Lintasan (path) adalah jalan yang sisi dan titiknya tidak boleh berulang.

2.6 Sikel

Sikel adalah jalan (v0,v0) = v0v1v2...vnv0 dengan n ≥ 0 dan vi ≠ vj, jika i ≠ j.

2.7 Trail

Trail adalah jalan yang memuat semua sisi, tapi titik tidak harus memuat semua titik

2.8 Graph Hamilton

G adalah graph Hamilton jika G adalah suatu graph terhubung dengan n titik, di mana

n dan , untuk setiap pasangan titik-titik yang tidak terhubung

langsung v dan w.

2.9 Algoritma-algoritma yang Mendukung Penyelesaian TSP

Algoritma-algoritma yang mendukung penyelesaian Travelling Salesman Problem

(TSP) untuk mendapatkan lintasan terpendek diantaranya adalah:

1. Nearest Neightbour Heuristik

Metode ini dapat digunakan untuk menentukan sikel Hamilton dengan total jarak

terpendek. Metode ini sangat sederhana dan lebih banyak digunakan daripada metode lain

yang dalam menyelesaikan masalah TSP. Adapun langkah-langkahnya sebagai berikut :

1. Pilih sembarang titik sebagai titik awal dari lintasan.

2. Pilih titik dengan sisi yang terkait yang memiliki bobot minimum.

3. Dari titik baru, pilih titik yang belum terpilih pada lintasan dengan bobot sisi

minimum.

4. Kembali lakukan langkah 3 sampai semua titik telah termuat dalam lintasan.

Selanjutnya hubungkan titik awal dengan titik akhir sehingga terbentuk sikel.

2. Cheapest Insertion Heuristik

Metode ini dapat digunakan untuk menentukan sikel Hamilton dengan jumlah bobot

yang minimum. Adapun langkah-langkahnya sebagai berikut :

1. Pilih sembarang titik sebagai titik awal dan siklus S hanya terdiri dari titik awal

tersebut.

2. Cari titik j di luar S sehingga Cij minimum dan membentuk sikel tertutup {(i, j), (j,

i)}.

3. Pemilihan. Cari titik k (bukan dalam sikel) yang terdekat ke sembarang titik di S.

4. Penyimpanan. Cari sisi (i, j) dalam sikel dengan Cik + Ckj – Cij yang memiliki

nilai minimum, masukkan k di antara i dan j sehingga diperoleh (i, k) dan (k, j).

5. Jika sikel telah terisi oleh semua titik maka terbentuklah sikel Hamilton sehingga

iterasi berhenti.

3. Metode Koloni Semut

Algoritma Koloni Semut terinspirasi oleh tingkah laku semut pada saat mencari

makan.Intinya adalah komunikasi tak langsung antar semut. Semut memiliki zat khusus yang

disebut pheromone, yang digunakan oleh semut untuk memeberikan jejak pada jalan yang

dilewati,dan juga sebagai komunikasi antar semut. Semut akan memilih salah satu jalan, yaitu

jalan yang terdapat banyak pheromone yang menunjukkan bahwa jalan tersebut banyak

dilewati oleh semut lain, sehingga akan lebih cepat untuk mencapai sumber makanan dan

kembali ke sarang. Pembahasan dari algoritma Koloni Semut untuk menyelesaikan masalah

Travelling Salesman Problem (TSP), adalah sebagai berikut:

a. bi (t) (i=1,2,3,… n) adalah banyaknya semut pada kota I dalam waktu t.

b. m = ∑ adalah jumlah semua semut pada semua kota dalam waktu t.

c. di j adalah jarak lintasan yang menghubungkan antara kota i dan kota j

adalah intensitas lintasan sisi (I,j) dalam waktu t.

Masing-masing semut pada waktu t akan memilih kota berikutnya, sehingga waktunya akan

menjadi t+1. Yang dimaksud 1 iterasi dari algoritma Koloni Semut ini adalah satu kali

perjalanan pergi-pulang yang dilakukan oleh satu semut pada interval (t, t+1), dan intensitas

lintasan akan diperbaharui dengan rumus, dengan adalah

koefisien penguapan lintasan antara waktu t dan t+n, nilai (0 <1). n= 1,2,…,q,

dengan q adalah banyaknya rute yang mungkin dilewati = ∑

, dengan

adalah banyaknya pheromone yang ditinggalkan oleh k-semut pada sisi (I,j) dalam

waktu t dan t+n,

Q adalah konstanta relatif banyaknya lintasan yang dilewati oleh semut, nilai Q € (0, 10, 100,

1000) dan Lk panjang sisi yang dibuat oleh k-semut. Hasil yang diharapkan adalah rute

terpendek yang diperoleh dari banyaknya pheromone yang ditinggalkan oleh masing-masing

semut pada setiap jalan yang dilewatinya.(Dorigo, 1996).

4. Cheapest Link

Langkah-langkah:

1. Dalam metode ini kita tidak memilih simpul awal yang memilih link atau sisi

dengan bobot terkecil pada graph.

2. Kita memilih sisi dengan bobot terkecil kedua (sisi ini tidak perlu berbagi dengan

ujung simpul sebelumnya). Lakukan teruslangkah ini, kecuali kita menolak setiap

sisi jika:

1) membentuk sebuah "hubungan pendek" (sirkuit yang bukan Hamilton sirkuit) ,

atau

2) mengakibatkan 3 pertemuan sisi di simpul yang sama.

3. Telah terpilih n-1 sisi, yang ujung-ujungnya membentuk lintasan Hamilton.

Lalu untuk sisi terakhir kita pilih satu sisi yang menggabungkan dengan simpul

terakhir.

5. Algoritma Brute Force

Algoritma bruteforce menyelesaikan masalah TSP dengan cara:

- Mengenumerasi semua Sirkuit Hamilton dari graf lengkap TSP,

- Menghitung bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1,

- Memilih sirkuit Hamilton yang mempunyai bobot terkecil.

Karena algoritma ini menghitung bobot untuk setiap Sirkuit Hamilton yang mungkin

terjadi, maka kompleksitasnya sebesar jumlah Sirkuit Hamilton untuk graf lengkap

bersimpul n yang dimulai dari sebuah simpul, yakni permutasi dari n buah simpul =

n1* ... * 1 = (n1)!.

Maka, kompleksitasnya adalah O(n!).

6. Algoritma DFS

Algoritma DFS untuk menyelesaikan TSP adalah seperti ini:

- Bangun sebuah pohon yang cabangnya berupasimpul pada graf, Lakukan

metode DFS pada tiap cabang sampai semua simpul dipilih (tidak ada yang

dipilih dua kali),

- Hitung bobotnya,

- Lakukan langkah ke2 dan ke3 sampai seluruhsimpul asal telah dipilih. Apabila

pada waktu membangkitkan simpul anak ternyata tidak lebih kecil dari

minimum sementara, maka simpul tersebut dimatikan (tidak diekspansi lebih

lanjut).

7. Algoritma Branch and Bound

Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih

simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan

sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk

setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung

taksiran nilai tersebut dinyatakan secara umum sebagai :

Misalkan

(i) G=(V,E) adalah graf lengkap TSP

(ii) V=n = jumlah simpul dalam graf G.

Simpul- simpul diberi nomor 1, 2, …,n.

(iii) cij= bobot sisi (i, j)

(iv) perjalanan (tur) berawal dan berakhir di simpul 1.

(v) S adalah ruang solusi, yang dalam hal ini

S = { (1, , 1) adalah permutasi (2, 3, ..., n) }

(vi) S= (n – 1)! = banyaknya kemungkinan solusi

Solusi TSP dinyatakan sebagai

X = (1, x1, x2, ..., xn – 1,1)

yang dalam hal ini

xo= xn = 1(simpul asal = simpul akhir= 1).

1 2

34

12

15

8

5 9

Gambar 7.6 Graf lengkap berbobot dengan 4 buah simpul

1

32 4

5 6 7 8 9 10

11 12 13 14 15 16

x1=2

x1=3

x1=4

x2=3 x

2=4 x

2=2 x

2=4 x

2=2

x3=4 x

3=3 x

3=4 x

3=2 x

3=3 x

3=2

Gambar 7.7 Pohon ruang status dari persoalan TSP dengan graf pada Gambar 7.6.

Ongkos atau nilai batas untuk setiap simpul dihitung dengan menggunakan matriks

ongkos-tereduksi (reduced cost matrix) dari graf G.

Sebuah matriks dikatakan tereduksi jika setiap kolom dan barisnya mengandung

paling sedikit satu buah nol dan semua elemen lainnya non-negatif.

8. Algoritma Heuristik

Permasalahan Traveling Salesman Problem (TSP) dengan algoritma heuristik ini

digunakan untuk permasalahan yang identik dengan permasalahan berikut: jika sebuah

kendaraan yang melakukan perjalanan ke n kota, perjalanan dimulai dan diakhiri pada satu

kota dan harus mengunjungi n-1 kota yang lain. Jaringan transportasi yang menghubungkan

ke-n kota tersebut adalah completely connected, artinya dari tiap kota terdapat jalur

transportasi langsung ke n-1 kota lainnya tanpa melalui kota perantara lainnya.

Langkah-langkah untuk menyelesaikan permasalahan TSP adalah sebagai berikut:

1. Cari minimum spanning tree yang menghubungkan tiap n simpul dari graph. Hasil

pencarian minimum spanning tree ini dinamakan A.

2. Tentukan simpul graph yang berderajat ganjil, jika k merupakan jumlah simpul

graph berderajat ganjil dari n simpul maka k pasti bilangan genap. Kita pasangkan

k simpul sehingga panjang dari cabang yang menghubungkan simpul-simpul

tersebut minimum.K simpul dengan tiap cabangnya yang diperoleh dari

memasangkan masing- masing simpul dari k simpul tersebut membentuk jaringan

yang dinamakan B. Jaringan A dan B yang sudah terbentuk kita gabungkan

menjadi jaringan C.

3. Sekarang jaringan C tidak mempunyai simpul berderajat ganjil. Kita dapat

menggambarkan sirkuit Euler pada jaringan C. Sirkuit Euler merupakan

aproksimasi solusi dari Traveling Salesman Problem.

4. Periksa tiap nodes pada jaringan C yang dikunjungi lebih dari satu kali dan

perbaiki solusi Traveling Salesman Problem dari langkah 3 dengan menerapkan

ketidaksamaan dibawah ini:

l(a,b) < l(a,c) + l (c,b)

9. Algoritma Genetika

Proses algoritma genetika terdiri dari beberapa langkah, yaitu pengkodean (encoding),

seleksi (selection), persilangan (crossover), mutasi (mutation), decoding. Pertama-tama,

proses encoding adalah suatu proses kodifikasi atas solusi dari permasalahannya. Hasil

encoding adalah berbentuk string yang merupakan representasi dari suatu kromosom. Proses

selection menentukan kromosom mana yang tetap tinggal pada generasi berikutnya. Proses

crossover akan menghasilkan kromosom baru yang merupakan pengganti dari kromosom

yang hilang sehinga total kromosom pada satu generasi berjumlah tetap. Proses mutation

memungkinkan terjadinya kromosom baru secara unpredictable. Proses terakhir adalah

decoding yaitu mengambil makna dari hasil kromosom terbaik untuk menjawab

permasalahannya.

Proses algoritma genetika terdiri dari beberapa langkah, yaitu pengkodean (encoding),

seleksi (selection), persilangan (crossover), mutasi (mutation), decoding.

Pertama-tama, proses encoding adalah suatu proses kodifikasi atas solusi dari

permasalahannya.

Hasil encoding adalah berbentuk string yang merupakan representasi dari suatu

kromosom. Proses selection menentukan cromosom mana yang tetap tinggal pada

generasi berikutnya.

Proses crossover akan menghasilkan kromosom baru yang merupakan pengganti dari

kromosom yang hilang sehinga total kromosom pada satu generasi berjumlah tetap.

Proses mutation memungkinkan terjadinya kromosom baru secara unpredictable.

Proses terakhir adalah decoding yaitu mengambil makna dari hasil kromosom terbaik

untuk menjawab permasalahannya.

10. Fartest Insertion Heuristik

Metode ini hanpir sama dengan metode Nearest Insertion Heuristik, hanya berbeda

pada cara pemilihan titik yang akan disisipkan berikutnya.

Metode ini berawal dari penentuan titik awal lalu mencari titik baru dimana sisi

terkaitnya memiliki bobot maksimum kemudian melakukan langkah seleksi yaitu

menyisipkan titik baru tersebut pada sisi dalam sikel yang memiliki nilai minimum.Ulangi

langkah seleksi sampai semua titik telah terpilih sehingga terbentuk sikel Hamilton.

Untuk memperjelas dalam pencarian sikel Hamilton dengan metode Fartest Insertion

Heuristik dapat dilakukan langka-langkah sebagi berikut:

1. Pilih sebarang titikio sebagai titik awal.

2. Cari titik dalam graph sehingga xio,k adalah maksimum dan membentuk subtour

io-k-io.

3. Langkah seleksi dari subtour.

11. Nearest Insertion Heuristik

Langkah-langkah untuk menyelesaikan Travelling Salesman Problem dengan

Algoritma Nearest Insertion Heuristik adalah:

Langkah 1: Pilih sembarang titik i sebagai titik awal dan siklus S yang hanya terdiri

dari i.

Langkah 2: Cari titik j di luar jalur S sehingga cij minimum dan membentuk sikel {(i, j),

(j,i)}.

Langkah 3: Cari titik k (yang bukan dalam sikel) yang terdekat ke sebarang titik dari S.

Langkah 4: Penyisipan, cari sisi (i, j) dalam sikel dengan cik+ckj-cij yang mempunyai

nilai minimum. Masukkan k diantara i dan j sehingga diperoleh (i, k) dan (k,

l).

Langkah 5: Jika sikel sudah terisi oleh semua titik maka telah terbentuk sikel Hamilton

dan operasi berhenti. Namun jika sebaliknya lakukan langkah tiga.

12. Algoritma Tabu Search.

Tabu search dapat digunakan untuk menemukan solusi Masalah Perjalanan Salesman

(Travelling Salesman Problem)(yaitu solusi yang memenuhi criteria kecukupan, bukan solusi

yang benar-benar optimal).

1. Tabu Search dimulai dengan solusi awal, yang dapat dihasilkan secara acak atau

sesuai dengan Algoritma Nearest Neightbour. Untuk menghasilkan solusi baru, agar

dua kota yang dikunjungi merupakan solusi yang potensial.

2. Untuk menghindari terjadinya sikel, solusi di tambahkan ke daftar tabu dalam

lingkungan N*(x).

3. Jika semua criteria terpenuhi maka berhenti. Setelah selesai, akan ditemukan solusi

terbaik dengan diperoleh jarak terpendek.

Tabu Search (TS) adalah algoritma metaheuristic yang merupakan modifikasi dari

pencarian lokal dasar.

Tabu daftar diimplementasikan menggunakan memori jangka pendek.

Menyimpan daftar Tabu tab.

Implementasi solusi paling sederhana toko seluruh dilarang.

Pendekatan ini tidak digunakan terlalu sering, karena persyaratan yang sangat besar

mengenai memori dan waktu pemrosesan.

Paling sering, daftar tabu toko transformasi terakhir beberapa atau fitur kunci dari

solusi yang dikunjungi.

Setiap transformasi berlawanan dengan yang digunakan untuk mencapai titik saat ini

dilarang.

Perubahan dari fitur kembali ke yang sebelumnya dilarang.

Lingkungan terdiri dari semua vektor yang berbeda dalam satu posisi bit.

Daftar Tabu: T=[t1,t2,...,tn] .

Setiap elemen dari daftar tabu mewakili jumlah iterasi yang selama ini tidak

diperbolehkan untuk mengubah nilai bit untuk setiap posisi solusi saat ini.

Daftar tabu diperbarui setelah setiap iterasi

13. Simulated Annealing

Proses Simulated Annealling terdiri dari beberapa langkah dimana setiap langkahnya

terdiri atas beberapa iterasi. Yang mana proses tersebut adalah sebagai berikut:

1. Membangkitkan kondisi awal simulasi.

2. Menghitung Energi awal yang dihasilkan pada kondisi awal.

3. Update state awal dengan menggunkan aturan yang bersesuaian dengan

permasalahan.

4. Hitung kembali energi yang dihasilkan pada setiap updating.

5. Bangkitkan bilangan random berdistribusi Uniform [0,1].

Uji kriteria, bila

update state diterima atau pertukaran diterima, lain dari

kondisi ini di tolak. Dengan Energi E untuk masalah TSP didifinisikan sebagai berikut:

∑ …….(8)

Dimana : E: fungsi energy setelah iterasi

: posisi dari titik ke-I

( ) : jarak dari titik ke-I menuju ke-j

: jumlah kota yang dituju

6. Turunkan T dengan fungsi cooling schedule yang digunakan

Dimana: : temperature cooling schedule ke-I

: te,peratur awal

: temperature cooling schedule

: jumlah iterasi

: iterasi ke-i

7. Ulang langkah ke-3 sampai mencapai criteria lalu berhenti.

14. Complete Enumeration

Langkah-langkah Algoritma Complate Enumeration:

Langkah1: Cari banyaknya kemungkinan lintasan, dengan cara mencari semua subgraph

yang mungkin dari graph tersebut.

Langkah 2: Hitung panjag lintasan dari masing-masing subgraph tersebut.

Langkah3: Cari lintasan yang mempunyai panjang terpendek dari suggrph-subgraph

tersebut.

15. Jaringan Saraf Kahonen Self Organizer

Pada TSP, optimasi yang diinginkan agar ditemukan rute perjalanan terpendek

untuk melewati sejumlah kota dengan jalur tertentu sehingga setiap kota hanya terlewati

satu kali dan perjalanan diakhiri dengan kembali ke kota semula.Pendekatan dengan

menggunakan Jaringan Saraf Kohonen Self Organizing memberikan solusi atau

penyelesaian dalam perhitungan waktu yang lebih singkat dibandingkan dengan

sejumlah algoritma lain yang diterapkan pada komputer dalam bentuk program.

Jaringan Saraf Tiruan

Seperti halnya otak manusia yang terdiri dari sekumpulan sel saraf (neuron),

jaringan saraf juga terdiri dari beberapa neuron dan terdapat hubungan antara neuron-

neuron tersebut.Neuron-neuron tersebut akan memindahkan informasi yang diterima

melalui sambungan keluarnya menuju neuron-neuron yang lain. Pada jaringan saraf,

hubungan ini dikenal dengan namabobot.

Ada beberapa arsitektur jaringan saraf tiruan (Kusumadewi, 2003), antara lain:

1. Jaringan dengan lapisan tunggal (single layer net)

Jaringan dengan lapisan tunggal hanya memiliki satu lapisan dengan bobot-bobot

terhubung. Jaringan ini hanya menerima input kemudian secara langsung akan

mengolahnya menjadi output tanpa harus melalui lapisan tersembunyi, seperti yang

terlihat pada Gambar 2.

Pada Gambar 2 tersebut, lapisan input memiliki 3 neuron, yaitu X1, X2 dan X3.

Sedangkan pada lapisan output memiliki 2 neuron yaitu Y1 dan Y2. Neuronneuron

pada kedua lapisan saling berhubungan.Seberapa besar hubungan antara 2 neuron

ditentukan oleh bobot yang bersesuaian. Semua unit input akan dihubungkan dengan

setiap unit output.

2. Jaringan dengan banyak lapisan (multilayer net)

Jaringan dengan banyak lapisan memiliki 1 atau lebih lapisan yang terletak

diantara lapisan input dan lapisan output (memiliki 1 atau lebih lapisan tersembunyi).

Umumnya, ada lapisan bobot-bobot yang terletak antara 2 lapisan yang bersebelahan.

Setiap nilai yang diinputkan akan dikalikan dengan bobot yang terhubung ke tiap

neuron pada lapisan tersembunyi, lalu dijumlah. Hasil penjumlahannya diinputkan

pada fungsi aktivasi yang berlaku pada neuron lapisan tersembunyi tersebut untuk

mendapatkan hasilnya.Kemudian, nilai hasil dari tiap neuron lapisan tersembunyi

dikalikan dengan bobot yang terhubung ke masingmasing neuron pada sisi

output.Hasil penjumlahannya dimasukkan pada fungsi aktivasi yang berlaku untuk

mendapatkan nilai keluarannya. Jaringan dengan

banyak lapisan ini dapat menyelesaikan permasalahan yang lebih sulit daripada

lapisan dengan lapisan tunggal, tentu saja dengan pembelajaran yang lebih rumit.

3. Jaringan dengan lapisan kompetitif (competitive layer net)

Merupakan jenis jaringan saraf yang memiliki bobot yang telah ditetapkan dan

tidak memiliki proses pelatihan. Digunakan untuk mengetahui neuron pemenang dari

sejumlah neuron yang ada. Nilai bobot untuk diri sendiri tiap neuron adalah 1,

sedangkan untuk neuron lain adalah bobot random negatif. Gambar 4 menunjukkan

salah satu contoh arsitektur jaringan dengan lapisan kompetitif yang memiliki bobot -

η.

Tujuan pembelajaran dari algoritma ini adalah untuk mentransformasikan suatu

pola sinyal masukan yang mempunyai dimensi yang berubah-ubah ke suatu peta yang

berdimensi satu atau dua.Sifat pemetaan yang dimiliki Jaringan Saraf Kohonen Self

Organizing meniru pada otak manusia yang tidak terdapat pada Jaringan Saraf Tiruan

lainnya.Terdapat m unit kelompok yang tersusun dalam arsitektur satu atau dua

dimensi dan sinyal-sinyal masukan sejumlah n. vektor bobot untuk suatu unit

kelompok disediakan satu eksemplar dari pola-pola masukan yang tergabung dengan

kelompok tersebut. Selama proses pengorganisasian sendiri, unit kelompok yang

memiliki vektor bobot paling cocok dengan pola masukan (ditandai dengan jarak

Euclidean paling minimum) dipilih sebagai pemenang. Unit pemenang dan unit

tetangganya diperbaharui bobotnya. Untuk susunan unit kelompok linier, tetangga

dengan radius R di sekitar unit kelompok jaringan terdiri atas semua unit jaringan

yang memenuhi maksimal fungsi Aj : (1, J-R < = j,= min (J+R, m) (Fausset, 1994).

Arsitektur Jaringan Saraf Kohonen ditunjukkanpada Gambar 8.

Untuk selengkapnya, algoritma TSP dapat dijabarkan (Kusumadewi, 2003),

sebagai berikut:

1. Tetapkan parameter-parameter:

a. Maksimum epoh (MaxEpoh).

b. Learning rate untuk perubahan bobot antar neuron (θ).

c. Learning rate untuk perubahan bobot antara koordinat kota dengan neuron

(ϕ). Nilai θ dan ϕbisa dibuat sama.

d. Pengurangan learning rate (momentum).

e. Faktor pengali untuk menuju koordinat kota (near).

2. Masukkan koordinat kota (Xi,Yi), dengan i=1,2,…,N.

a. Cari jarak antar setiap kota ke-i dengan kota ke-j, Dij, dengan

i,j=1,2,…,N.

3. Tetapkan:

Jumlah neuron (Q), dengan Q ≥ N.

Tetapkan koordinat awal setiap neuron (nXi, nYi), sedemikian hingga neuron-

neuron membentuk lingkaran.

Misal:

nXi =0.5 cos(αi) ……………(8)

nYi = 0.5 sin(αi) ……………(9)

dengan i=1,2,…,Q; α1 = 0, dan αi = αi-1 + 2π/Q, untuk i>1.

4. Tetapkan bobot awal antara koordinat kota (x,y) dengan setiap neuron, sebut

sebagai wXi dan wYi secara acak, antara 0 sampai 1; dengan i=1,2,…,Q.

5. Tetapkan bobot awal antar neuron, sebut sebagai rij, dengan i,j = 1,2,…,Q,

dengan cara:

a. Cari jarak setiap antar neuron, nDij, dengan i,j = 1,2,…,Q.

b. ……….(10)

7. Set epoh = 0.

8. Kerjakan selama epoh < MaxEpoh:

a. epoh = epoh+1.

b. Pilih sembarang kota secara random, misal kota terpilih adalah kota keidx.

c. Set koordinat lokasi yang akan didekati (tX,tY):

i. Bangkitkan bilangan satu random r antara 0 sampai 1.

ii. tX = Xidx + r*Near – Near/2 …………(2.10)

iii. tY = Yidx + r*Near – Near/2 ………...(2.11)

d. Cari jarak minimum antara (tX,tY) dengan bobot antara koordinat kota dan neuron

(wXi,wYi), i=1,2,…,Q. Misalkan jarak minimumnya jatuh pada jarak antara

(tX,tY) dengan bobot ke-j (wXj,wYj).

e. Perbaiki bobot antara koordinat kota dan setiap neuron (wXi,wYi),

i=1,2,…,Q:

i. wXi = wXi + ϕ* rij * (tX - wXi)…………… (11)

ii. wYi = wYi + ϕ* rij * (tY - wYi)…………… (12)

dengan j adalah indeks terpilih pada (d).

f. Perbaiki nilai θ dan ϕ:

i. θ = θ * momentum ……………(13)

ii. ϕ= ϕ* momentum……………. (14)

g.Perbaiki bobot antar neuron (rij), dengan i=1,2,…,Q; dan j adalah indeks terpilih

pada (d):

9. Cari jarak minimum antara setiap kota ke-i dengan setiap bobot koordinat

kota ke neuron ke-j, sebut sebagai mJi, dan indeksnya sebut sebagai Li dengan

i=1,2,…,N:

a. mJi = minimum ; dengan j=1,2,…,Q ……. (16)

b. Li = j, sedemikian hingga …………(17)

c. Bentuk matriks P berukuran Nx2 dengan kolom pertama adalah mJi dan kolom

kedua berisi Li.

10. Urutkan naik matriks P, berdasarkan kolom pertama.

11. Jalur terpendek adalah matriks P terurut kolom kedua. Cari panjang jalur terpendek.

16. Metode Matriks Bentuk Normal

Untuk menentukan suatu sikel Hamilton dan graph dapat digunakan metode matriks

bentuk normal, dimana langkah-langkahnya adalah sebagai berikut :

1. Tentukan matriks adjacent A=[aij], dimana i, j = 1,2,3….,n dan aii=0 atau entri pada

diagonal utamanya=0.

2. Identifikasi setiap kolom dengan Ci dan baris dengan Ri, dimana Ci dan Ri bersesuaian

dengan vi dan mempunyai nilai I, dimana i=1,2,…..,n.

3. Tentukan himpunan titik yang terhubung langsung dengan titik vi.

4. Jika matriks keterhubungan A dalam bentu normal, maka sikel Hamiltonnya adalah v1

v2…vk, jika tidak lanjutkan ke langkah berikutnya.

5. Pemrosesan dimulai dari kiri ke kanan sepanjang lintasan normal. Jika ditemukan

entri=0 pada lintasan normal, maka tukarkan entri-entri pada kolom yang memuat

entri=0 tadi dengan entri-entri pada kolom yang tidak memuat 0 pada baris yang

sama. Penukaran dilakukan dengan menukar entri-entri pada Ridan Rj. Penukaran

dilakukan sampai lintasan normal terbentuk.

6. Jika anchor matriks atau entri [an1]=0, maka entri tersebut diganti dengan entri yang

tidak nol pada baris yang sama, dengan memperhatikan bahwa lintasan normal sebisa

mungkin dipertahankan. Apabila penukaran entrinya menyebabkan lintasan tidak

normal, maka pilih entri di sebelah kanannya yang menyebabkan lintasan tetap

normal.

7. Jika matriks sudah dalam bentuk normal, maka sikel Hamilton diidentifikasikan oleh

titik-titik yang bersesuaian dengan C1 C2…..Cn.

18. Program Dinamik (Dynamic Program)

Langkah-langkah:

p(i,L) = min[c(j,i) + p(j,L–{j})]

p(i,S) adalah panjang jalur dari node awal menuju node i setelah sebelumnya

melewati rangkaian jalur L.

Jarak dari node j ke node i dilambangkan dengan c(j,i).

Perhatikan bahwa c(j,i) tidak sama dengan c(i,j) karena graph di atas mengandung 2

directed edge dengan arah berbeda dan weight berbeda.

L-{j} dapat diartikan sebagai rangkaian jalur L yang dikurangi dengan node j.

Maka, panjang lintasan terpendek untuk graph pada gambar di atas adalah

p(A,{B,C,D}) yang artinya panjang lintasan dari node awal menuju node A setelah

melewati node B, C, D dengan urutan apa pun (dicari yang terpendek).

19. Algoritma Exhaustive Search

Algoritma exhaustive search untuk persoalan TSP :

Enumerasikan (list) semua sirkuit Hamilton dari graf lengkap dengan n buah simpul.

Hitung (evaluasi) bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1.

Pilih sirkuit Hamilton yang mempunyai bobot paling terkecil.

Hamilton diidentifikasi oleh titik-titik yang bersesuaian

20. Algoritma Simple Hill Climbing

Langkah-langkah:

1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti;

dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak

ada operator baru yang akan diaplikasikan pada keadaan sekarang:

a. Cari operator yang belum pernah digunakan; gunakan operator ini untuk

mendapatkan keadaan yang baru.

b. Evaluasi keadaan baru tersebut.

i. Jika keadaan baru merupakan tujuan, keluar.

ii. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan

sekarang, maka jadikan keadaan baru tersebut menjadi keadaan

sekarang.

iii. Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka

lanjutkan iterasi.

3. Pada simple hill climbing ini, ada 3 masalah yang mungkin, yaitu:

Algoritma akan berhenti kalau mencapai nilai optimum lokal.

Urutan penggunaan operator akan sangat berprngaruh pada penemuan solusi.

Tidak diijinkan untuk melihat satupun langkah sebelumnya.

21. Algoritma Generate and Test

Algoritma dari metode Generate and Test ini adalah:

1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau

lintasan tertentu dari keadaan awal)

2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara

membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan

kumpulan tujuan yang diharapkan.

3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.

BAB III

METODOLOGI PENELITIAN

3.1 Metodelogi Penelitian

Berikut beberapa objek yang akan kita kaji:

a. Tempat untuk pendistribusian berperan sebagai titik atau simpul.

b. Jalur pendistribusian yang dilalui berperan sebagai sisi.

c. Jarak antara tempat satu ke tempat lain berperan sebagai bobot.

Algoritma yang digunakan

Nearest Neightbour Heuristik

Metode ini dapat digunakan untuk menentukan sikel Hamilton dengan total

jarak terpendek. Metode ini sangat sederhana dan lebih banyak digunakan daripada

metode lain yang dalam menyelesaikan masalah TSP. Adapun langkah-langkahnya

sebagai berikut :

1. Pilih sembarang titik sebagai titik awal dari lintasan.

2. Pilih titik dengan sisi yang terkait yang memiliki bobot minimum.

3. Dari titik baru, pilih titik yang belum terpilih pada lintasan dengan bobot sisi

minimum.

4. Kembali lakukan langkah 3 sampai semua titik telah termuat dalam

lintasan. Selanjutnya hubungkan titik awal dengan titik akhir sehingga

terbentuk sikel.

1. Penyelesaian dengan Alat Bantu

Heuristik.

WinQSB adalah salah satu program atau alat bantu yang dapat digunakan untuk

menyelesaikan beberapa masalah pada Teori Graph. Berikut adalah tampilan dari

winQSB.

Dari 18 aplikasi pada WinQSB, sebagai contoh, disini kita gunakan aplikasi Network

Modelling.Ini dikarenakan selain digunakan pada pembahasan masalah, Network

Modelling juga dapat menyelesaikan 7 permasalahan Graph. Berikut adalah lambang

aplikasi Network Modelling

Selanjutnya pilih File-New Problem, kemudian akan muncul window (halaman)

berikut :

Dari Window diatas, dapat kita lihat 7 permasalahan Graph yang dapat diselesaikan

dengan menggunakan Network Modelling. Apabila kita menemui kesulitan dalam

mengoperasikan atau memahami istilah pada WinQSB, maka WinQSB telah menyediakan

menu Help, yang dapat membantu menjawab kesulitan yang kita hadapi. Menu Help dapat

diakses dengan menekan tombol F1 pada keyboard, atau memilih menu berikut pada

toolbar WinQSB.

Selanjutnya kita dapat memilih menu search, Dan kemudian kita dapat

mengetikkan kata kunci (keyword) yang menjadi permasalahan kita, pada edit

box.

Pembahasan TSP dengan Metode Nearest Neighbour Heuristic, menggunakan alat

bantuWinQSB. Berikut cara mengaplikasikannya:

1. Melalui menu Start, cari folder yang bernama winQSB, dan kemudian klik pada

aplikasi Network Modelling.

2. Setelah window Network Modelling muncul, pilih menu file kemudian pilih New

Problem.

3. Pada NET Problem Spesification, ikuti seperti pada gambar.

BAB IV

PEMBAHASAN

4.1 Permasalahan

UD.Q-A merupakan suatu usaha keluarga yang meproduksi air mineral dan

baru saja beroperasi, mengalami kesulitan dalam pendistribusian produknya yaitu

pendistribusian air mineral.Karena daerah pendistribusiannya yang cukup luas yaitu

se Malang Raya, UD. Q-A mengalami kesulitan untuk mengoptimalisasi

pedistribusiannya. Air mineral tersebut di distribusikan ke agen-agen dan ke rumah-

rumah, yang mana daerah penditribusiannya meliputi:

4. Jl. B. S. Riadi.

5. Jl. Dirgantar.

6. Jl. Danau Brantan.

7. Jl. Danau Poso.

8. Jl. Danau Sentani.

9. Perum Griya Shanta.

10. Jl. Kalpataru.

11. Jl. Borobudur

12. Purwantoro

13. Jl. A. Yani

14. Perum Mondoroko

15. Araya

16. Arjosari

17. Singosari

18. Ngijo

19. Tegalgondo

20. Sengkaling

21. Tlogomas

22. Dinoyo

23. Sumbersari

4.2 Penyelesaian Masalah dengan Algoritma

Penyelesaian Dengan Algoritma Nearest Neightbour Heuristik

Teori graph yang digunakan dalam observasi ini adalah dengan menggunkan

Algoritma Nearest Neightbour Heuristik.

Langkah-langkah menyelesaikan permasalahan dengan Algoritma Nearest

Neighbour Heuristik adalah:

Langkah 1: Pilih titik awal, yaitu titik UD.Q-A (Jl. Ciamis).

Langkah 2: Dari UD.Q-A (Jl. Ciamis) pilih titik yang terhubung langsung yang memiliki

bobot terkecil pilih Sumbersari dengan bobot 1812 m.

UD.Q-A

Langkah 3: Dari Sumbersari pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih S. Riadi dengan bobot 2419 m.

Langkah 4: Dari S. Riadi pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih Dinoyo dengan bobot 3710 m.

Langkah 5: Dari Dinoyo pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih Perum. Griya Shanta dengan bobot 2656 m.

Langkah 6: Dari Griya Shanta pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Jl. Borobudur dengan bobot 2290 m.

Langkah 7: Dari Jl. Borobudur pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Jl. A. Yani dengan bobot 1661 m.

Langkah8: Dari Jl. A. Yani pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih Araya dengan bobot 1760 m.

Langkah 9: Dari Araya pilih titik yang terhubung langsung yang memiliki bobot terkecil pilih

Arjosari dengan bobot 900 m.

Langkah10: Dari Arjosari pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih Purwantoro dengan bobot 1050 m

.

Langkah11: Dari Purwantoro pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Dirgantara dengan bobot 4146 m.

Langkah 12: Dari Dirgantara pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Danau Poso dengan bobot 7639 m.

Langkah 13: Dari Jl. Danau Poso pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Jl. Danau Brantan dengan bobot 1060 m.

Langkah 14: Dari Jl.Danau Brantan pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Jl. Danau Sentani dengan bobot 320 m.

Langkah 15: Dari Jl. Danau Sentani pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Kalpataru dengan bobot 7169 m.

Langkah 16: Dari Kalpataru pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih Tlogomas dengan bobot 4470 m.

Langkah 17: Dari Tlogomas pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih Sengkalaling dengan bobot 2350 m.

Langkah 18: Dari Sengkaling pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Tegalgondo dengan bobot 4150 m.

Langkah 19: Dari Tegalgondo pilih titik yang terhubung langsung yang memiliki bobot

terkecil pilih Ngijo dengan bobot 3600 m.

Langkah 20: Dari Ngijoo pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih Singosari dengan bobot 7747 m.

Langkah 21: Dari Singosari pilih titik yang terhubung langsung yang memiliki bobot terkecil

pilih Perum Mondoroko dengan bobot 1650 m.

Langkah 22: Karena semua titik telah terlewati maka kembali ke titik UD. Q-A dengan bobot

10942

Jadi diperoleh sickle dengan rute:

UD. QA (Jl. Ciamis) – Sumbersari – Jl. S.Riad – Dinoyo – Griya Shanta-- Jl.

Borobudur – Jl. A. Yani – Araya – Arjosari – Purwantoro –Jl. Dirgantara – Jl. Danau

Poso – Jl. Danau Brantan – Jl. Sentani – Kalpataru – Tlogomas –– Sengkaling –

Tegalgondo – Ngijo – Singosari – Mondoroko -- UD. QA (Jl. Ciamis).

Dengan Jarak

Penyelesaiana dengan Algoritma Chepest Link

Langkah 1: Pilih sisi dengan bobot terkecil antara UD.Q-A dengan titik lain yang

terhubung langsung, sehingga pilih sisi UD. Q-A dengan Sumbersari dengan bobot

1812.

Langkah 2: Pilih sisi dengan bobot terkecil antara Sumbersari dengan titik lain yang

terhubung langsung, sehingga pilih sisi Sumbersari dengan S.Riadi dengan bobot 2419.

Langkah 3: Pilih sisi dengan bobot terkecil antara S.Riadi dengan titik lain yang terhubung

langsung, sehingga pilih sisi S.Riadi dengan Dinoyo dengan bobot 3710.

Langkah 4: Pilih sisi dengan bobot terkecil antara Dinoyo dengan titik lain yang terhubung

langsung, sehingga pilih sisi Dinoyo dengan Griya Shanta dengan bobot 2656.

Langkah 6: Pilih sisi dengan bobot terkecil antara Griya Shanta dengan titik lain yang

terhubung langsung, sehingga pilih sisi Griya Shanta dengan Jl. Borobudur dengan bobot

2290.

Langkah 7: Pilih sisi dengan bobot terkecil antara Jl. Borobudur dengan titik lain yang

terhubung langsung, sehingga pilih sisi Jl. Borobudur dengan Jl. A. Yani dengan bobot 1661.

Langkah 8: Pilih sisi dengan bobot terkecil antara Jl. A. Yani dengan titik lain yang

terhubung langsung, sehingga pilih sisi Jl. A. Yani dengan Araya dengan bobot 1760.

Langkah 10: Pilih sisi dengan bobot terkecil antara Araya dengan titik lain yang terhubung

langsung, sehingga pilih sisi Araya dengan Arjosari dengan bobot 900.

Langkah 11: Pilih sisi dengan bobot terkecil antara Arjosari dengan titik lain yang terhubung

langsung, sehingga pilih sisi Arjosari dengan Purwantoro dengan bobot 1050.

.

Langkah 12: Pilih sisi dengan bobot terkecil antara Purwantoro dengan titik lain yang

terhubung langsung, sehingga pilih sisi Purwantoro dengan Dirgantara dengan bobot 4146.

Langkah 12: Pilih sisi dengan bobot terkecil antara Dirgantara dengan titik lain yang

terhubung langsung, sehingga pilih sisi Dirgantara dengan Danau Poso dengan bobot 1080.

Langkah 13: Pilih sisi dengan bobot terkecil antara Danau Poso dengan titik lain yang

terhubung langsung, sehingga pilih sisi Danau Poso dengan Danau Brantan dengan bobot

1060.

Langkah 14: Pilih sisi dengan bobot terkecil antara Danau Brantan dengan titik lain yang

terhubung langsung, sehingga pilih sisi Danau Brantan dengan Danau Sentani dengan bobot

320.

Langkah 15: Pilih sisi dengan bobot terkecil antara Danau Sentani dengan titik

lain yang terhubung langsung, sehingga pilih sisi Danau Sentani dengan Kalpataru

dengan bobot 7169.

Langkah 16: Pilih sisi dengan bobot terkecil antara Kalpataru dengan titik lain yang

terhubung langsung, sehingga pilih sisi Kalpataru dengan Tlogomas dengan bobot 4470.

Langkah 17: Pilih sisi dengan bobot terkecil antara Tlogomas dengan titik lain yang

terhubung langsung, sehingga pilih sisi Tlogomas dengan Sengkaling dengan bobot 2350.

Langkah 18: Pilih sisi dengan bobot terkecil antara Sengkaling dengan titik lain yang

terhubung langsung, sehingga pilih sisi Sengkaling dengan Tegalgondo dengan bobot 4350.

Langkah 19: Pilih sisi dengan bobot terkecil antara Tegalgondo dengan titik

lain yang terhubung langsung, sehingga pilih sisi Tegalgondo dengan Bgijo

dengan bobot 3600.

Langkah 20: Pilih sisi dengan bobot terkecil antara Bgijo dengan titik lain

yang terhubung langsung, sehingga pilih sisi Bgijo dengan Singosari dengan

bobot 7747.

Langkah 21: Pilih sisi dengan bobot terkecil antara Singosari dengan titik lain

yang terhubung langsung, sehingga pilih sisi Singosari dengan Mondoroko

dengan bobot 1650.

Langkah 22: Karena semua titik telah terlewati maka kembali ke titik UD. Q-

A dengan bobot 10942

Jadi diperoleh sickle dengan rute:





Dengan Jarak

Penyelesaian dengan Algoritma Branch and Bound

Langkah 1:

Table 1.1

Solusi masalah yang ditetapkan adalah:

Adalah mungkin dengan nilai :

Sehingga kita atur

Langkah 2:

Buat percabangan

Titik 2:

Lihat tabel 1.2

Hapus baris 1 kolom 2 dari data awal dan set

Solusinya adalah:

Dengan nilai

dengan

Jadi

Kemudian set

Titik 3

Hapus baris 1 kolom ke 3 dari data awal set =M

Solusinya adalah:

=

dengan

Jadi

Titik 4


Solusinya adalah:

=

Dengan nilai

dengan

Jadi

Titik 5


Solusinya adalah:

=

Dengan nilai

8 dengan 8

Jadi 8=73412

Titik 6


Solusinya adalah:

=

Dengan nilai

dengan

Jadi =70016

Titik 7


Solusinya adalah:

=

Dengan nilai

dengan

Jadi = 68186

Titik 8


Solusinya adalah:

=

Dengan nilai

dengan

Jadi = 65203

Titik 9


Solusinya adalah:

=

Dengan nilai

dengan

Jadi = 69833

Titik 10


Solusinya adalah:

Dengan nilai

dengan

Jadi = 69552

Titik 11


Solusinya adalah:

Dengan nilai

dengan

Jadi = 73153

Titik 12


Solusinya adalah:

Dengan nilai

dengan

Jadi =70860

Titik 13


Solusinya adalah:

Dengan nilai

dengan

Jadi =73062

Titik 14


Solusinya adalah:

Dengan nilai

dengan

Jadi =79702

Titik 16

Solusinya adalah:

Dengan nilai

dengan

Jadi =82758

Titik 17


Solusinya adalah:

Dengan nilai

dengan

Jadi =71149

Titik 18


Solusinya adalah:

Dengan nilai

dengan

Jadi =75727

Titik 19


Solusinya adalah:

Dengan nilai

dengan

Jadi =69240

Titik 20


Solusinya adalah:

Dengan nilai

dengan

Jadi =77213

Titik 21


Solusinya adalah:

Dengan nilai

dengan

Jadi =64726

Langkah 3

Terdapat dua titik aktif yaitu titik 8 dan titik 21.

Lalu buat percabangan dari masing-masing titik tersebut.

Percabangan dari titik 8

Percabangan dari titik 21

Langkah 4

Buat batasan pada titik 22 sampai 40 dengan memodifikasi data pada titik 8, karena

titik ini adalah turunan yang berasal dari titik 8.

Lihat tabel 1.3

Titik 22 : Hapus baris 8 kolom ke 2 dari data baru dan set C21 = M

solusinya adalah :

Dengan nilai :

dan f=60699

Jadi,

Titik 23 :

Hapus baris 8 kolom ke 3 dari data baru dan set C31 = M

solusinya adalah :

dan f = 60437

Jadi,

Titik 24 :


solusinya adalah :

Dengan nilai :

dan f=59422

Jadi

Titik 25 :


solusinya adalah :

Dengan nilai :

dan f=56511

Jadi, > fu2

Titik 26 :


solusinya adalah :

Dengan nilai :

dan f=54018

Jadi,

Titik 27 :


solusinya adalah :

Dengan nilai :

dan f=60426

Jadi,

Titik 28 :


solusinya adalah :

Dengan nilai :

dan f=61517

Jadi,

Titik 29 :


solusinya adalah :

Dengan nilai :

dan f=63333

Jadi,

Titik 30 :


solusinya adalah :

Dengan nilai :

dan f=61928

Jadi

Titik 31 :


solusinya adalah :

Dengan nilai :

dan f=56752

Jadi,

Titik 32 :


solusinya adalah :

Dengan nilai :

dan f=63842

Jadi,

Titik 33 :


solusinya adalah :

Dengan nilai :

dan f=65994

Jadi

Titik 34 :


solusinya adalah :

Dengan nilai :

dan f=58565

Jadi,

Titik 35 :


solusinya adalah :

Dengan hasil :

dan f=64557

Jadi

Titik 36


Solusinya adalah:

Dengan nilai

dengan

Jadi =60798

Titik 37 :


solusinya adalah :

Dengan nilai :

dan f=64828

Jadi

Titik 38


(lihat tabel)

Solusinya adalah:

Dengan nilai

dengan

Jadi =67951

Titik 39

Hapus baris 8 kolom ke 20dari data awal set =M

(lihat tabel)

Solusinya adalah:

Dengan nilai

engan

Jadi =64218

Titik 40


(lihat tabel)

Solusinya adalah:

Dengan nilai

engan

Jadi =73409

Buat batasan pada titik 41 sampai 59 dengan memodifikasi data pada titik 21, karena

titik ini adalah turunan yang berasal dari titik 21.

Lihat tabel 1.4

Titik 41

Hapus baris 21 kolom ke 2 dari data baru (dari titik 21) set =M

Solusinya adalah:

Dengan nilai

dengan

Jadi =74574

Titik 42


Solusinya adalah:

Dengan nilai

dengan

Jadi =73596

Titik 43


Solusinya adalah:

Dengan nilai

dengan

Jadi =74000

Titik 44


Solusinya adalah:

Dengan nilai

dengan

Jadi =67886

Titik 45


Solusinya adalah:

Dengan nilai

dengan

Jadi =67665

Titik 46


Solusinya adalah:

Dengan nilai

dengan

Jadi =70284

Titik 47

Hapus baris 21 kolom ke 8dari data baru (dari titik 21) set =M

Solusinya adalah:

Dengan nilai

dengan

Jadi =66914

Titik 48


Solusinya adalah:

Dengan nilai

dengan

Jadi =71240

Titik 49


Solusinya adalah:

Dengan nilai

dengan

Jadi =73469

Titik 50


Solusinya adalah:

Dengan nilai

+1050+1650+7746+3600+4150+2350+3822+3710 =60269 dengan

Jadi

Titik 51


Solusinya adalah:

Dengan nilai

dengan

Jadi

Titik 52


Solusinya adalah:

Dengan nilai

dengan

Jadi

Titik 53


Solusinya adalah:

Dengan nilai

dengan

Jadi

Titik 54


Solusinya adalah:

Dengan nilai

dengan

Jadi

Titik 55


Solusinya adalah:

Dengan nilai

dengan

Jadi

Titik 56


Solusinya adalah:

Dengan nilai

dengan

Jadi

Titik 57


Solusinya adalah:

Dengan nilai

dengan

Jadi

Titik 58


Solusinya adalah:

Dengan nilai

dengan

Jadi

Titik 59


Solusinya adalah:

Dengan nilai

dengan

Jadi

Karena semua titik telah tidak ada yang aktif dan jarak minimum diperoleh dari titik

36 dengan rute:

Dengan nilai

Gambar percabangan:

Iterasi 1

1. Pilih titik sembarang titik awal, yaitu titik Q-A.

2. Cari titik j

Cij = min {2100, 6284, 7664, 6954, 7517, 3370, 2383, 4903, 5074, 6542,

10942, 7752, 7252, 8600, 12484, 8041, 6524, 4874, 1953, 1812}

= 1812, yaitu C(Q-A)(Sumbersari)

Titik yang telah terambil adalah S={Q-A, Sumbersari}

Sehingga terbentuk sikel C={(Q-A, Sumbersari), (Sumbersari, Q-A)}

3. Cari titik k yang terdekat ke sembarang titik dari S

ds (k) = min {ds(B.S Riadi), ds(Dirgantara), ds(Danau Brantan), ds(Danau

Poso), ds(Danau Sentani), ds(Perum Griya Shanta), ds(Kalpataru),

ds(Borobudur), ds(Purwantoro), ds(A. Yani), ds(Perum Mondoroko),

ds(Araya), ds(Arjosari), ds(Singosari), ds(Ngijo), ds(Tegalgondo),

ds(Sengkaling), ds(Tlogomas), ds(Dinoyo)}

= min {2419, 9811, 8520, 7998, 9811, 6094, 4117, 6565, 9497, 7415,

11915, 9093, 9015, 10625, 9150, 7804, 6260, 3810, 3592}

= 2419, yaitu ds(B.S Riadi) dengan k=B.S Riadi

S = {Q-A, Sumbersari, B.S Riadi} dan C={(Q-A, Sumbersari), (Sumbersari, B.S Riadi),

(B.S Riadi, Q-A)}

Iterasi 2

1. ds (k) = min {ds(Dirgantara), ds(Danau Brantan), ds(Danau Poso), ds(Danau

Sentani), ds(Perum Griya Shanta), ds(Kalpataru), ds(Borobudur),

ds(Purwantoro), ds(A. Yani), ds(Perum Mondoroko), ds(Araya),

ds(Arjosari, ds(Singosari), ds(Ngijo), ds(Tegalgondo), ds(Sengkaling),

ds(Tlogomas), ds(Dinoyo)}

= min {4660, 6040, 5330, 5893, 7338, 4560, 5170, 3776, 5820, 10270,

6270, 6470, 7928, 14241, 9798, 8281, 5831, 3710}

= 3710, yaitu ds(Dinoyo) dengan k=Dinoyo

S = {Q-A, Sumbersari, B.S Riadi, Dinoyo}

2. Cari sisi (i,j) dalam sikel yang memiliki nilai minimum dengan titik baru yang telah

terambil yaitu k=Dinoyo

Cik + Ckj - Cij sehingga

sisi (Q-A, Sumbersari) = C(Q-A)(Dinoyo) + C(Dinoyo)(Sumbersari) – C(Q-A)(Sumbersari)

= 1953+3592-1812

= 3733

sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Dinoyo) + C(Dinoyo)(B.S Riadi) -

C(Sumbersari)(B.S Riadi)

= 1953+3710-2419

= 3244

sisi (B.S Riadi, Q-A) = C(B.S Riadi)(Dinoyo) + C(Dinoyo)(Q-A) – C(B.S Riadi)(Q-A)

= 3710+1953-2100

= 3563

Nilai minimum adalah 3563, yaitu sisi (B.S Riadi, Q-A)

Jadi, titik Dinoyo disisipkan dalam sisi (B.S Riadi, Q-A)

Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi),

(B.S Riadi, Dinoyo), (Dinoyo, Q-A)}

Iterasi 3

1. k = Perumahan Griya Shanta

S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Griya Shanta) + C(Griya Shanta)(Sumbersari) –

C(Q-A)(Sumbersari)

= 3370+6097-1812

= 7655

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Griya Shanta) + C(Griya Shanta)(B.S Riadi) -


= 6097+7338-2419

= 11016

Sisi (B.S Riadi, Dinoyo) = C(B.S Riadi)(Griya Shanta) + C(Griya Shanta)(Dinoyo) –

C(B.S Riadi)(Dinoyo)

= 7338+2656-3710

= 6284

Sisi (Dinoyo, Q-A) = C(Dinoyo)(Griya Shanta) + C(Griya Shanta)(Q-A) – C(Dinoyo)(Q-A)

= 2656+6097-1953

= 6800

Nilai minimum adalah 6284, yaitu sisi (B.S Riadi, Dinoyo)

Jadi Perumahan Griya Shanta disisipkan dalam sisi (B.S Riadi, Dinoyo)

Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi,

Perum Griya Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo, Q-A)}

Iterasi 4

1. k = Borobudur

S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta,

Borobudur}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Borobudur) + C(Borobudur)(Sumbersari) – C(Q-A)(Sumbersari)

= 4903+6565-1812

= 9656

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Borobudur) + C(Borobudur) (B.SRiadi) -


= 6565+5170-2419

= 9316

Sisi (B.S Riadi, Perum Griya Shanta) = C(B.S Riadi)(Borobudur) + C(Borobudur)(GriyaShanta)

- C(B.S Riadi)(GriyaShanta)

= 5170+2290-7338

= 122

Sisi (Perum Griya Shanta, Dinoyo) = C(GriyaShanta)(Borobudur) + C(Borobudur)(Dinoyo) –

C(GriyaShanta)(Dinoyo)

= 2290+3124-2656

= 2758

Sisi (Dinoyo, Q-A) = C(Dinoyo)(Borobudur) + C(Borobudur)(Q-A) – C(Dinoyo)(Q-A)

= 3124+4903-1953

= 6074

Nilai minimum adalah 122, yaitu sisi (B.S Riadi, Perum Griya Shanta)

Jadi Borobudur disisipkan dalam sisi (B.S Riadi, Perum Griya Shanta)


Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo,

Q-A)}

Iterasi 5

1. k = A.Yani


Borobudur, A.Yani}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(A.Yani) + C(A.Yani)(Sumbersari) – C(Q-A)(Sumbersari)

= 6542+7415-1812

= 12145

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(A.Yani) + C(A.Yani)(B.S Riadi) –


= 7415+5820-2419

= 10816

Sisi (B.S Riadi, Borobudur) = C(B.S Riadi)(A.Yani) + C(A.Yani)(Borobudur) –

C(B.S Riadi)(Borobudur)

= 5820+1661-5170

= 2311

Sisi (Borobudur, Perum Griya Shanta) = C(Borobudur)(A.Yani) + C(A.Yani)(GriyaShanta) -

C(Borobudur)(GriyaShanta)

= 1661+3929-2290

= 3300

Sisi (Perum Griya Shanta, Dinoyo) = C(GriyaShanta)(A.Yani) + C(A.Yani)(Dinoyo) –


= 3929+3977-2656

= 5250

Sisi (Dinoyo, Q-A) = C(Dinoyo)(A.Yani) + C(A.Yani)(Q-A) – C(Dinoyo)(Q-A)

= 3977+6542-1953

= 8566

Nilai minimum adalah 2311, yaitu sisi (B.S Riadi, Borobudur)

Jadi, A.Yani disisipkan dalam sisi (B.S Riadi, Borobudur)


A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta,

Dinoyo), (Dinoyo, Q-A)}

Iterasi 6

1. k = Araya

S = { Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta,

Borobudur, A.Yani, Araya}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Araya) + C(Araya)(Sumbersari) – C(Q-A)(Sumbersari)

= 7752+9093-1812

= 15033

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Araya) + C(Araya)(B.S Riadi) –


= 9093+6270-2419

= 12944

Sisi (B.S Riadi, A.Yani) = C(B.S Riadi)(Araya) + C(Araya)(A.Yani) – C(B.S Riadi)(A.Yani)

= 6270+1760-5820

= 2210

Sisi (A.Yani, Borobudur) = C(A.Yani)(Araya) + C(Araya)(Borobudur) – C(A.Yani)(Borobudur)

= 1760+2171-1661

= 2270

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Araya) + C(Araya)(GriyaShanta) –


= 2171+4439-2290

= 4320

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Araya) + C(Araya)(Dinoyo) –


= 4439+5655-2656

= 7438

Sisi (Dinoyo, Q-A) = C(Dinoyo)(Araya) + C(Araya)(Q-A) – C(Dinoyo)(Q-A)

= 5655+7752-1953

= 11454

Nilai minimum adalah 2210, yaitu sisi (B.S Riadi, A.Yani)

Jadi, Araya disisipkan dalam sisi (B.S Riadi, A.Yani)


Araya), (Araya, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum

Griya Shanta, Dinoyo), (Dinoyo, Q-A)}

Iterasi 7

1. k = Arjosari


Borobudur, A.Yani, Araya, Arjosari}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Arjosari) + C(Arjosari)(Sumbersari) – C(Q-A)(Sumbersari)

= 7252+9015-1812

= 14455

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Arjosari) + C(Arjosari)(B.S Riadi) –


= 9015+6470-2419

= 13066

Sisi (B.S Riadi, Araya) = C(B.S Riadi)(Arjosari) + C(Arjosari)(Araya) – C(B.S Riadi)(Araya)

= 6470+900-6270

= 1100

Sisi (Araya, A.Yani) = C(Araya)(Arjosari) + C(Arjosari)(A.Yani) – C(Araya)(A.Yani)

= 900+1960-1760

= 1100

Sisi (A.Yani, Borobudur) = C(A.Yani)(Arjosari) + C(Arjosari)(Borobudur) –

C(A.Yani)(Borobudur)

= 1960+2371-1661

= 2670

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Arjosari) + C(Arjosari)(GriyaShanta) –


= 2371+3739-2290

= 3820

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Arjosari) + C(Arjosari)(Dinoyo) –


= 3739+5577-2656

= 6660

Sisi (Dinoyo, Q-A) = C(Dinoyo)(Arjosari) + C(Arjosari)(Q-A) – C(Dinoyo)(Q-A)

= 5577+7252-1953

= 10876

Nilai minimum adalah 1100, yaitu sisi (B.S Riadi, Araya) dan sisi (Araya, A.Yani)

Karena ada 2 sisi yang sama-sama memiliki nilai minimum, maka kita pilih salah

satu, misalkan kita pilih sisi (B.S Riadi, Araya)

Jadi, Arjosari disisipkan dalam sisi (B.S Riadi, Araya)


Arjosari), (Arjosari, Araya), (Araya, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum

Griya Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo, Q-A)}

Iterasi 8

1. k = Purwantoro


Borobudur, A.Yani, Araya, Arjosari, Purwantoro}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Purwantoro) + C(Purwantoro)(Sumbersari) – C(Q-A)(Sumbersari)

= 5074+9597-1812

= 12859

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Purwantoro) + C(Purwantoro)(B.S Riadi) –


= 9597+3776-2419

= 10954

Sisi (B.S Riadi, Arjosari) = C(B.S Riadi)(Purwantoro) + C(Purwantoro)(Arjosari) –

C(B.S Riadi)(Arjosari)

= 3776+1050-6470

= - 1644

Sisi (Arjosari, Araya) = C(Arjosari)(Purwantoro) + C(Purwantoro)(Araya) – C(Arjosari)(Araya)

= 1050+2799-900

= 2949

Sisi (Araya, A.Yani) = C(Araya)(Purwantoro) + C(Purwantoro)(A.Yani) – C(Araya)(A.Yani)

= 2799+3499-1760

= 4538

Sisi (A.Yani, Borobudur) = C(A.Yani)(Purwantoro) + C(Purwantoro)(Borobudur) –


= 3499+3117-1661

= 4955

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Purwantoro) + C(Purwantoro)(GriyaShanta) –


= 3117+8206-2290

= 9033

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Purwantoro) + C(Purwantoro)(Dinoyo) –


= 8206+6416-2656

= 11966

Sisi (Dinoyo, Q-A) = C(Dinoyo)(Purwantoro) + C(Purwantoro)(Q-A) – C(Dinoyo)(Q-A)

= 6416+ 5074-1953

= 9537

Nilai minimum adalah -1644, yaitu sisi (B.S Riadi, Arjosari)

Jadi Purwantoro disisipkan dalam sisi (B.S Riadi, Arjosari)


Purwantoro) (Purwantoro, Arjosari), (Arjosari, Araya), (Araya, A.Yani), (A.Yani,


Q-A)}

Iterasi 9

1. k = Dirgantara


Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Dirgantara) + C(Dirgantara)(Sumbersari) – C(Q-A)(Sumbersari)

= 6284+7498-1812

= 11970

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Dirgantara) + C(Dirgantara)(B.S Riadi) –


= 7498+4660-2419

= 9739

Sisi (B.S Riadi, Purwantoro) = C(B.S Riadi)(Dirgantara) + C(Dirgantara)(Purwantoro) –

C(B.S Riadi)(Purwantoro)

= 4660+4146-3776

= 5030

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Dirgantara) + C(Dirgantara)(Arjosari) –

C(Purwantoro)(Arjosari)

= 4146+6840-1050

= 9936

Sisi (Arjosari, Araya) = C(Arjosari)(Dirgantara) + C(Dirgantara)(Araya) – C(Arjosari)(Araya)

= 6840+6640-900

= 12580

Sisi (Araya, A.Yani) = C(Araya)(Dirgantara) + C(Dirgantara)(A.Yani) – C(Araya)(A.Yani)

= 6840+7340-1760

= 12420

Sisi (A.Yani, Borobudur) = C(A.Yani)(Dirgantara) + C(Dirgantara)(Borobudur) –


= 7340+4418-1661

= 10097

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Dirgantara) + C(Dirgantara)(GriyaShanta) –


= 4418+8704-2290

= 10832

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Dirgantara) + C(Dirgantara)(Dinoyo) –


= 8704+9667-2656

= 15715

Sisi (Dinoyo, Q-A) = C(Dinoyo)(Dirgantara) + C(Dirgantara)(Q-A) – C(Dinoyo)(Q-A)

= 8704+6284-1953

= 13035

Nilai minimum adalah 5030, yaitu sisi (B.S Riadi, Purwantoro)

Jadi, Dirgantara disisipkan dalam sisi (B.S Riadi, Purwantoro)


Dirgantara), (Dirgantara, Purwantoro) (Purwantoro, Arjosari), (Arjosari, Araya), (Araya,

A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta,

Dinoyo), (Dinoyo, Q-A)}

Iterasi 10

1. k = Danau Poso


Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(DanauPoso) + C(DanauPoso)(Sumbersari) – C(Q-A)(Sumbersari)

= 6954+7998-1812

= 13140

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(DanauPoso) + C(DanauPoso)(B.S Riadi) –


= 7998+5330-2419

= 10909

Sisi (B.S Riadi, Dirgantara) = C(B.S Riadi)(DanauPoso) + C(DanauPoso)(Dirgantara) –

C(B.S Riadi)(Dirgantara)

= 5330+1080-4660

= 1750

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(DanauPoso) + C(DanauPoso)(Purwantoro) –

C(Dirgantara)(Purwantoro)

= 1080+4859-4146

= 1793

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(DanauPoso) + C(DanauPoso)(Arjosari) –


= 4859+5254-1050

= 9063

Sisi (Arjosari, Araya) = C(Arjosari)(DanauPoso) + C(DanauPoso)(Araya) – C(Arjosari)(Araya)

= 5254+7140-900

= 11494

Sisi (Araya, A.Yani) = C(Araya)(DanauPoso) + C(DanauPoso)(A.Yani) – C(Araya)(A.Yani)

= 7140+7840-1760

=13220

Sisi (A.Yani, Borobudur) = C(A.Yani)(DanauPoso) + C(DanauPoso)(Borobudur) –


= 7840+7040-1661

= 13219

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(DanauPoso) + C(DanauPoso)(GriyaShanta) –


= 7040+9208-2290

= 13958

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(DanauPoso) + C(DanauPoso)(Dinoyo) -


= 9208+20167-2656

= 26719

Sisi (Dinoyo, Q-A) = C(Dinoyo)(DanauPoso) + C(DanauPoso)(Q-A) – C(Dinoyo)Q-A)

= 20167+6954-1953

= 25168

Nilai minimum adalah 1750, yaitu sisi (B.S Riadi, Dirgantara)

Jadi, Danau Poso disisipkan dalam sisi (B.S Riadi, Dirgantara)


Danau Poso), (Danau Poso, Dirgantara), (Dirgantara, Purwantoro) (Purwantoro, Arjosari),

(Arjosari, Araya), (Araya, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya

Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo, Q-A)}

Iterasi 11

1. k = Danau Brantan


Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau

Brantan}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(DanauBrantan) + C(DanauBrantan)(Sumbersari) –

C(Q-A)(Sumbersari)

= 7664+7438-1812

= 13290

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(DanauBrantan) + C(DanauBrantan)(B.S Riadi) –


= 7438+6040-2419

= 11059

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Danau Brantan) + C(DanauBrantan)(DanauPoso) –

C(B.S Riadi)(DanauPoso)

= 6040+1060-5330

= 1770

Sisi (Danau Poso, Dirgantara) = C(DanauPoso)(DanauBrantan) + C(DanauBrantan)(Dirgantara) –

C(DanauPoso)(Dirgantara)

= 1060+1590-1080

= 1570

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(DanauBrantan) + C(DanauBrantan)(Purwantoro) –


= 1590+5154-4146

= 2598

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(DanauBrantan) + C(DanauBrantan)(Arjosarai) –


= 5154+5361-1050

= 9465

Sisi (Arjosari, Araya) = C(Arjosari)(DanauBrantan) + C(DanauBrantan)(Araya) – C(Arjosari)(Araya)

= 5361+7260-900

= 11721

Sisi (Araya, A.Yani) = C(Araya)(DanauBrantan) + C(DanauBrantan)(A.Yani) – C(Araya)(A.Yani)

= 7260+7260-1760

= 12760

Sisi (A.Yani, Borobudur) = C(A.Yani)(DanauBrantan) + C(DanauBrantan)(Borobudur) –


= 7260+7548-1661

= 13147

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(DanauBrantan) + C(DanauBrantan)(GriyaShanta)

– C(Borobudur)(GriyaShanta)

= 7548+9716-2290

= 14974

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(DanauBrantan) + C(DanauBrantan)(Dinoyo) –


= 9716+8500-2656

= 15560

Sisi (Dinoyo, Q-A) = C(Dinoyo)(DanauBrantan) + C(DanauBrantan)(Q-A) – C(Dinoyo)(Q-A)

= 8500+13290-1953

= 19837

Nilai minimum adalah 1570, yaitu sisi (Danau Poso, Dirgantara)

Jadi, Danau Brantan disisipkan dalam sisi (Danau Poso, Dirgantara)


Danau Poso), (Danau Poso, Danau Brantan), (Danau Brantan, Dirgantara), (Dirgantara,

Purwantoro) (Purwantoro, Arjosari), (Arjosari, Araya), (Araya, A.Yani), (A.Yani,


Q-A)}

Iterasi 12

1. k = Danau Sentani



Brantan, Danau Sentani}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(DanauSentani) + C(DanauSentani)(Sumbersari) –

C(Q-A)(Sumbersari)

= 7517+9811-1812

= 15516

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(DanauSentani) + C(DanauSentani)(B.S Riadi) –


= 9811+5893-2419

= 13285

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(DanauSentani) + C(DanauSentani)(DanauPoso) –


= 5893+1529-5330

= 2092

Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(DanauSentani) +

C(DanauSentani)(DanauBrantan) – C(DanauPoso)(DanauBrantan)

= 1529+320-1060

= 789

Sisi (Danau Brantan, Dirgantara) = C(DanauBrantan)(DanauSentani) +

C(DanauSentani)(Dirgantara) – C(DanauBrantan)(Dirgantara)

= 320+1640-1590

= 370

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(DanauSentani) + C(DanauSentani)(Purwantoro) –


= 1640+5379-4146

= 2873

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(DanauSentani) + C(DanauSentani)(Arjosari) –


= 5379+6724-1050

= 11053

Sisi (Arjosari, Araya) = C(Arjosari)(DanauSentani) + C(DanauSentani)(Araya) – C(Arjosari)(Araya)

= 6724+7873-900

= 13697

Sisi (Araya, A.Yani) = C(Araya)(DanauSentani) + C(DanauSentani)(A.Yani) – C(Araya)(A.Yani)

= 7873+7923-1760

= 14036

Sisi (A.Yani, Borobudur) = C(A.Yani)(DanauSentani) + C(DanauSentani)(Borobudur) –


= 7923+7773-1661

= 14035

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(DanauSentani) + C(DanauSentani)(GriyaShanta)

– C(Borobudur)(GriyaShanta)

= 7773+9061-2290

= 14544

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(DanauSentani) + C(DanauSentani)(Dinoyo) –


= 9061+10900-2656

= 17305

Sisi (Dinoyo, Q-A) = C(Dinoyo)(DanauSentani) + C(DanauSentani)(Q-A) – C(Dinoyo)(Q-A)

= 10900+7517-1953

= 16464

Nilai minimum adalah 370, yaitu sisi (Danau Brantan, Dirgantara)

Jadi, Danau Sentani disisipkan dalam sisi (Danau Brantan, Dirgantara)


Danau Poso), (Danau Poso, Danau Brantan), (Danau Brantan, Danau Sentani), (Danau

Sentani, Dirgantara), (Dirgantara, Purwantoro) (Purwantoro, Arjosari), (Arjosari, Araya),

(Araya, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya

Shanta, Dinoyo), (Dinoyo, Q-A)}

Iterasi 13

1. k = Kalpataru



Brantan, Danau Sentani, Kalpataru}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Kalpataru) + C(Kalpataru)(Sumbersari) – C(Q-A)(Sumbersari)

= 2383+4117-1812

= 4688

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Kalpataru) + C(Kalpataru)(B.S Riadi) –


= 4117+4560-2419

= 6258

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Kalpataru) + C(Kalpataru)(DanauPoso) –


= 4560+6430-5330

= 5660

Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Kalpataru) + C(Kalpataru)(DanauBrantan) –

C(DanauPoso)(DanauBrantan)

= 6430+6238-1060

= 11608

Sisi (Danau Brantan, Danau Sentani) = C(DanauBrantan)(Kalpataru) +

C(Kalpataru)(DanauSentani) – C(DanauBrantan)(DanauSentani)

= 6238+7169-320

= 13087

Sisi (Danau Sentani, Dirgantara) = C(DanauSentani)(Kalpataru) + C(Kalpataru)(Dirgantara) –

C(DanauSentani)(Dirgantara)

= 7169+4450-1640

= 9979

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Kalpataru) + C(Kalpataru)(Purwantoro) –


= 4450+6150-4146

= 6454

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Kalpataru) + C(Kalpataru)(Arjosari) –


= 6150+3440-1050

= 8540

Sisi (Arjosari, Araya) = C(Arjosari)(Kalpataru) + C(Kalpataru)(Araya) – C(Arjosari)(Araya)

= 3440+4140-900

= 6680

Sisi (Araya, A.Yani) = C(Araya)(Kalpataru) + C(Kalpataru)(A.Yani) – C(Araya)(A.Yani)

= 4140+3600-1760

= 5980

Sisi (A.Yani, Borobudur) = C(A.Yani)(Kalpataru) + C(Kalpataru)(Borobudur) –


= 3600+2950-1661

= 4889

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Kalpataru) + C(Kalpataru)(GriyaShanta) –


= 2950+3299-2290

= 3959

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Kalpataru) + C(Kalpataru)(Dinoyo) –


= 3299+2770-2656

= 3413

Sisi (Dinoyo, Q-A) = C(Dinoyo)(Kalpataru) + C(Kalpataru)(Q-A) – C(Dinoyo)(Q-A)

= 2770+2383-1953

= 3200

Nilai minimum adalah 3200, yaitu sisi (Dinoyo, Q-A)

Jadi, Kalpataru disisipkan dalam sisi (Dinoyo, Q-A)





Shanta, Dinoyo), (Dinoyo, Kalpataru), (Kalpataru, Q-A)}

Iterasi 14

1. k = Tlogomas



Brantan, Danau Sentani, Kalpataru, Tlogomas}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Tlogomas) + C(Tlogomas)(Sumbersari) – C(Q-A)(Sumbersari)

= 4874+3810-1812

= 6872

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Tlogomas) + C(Tlogomas)(B.S Riadi) –


=3810+5831-2419

= 7222

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Tlogomas) + C(Tlogomas)(DanauPoso) –


= 5831+9715-5330

= 10216

Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Tlogomas) + C(Tlogomas)(DanauBrantan) –


= 9715+10223-1060

= 18878

Sisi (Danau Brantan, Danau Sentani) = C(DanauBrantan)(Tlogomas) +

C(Tlogomas)(Danau Sentani) – C(DanauBrantan)(DanauSentani)

= 10223+10448-320

= 20351

Sisi (Danau Sentani, Dirgantara) = C(DanauSentani)(Tlogomas) + C(Tlogomas)(Dirgantara) –


= 10448+9215-1640

= 18023

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Tlogomas) + C(Tlogomas)(Purwantoro) –


= 9215+9036-4146

= 14105

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Tlogomas) + C(Tlogomas)(Arjosari) –


= 9036+8200-1050

= 16186

Sisi (Arjosari, Araya) = C(Arjosari)(Tlogomas) + C(Tlogomas)(Araya) – C(Arjosari)(Araya)

= 8200+8278-900

= 15578

Sisi (Araya, A.Yani) = C(Araya)(Tlogomas) + C(Tlogomas)(A.Yani) – C(Araya)(A.Yani)

= 8278+6600-1760

= 13118

Sisi (A.Yani, Borobudur) = C(A.Yani)(Tlogomas) + C(Tlogomas)(Borobudur) –


= 6600+5750-1661

= 10689

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Tlogomas) + C(Tlogomas)(GriyaShanta) –


= 5750+3822-2290

= 7282

Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Tlogomas) + C(Tlogomas)(Dinoyo) –


= 3822+3079-2656

= 4245

Sisi (Dinoyo, Kalpataru) = C(Dinoyo)(Tlogomas) + C(Tlogomas)(Kalpataru) –

C(Dinoyo)(Kalpataru)

= 3079+4470-2770

= 4779

Sisi (Kalpataru, Q-A) = C(Kalpataru)(Tlogomas) + C(Tlogomas)(Q-A) – C(Kalpataru)(Q-A)

= 4470+4847-2383

= 6934

Nilai minimum adalah 4245, yaitu sisi (Griya Shanta, Dinoyo)

Jadi, Tlogomas disisipkan dalam sisi (Griya Shanta, Dinoyo)





Shanta, Tlogomas), (Tlogomas, Dinoyo), (Dinoyo, Kalpataru), (Kalpataru, Q-A)}

Iterasi 15

1. k = Sengkaling



Brantan, Danau Sentani, Kalpataru, Tlogomas, Sengkaling}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Sengkaling) + C(Sengkaling)(Sumbersari) – C(Q-A)(Sumbersari)

= 6524+6260-1812

= 10972

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Sengkaling) + C(Sengkaling)(B.S Riadi) –


= 6260+8281-2419

= 12122

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Sengkaling) + C(Sengkaling)(DanauPoso) –


= 8281+12165-5330

= 15116

Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Sengkaling) + C(Sengkaling)(DanauBrantan)

– C(DanauPoso)(DanauBrantan)

= 12165+12673-1060

= 23778

Sisi (Danau Brantan, Danau Sentani) = C(DanauBrantan)(Sengkaling) +

C(Sengkaling)(DanauSentani) – C(DanauBrantan)(DanauSentani)

= 12673+12898-320

= 25251

Sisi (Danau Sentani, Dirgantara) = C(DanauSentani)(Sengkaling) + C(Sengkaling)(Dirgantara) –


= 12898+11665-1640

= 22923

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Sengkaling) + C(Sengkaling)(Purwantoro) –


= 11665+11489-4146

= 19008

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Sengkaling) + C(Sengkaling)(Arjosari) –


= 11489+10650-1050

= 21089

Sisi (Arjosari, Araya) = C(Arjosari)(Sengkaling) + C(Sengkaling)(Araya) – C(Arjosari)(Araya)

= 10650+10728-900

= 20478

Sisi (Araya, A.Yani) = C(Araya)(Sengkaling) + C(Sengkaling)(A.Yani) – C(Araya)(A.Yani)

= 10728+9050-1760

= 18018

Sisi (A.Yani, Borobudur) = C(A.Yani)(Sengkaling) + C(Sengkaling)(Borobudur) –


= 9050+8200-1661

= 15589

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Sengkaling) + C(Sengkaling)(GriyaShanta) –


= 8200+5472-2290

= 11382

Sisi (Griya Shanta, Tlogomas) = C(GriyaShanta)(Sengkaling) + C(Sengkaling)(Tlogomas) –

C(GriyaShanta)(Tlogomas)

= 5472+2350-3822

= 4000

Sisi (Tlogomas, Dinoyo) = C(Tlogomas)(Sengkaling) + C(Sengkaling)(Dinoyo) –

C(Tlogomas)(Dinoyo)

= 2350+5547-3079

= 4818

Sisi (Dinoyo, Kalpataru) = C(Dinoyo)(Sengkaling) + C(Sengkaling)(Kalpataru) –


= 5547+6920-2770

= 9697

Sisi (Kalpataru, Q-A) = C(Kalpataru)(Sengkaling) + C(Sengkaling)(Q-A) – C(Kalpataru)(Q-A)

= 6920+6524-2383

= 11061

Nilai minimum adalah 4000, yaitu sisi (Griya Shanta, Tlogomas)

Jadi, Sengkaling disisipkan dalam sisi (Griya Shanta, Tlogomas)





Shanta, Sengkaling), (Sengkaling, Tlogomas), (Tlogomas, Dinoyo), (Dinoyo, Kalpataru),

(Kalpataru, Q-A)}

Iterasi 16

1. k = Tegalgondo



Brantan, Danau Sentani, Kalpataru, Tlogomas, Sengkaling, Tegalgondo}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Tegalgondo) + C(Tegalgondo)(Sumbersari) – C(Q-A)(Sumbersari)

= 8041+7804-1812

= 14033

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Tegalgondo) + C(Tegalgondo)(B.S Riadi) –


= 7804+9798-2419

= 15183

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Tegalgondo) + C(Tegalgondo)(DanauPoso) –


= 9798+14310-5330

= 18778

Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Tegalgondo) +

C(Tegalgondo)(DanauBrantan) – C(DanauPoso)(DanauBrantan)

= 14310+14818-1060

= 28068

Sisi (Danau Brantan, Danau Sentani) = C(DanauBrantan)(Tegalgondo) +

C(Tegalgondo)(DanauSentani) – C(DanauBrantan)(DanauSentani)

= 14818+15043-320

= 29541

Sisi (Danau Sentani, Dirgantara) = C(DanauSentani)(Tegalgondo) + C(Tegalgondo)(Dirgantara)

– C(DanauSentani)(Dirgantara)

= 15043+13810-1640

= 27213

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Tegalgondo) + C(Tegalgondo)(Purwantoro) –


= 13810+9329-4146

= 18993

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Tegalgondo) + C(Tegalgondo)(Arjosari) –


= 9329+9720-1050

= 17999

Sisi (Arjosari, Araya) = C(Arjosari)(Tegalgondo) + C(Tegalgondo)(Araya) – C(Arjosari)(Araya)

= 9720+9798-900

= 18618

Sisi (Araya, A.Yani) = C(Araya)(Tegalgondo) + C(Tegalgondo)(A.Yani) – C(Araya)(A.Yani)

= 9798+8120-1760

= 16158

Sisi (A.Yani, Borobudur) = C(A.Yani)(Tegalgondo) + C(Tegalgondo)(Borobudur) –


= 8120+7270-1661

=13729

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Tegalgondo) + C(Tegalgondo)(GriyaShanta) –


= 7270+5185-2290

= 10165

Sisi (Griya Shanta, Sengkaling) = C(GriyaShanta)(Tegalgondo) + C(Tegalgondo)(Sengkaling) –

C(GriyaShanta)(Sengkaling)

= 5185+4150-5472

= 3863

Sisi (Sengkaling, Tlogomas) = C(Sengkaling)(Tegalgondo) + C(Tegalgondo)(Tlogomas) –

C(Sengkaling)(Tlogomas)

= 4150+3800-2350

= 5600

Sisi (Tlogomas, Dinoyo) = C(Tlogomas)(Tegalgondo) + C(Tegalgondo)(Dinoyo) –

C(Tlogomas)(Dinoyo)

= 3800+7277-3079

= 7998

Sisi (Dinoyo, Kalpataru) = C(Dinoyo)(Tegalgondo) + C(Tegalgondo)(Kalpataru) –


= 7277+8100-2770

= 12607

Sisi (Kalpataru, Q-A) = C(Kalpataru)(Tegalgondo) + C(Tegalgondo)(Q-A) – C(Kalpataru)(Q-A)

= 8100+8041-2383

= 13758

Nilai minimum adalah 3863, yaitu sisi (Griya Shanta, Sengkaling)

Jadi, Tegalgondo disisipkan dalam sisi (Griya Shanta, Sengkaling)





Shanta, Tegalgondo), (Tegalgondo, Sengkaling), (Sengkaling, Tlogomas), (Tlogomas,

Dinoyo), (Dinoyo, Kalpataru), (Kalpataru, Q-A)}

Iterasi 17

1. k = Ngijo



Brantan, Danau Sentani, Kalpataru, Tlogomas, Sengkaling, Tegalgondo, Ngijo}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Ngijo) + C(Ngijo)(Sumbersari) – C(Q-A)(Sumbersari)

= 12484+9150-1812

= 19822

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Ngijo) + C(Ngijo)(B.S Riadi) –


= 9150+14241-2419

= 20972

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Ngijo) + C(Ngijo)(DanauPoso) –


= 14241+17370-5330

= 26281

Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Ngijo) + C(Ngijo)(DanauBrantan) –


= 17370+16790-1060

= 33100

Sisi (Danau Brantan, Danau Sentani) = C(DanauBrantan)(Ngijo) + C(Ngijo)(DanauSentani) –

C(DanauBrantan)(DanauSentani)

= 16790+18103-320

= 34573

Sisi (Danau Sentani, Dirgantara) = C(DanauSentani)(Ngijo) + C(Ngijo)(Dirgantara) –


= 18103+17670-1640

= 34133

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Ngijo) + C(Ngijo)(Purwantoro) –


= 17670+4587-4146

= 18111

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Ngijo) + C(Ngijo)(Arjosari) –


= 4587+11130-1050

= 14667

Sisi (Arjosari, Araya) = C(Arjosari)(Ngijo) + C(Ngijo)(Araya) – C(Arjosari)(Araya)

= 11130+10118-900

= 20348

Sisi (Araya, A.Yani) = C(Araya)(Ngijo) + C(Ngijo)(A.Yani) – C(Araya)(A.Yani)

= 10118+11060-1760

= 19418

Sisi (A.Yani, Borobudur) = C(A.Yani)(Ngijo) + C(Ngijo)(Borobudur) – C(A.Yani)(Borobudur)

= 11060+9960-1661

= 19359

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Ngijo) + C(Ngijo)(GriyaShanta) –


= 9960+8759-2290

= 16429

Sisi (Griya Shanta, Tegalgondo) = C(GriyaShanta)(Ngijo) + C(Ngijo)(Tegalgondo) –

C(GriyaShanta)(Tegalgondo)

= 8759+3600-5185

= 7174

Sisi (Tegalgondo, Sengkaling) = C(Tegalgondo)(Ngijo) + C(Ngijo)(Sengkaling) –

C(Tegalgondo)(Sengkaling)

= 3600+5950-4150

= 5400

Sisi (Sengkaling, Tlogomas) = C(Sengkaling)(Ngijo) + C(Ngijo)(Tlogomas) –


= 5950+5600-2350

= 9200

Sisi (Tlogomas, Dinoyo) = C(Tlogomas)(Ngijo) + C(Ngijo)(Dinoyo) – C(Tlogomas)(Dinoyo)

= 5600+8797-3079

= 11318

Sisi (Dinoyo, Kalpataru) = C(Dinoyo)(Ngijo) + C(Ngijo)(Kalpataru) – C(Dinoyo)(Kalpataru)

= 8797+12880-2770

= 18907

Sisi (Kalpataru, Q-A) = C(Kalpataru)(Ngijo) + C(Ngijo)(Q-A) – C(Kalpataru)(Q-A)

= 12880+12484-2383

= 22981

Nilai minimum adalah 5400, yaitu sisi (Tegalgondo, Sengkaling)

Jadi, Ngijo disisipkan dalam sisi (Tegalgondo, Sengkaling)





Shanta, Tegalgondo), (Tegalgondo, Ngijo), (Ngijo, Sengkaling), (Sengkaling, Tlogomas),

(Tlogomas, Dinoyo), (Dinoyo, Kalpataru), (Kalpataru, Q-A)}

Iterasi 18

1. k = Singosari



Brantan, Danau Sentani, Kalpataru, Tlogomas, Sengkaling, Tegalgondo, Ngijo,

Singosari}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Singosari) + C(Singosari)(Sumbersari) – C(Q-A)(Sumbersari)

= 8600+10265-1812

= 17053

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Singosari) + C(Singosari)(B.S Riadi) –


= 10265+7928-2419

= 15774

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Singosari) + C(Singosari)(DanauPoso) –


= 7928+9638-5330

= 12236

Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Singosari) + C(Singosari)(DanauBrantan) –


= 9638+9058-1060

= 17636

Sisi (Danau Brantan, Danau Sentani) = C(DanauBrantan)(Singosari) +

C(Singosari)(DanauSentani) – C(DanauBrantan)(DanauSentani)

= 9058+10371-320

= 19109

Sisi (Danau Sentani, Dirgantara) = C(DanauSentani)(Singosari) + C(Singosari)(Dirgantara) –


= 10371+9138-1640

= 17869

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Singosari) + C(Singosari)(Purwantoro) –


= 9138+5307-4146

= 10299

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Singosari) + C(Singosari)(Arjosari) –


= 5307+3398-1050

= 7655

Sisi (Arjosari, Araya) = C(Arjosari)(Singosari) + C(Singosari)(Araya) – C(Arjosari)(Araya)

= 3398+2386-900

= 4884

Sisi (Araya, A.Yani) = C(Araya)(Singosari) + C(Singosari)(A.Yani) – C(Araya)(A.Yani)

= 2386+3328-1760

= 3954

Sisi (A.Yani, Borobudur) = C(A.Yani)(Singosari) + C(Singosari)(Borobudur) –


= 3328+3719-1661

= 5386

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Singosari) + C(Singosari)(GriyaShanta) –


= 3719+5987-2290

=7416

Sisi (Griya Shanta, Tegalgondo) = C(GriyaShanta)(Singosari) + C(Singosari)(Tegalgondo) –


= 5987+10157-5185

= 10959

Sisi (Tegalgondo, Ngijo) = C(Tegalgondo)(Singosari) + C(Singosari)(Ngijo) –

C(Tegalgondo)(Ngijo)

= 10157+7747-3600

= 14304

Sisi (Ngijo, Sengkaling) = C(Ngijo)(Singosari) + C(Singosari)(Sengkaling) – C(Ngijo)(Sengkaling)

= 7747+12507-5950

= 14304

Sisi (Sengkaling, Tlogomas) = C(Sengkaling)(Singosari) + C(Singosari)(Tlogomas) –


= 12507+9450-2350

= 19607

Sisi (Tlogomas, Dinoyo) = C(Tlogomas)(Singosari) + C(Singosari)(Dinoyo) –

C(Tlogomas)(Dinoyo)

= 9450+6827-3079

= 13198

Sisi (Dinoyo, Kalpataru) = C(Dinoyo)(Singosari) + C(Singosari)(Kalpataru) –


= 6827+5708-2770

= 9765

Sisi (Kalpataru, Q-A) = C(Kalpataru)(Singosari) + C(Singosari)(Q-A) – C(Kalpataru)(Q-A)

= 5708+8600-2383

= 11925

Nilai minimum adalah 3954, yaitu sisi (Araya, A.Yani)

Jadi, Singosari disisipkan dalam sisi (Araya, A.Yani)

Sehingga didapatkan sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi,



(Araya, Singosari), (Singosari, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya

Shanta), (Perum Griya Shanta, Tegalgondo), (Tegalgondo, Ngijo), (Ngijo, Sengkaling),

(Sengkaling, Tlogomas), (Tlogomas, Dinoyo), (Dinoyo, Kalpataru), (Kalpataru, Q-A)}

Iterasi 19

1. k = Perum Mondoroko



Brantan, Danau Sentani, Kalpataru, Tlogomas, Sengkaling, Tegalgondo, Ngijo,

Singosari, Perumahan Mondoroko}

2. Sisi (Q-A, Sumbersari) = C(Q-A)(Mondoroko) + C(Mondoroko)(Sumbersari) – C(Q-A)(Sumbersari)

= 10942+11915-1812

= 21045

Sisi (Sumbersari, B.S Riadi) = C(Sumbersari)(Mondoroko) + C(Mondoroko)(B.S Riadi) –


= 11915+10270-2419

= 19766

Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Mondoroko) + C(Mondoroko)(DanauPoso) –


= 10270+11080-5330

= 16020

Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Mondoroko) +

C(Mondoroko)(DanauBrantan) – C(DanauPoso)(DanauBrantan)

= 11080+11480-1060

= 21500

Sisi (Danau Brantan, Danau Sentani) = C(DanauBrantan)(Mondoroko) +

C(Mondoroko)(DanauSentani) – C(DanauBrantan)(DanauSentani)

= 11480+11812-320

= 22972

Sisi (Danau Sentani, Dirgantara) = C(DanauSentani)(Mondoroko) + C(Mondoroko)(Dirgantara)

– C(DanauSentani)(Dirgantara)

= 11812+11480-1640

= 21652

Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Mondoroko) + C(Mondoroko)(Purwantoro) –


= 11480+7639-4146

= 14973

Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Mondoroko) + C(Mondoroko)(Arjosari) –


= 7639+5049-1050

= 11638

Sisi (Arjosari, Araya) = C(Arjosari)(Mondoroko) + C(Mondoroko)(Araya) – C(Arjosari)(Araya)

= 5049+4199-900

= 8348

Sisi (Araya, Singosari) = C(Araya)(Mondoroko) + C(Mondoroko)(Singosari) – C(Araya)(Singosari)

= 4199+1650-2386

= 3463

Sisi (Singosari, A.Yani) = C(Singosari)(Mondoroko) + C(Mondoroko)(A.Yani) –

C(Singosari)(A.Yani)

= 1650+5670-3328

= 3992

Sisi (A.Yani, Borobudur) = C(A.Yani)(Mondoroko) + C(Mondoroko)(Borobudur) –


= 5670+6061-1661

= 10070

Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Mondoroko) + C(Mondoroko)(GriyaShanta) –


= 6061+8329-2290

= 12100

Sisi (Griya Shanta, Tegalgondo) = C(GriyaShanta)(Mondoroko) + C(Mondoroko)(Tegalgondo) –


= 8329+11850-5185

= 14994

Sisi (Tegalgondo, Ngijo) = C(Tegalgondo)(Mondoroko) + C(Mondoroko)(Ngijo) –

C(Tegalgondo)(Ngijo)

= 11850+9440-3600

= 17690

Sisi (Ngijo, Sengkaling) = C(Ngijo)(Mondoroko) + C(Mondoroko)(Sengkaling) –

C(Ngijo)(Sengkaling)

= 9440+14200-5950

= 17690

Sisi (Sengkaling, Tlogomas) = C(Sengkaling)(Mondoroko) + C(Mondoroko)(Tlogomas) –


= 14200+11100-2350

= 22950

Sisi (Tlogomas, Dinoyo) = C(Tlogomas)(Mondoroko) + C(Mondoroko)(Dinoyo) –

C(Tlogomas)(Dinoyo)

= 11100+8477-3079

= 16498

Sisi (Dinoyo, Kalpataru) = C(Dinoyo)(Mondoroko) + C(Mondoroko)(Kalpataru) –


= 8477+8050-2770

= 13757

Sisi (Kalpataru, Q-A) = C(Kalpataru)(Mondoroko) + C(Mondoroko)(Q-A) – C(Kalpataru)(Q-A)

= 8050+10942-2383

= 16609

Nilai minimum adalah 3463, yaitu sisi (Araya, Singosari)

Jadi, Perumahan Mondoroko disisipkan dalam sisi (Araya, Singosari)

Sehingga terbentuk

sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, Danau Poso), (Danau

Poso, Danau Brantan), (Danau Brantan, Danau Sentani), (Danau Sentani, Dirgantara),

(Dirgantara, Purwantoro) (Purwantoro, Arjosari), (Arjosari, Araya), (Araya, Perum

Mondoroko), (Perum Mondoroko, Singosari), (Singosari, A.Yani), (A.Yani, Borobudur),

(Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Tegalgondo), (Tegalgondo,

Ngijo), (Ngijo, Sengkaling), (Sengkaling, Tlogomas), (Tlogomas, Dinoyo), (Dinoyo,

Kalpataru), (Kalpataru, Q-A)}

dengan panjang sikel =

1812+2419+5330+1060+320+1640+4146+1050+900+4199+1650+3328+1661+2290+518

5+3600+5950+2350+3079+2770+2383 = 57122

4.3 Penyelesaian Dengan Alat Bantu

Jika kita memilih Spreadsheet Matrix Form ( padaFormat visual dalam memasukkan

data), maka tampilannya akan seperti berikut.

4. Kemudian untuk menemukan solusinya, klik Solve and Analyze pada menu, lalu pilih

Solve The Problem.

5. Berikutnya akan muncul window baru. Window ini meminta kita untuk memilih cara

penyelesaian masalah. Pilih Algoritma yang diinginkan, dan klik Solve.

6. Maka akan muncul tampilan solusi, dalam bentuk tabel.

4.3.1 Algortma Nearest Neighbour Heuristik

Dengan rute

3.4.2 Algoritma Branch and Bound

Dengan rute:

3.4.3 Algoritma Cheapest Insertion Heuristik

Dengan rute

4.4 Analisa Hasil

Dari permasalahan di atas diperoleh hasil, bahwa untuk penyelesaian dengan

menggunkan:

Algoritma Nearest Neightbour Heuristik dengan alat bantu WINQSB diperoleh hasil

yang sama, yaitu dengan rute sebagai berikut:

UD. QA (Jl. Ciamis) – Sumbersari – Jl. S.Riadi – Dinoyo – Griya Shanta-- Jl. Borobudur –

Jl. A. Yani – Araya – Arjosari – Purwantoro –Jl. Dirgantara – Jl. Danau Poso – Jl. Danau

Brantan – Jl. Sentani – Kalpataru – Tlogomas –– Sengkaling – Tegalgondo – Ngijo –

Singosari – Mondoroko -- UD. QA (Jl. Ciamis).

Dengan Jarak

Algoritma Cheapest Link diperoleh hasil sebagai berikut:





Dengan Jarak

Algoritma Branch and Bound dengan alat bantu WINQSB diperoleh hasil yang sama,

yaitu dengan rute sebagai berikut:

Dengan nilai

Dimana:

1. UD. Q-A

2. Jl. B. S. Riadi.

3. Jl. Dirgantara.

4. Jl. Danau Brantan.

5. Jl. Danau Poso.

6. Jl. Danau Sentani.

7. Perum Griya Shanta.

8. Jl. Kalpataru.

9. Jl. Borobudur

10. Purwantoro

11. Jl. A. Yani

12. Perum Mondoroko

13. Araya

14. Arjosari

15. Singosari

16. Ngijo

17. Tegalgondo

18. Sengkaling

19. Tlogomas

20. Dinoyo

21. Sumbersari

Algoritma Chepast Insertion Heuristik dengan alat bantu WINQSB diperoleh hasil yang

berbeda, yaitu dengan rute cara manual diperoleh:





(Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Tegalgondo), (Tegalgondo,

Ngijo), (Ngijo, Sengkaling), (Sengkaling, Tlogomas), (Tlogomas, Dinoyo), (Dinoyo,

Kalpataru), (Kalpataru, Q-A)}


1812+2419+5330+1060+320+1640+4146+1050+900+4199+1650+3328+1661+2290+518

5+3600+5950+2350+3079+2770+2383 = 57122

Dengan alat bantu diperoleh hasil:

Brantan - danau poso – dirgantara – purwanrtoro – arjosari – araya- mondoroko –

singosari – A.yani – Borobudur – Griya Shanta – Dinoyo – QA- Kalpataru – Tegalgondo –

Ngijo – Sengkaling – Tlogomas – Sumbersari – B.S riadi – sentani – brantan.

Dengan jarak

1060+1080+4146+900+4199+1650+3328+1661+2290+2656+1953+2383+

8100+3600+5950+2350+3810+2419+5893+320 = 60798

V. KESIMPULAN

Traveling Salesman Problem (TSP) adalah permasalahan untuk mencari rute

terpendek yang dapat dilalui untuk mengunjungi beberapa kota tanpa harus mendatangi

kota yang sama lebih dari satu kali.

Dari permasalahan pendistribusian air mineral pada UD. Q-A di atas diperoleh hasil,

bahwa untuk penyelesaian dengan menggunkan Algoritma Nearest Neightbour Heuristik dan

dengan alat bantu WINQSB diperoleh hasil yang sama, yaitu dengan rute sebagai berikut:

UD. QA (Jl. Ciamis) – Sumbersari – Jl. S.Riad – Dinoyo – Griya Shanta-- Jl. Borobudur –




Dengan Jarak

Dengan aAlgoritma Cheapest Link diperoleh hasil sebagai berikut:

UD. QA (Jl. Ciamis) – Sumbersari – Jl. S.Riad – Dinoyo – Griya Shanta-- Jl. Borobudur –




Dengan Jarak

Algoritma Branch and Bound dengan alat bantu WINQSB diperoleh hasil

yang sama, yaitu dengan rute sebagai berikut:

Dengan nilai

Algoritma Chepast Insertion Heuristik dengan alat bantu WINQSB diperoleh

hasil yang berbeda, yaitu dengan rute cara manual diperoleh:





(Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Tegalgondo), (Tegalgondo, Ngijo),

(Ngijo, Sengkaling), (Sengkaling, Tlogomas), (Tlogomas, Dinoyo), (Dinoyo, Kalpataru),

(Kalpataru, Q-A)}


1812+2419+5330+1060+320+1640+4146+1050+900+4199+1650+3328+1661+2290+5185+

3600+5950+2350+3079+2770+2383 = 57122

Dengan alat bantu diperoleh hasil:

Brantan - danau poso – dirgantara – purwanrtoro – arjosari – araya- mondoroko – singosari –

A.yani – Borobudur – Griya Shanta – Dinoyo – QA- Kalpataru – Tegalgondo – Ngijo –

Sengkaling – Tlogomas – Sumbersari – B.S riadi – sentani – brantan.

Dengan jarak

1060+1080+4146+900+4199+1650+3328+1661+2290+2656+1953+2383+

8100+3600+5950+2350+3810+2419+5893+320 = 60798

Dan dari Algoritma-algoritma di atas Algoritma Cheapest Insertion Heuristik

menyelesaikan masalah paling optimum dari pada Algortma Nearest Insertion Heuristi,

Cheapest Link, dan Branch and Bound

Pengalaman Survey

Observasi pendistribusian air mineral pada UD. Q-A ini dimulai pada hari Sabtu

tanggal 11 Februari. Observasi ini kami lakukan 2 kali observasi, yaitu pada hari Sabtu

tanggal 11 februari 2012 dan pada hari Sabtu tanggal 18 februari 2012. Untuk observasi

pertama, kami mensurvei untuk mencari tahu jalan mana saja yang di lewati pada saat

pendistribusian.Untuk observasi ke dua kami mencari tahu jarak dari satu tempat ke tempat

lain, dengan batuan peta yang telah di sediakan di UD.Q-A.

Tapi dengan bantuan peta kami mengalami kesulitan, karena yang kami mencari 20

titik dan harus terhubung untuk setiap kotanya sehingga kami sama dengan mencari jarak 40

titik. Sehingga kami memetuskan menggunakan google map untuk membantu meringankan

pekerjaan kita.

Daftar Pustaka

- Aldous, Joan M, and Wilson, Robin J, (2004), Graph And Aplication An Introductory

Approach, Springer, Great Britain.

- Wahyuningsih, Sapti, (2011), Penyelesaian Optmasi di Perusahaan dengan

Pemodelan Teori Graph, Malang.

- Kurniawati, Dewi, (2012) Optimalisasi Pengiriman Surat dan Paket Pos dari PT. Pos

Probolinggo ke Wilayah-Wilayah Jalur Rantai I Menggunakan Algoritma Dalam

TSP, Malang.

- Afriani, Griselda (2012), Optimalisasi Rute Pengiriman Surat dan paket Pos dari PT.

Pos Probolinggo ke wilayah jalur 1 Menggunakan Algoritma dalam TSP, Malang.

- Fitrah, Aulia, dkk (2007), “Penerapan Algoritma Genetika Pada Persoalan Pedagang

Keliling (TSP), Malang.

- Regista, Dyah, dkk,( 2007) “Penerapan Travelling Salesman Problem (TSP) untuk

menyelesaikan Masalah Pendistribusian di PT Millenium Pharmacon Int (MPI)

cabang Malang , Malang.

tsp

Documents