Teknik Transformasi Clustered Generalized Traveling Salesman Problem dan Penerapannya pada Logistik

ISFAN CH NASUTION, Dr.rer.nat. Ari Suparwanto, M.Si.

2022 | Skripsi | S1 MATEMATIKA

Perubahan gaya hidup masyarakat yang semakin gemar berbelanja di toko online menimbulkan masalah baru pada layanan pengiriman paket. Jumlah paket yang dikirimkan semakin banyak tetapi masyarakat justru menginginkan paket dikirimkan dengan lebih cepat. Model pengiriman paket yang dapat dikembangkan adalah dengan menggunakan drone karena drone dapat mengirim paket lebih cepat dan menjangkau akses yang lebih luas. Namun, drone masih memiliki durasi terbang dan daya angkut yang terbatas. Keterbatasan drone dapat diatasi dan dimaksimalkan potensinya jika drone dikolaborasikan dengan truk pengantar. Pada skripsi ini akan dipaparkan lintasan yang dapat mengoptimalkan aksi kolaborasi antara truk pengantar dan drone untuk mengirimkan paket. Lintasan Traveling Salesman Problem (TSP) ditransformasikan menjadi lintasan Clustered Generalized Traveling Salesman Problem (CGTSP) untuk mendapatkan lintasan yang memiliki potensi untuk diterapkan pada berbagai kebutuhan. Lintasan CGTSP dikembangkan menjadi lintasan Parcel Delivery Services (PDS) yaitu lintasan aksi kolaborasi antara truk pengantar dan drone untuk mengirimkan paket. Algoritma Brute Force digunakan untuk mencari solusi lintasan yang optimal. Dibuatkan simulasi pada kasus khusus untuk mencari solusi optimal dibantu dengan komputasi menggunakan bahasa pemrograman Python. Hasil penelitian ini menunjukkan bahwa solusi lintasan PDS lebih optimal karena membutuhkan waktu pengiriman yang lebih singkat daripada solusi lintasan TSP.

People’s changing lifestyles increasingly enjoy shopping in online stores, creating new problems with package delivery services. The number of packages is increasing, but people want packages to be delivered faster. The package delivery model that can be developed is a drone because the drone can send packages faster and reach complete access. However, the drone still has limited flight duration and carrying capacity. The limitations of the drone can be overcome and maximized potential if the drone collaborates with delivery trucks. This thesis presented a track that can optimize the collaboration between the delivery truck and the drones to deliver packages. The Traveling Salesman Problem (TSP) track is transformed into a Clustered Generalized Traveling Salesman Problem (CGTSP) track to obtain a track that has the potential to be applied to various needs. The CGTSP track was expanded into a Parcel Delivery Services (PDS) track, a collaborative action track between delivery trucks and drones to deliver packages. The Brute Force algorithm will seek the solution to generate its optimal track. Simulations are created in special cases to find optimal solutions assisted by computing using Python programming. The results of this study show that the PDS solution is more optimal because it needs a shorter delivery time than the TSP solution.

Kata Kunci : Traveling Salesman Problem, TSP, CGTSP, Parcel Delivery Services, Drone