Karya Ilmiah Dosen FMIPA a.n Sapti Wahyuningsih pada Prosiding SEMNASTIKA 2015 di UNESA

Prosiding Seminar Nasional Matematika dan Pendidikan Matematika 2015
ISBN No. 978-979-028-728-0490

25 April 2015 Universitas Negeri Surabaya


KAJIAN KARAKTERISTIK SOLUSI VARIAN TRAVELING
SALESMAN PROBLEM (TSP) DAN APLIKASINYA

Sapti Wahyuningsih1, Darmawan Satyananda2, Dahliatul Hasanah3
1 Jurusan Matematika FMIPA UM Malang, sapti.wahyuningsih.fmipa@um.ac.id
2 Jurusan Matematika FMIPA UM Malang , darmawan.satyananda.fmipa@um.ac.id
3 Jurusan Matematika FMIPA UM Malang , dahliatul. Hasanah.fmipa@um.ac.id


Abstrak. Pada kajian teori graph, permasalahan TSP merupakan masalah menentukan sikel Hamilton dengan jumlah bobot sisi yang minimal. Pada perkembangannya terdapat bermacam-macam varian dari TSP. Varian TSP ini dapat diaplikasikan pada permasalahan distribusi. Telah banyak riset tentang bermacam-macam varian TSP yaitu Traveling Salesman Problem with Time Windows (TSPTW), Clustered Traveling Salesman Problem (CTSP), Multiple Traveling Salesman Problem (MTSP), Dynamic Traveling Salesman Problem (DTSP), dan Travelling Salesman Problem with Precedence Constraints (TSPPC). Varian-varian ini dikembangkan antara lain bertujuan untuk memodelkan aplikasi dalam dunia nyata dengan lebih baik sesuai dengan kebutuhan yang diperlukan. Pada artikel ini diidentifikasi formulasinya dalam teori graph serta dikaji syarat cukup graph dari varian TSP. Pada aplikasinya model graph atau digraph yang diperlukan, akan menentukan pemilihan varian TSP. Oleh karena itu pada artikel ini dikaji karakteristik solusi DTSP dan TSPPC yang merupakan contoh model untuk graph dan digraph. Algoritma nearest neighbor heuristic dan algoritma nearest insertion heuristic digunakan untuk menentukan solusi optimal DTSP dikaji langkah iterasi dan kelebihan/kekurangannya. Diberikan contoh aplikasinya pada masalah optimalisasi distribusi dengan implementasi program yang disusun dalam bahasa Delphi.
Kata kunci: varian TSP, TSPTW, CTSP, MTSP, DTSP, TSPPC, optimalisasi distribusi.


Chat