Judul | : | FORMULASI TSP (TRAVELING SALESMAN PROBLEM) |
Jenis | : | Skripsi |
Penulis | : | Cahyadi |
NRP | : | G05400032 |
Tanggal Lulus | : | 21 August 2008 |
Tanggal Seminar | : | 30 May 2008 14:00 |
Tanggal Sidang | : | 23 June 2008 13:00 |
Pembimbing | : |
Drs. Prapto Tri Supriyo, M.Kom. Dr. Ir. Fahren Bukhari, M.Sc. |
Ringkasan | : | 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. |