Seminar Tugas Akhir

Cahyadi
G05400032

FORMULASI TSP (TRAVELING SALESMAN PROBLEM)

Traveling Salesman Problem (TSP) adalah suatu perjalanan salesman dari kota (tempat) asalnya mengunjungi n-kota (tempat) tepat satu kali kemudian kembali ke kota (tempat) asalnya dengan jarak total yang minimum. Tujuannya untuk meminimumkan biaya operasional yang dikeluarkan oleh perusahaan. Rute kendaraan pada TSP berupa suatu cycle Hamilton, yaitu path tertutup yang memuat semua node pada graf yang merepresentasikan jaringan jalan. Masalahnya adalah menentukan rute perjalanan yang fisibel (yang mungkin dapat dilalui) sedemikian sehingga jarak tempuh kendaraan yang melalui rute tersebut minimum. Tulisan ini menyajikan penyelesaian TSP menggunakan Integer Linear Programming (ILP) dengan fungsi objektif menentukan bobot total arcs minimum yang termasuk dalam perjalanan dengan kendala-kendala yaitu salesman tiba tepat satu kali di setiap node, salesman meninggalkan setiap node tepat satu kali, tidak ada subtour yang infisibel, dan terbentuknya Hamilton cycle yang fisibel.