Pengertian Travelling salesman problem (TSP)

-

Pengertian Travelling Salesman Problem (TSP)

TSP


Travelling Salesman Problem (TSP) adalah salah satu permasalahan klasik dalam bidang ilmu komputer dan optimisasi kombinatorial. Dalam TSP, seorang salesman harus mengunjungi sejumlah kota yang berbeda tepat satu kali dan kembali ke kota asalnya, sehingga total jarak yang ditempuhnya adalah minimum.

Secara umum, TSP dapat dinyatakan sebagai berikut: 

Diberikan sebuah himpunan kota dan jarak antara setiap pasangan kota, tujuan TSP adalah menemukan tur yang melintasi setiap kota tepat satu kali dan kembali ke kota awal, dengan total jarak yang ditempuh adalah minimum.

Karakteristik permasalahan Travelling Salesman Problem

Berikut ini karakteristik atau ciri-ciri dari permasalahan TSP:

  1. Perjalanan berawal dan berakhir dari dan ke kota awal.
  2. Ada sejumlah kota yang semuanya harus dikunjungi tepat satu kali.
  3. Perjalanan tidak boleh kembali ke kota awal sebelum semua kota tujuan dikunjungi
  4. Tujuan dari permasalahan ini adalah meminimalkan total jarak yang ditempuh salesman dengan mengatur urutan kota yang harus dikunjunggi.

Contoh Permasalahan Travelling Salesman Problem

Berikut ini beberapa contoh Permasalahan Travelling Salesman Problem: 

  1. Pencarian rute bus sekolah untuk mengantarkan siswa.
  2. Petugas pos mengambil surat di kotak pos yang tersebar pada beberapa titik lokasi.
  3. Petugas koran yang mengantarkan koran ke beberapa titik lokasi pelanggan.

TSP termasuk ke dalam kategori masalah NP-sulit, yang berarti tidak ada algoritma yang dapat menyelesaikannya dengan efisien dalam semua kasus, terutama ketika jumlah kota sangat besar. Namun, ada berbagai pendekatan yang dapat digunakan untuk mendekati solusi optimal atau mendapatkan solusi yang cukup baik, berikut ini beberapa teknik penyelesaian masalah TSP:

1. Algoritma Eksak: Algoritma yang mencoba untuk menemukan solusi optimal dengan menghitung semua kemungkinan tur yang mungkin dan memilih yang terpendek. 

Contoh dari algoritma eksak adalah algoritma percabangan dan batasan (Branch and Bound).

2. Algoritma Pendekatan: Algoritma yang mencoba untuk mendekati solusi optimal tanpa menjamin solusi terbaik. 

Contoh algoritma pendekatan termasuk, algoritma Greedy, Simulated Annealing, Genetic Algorithm, dan Ant Colony Optimization.

Baca Juga: Algoritma Particle Swarm Optimization pada TSP

3. Heuristik: Pendekatan yang menggunakan aturan atau strategi sederhana untuk mencapai solusi yang cukup baik dalam waktu yang singkat.

Contoh heuristik untuk TSP termasuk Nearest Neighbor, Insertion, dan 2-Opt.

Meskipun TSP merupakan masalah yang sulit, namun penting dalam berbagai bidang seperti logistik, perencanaan rute, pemrosesan paralel, dan optimisasi jaringan. Solusi yang baik untuk TSP dapat memberikan efisiensi yang signifikan dalam perencanaan dan pengaturan rute, yang memiliki dampak penting dalam dunia nyata.


Demikian artikel terkait Travelling Salesman Problem, semoga artikel ini bermafaat. Terima kasih telah berkunjung di faqirilmu.com

Komentar

Posting Komentar

Postingan populer dari blog ini

Cara Membaca nilai R Tabel dan Download R Tabel (Tabel R)

-
Gambar
Pengertian R Tabel Apa yang dimaksud R Tabel? R tabel merupakan sebuah tabel angka yang biasa dipakai untuk melakukan uji validitas suatu instrumen penelitian.  Fungsi R Tabel Berdasarkan definisi di atas, maka dapat diambil kesimpulan bahwa r tabel ini mempunyai fungsi untuk melakukan suatu pengujian terhadap instrumen penelitian agar mengetahui apakah instumen penelitian tersebut valid atau tidak.  Dibawah ini merupakan R tabel. Gambar Tabel R ( R Tabel) Mau mendownload R tabel? Silahkan melalui link dibawah ini.  DOWNLOAD R Tabel Cara Membaca Nilai r Tabel dalam Uji Validitas Pearson Ada beberapa cara dalam mengambil keputusan uji validitas. Cara yang pertama dengan menggunakan r tabel dan cara kedua dengan menggunakan nilai signifikansi . Berikut ini pedoman pengambilan keputusan uji validitas SPSS: Membandingkan Nilai r Hitung dengan Nilai r Tabel Jika nilai r hitung > r tabel, maka item pertanyaan kuesioner valid Jika nilai r hitung < r tabel, maka item pertanyaan kuesione
Read more »

Perbedaan Scale, Nominal dan Ordinal pada Measure di SPSS

-
Gambar
Perbedaan Scale, Nominal dan Ordinal pada Measure di SPSS      Measure merupakan salah satu kolom yang berada di variable view IBM SPSS. Kolom measure harus ditetapkan terlebih dahulu sebelum melakukan analisis data lebih lanjut. Terdapat 3 tipe variabel pada kolom measure SPSS yaitu scale, nominal dan ordinal . Ketiga variabel tersebut memberikan jenis nilai serta informasi analisis yang berbeda. Berikut ini pengertian dan perbedaan scale, nominal dan ordinal pada SPSS.      Penentuan measure merupakan hal dasar yang sangat penting untuk diketahui saat bekerja menggunakan SPSS. Misalnya kita tidak boleh membuat variabel nominal untuk melakukan perhitungan nilai rata-rata dan standar deviasi.  Pilihan untuk mengubah tipe variabel suatu variabel terdapat pada lembar kerja Variabel View SPSS. Gambar dibawah ini merupakan ilustrasinya. A.  Variabel Nominal pada SPSS      Variabel nominal merupakan tipe variabel yang digunakan hanya sebatas memberi label pembeda pada suatu data. Variabel
Read more »

Analisis Crosstab dengan SPSS [Uji Chi-Square dan Correlation]

-
Gambar
Cara Analisis Crosstab Menggunakan SPSS  Pada artikel ini, Kita akan belajar analisis crosstabs menggunakan SPSS. Silahkan baca artikel ini sampai selesai ya, agar paham apa itu analisis crosstabs. Pada SPSS, analisis crosstab merupakan bagian dari statistik deskriptif . Lalu apa kegunaan analisis crosstabs? Analisis crosstab merupakan alat analisis untuk mendeskripsikan data dalam bentuk kolom dan baris. Selain itu digunakan untuk memeriksa hubungan antar variabel kategori (nominal atau ordinal). Analisis crosstab ini dibagi menjadi 2 bagian: Analisis Crosstab – Chi Square Analisis Crosstab – Correlations Lalu apa perbedaannya? Ok, kita langsung ke yang pertama, analisis Crosstab – Chi Square A. Analisis Crosstab Chi-Square Analisis Crosstab Chi-Square ini merupakan teknik analisis untuk melihat hubungan antar variabel data nominal. Syarat uji chi-squre ini variabel yang akan kita uji harus data nominal. Langsung aja ke contoh kasus, Suatu perusahaan mengamati apakah pelayanan karya
Read more »

Pengertian Data View dan Variabel View SPSS serta Fungsinya

-
Gambar
Pengertian Data View dan Variabel View serta Penggunaanya pada SPSS      IBM SPSS mempunyai dua lingkungan kerja yaitu data view dan variabel view. Untuk pembahasan yang pertama kita ke Data View dulu, setelah itu baru ke Variabel View. A.  Data View      Data View merupakan tampilan lembar kerja SPSS sebagai tempat kita memasukkan data hasil pengamatan. Data View pada SPSS menampilkan setiap baris sebagai suatu kasus (case) dan setiap kolom merepresentasikan suatu variabel. Berikut ini penjelasan mengenai variabel dan kasus yang terdapat pada data view. 1.  Kasus (case)      Kasus (case) pada SPSS merepresentasikan suatu hasil pengamatan terhadap suatu objek, dapat berupa pengamatan berdasarkan observasi atau eksperimen. Banyaknya kasus pada Data View dapat dilihat pada bagian baris, sedangkan untuk banyaknya variabel dapat dilihat pada bagian kolom. 2.  Variabel      Variabel merupakan suatu karakteristik yang akan diteliti atau apa yang akan menjadi titik perhatian suatu penelit
Read more »

Cara Analisis Regresi Linear Berganda dengan SPSS

-
Gambar
Analisis Regresi Linear Berganda dengan SPSS Pengertian Analisis Regresi Linear Berganda Analisis regresi linear berganda adalah analisis yang digunakan untuk mengetahui pengaruh dua atau lebih variabel independen terhadap variabel dependen . Selain itu analisis regresi linear berganda juga digunakan untuk meramalkan suatu variabel dependen berdasarkan beberapa variabel independen. Regresi linear berganda disebut juga dengan regresi berganda . Pada regresi linear, variabel independen disimbolkan dengan X dan variabel dependen disimbolkan dengan Y.  Perbedaan regresi linear berganda dengan regresi linear sederhana  Apakah Anda tahu perbedaan regresi linear berganda dengan regresi linear sederhana ?  Perbedaan regresi linear berganda dengan regresi linear sederhana terletak pada jumlah variabel independen. Apabila pada regresi linear sederhana hanya terdapat satu variabel independen , sedangkan pada regresi linear berganda terdapat dua atau lebih variabel independen yang mempengaruhi
Read more »