METODE EKSAK DAN METODE PENDEKATAN UNTUK PENYELESAIAN TRAVELING SALESMAN PROBLEM SIMETRIS

GISELA DELICIA Y, Dr. Solikhatun, M.Si. ; Dr. Irwan Endrayanto, M.Sc.

2017 | Skripsi | S1 MATEMATIKA

Pada skripsi ini akan dibahas mengenai Traveling Salesman Problem (TSP). TSP adalah masalah pencarian rute perjalanan yang akan dilalui oleh seorang salesman yang ditugaskan untuk mengunjungi beberapa kota tujuan dengan memperhatikan beberapa kendala, yaitu setiap kota tujuan harus dikunjungi dan tidak boleh kembali ke kota yang sudah dikunjungi, artinya kota tujuan hanya boleh dikunjungi satu kali saja, salesman tersebut harus mengawali dan mengakhiri perjalanannya pada sebuah kota yang sama. Tujuan dari TSP adalah meminimumkan biaya perjalanan yang akan ditempuh oleh salesman dengan kendala-kendala tersebut. Pada skripsi ini TSP akan dimodelkan menggunakan program linear, baik menggunakan masalah primal maupun masalah dualnya. Kemudian dilakukan perbandingan hasil dengan menggunakan dua algoritma yang termasuk di dalam metode pendekatan, yaitu algoritma Nearest-Neighbor dan algoritma geometris.

In this paper, we will explain about Traveling Salesman Problem (TSP). TSP is a problem of searching a route that should be traveled by a salesman that was assigned to visit several destination cities with some constraints, i.e every destination city must be visited and the traveler is not allowed to return to the visited city, meaning the destination city may only be visited once, and the salesman must start and end his journey at the same city. The purpose of TSP is to minimize travel costs which will be pursued by the salesman under the constraints. In this paper, TSP will be modeled using linear programming, using both primal and dual problems. Then comparing the result using two algorithms include the approach method, the Nearest-Neighbor algorithm and geometric algorithm.

Kata Kunci : traveling salesman problem, linear programming, nearest-neighbor algorithm, geometric algorithm