METODE TRAVELING SALESMAN UNTUK

MENENTUKAN LINTASAN TERPENDEK PADA

DAERAH-DAERAH YANG TERIDENTIFIKASI

BAHAYA

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA

2010

Oleh :Aisyah Lestari1206 100 016

Dosen Pembimbing:Subchan, Ph.D

19710513 199702 1 001

AGENDA

PENDAHULUAN

TINJAUAN PUSTAKA

METODE PENELITIAN

PEMBAHASAN DAN HASIL

KESIMPULAN DAN SARAN

DAFTAR PUSTAKA

PENDAHULUANLATAR BELAKANG

RUMUSAN MASALAH

BATASAN MASALAH

TUJUAN DAN MANFAAT

Traveling Salesman Problem

Branch and bound

Nearest neighbor

Pada suatu daerahatau negara yang sedang dalamkeadaan kurangaman penentuanlintasan terpendekmenjadi hal yang cukup penting

PENDAHULUANLATAR BELAKANG

RUMUSAN MASALAH

BATASAN MASALAH

TUJUAN DAN MANFAAT

Bagaimana menentukan lintasan terpendekmenggunakan metode Traveleng Salesman

Problem (TSP) pada daerah-daerah yang diidentifikasi terdapat bahaya sehingga

dapat meminimalkan kecelakan atau halburuk yang mungkin terjadi.

Bagaimana mensimulasikanlintasan terpendeknya dengan

menggunakan software MATLAB.

1

2

PENDAHULUANLATAR BELAKANG

RUMUSAN MASALAH

BATASAN MASALAH

TUJUAN DAN MANFAAT

Daerah yang akan didatangi sudah diidentifikasi. Setiap daerah dikunjungi satu kali. Daerah yang akan dikunjungi berada di darat. Tidak ada bahaya yang diprioritaskan. Diasumsikan seluruh daerah terhubung satu sama

lain dengan jarak antara 2 daerah memiliki nilai yangsama meskipun dengan arah yang berbeda. Misaljarak daerah A ke daerah B sama dengan jarakdaerah B ke daerah A.

Simulasi dilakukan dengan menggunakan softwareMATLAB.

PENDAHULUANLATAR BELAKANG

RUMUSAN MASALAH

BATASAN MASALAH

TUJUAN DAN MANFAAT

MANFAAT :memberikan informasi tentang travelingsalesman problem dan diharapkan dapatdigunakan dalam aplikasi kehidupan sehari-hari baik oleh warga sipil maupun militer yangmemerlukan efisiensi waktu dan biaya.

TUJUAN :menentukan lintasan terpendek daridaerah-daerah berbahaya yang akandikunjungi sehingga dapatmeminimalkan bahaya yang mungkin terjadi pada daerahtersebut.

TINJAUAN PUSTAKA

TSP dikenal sebagai suatu permasalah optimasi yang bersifat klasik danNon-Deterministic Polynomial-time Complete (NPC), dimana tidak adapenyelesaian yang paling optimal selain mencoba seluruhkemungkinan penyelesaian yang ada. Permasalahan ini melibatkanseorang traveling salesman yang harus melakukan kunjungan sekalipada semua kota dalam sebuah lintasan sebelum dia kembali ke titikawal, sehingga perjalanannya dikatakan sempurna.

Definisi dari Traveling Saleman Problem yaitu diberikan n buah kotadan Cij yang merupakan jarak antara kota i dan kota j, seseorang inginmembuat suatu lintasan tertutup dengan mengunjungi setiap kotasatu kali. Tujuannya adalah memilih lintasan tertutup yang totaljaraknya paling minimum diantara pilihan dari semua kemungkinanlintasan.

Traveling Salesman Problem1

Berikut ini adalah bentuk modelnya :

dengan :

n = jumlah kota / lokasi / pelanggan yang akan dikunjungi (n tidak termasuktempat asal (base), yang diindekkan dengan i = 0).

Cij = biaya / jarak traveling dari kota i ke kota j

A = sepasang arc / edge (i,j) yang ada. Note bahwa (i,j) yang dimaksudadalah arc yang ada dari node i ke node j.

Variable :

Metode branch and bound

Langkah-langkah untuk menyelesaikan Metode Branch and Bound: Misalkan : 1. G = (V,E) adalah graf lengkap TSP. 2. |V|= n = jumlah simpul dalam graf G.

Simpul-simpul diberi nomor 1,2,…,n.3. Cij = bobot sisi (i,j).4. Perjalanan berawal dan berakhir di simpul 1.5. S adalah ruang penyelesaian, yang dalam hal ini

S = {()} S = { (1, π ,1) | π adalah permutasi (2,3,.....,n) }.6. |S|= (n-1)! = banyaknya kemungkinan penyelesaian.

Penyelesaian TSP dinyatakan sebagai X = (1, x1, x2, ..., xn – 1, 1) yang dalam hal ini xo= xn = 1 (simpul asal = simpul akhir = 1).

2

Metode nearest neighbor

Pada metode ini, pemilihan lintasan akan dimulai pada lintasan yang memiliki nilai jarak paling minimum setiap melalui kota, kemudianakan memilih kota selanjutnya yang belum dikunjungi dan memilikijarak yang paling minimum.

Langkah-langkah untuk menyelesaikan Metode Nearest Neighbor : 1. Buat peta aliran yang menggambarkan letak-letak daerah yang akan

dituju beserta jarak antar daerah. 2. Proses pengerjaan dengan melihat daerah dengan jarak terpendek.

Setiap mencapai satu daerah, algoritma ini akan memilih daerahselanjutnya yang belum dikunjungi dan memiliki jarak yang paling minimum.

3. Perhitungan nilai optimal dengan menjumlah jarak dari awal sampaiakhir perjalanan.

3

METODE PENELITIAN

1. Studi Pendahuluan

2. Pengambilan dan Pengumpulan Data

3. Penyelesaian traveling salesman problem dengan metodebranch and bound menggunakan software QS (Quantitative System)

4. Penyelesaian traveling salesman problem dengan metodenearest neighbor

5. Simulasi dengan MATLAB

6. Penarikan kesimpulan

PEMBAHASAN DAN HASIL

Data yang dikumpulkan adalah merupakan data koordinat yang diperoleh dari Google Earth serta jarak antar daerah yang akan dikunjungi. Dalam tugas akhir ini diambil 3 contoh kota yang akan dihitung lintasan terpendeknya. Dimana pada tiap kota sudahditentukan daerah-daerah yang terdapat bahaya.

Table 1

Jarak antar daerah pada kota Surabaya (km)

Keterangan :

1 = Gubeng

2 = Airlangga

3 = Kertajaya

4 = Ngagel

5 = Klampis Ngasem

6 = Gebang Putih

7 = Mulyorejo

Pengumpulan Data1

1 2 3 4 5 6 7

1 0 0.689 1.312 1.755 3.381 4.46 3.624

2 0.689 0 0.989 1.846 2.733 3.771 2.975

3 1.312 0.989 0 1.103 2.334 3.683 3.305

4 1.755 1.846 1.103 0 3.191 4.662 4.403

5 3.381 2.733 2.334 3.191 0 1.567 2.169

6 4.46 3.771 3.683 4.662 1.567 0 1.571

7 3.624 2.975 3.305 4.403 2.169 1.571 0

Table 2Jarak antar daerah pada kota Jakarta (km)

Keterangan :1 = Tanah Abang2 = Menteng3 = Pegangsaan4 = Gelora Bung Karno5 = Rawmangun6 = Tebet7 = Senayan8 = Jakarta Selatan

Table 3Jarak antar daerah pada kota Bandung (km)

Keterangan :1 = Antapani2 = Cicaheum3 = Ciroyom4 = Arcamanik5 = Kebon Jeruk6 = Cibadak7 = Binong8 = Ancol9 = Taman Sari

1 2 3 4 5 7 8 9

1 0 2.385 4.215 2.378 7.953 5.154 3.118 3.964

2 2.385 0 1.936 4.523 5.627 3.897 4.422 4.089

3 4.215 1.936 0 6.071 3.738 2.929 5.446 4.356

4 2.378 4.523 6.071 0 9.725 5.948 1.893 3.774

5 7.953 5.627 3.738 9.725 0 4.788 8.812 7.229

6 5.154 3.897 2.929 5.948 4.788 0 4.502 2.599

7 3.118 4.422 5.446 1.893 8.812 4.502 0 2.032

8 3.964 4.089 4.356 3.774 7.229 2.599 2.032 0

1 2 3 4 5 6 7 8 9

1 0 1.994 7.702 1.533 6.513 6.785 2.727 4.996 6.019

2 1.994 0 6.458 2.489 5.325 5.765 3.396 4.847 4.381

3 7.702 6.458 0 8.838 1.193 1.219 6.099 4.106 2.576

4 1.533 2.489 8.838 0 7.67 8.027 4.261 6.477 6.866

5 6.513 5.325 1.193 7.67 0 0.709 4.955 3.159 1.934

6 6.785 5.765 1.219 8.027 0.709 0 4.968 2.889 2.642

7 2.727 3.396 6.099 4.261 4.955 4.968 0 2.502 5.304

8 4.996 4.847 4.106 6.477 3.159 2.889 2.502 0 4.345

9 6.019 4.381 2.576 6.866 1.934 2.642 5.304 4.345 0

Pengolahan Data

2.1 Jalur Reguler

Yang dimaksudkan jalur reguler disini adalah jalur yang ditempuh secaraberururtan dari daerah awal (daerah nomor 1) menuju daerah selanjutnya sampai kedaerah terakhir (kembali ke daerah awal). Berdasarkan tabel 1 – 3 hasil dari perhitunganjalur reguler untuk tiap kota adalah sebagai berikut :

Kota Surabaya = 1 – 2 – 3 – 4 – 5 – 6 – 7 = 12,734 km

Kota Jakarta = 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 = 35,393 km

Kota Bandung = 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 = 43,503 km

2.2 Dengan metode branch and bound menggunakan software QS (Quantitative System)

Pengolahan jarak yang dilakukan adalah menggunakan Software QS (Quantitative System). Berikut adalah hasil yang diperoleh untuk tiap kota :

Surabaya

2

Jakarta

Bandung

2.3 Dengan metode nearest neighbor

Pengolahan jarak yang dilakukan adalah menggunakan metode Nearest Neighbor. Berikutadalah hasil yang diperoleh untuk tiap kota :

Surabaya

Dari hasil perhitungan diatas didapat lintasan terpendeknya adalah 1 – 2 – 3 – 4 – 5 – 6 – 7

– 1 dengan total jarak tempuh sebesar 12,734 km.

Jakarta

Dari hasil perhitungan diatas didapat lintasan terpendeknya adalah 1 – 4 – 7 – 8 – 6 – 3 – 2 – 5 – 1 dengan total jarak tempuh sebesar 27,347 km.

S T J S T J S T J S T J S T J S T J S T J

1 2 0.689 2 3 0.989 3 4 1.103 4 5 3.191 5 6 1.567 6 7 1.571 7 1 3.624

3 1.312 4 1.846 5 2.334 6 4.662 7 2.169

4 1.755 5 2.733 6 3.683 7 4.403

5 3.381 6 3.771 7 3.305

6 4.46 7 2.975

7 3.624

S T J S T J S T J S T J S T J S T J S T J S T J

1 2 2.385 4 2 4.523 7 2 4.422 8 2 4.089 6 2 3.897 3 2 1.936 2 5 5.627 5 1 7.953

3 4.215 3 6.071 3 5.446 3 4.356 3 2.929 5 3.738

4 2.378 5 9.725 5 8.812 5 7.229 5 4.788

5 7.953 6 5.948 6 4.502 6 2.599

6 5.154 7 1.893 8 2.032

7 3.118 8 3.774

8 3.964

Bandung

Dari hasil perhitungan diatas didapat lintasan terpendeknya adalah 1 – 4 – 2 – 7 – 8 – 6 – 5 – 3 – 9 – 1 dengan total jarak tempuh 23,306 km.

Keterangan :

S = start (mulai perjalanan)

T = tujuan

J = jarak antara masing-masing daerah

S T J S T J S T J S T J S T J S T J S T J S T J S T J

1 2 1.994 4 2 2.489 2 3 6.458 7 3 6.099 8 3 4.106 6 3 1.219 5 3 1.193 3 9 2.576 9 1 6.019

3 7.702 3 8.838 5 5.325 5 4.955 5 3.159 5 0.709 9 1.934

4 1.533 5 7.67 6 5.765 6 4.968 6 2.889 9 2.642

5 6.513 6 8.027 7 3.396 8 2.502 9 4.345

6 6.785 7 4.261 8 4.847 9 5.304

7 2.727 8 6.477 9 4.381

8 4.996 9 6.866

9 6.019

Rekapitulasi hasil perhitungan jalur yang dilalui

Dari hasil perhitungan traveling salesman dengan metode branch and bound danmetode nearest neighbor pada pembahasan diatas dapat dibuat tabelrekapitulasinya agar dapat dilihat perbandingannya.

Tabel Rekapitulasi Hasil Perhitungan Jalur yang Dilalui

Tabel Pesentase Efisiensi Penghematan Jarak

3

Kota

Perhitungan jalur (km) Penghematan jarak (km)

RegulerBranch and

bound

Nearest

neighborReguler - BB Reguler - NN

Surabaya 12,734 11,994 12,734 0,740 0,000

Jakarta 35,393 21,749 27,347 13,644 8,046

Bandung 43,503 20,867 23,306 22,636 20,197

Kota Branch and bound Nearest neighbor

Surabaya 5,811 % 0 %

Jakarta 38,549 % 22,733 %

Bandung 52,033 % 46,426 %

Simulasi dengan MATLAB

Setelah dilakukan perhitungan dengan metode branch and bound menggunakansoftware QS (Quantitative System) dan metode nearest neighbor, pada tahap inidilakukan simulasi dengan menggunakan software MATLAB 7.4 sehingga dapatdiketahui gambar lintasan terpendeknya. Form antar muka simulasi dibangun olehGraphic User Interface (GUI) yang sudah tersedia dalam perangkat lunak MATLAB7.4.

Gambar form awal simulasi lintasan terpendek

4

Hasil simulasi untuk kota Surabaya

Hasil simulasi untuk kota Jakarta

Hasil simulasi untuk kota Bandung

KESIMPULAN

Kesimpulan yang diperoleh dari hasil dan pembahasan adalah :

1. Jarak terpendek yang diperoleh setelah melakukan perhitungandengan metode branch and bound dan metode nearest neighboruntuk masing-masing lintasan adalah :

2. Penghematan jarak yang diperoleh dari masing-masing metodeadalah :

3. Metode branch and bound lebih baik dalam menyelesaikanpermasalahan traveling salesman dibandingkan dengan metodenearest neighbor.

Kota Metode branch and bound Metode nearest neighbor

Surabaya 11,994 km 12,734 km

Jakarta 21,749 km 27,347 km

Bandung 20,867 km 23,306 km

KotaPenghematan jarak (km)

Reguler - BB Reguler - NN

Surabaya 0,740 0,000

Jakarta 13,644 8,046

Bandung 22,636 20,197

SARAN

Pada Tugas Akhir ini metode yang digunakan untukpenyelesaian traveling salesman problem adalahmetode branch and bound dan metode nearest neighbor. Dimana kemungkinan hasil yang didapatkurang optimal. Diharapkan pada penelitian selanjutnyadapat menggunakan metode yang lebih optimal untukmenyelesaikan traveling salesman problem.

DAFTAR PUSTAKA

Amin, Rahma Aulia. Dkk, 2006. Traveling Salesman Problem, Bandung: Institut Teknologi Bandung. <www.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik30.pdf >

Biggs, N. L., dkk. 1976. Graph Theory 1736-1936. New York : Clarendon Press, Oxford University.

Munir, Rinaldi. 2006. Bahan Kuliah: Algoritma Branch and Bound, Bandung: Institut Teknologi Bandung.

Sarker, A. R., dan Newton C. 2007. Optimization Modeling: A Practical Aproach. Taylor & Francis Group, LLC.

Wahyudi, Agus. 2002. Studi Komparatif Antara Algoritma Genetika danSimulated Annealing untuk Menyelesaikan Traveling Salesman Problem. Tugas Akhir, Matematika, Institut Teknologi Sepuluh Nopember, Surabaya.

Zuhdi, Mohd. 2009. Kuliah2: Sistem Koordinat. <www.angelfire.com/mo/zuhdi/Kuliah2.pdf>

www.wikipedia.org/wiki/Google_earth diakses 13 Mei 2010 pukul 14.23 WIBwww.divshare.com/download/3088474-054 diakses 13 Mei 2010 pukul 13.02

WIB