TSP [PDF]

Citation preview

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



perkuliahan bidang keahlian yang sesuai.



ketrampilan



yang



berkaitan



dengan



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 | V (G) | dan banyaknya sisi pada graph G dinotasikan dengan |E(G)|



. Dari Gambar diatas dapat dilihat bahwa V (G)  {A, B, C, D, E, } dan E(G)={e1, e2, e3, e4, e5, e6, e7, e8, e9, e10} sehingga | V (G) | 5 dan | E (G) | 10 .



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, koefisien penguapan lintasan antara waktu t dan t+n, nilai



dengan



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 mJ i 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 v 1 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 [a n1]=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 rumahrumah, 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). UD.Q-A



Langkah 2: Dari UD.Q-A (Jl. Ciamis) pilih titik yang terhubung langsung yang memiliki bobot terkecil pilih Sumbersari dengan bobot 1812 m.



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







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 Hapus baris 1 kolom ke 4 dari data awal set



=M



Solusinya adalah: =



Dengan nilai



dengan Jadi 



Titik 5 Hapus baris 1 kolom ke 5 dari data awal set



=M



Solusinya adalah: =



Dengan nilai



8 dengan Jadi 



8 8=73412



Titik 6 Hapus baris 1 kolom ke 6 dari data awal set



=M



Solusinya adalah: =



Dengan nilai



dengan Jadi 



=70016



Titik 7 Hapus baris 1 kolom ke 7 dari data awal set



=M



Solusinya adalah: =



Dengan nilai



dengan Jadi 



= 68186



Titik 8 Hapus baris 1 kolom ke 8 dari data awal set



=M



Solusinya adalah: =



Dengan nilai



dengan



Jadi 



= 65203



Titik 9 Hapus baris 1 kolom ke 9 dari data awal set



=M



Solusinya adalah: =



Dengan nilai



dengan Jadi 



= 69833



Titik 10 Hapus baris 1 kolom ke 10 dari data awal set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



= 69552



Titik 11 Hapus baris 1 kolom ke 11 dari data awal set Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 12



= 73153



=M



Hapus baris 1 kolom ke 12 dari data awal set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=70860



Titik 13 Hapus baris 1 kolom ke 13 dari data awal set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=73062



Titik 14 Hapus baris 1 kolom ke 14 dari data awal set Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 16



=79702



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=82758



Titik 17 Hapus baris 1 kolom ke 17 dari data awal set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=71149



Titik 18 Hapus baris 1 kolom ke 18 dari data awal set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=75727



Titik 19 Hapus baris 1 kolom ke 19 dari data awal set Solusinya adalah:



=M



Dengan nilai



dengan Jadi 



=69240



Titik 20 Hapus baris 1 kolom ke 20 dari data awal set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=77213



Titik 21 Hapus baris 1 kolom ke 21 dari data awal set



=M



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 C 21 = 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 : Hapus baris 8 kolom ke 4 dari data baru dan set C41 = M solusinya adalah :



Dengan nilai :



dan f=59422 Jadi 



Titik 25 : Hapus baris 8 kolom ke 5 dari data baru dan set C51 = M solusinya adalah :



Dengan nilai :



dan f=56511 Jadi, 



Titik 26 : Hapus baris 8 kolom ke 6 dari data baru dan set C61 = M solusinya adalah :



> fu2



Dengan nilai :



dan f=54018 Jadi, 



Titik 27 : Hapus baris 8 kolom ke 7 dari data baru dan set C71 = M solusinya adalah :



Dengan nilai :



dan f=60426 Jadi, 



Titik 28 : Hapus baris 8 kolom ke 9 dari data baru dan set C91 = M solusinya adalah :



Dengan nilai :



dan f=61517 Jadi, 



Titik 29 : Hapus baris 8 kolom ke 10 dari data baru dan set C101 = M solusinya adalah :



Dengan nilai :



dan f=63333 Jadi, 



Titik 30 : Hapus baris 8 kolom ke 11 dari data baru dan set C111 = M solusinya adalah :



Dengan nilai :



dan f=61928 Jadi 



Titik 31 : Hapus baris 8 kolom ke 11 dari data baru dan set C121 = M solusinya adalah :



Dengan nilai :



dan f=56752 Jadi, 



Titik 32 : Hapus baris 8 kolom ke 13 dari data baru dan set C131 = M solusinya adalah :



Dengan nilai :



dan f=63842 Jadi, 



Titik 33 : Hapus baris 8 kolom ke 14 dari data baru dan set C141 = M solusinya adalah :



Dengan nilai :



dan f=65994 Jadi 



Titik 34 : Hapus baris 8 kolom ke 15 dari data baru dan set C151 = M solusinya adalah :



Dengan nilai :



dan f=58565 Jadi, 



Titik 35 : Hapus baris 8 kolom ke 16 dari data baru dan set C161 = M solusinya adalah :



Dengan hasil :



dan f=64557 Jadi 



Titik 36 Hapus baris 8 kolom ke 17 dari data awal set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=60798



Titik 37 : Hapus baris 8 kolom ke 18 dari data baru dan set C181 = M solusinya adalah :



Dengan nilai :



dan f=64828 Jadi 



Titik 38 Hapus baris 8 kolom ke 19 dari data awal set (lihat tabel) Solusinya adalah:



=M



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 Hapus baris 8 kolom ke 21 dari data awal set



=M



(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 Hapus baris 21 kolom ke 3 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=73596



Titik 43 Hapus baris 21 kolom ke 4 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=74000



Titik 44 Hapus baris 21 kolom ke 5 dari data baru (dari titik 21) set Solusinya adalah:



=M



Dengan nilai



dengan Jadi 



=67886



Titik 45 Hapus baris 21 kolom ke 6 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=67665



Titik 46 Hapus baris 21 kolom ke 7 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan



Jadi 



=70284



Titik 47 Hapus baris 21 kolom ke 8dari data baru (dari titik 21) set Solusinya adalah:



Dengan nilai



=M



dengan



Jadi 



=66914



Titik 48 Hapus baris 21 kolom ke 9 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=71240



Titik 49 Hapus baris 21 kolom ke 10 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



=73469



Titik 50 Hapus baris 21 kolom ke 11 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



+1050+1650+7746+3600+4150+2350+3822+3710



=60269 dengan



Jadi 



Titik 51 Hapus baris 21 kolom ke 12 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 52 Hapus baris 21 kolom ke 13 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 53 Hapus baris 21 kolom ke 14 dari data baru (dari titik 21) set Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 54



=M



Hapus baris 21 kolom ke 15 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi







Titik 55 Hapus baris 21 kolom ke 16 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 56 Hapus baris 21 kolom ke 17 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 57 Hapus baris 21 kolom ke 18 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 58 Hapus baris 21 kolom ke 19 dari data baru (dari titik 21) set



=M



Solusinya adalah:



Dengan nilai



dengan Jadi 



Titik 59 Hapus baris 21 kolom ke 20 dari data baru (dari titik 21) set



=M



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) C(Sumbersari)(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) C(Sumbersari)(B.S Riadi) = 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) Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo, Q-A)}



Iterasi 5



1. k = A.Yani S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, 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) – C(Sumbersari)(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) – C(GriyaShanta)(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) Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, 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) – C(Sumbersari)(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) – C(Borobudur)(GriyaShanta) = 2171+4439-2290 = 4320 Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Araya) + C(Araya)(Dinoyo) – C(GriyaShanta)(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)



Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, Araya), (Araya, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo, Q-A)}



Iterasi 7



1. k = Arjosari S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, 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) – C(Sumbersari)(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) – C(Borobudur)(GriyaShanta) = 2371+3739-2290 = 3820 Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Arjosari) + C(Arjosari)(Dinoyo) – C(GriyaShanta)(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) Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, 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 S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, 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) – C(Sumbersari)(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) – C(A.Yani)(Borobudur) = 3499+3117-1661 = 4955 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Purwantoro) + C(Purwantoro)(GriyaShanta) – C(Borobudur)(GriyaShanta) = 3117+8206-2290 = 9033 Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Purwantoro) + C(Purwantoro)(Dinoyo) – C(GriyaShanta)(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) Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, Purwantoro) (Purwantoro, Arjosari), (Arjosari, Araya), (Araya, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo, Q-A)}



Iterasi 9 1. k = Dirgantara S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, 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) – C(Sumbersari)(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) – C(A.Yani)(Borobudur) = 7340+4418-1661 = 10097 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Dirgantara) + C(Dirgantara)(GriyaShanta) – C(Borobudur)(GriyaShanta) = 4418+8704-2290 = 10832 Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Dirgantara) + C(Dirgantara)(Dinoyo) – C(GriyaShanta)(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) Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, 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 S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, 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) – C(Sumbersari)(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) – C(Purwantoro)(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) –



C(A.Yani)(Borobudur) = 7840+7040-1661 = 13219 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(DanauPoso) + C(DanauPoso)(GriyaShanta) – C(Borobudur)(GriyaShanta) = 7040+9208-2290 = 13958 Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(DanauPoso) + C(DanauPoso)(Dinoyo) C(GriyaShanta)(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) Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, 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 S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, 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) – C(Sumbersari)(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) – C(Dirgantara)(Purwantoro) = 1590+5154-4146 = 2598 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(DanauBrantan) + C(DanauBrantan)(Arjosarai) – C(Purwantoro)(Arjosari) = 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) – C(A.Yani)(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) – C(GriyaShanta)(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) Sehingga terbentuk sikel C = {(Q-A, Sumbersari), (Sumbersari, B.S Riadi), (B.S Riadi, Danau Poso), (Danau Poso, Danau Brantan), (Danau Brantan, 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 12 1. k = Danau Sentani S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau 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) – C(Sumbersari)(B.S Riadi) = 9811+5893-2419 = 13285 Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(DanauSentani) + C(DanauSentani)(DanauPoso) – C(B.S Riadi)(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) – C(Dirgantara)(Purwantoro) = 1640+5379-4146 = 2873 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(DanauSentani) + C(DanauSentani)(Arjosari) – C(Purwantoro)(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) – C(A.Yani)(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) – C(GriyaShanta)(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) 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, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo, Q-A)}



Iterasi 13



1. k = Kalpataru S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau 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) – C(Sumbersari)(B.S Riadi) = 4117+4560-2419 = 6258 Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Kalpataru) + C(Kalpataru)(DanauPoso) – C(B.S Riadi)(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) – C(Dirgantara)(Purwantoro) = 4450+6150-4146 = 6454 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Kalpataru) + C(Kalpataru)(Arjosari) – C(Purwantoro)(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) – C(A.Yani)(Borobudur) = 3600+2950-1661 = 4889 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Kalpataru) + C(Kalpataru)(GriyaShanta) – C(Borobudur)(GriyaShanta) = 2950+3299-2290 = 3959 Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Kalpataru) + C(Kalpataru)(Dinoyo) – C(GriyaShanta)(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) 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, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Dinoyo), (Dinoyo, Kalpataru), (Kalpataru, Q-A)}



Iterasi 14



1. k = Tlogomas S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau 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) – C(Sumbersari)(B.S Riadi) =3810+5831-2419 = 7222 Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Tlogomas) + C(Tlogomas)(DanauPoso) – C(B.S Riadi)(DanauPoso) = 5831+9715-5330 = 10216 Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Tlogomas) + C(Tlogomas)(DanauBrantan) – C(DanauPoso)(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) – C(DanauSentani)(Dirgantara) = 10448+9215-1640 = 18023 Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Tlogomas) + C(Tlogomas)(Purwantoro) – C(Dirgantara)(Purwantoro) = 9215+9036-4146 = 14105 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Tlogomas) + C(Tlogomas)(Arjosari) – C(Purwantoro)(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) – C(A.Yani)(Borobudur) = 6600+5750-1661 = 10689 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Tlogomas) + C(Tlogomas)(GriyaShanta) – C(Borobudur)(GriyaShanta) = 5750+3822-2290 = 7282 Sisi (Griya Shanta, Dinoyo) = C(GriyaShanta)(Tlogomas) + C(Tlogomas)(Dinoyo) – C(GriyaShanta)(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) 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, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Tlogomas), (Tlogomas, Dinoyo), (Dinoyo, Kalpataru), (Kalpataru, Q-A)} Iterasi 15 1. k = Sengkaling S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau 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) – C(Sumbersari)(B.S Riadi) = 6260+8281-2419 = 12122 Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Sengkaling) + C(Sengkaling)(DanauPoso) – C(B.S Riadi)(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) – C(DanauSentani)(Dirgantara) = 12898+11665-1640 = 22923 Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Sengkaling) + C(Sengkaling)(Purwantoro) – C(Dirgantara)(Purwantoro) = 11665+11489-4146 = 19008 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Sengkaling) + C(Sengkaling)(Arjosari) – C(Purwantoro)(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) – C(A.Yani)(Borobudur) = 9050+8200-1661 = 15589 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Sengkaling) + C(Sengkaling)(GriyaShanta) – C(Borobudur)(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) – C(Dinoyo)(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) 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, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya Shanta, Sengkaling), (Sengkaling, Tlogomas), (Tlogomas, Dinoyo), (Dinoyo, Kalpataru), (Kalpataru, Q-A)}



Iterasi 16



1. k = Tegalgondo S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau 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) –



C(Sumbersari)(B.S Riadi) = 7804+9798-2419 = 15183 Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Tegalgondo) + C(Tegalgondo)(DanauPoso) – C(B.S Riadi)(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) – C(Dirgantara)(Purwantoro) = 13810+9329-4146 = 18993 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Tegalgondo) + C(Tegalgondo)(Arjosari) – C(Purwantoro)(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) –



C(A.Yani)(Borobudur) = 8120+7270-1661 =13729 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Tegalgondo) + C(Tegalgondo)(GriyaShanta) – C(Borobudur)(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) – C(Dinoyo)(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) 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, A.Yani), (A.Yani, Borobudur), (Borobudur, Perum Griya Shanta), (Perum Griya



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



Iterasi 17



1. k = Ngijo S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau 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) – C(Sumbersari)(B.S Riadi) = 9150+14241-2419 = 20972 Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Ngijo) + C(Ngijo)(DanauPoso) – C(B.S Riadi)(DanauPoso) = 14241+17370-5330 = 26281 Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Ngijo) + C(Ngijo)(DanauBrantan) – C(DanauPoso)(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) – C(DanauSentani)(Dirgantara) = 18103+17670-1640 = 34133 Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Ngijo) + C(Ngijo)(Purwantoro) –



C(Dirgantara)(Purwantoro) = 17670+4587-4146 = 18111 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Ngijo) + C(Ngijo)(Arjosari) – C(Purwantoro)(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) – C(Borobudur)(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) – C(Sengkaling)(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) 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, 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 18



1. k = Singosari S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau 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) – C(Sumbersari)(B.S Riadi) = 10265+7928-2419 = 15774 Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Singosari) + C(Singosari)(DanauPoso) – C(B.S Riadi)(DanauPoso)



= 7928+9638-5330 = 12236 Sisi (Danau Poso, Danau Brantan) = C(DanauPoso)(Singosari) + C(Singosari)(DanauBrantan) – C(DanauPoso)(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) – C(DanauSentani)(Dirgantara) = 10371+9138-1640 = 17869 Sisi (Dirgantara, Purwantoro) = C(Dirgantara)(Singosari) + C(Singosari)(Purwantoro) – C(Dirgantara)(Purwantoro) = 9138+5307-4146 = 10299 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Singosari) + C(Singosari)(Arjosari) – C(Purwantoro)(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) – C(A.Yani)(Borobudur) = 3328+3719-1661 = 5386 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Singosari) + C(Singosari)(GriyaShanta) –



C(Borobudur)(GriyaShanta) = 3719+5987-2290 =7416 Sisi (Griya Shanta, Tegalgondo) = C(GriyaShanta)(Singosari) + C(Singosari)(Tegalgondo) – C(GriyaShanta)(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) – C(Sengkaling)(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) – C(Dinoyo)(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, Danau Poso), (Danau Poso, Danau Brantan), (Danau Brantan, Danau Sentani), (Danau



Sentani, Dirgantara), (Dirgantara, Purwantoro) (Purwantoro, Arjosari), (Arjosari, Araya), (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 S = {Q-A, Sumbersari, B.S Riadi, Dinoyo, Perumahan Griya Shanta, Borobudur, A.Yani, Araya, Arjosari, Purwantoro, Dirgantara, Danau Poso, Danau 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) – C(Sumbersari)(B.S Riadi) = 11915+10270-2419 = 19766 Sisi (B.S Riadi, Danau Poso) = C(B.S Riadi)(Mondoroko) + C(Mondoroko)(DanauPoso) – C(B.S Riadi)(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) – C(Dirgantara)(Purwantoro) = 11480+7639-4146 = 14973 Sisi (Purwantoro, Arjosari) = C(Purwantoro)(Mondoroko) + C(Mondoroko)(Arjosari) – C(Purwantoro)(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) – C(A.Yani)(Borobudur) = 5670+6061-1661 = 10070 Sisi (Borobudur, Griya Shanta) = C(Borobudur)(Mondoroko) + C(Mondoroko)(GriyaShanta) – C(Borobudur)(GriyaShanta) = 6061+8329-2290 = 12100 Sisi (Griya Shanta, Tegalgondo) = C(GriyaShanta)(Mondoroko) + C(Mondoroko)(Tegalgondo) – C(GriyaShanta)(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) – C(Sengkaling)(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) – C(Dinoyo)(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: 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







Algoritma Branch and Bound dengan alat bantu WINQSB diperoleh hasil yang sama, yaitu dengan rute sebagai berikut:



Dengan nilai



Dimana: 1.



UD. Q-A



11. Jl. A. Yani



2.



Jl. B. S. Riadi.



12. Perum Mondoroko



3.



Jl. Dirgantara.



13. Araya



4.



Jl. Danau Brantan.



5.



Jl. Danau Poso.



6.



Jl. Danau Sentani.



14. Arjosari



7.



Perum Griya Shanta.



15. Singosari



8.



Jl. Kalpataru.



16. Ngijo



9.



Jl. Borobudur



17. Tegalgondo



10. Purwantoro



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: 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



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 – 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



Dengan aAlgoritma Cheapest Link diperoleh hasil sebagai berikut: 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



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: 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+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.