UNCERTAIN TRAVELING SALESMAN PROBLEM

DWI NOVITA SARI, NIM. 12610005 (2018) UNCERTAIN TRAVELING SALESMAN PROBLEM. Skripsi thesis, UIN SUNAN KALIJAGA YOGYAKARTA.

Preview	Text (UNCERTAIN TRAVELING SALESMAN PROBLEM) 12610005_BAB_I_IV_DAFTAR-PUSTAKA1.pdf - Published Version Download (3MB) | Preview
	Text (UNCERTAIN TRAVELING SALESMAN PROBLEM) 12610005_BAB-II_S.D._SEBELUM-BAB-TERAKHIR.pdf - Published Version Restricted to Registered users only Download (4MB)

Abstract

Matematika merupakan ilmu yang luas dan banyak berkaitan dengan kehidupan. Banyak sekali permasalahan dalam kehidupan sehari-hari yang dapat direpresentasikan dengan graf, salah satunya yaitu Travelling salesman problem. Travelling salesman problem bertujuan untuk mencari rute terpendek dalam suatu perjalanan dari suatu tempat ketempat yang lain secara efektif dan efisien dimana tempat asal dan tujuan akhir haruslah sama. Dalam perjalanan tersebut pasti tidak selalu lancar. Terdapat beberapa hambatan yang ditemui, misalnya cuaca buruk, kondisi jalanan yang macet, terjadi bencana alam, dan masih banyak lagi yang mengakibatkan tersendatnya kegiatan tersebut. Oleh karena itu harus dicari solusi optimal untuk kegiatan pendistribusian suatu barang pada lingkungan yang tidak pasti yang biasa disebut dengan Uncertain Travelling Salesman Problem. Kota yang akan dikunjungi dinyatakan sebagai simpul, sedangkan jalan dinyatakan sebagai sisi. Variabel tidak pasti disini dilambangkan sebagai �. Permasalahan Uncertain Traveling Salesman Problem ini dapat diselesaikan dengan Algoritma Christofides. Cara kerja algoritma ini dimulai dengan menentukan shortest path yaitu rute terpendek yang akan dilalui oleh pedagang. Selanjutnya ditentukan subgraf dari Graf G yang mengandung semua simpul dari Graf G dan merupakan suatu pohon minimal (minimum spanning tree). Lalu ditentukan bobot terkecil dari setiap graf berbobot. Kemudian dicari sebuah sirkuit Euler. Pada Uncertain Travelling Salesman Problem ini dihasilkan model optimal untuk pendistribusian barang pada lingkungan tidak pasti, yaitu rute optimal yang diharapkan, rute �-optimal, rute distribusi optimal, pendekatan rute optimal yang diharapkan, dan rute optimal dengan pendekatan �.

Share this knowledge with your friends :

Actions (login required)

View Item