Pengembangan Algoritma Heuristik Berbasis Teori Graf untuk Memaksimalkan Keuntungan pada Travelling Salesman Problem

M YUDA REWANTO, Dr. Irwan Endrayanto Aluicius, S.Si., M.Sc.

2023 | Skripsi | S1 MATEMATIKA

Dalam skripsi ini akan dibahas permasalahan Travelling Salesman Problem (TSP) yang lebih luas, yaitu memaksimalkan nilai TSP-PUT (Profit per Unit Time) dan TSP-MPUT (Multi-edge Profit per Unit Time). Masalah ini dikatakan sebagai perluasan dari masalah TSP klasik karena bertujuan untuk memaksimalkan keuntungan (profit) dengan diberikan pilihan rute perjalanan antara setiap pasangan kota yang berbeda dengan biaya dan waktu durasi perjalanannya juga berbeda. Saat menyelesaikan sebuah tur, salesman akan menerima pendapatan yang telah ditentukan sebelumnya. Keuntungan salesman per unit waktu didefinisikan sebagai keuntungan yang diperoleh setelah menyelesaikan tur (dihitung dengan mengurangkan pendapatan yang diperoleh dengan total biaya perjalanan yang dilalui) dibagi dengan total waktu yang dibutuhkan untuk menyelesaikan sebuah tur. Rute perjalanan dengan waktu atau biaya perjalanan terkecil belum tentu akan mendapatkan keuntungan paling maksimal. Oleh karena itu, pada skripsi ini akan ditunjukkan bagaimana memperoleh rute perjalanan dengan keuntungan tertinggi dibandingkan dengan melewati rute perjalanan yang lain.

In this undergraduate thesis, an extent of the Travelling Salesman Problem (TSP) will be studied, namely Max TSP PUT (Profit per Unit Time) and Max TSP-MPUT (Multi-edge Profit per Unit Time). This problem is said to be an generalization of the classic TSP problem because it aims to maximize profit by being given a choice of travel routes between each pair of different cities with different costs and travel durations. When completing a tour, the salesman will receive a predetermined revenue. Salesman profit per unit time is defined as the profit earned after completing the tour (calculated by subtracting the revenue earned by the total cost of the trip) divided by the total time required to complete the tour. The route with the smallest travel time or cost will not necessarily get the maximum profit. Therefore, in this thesis, it will be shown how to obtain a travel route with the best profit compared to passing other travel routes.

Kata Kunci : Travelling Salesman Problem, Keuntungan per unit waktu, teori graf, algoritma heuristik