Sidang Tugas Akhir

Fikri Hidayat
g54100032

Penyelesaian Clustered Travelling Salesman Problem dengan Algoritme Lexisearch

Distribusi barang merupakan suatu kegiatan yang bertujuan mempermudah kegiatan penyaluran barang dari pihak produsen ke pihak konsumen. Masalah yang sering muncul dalam proses pendistribusian barang adalah menentukan rute terpendek tur yang efisien dan efektif untuk sampai tujuan. Permasalahan distribusi dapat dimodelkan sebagai masalah penentuan rute terpendek pada graf yang merupakan modifikasi dan pengembangan dari model Travelling Salesman Problem (TSP). TSP dapat diilustrasikan sebagai perjalanan seorang salesman dimulai dari suatu kota yang harus melalui semua kota yang dituju dengan jarak terpendek sehingga setiap kota hanya boleh dilalui satu kali dan kembali ke kota awal perjalanan. Solusi dari TSP ialah jalur yang dilalui oleh salesman tersebut. Tentunya solusi terbaik atau optimal dari permasalahan ini ialah jalur dengan jarak terpendek atau dapat disebut juga dengan rute perjalanan minimum. Salah satu varian dari TSP adalah Clustered Travelling Salesman Problem (CTSP). Model CTSP dibentuk berdasarkan kedekatan yang sama pada tiap cluster. Contoh aplikasi dalam kehidupan nyata, misalnya: dalam perencanaan produksi, operasional komputer, jadwal ujian, dll. Masalah CTSP dapat diselesaikan dengan beberapa metode, antara lain mentransformasikan CTSP menjadi TSP dengan cara memodifikasi matriks jarak (Chisman 1975) dan menyelesaikannya dengan algoritme branch and bound; atau dengan beberapa algoritme heuristik seperti dalam (Anily et al. 1999), dan (Guttmann-Beck et al. 2000), algoritme tabu search (Laporte et al. 1996), dan algoritme genetik 2 tingkat (Ding et al. 2007). Dalam karya ilmiah ini, masalah CTSP diselesaikan dengan algoritme lexisearch. Sumber utama karya ilmiah ini ialah artikel yang berjudul An exact algorithm for the clustered travelling salesman problem (Ahmed 2013).