PENERAPAN MULTIPLE TRAVELING SALESMAN PROBLEM PADA OPTIMASI PENDISTRIBUSIAN

(APPLICATION OF MULTIPLE TRAVELING SALESMAN PROBLEMS TO DISTRIBUTION OPTIMIZATION)

Abstract

ABSTRACT. Distribution is one of the important activities in sending goods from producers to consumers. This research was applied to PT. Kobe Boga Utama, Depok Branch. This company distributed products to 333 outlets in 2 weeks from Monday to Saturday. On certain days, the company visited more than one trip, requiring several salesmen. The distribution problem can be formed as a Multiple Traveling Salesman Problem and modeled as an Integer Linear Programming problem. This research aims to determine the optimal route with the shortest distance using the Branch and Bound method. The research results show that the salesman has to cover a minimum distance is 732.83 km in odd weeks with 149 outlets to visit. The number of trips taken is 7 trips, consisting of 1 trip on Monday, Thursday, and Friday, and 2 trips on Wednesday and Thursday. On even weeks, a salesman must visit 184 outlets with a minimum distance is 1292.3 km, consisting of 1 trip on Tuesday, Thursday, Friday, and Saturday, 2 trips on Wednesday, and 3 trips on Monday. The total minimum distance is 2025.09 km. The optimization result is about 359.97 km (49.12%) for odd weeks and 506.61 km (39.2%) for even weeks.
Keywords:: Distribution, Muliple Traveling Salesman Problem, Branch and Bound Method

ABSTRAK.  Pendistribusian merupakan salah satu kegiatan penting dalam mengirimkan barang dari produsen ke konsumen. Penelitian ini diterapkan pada PT. Kobe Boga Utama Cabang Depok. Perusahaan ini mendistribusikan produk ke 333 outlet dalam 2 pekan dari hari Senin hingga Sabtu. Pada hari tertentu, perusahaan mengunjungi lebih dari satu trip sehingga membutuhkan beberapa salesman. Masalah pendistribusian dapat dibentuk sebagai Multiple Traveling Salesman Problem dan dimodelkan sebagai masalah Integer Linear Programming. Penelitian ini bertujuan untuk menentukan rute optimal dengan jarak tempuh terpendek menggunakan metode Branch and Bound. Hasil penelitian menunjukkan bahwa pada pekan ganjil, salesman harus menempuh jarak minimal sebesar 732.83 km dengan outlet yang harus dikunjungi sebanyak 149. Banyaknya trip yang dilalui sebanyak 7 trip, yang terdiri dari 1 trip pada hari Senin, Kamis, dan Jumat, serta 2 trip untuk hari Rabu dan Kamis. Pada pekan genap, salesman harus mengunjungi 184 outlet dengan total jarak minimum sebesar 1292.3 km, yang terdiri dari 1 trip pada hari Selasa, Kamis, Jumat, dan Sabtu, 2 trip untuk hari Rabu, dan 3 trip untuk hari Senin. Total jarak tempuh minimum sebesar 2025.09 km. Hasil optimal dari pekan ganjil sebesar 359.97 km (49.12%) dan untuk pekan genap sebesar 506.61 km (39.2%).
Kata Kunci:: Distribusi, Integer Linear Programming, Metode Branch and Bound, Multiple Traveling Salesman Problem