Kombinasi Algoritma Branch and Bound dan Cheapest Insertion Heuristic dalam Menyelesaikan Asymmetric Travelling Salesman Problem

Abstract

Travelling Salesman Problem (TSP) adalah suatu permasalahan seorang salesman yang mengunjungi setiap kota tepat satu kali dan kembali lagi ke kota asal dengan jarak tempuh minimum. Tujuan dalam artikel ini adalah menentukan rute perjalanan layanan jemput donasi LAZIS dengan menerapkan kombinasi Algoritma Branch and Bound dan Cheapest Insertion Heuristic dalam menyelesaikan Asymmetric TSP. Data yang digunakan adalah data sekunder berisi alamat donatur yang didapatkan dari LAZIS. Analisis data dilakukan dengan cara menginterpretasikan permasalahan ke dalam bentuk graf kemudian dilakukan pencarian dan penentuan jarak dengan menggunakan aplikasi Google Maps, memberi bobot pada graf dengan jarak yang diperoleh kemudian kombinasi Algoritma Branch And Bound dan Cheapest Insertion Heuristic digunakan untuk menyelesaikan permasalahan. Hasil yang didapatkan untuk rute terpendeknya adalah Kantor LAZIS→ Sri→ Reza→ Bayu→ Tasya→ Maisaroh→ Sarmo→ Khusnul→ Lely→ Yayuk→ Ayniyatur→ Istiqomah→ Nina→ Heny→ Ainur→ Ratna→ Kantor LAZIS dengan total jarak 54,9 km.

Kata kunci: Teori Graf, Travelling Salesman Problem, Branch and Bound, Cheapest Insertion Heuristic