KOMBINASI ALGORITMA BRANCH AND BOUND DAN CHEAPEST INSERTION HEURISTIC DALAM MENYELESAIKAN ASYMMETRIC TRAVELLING SALESMAN PROBLEM

COMBINATION OF BRANCH-AND-BOUND AND CHEAPEST INSERTION HEURISTIC ALGORITHM IN ORDER TO ACCOMPLISH ASYMMETRIC TRAVELLING SALESMAN PROBLEM

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.

Travelling Salesman Problem (TSP) is an issue which a salesman visits each city exactly once and returns to the origin city by shortest possible distance. This research aimed to determine the peregrination routes about Donation Pick Up Services of LAZIS within apply combination of Branch-and-Bound and Cheapest Insertion Heuristic Algorithm in order to accomplish Asymmetric TSP. Data of this research is secondary data which contained donors address from LAZIS database. Data analysis method is interpreting this issue to become a Graph form, then finding and determining its possible distance using Google Maps, then adding weight and distance which obtained to graph and the last solving this problem using Branch-and-Bound and Cheapest Insertion Heuristic Algorithm Design. Result of this research is the shortest possible routes of Donation Pick Up Services may be reached was LAZIS Head Office→ Sri→ Reza→ Bayu→ Tasya→ Maisaroh→ Sarmo→ Khusnul→ Lely→ Yayuk→ Ayniyatur→ Istiqomah→ Nina→ Heny→ Ainur→ Ratna→ returned to LAZIS head office that has total distance 54,9 km.