PENYELESAIAN GRAPHICAL TRAVELING SALESMAN PROBLEM (GTSP)

Cahya Rustamaji, Heru (2000) PENYELESAIAN GRAPHICAL TRAVELING SALESMAN PROBLEM (GTSP). Masters thesis, UPN "VETERAN" YOGAYAKARTA.

[img]
Preview
PDF
Download (172Kb) | Preview

    Abstract

    Pada tesis ini telah dibangun suatu perangkat lunak yang diberi nama SiPerWira ( Solusi Perjalanan Wiraniaga), yaitu perangkat lunak penyelesaian Grhapical Traveling Salesman Problem (GTSP). GTSP adalah masalah percarian route terpendek untuk mengunjungi simpul yang dipilih pada suatu graph dan kembali lagi ke simpul asal. Berbeda dengan Traveling Salesman Problem klasik, rute yang dihasilkan pada GTSP tidak harus memenuhi syarat sirkuit Hamilton. Masalah ini merupakan masalah Nondeterministik Polinomial (NP), tetapi untuk kelas graph serial paralel dan graph roda dapat diselesaikan secara Polinomial (P). Kelas graph serial paralel dapat diselesaiakn dengan mengkonversi menjadi Generalized Traveling Salesman Problem , melakukan reduksi dan rekonstitusi busur pada graph. Kelas graph roda dapat diselesaikan dengan memanfaatkan algoritma penyelesaian graph serial paralel yang dikerjakan sebanyak busur keliling graph roda. Kelas graph separable mempunyai rute yang bisa dipisahkan pada tiap block. Pencarian rute pada graph separable dapat dilakukan dengan cara pendetesian block, menyelesaikan GTSP pada tiap block dan menggabungkannya. Perangkat lunak ini mendeteksi kemungkinan adanya graph separable, graph serial paralel pada graph sederhana. Graph sederhana dapat diselesaikan dengan membuat graph lengkapnya berdasarkan lintasan terpendeknya dan mencari sirkuit Hamilton minimum pada graph lengkap yang dibangun. Perangkat lunak ini membangun graph berdasarkan simpul yang dipilih dan menyelesaikannya berdasarkan kelas graph yang terdeteksi. Kata kunci : Traverling Salesman, Problem, Masalah Polynomia(P) dan Nondeterministik Polynomial(NP), graph serial paralel, graph roda, graph separable.

    Item Type: Thesis (Masters)
    Subjects: 000 Komputer, Informasi, dan Referensi Umum
    Divisions: Fakultas Teknologi Industri > Teknik Informatika
    Depositing User: dian praditya
    Date Deposited: 28 Dec 2011 11:57
    Last Modified: 28 Dec 2011 11:57
    URI: http://repository.upnyk.ac.id/id/eprint/1739

    Actions (login required)

    View Item