ANALISA KEBUTUHAN WAKTU PADA PROSES PENYELESAIAN TRAVELING SALESMAN PROBLEM

Abstract

Permasalahan traveling salesman problem (TSP) adalah seorang penjual yang harus mengunjungi
semua kota sebanyak satu sekali saja dimana dia harus mengawali dan mengakhiri perjalanan di kota yang
sama. Tujuan TSP adalah menentukan lintasan atau rute dengan total jarak atau biaya yang paling minimum.
Penelitian ini bertujuan untuk mengetahui kebutuhan waktu pada proses penyelesaian TSP menggunakan teknik
pencarian buta dan pencarian terbimbing.
Metode yang digunakan adalah pencarian melebar pertama (breadth-first search), pencarian mendalam
pertama (depth-first search), pembangkitan dan pengujian (generate and test), dan pencarian terbaik pertama
(best first search). Terdapat tiga buah ilustrasi kasus TSP yang digunakan yaitu TSP1 memiliki 4 buah kota
dengan 6 jalan penghubung, TSP2 memiliki 5 buah kota dengan 10 jalan penghubung, dan TSP3 memiliki 8
buah kota dengan 28 jalan penghubung. Dari hasil pengujian diperoleh pencarian mendalam pertama (depthfirst
search) membutuhkan waktu paling sedikit (tercepat) apabila dibandingkan dengan metode pencarian yang
lain. Pada pencarian terbaik pertama (best first search) membutuhkan waktu paling banyak (terlama) diantara
metode pencarian yang lain.