Optimasi Rute Distribusi Traveling Salesman Problem pada Perusahaan Fast-Moving Consumer Goods menggunakan Pendekatan Eksak

ZULVAN MUHAMMAD NABAWI, Ir. Nur Mayke Eka Normasari, S.T., M.Eng., Ph.D, IPM., ASEAN Eng.

2024 | Skripsi | TEKNIK INDUSTRI

IkiTelurQu merupakan produk telur puyuh RTE (ready-to-eat) yang telah tersebar luas di berbagai minimarket, pusat oleh-oleh, dan pasar tradisional di wilayah Yogyakarta dan sekitarnya. Proses distribusi dari pusat produksi ke tokotoko ritel menjadi komponen krusial dalam meningkatkan profitabilitas perusahaan. Saat ini, terdapat 74 agen yang bermitra dengan IkiTelurQu sehinnga perusahaan perlu mendistribusikan produknya sesuai permintaan agen. Setiap bulannya, IkiTelurQu mengalokasikan dana sebesar Rp 1,6 hingga 4,8 juta untuk biaya transportasi, dimana merupakan jumlah yang signifikan mengingat karakteristik produk FMCG dengan margin keuntungan yang relatif rendah. Optimalisasi rute distribusi menjadi salah satu strategi yang dapat diambil untuk meminimalkan biaya transportasi.

Traveling Salesman Problem (TSP) merupakan permasalahan yang umumnya sulit diselesaikan, dimana seorang salesman harus mengunjungi suatu kota tepat sekali dan kembali ke kota asal seperti yang terjadi di IkiTelurQu. Untuk mengatasi permasalahan ini, metode penelitian yang digunakan adalah metode eksak branch and bound. Branch and bound adalah pendekatan algoritmik yang efektif dalam menyelesaikan TSP dengan mengeksplorasi dan membatasi pencarian berdasarkan estimasi lower bound dari soolusi yang mungkin.

Data penelitian diambil dari satu minggu pengiriman, dimana menggunakan metode  branch and bound, total jarak yang ditempuh dapat diperpendek sebesar 46,48 km atau menghasilkan penghematan sebesar 9,78%. Biaya transportasi yang semula Rp 607.160 berhasil dikurangi menjadi Rp 546.706, mengindikasikan pengurangan biaya sekitar 9,95%. Hasil ini menunjukkan bahwa penerapan metode eksak branch and bound dapat memberikan kontribusi penghematan dalam efisiensi biaya operasional dan pengelolaan distribusi bagi perusahaan IkiTelurQu.

IkiTelurQu is a ready-to-eat quail egg product that has been widely distributed across various minimarkets, souvenir centers, and traditional markets in the Yogyakarta region and its surroundings. The distribution process from the production center to retail stores is a crucial component in enhancing the company's profitability. Currently, there are 74 agents partnering with IkiTelurQu, requiring the company to distribute its products according to the agents' demands. Each month, IkiTelurQu allocates between Rp 1.6 to 4.8 million for transportation costs, a significant amount given the low-profit margin characteristic of FMCG products. Optimization of distribution routes is one strategy that can be employed to minimize transportation costs.

The Traveling Salesman Problem (TSP) is a notoriously difficult problem where a salesman must visit each city exactly once and return to the starting city, analogous to the challenges faced by IkiTelurQu. To address this issue, the research method employed is the exact Branch and Bound method. Branch and Bound is an algorithmic approach effective in solving TSP by exploring and restricting searches based on lower bound estimates of possible solutions.

Data for the study was gathered over one week of deliveries, where using the Branch and Bound method, the total distance traveled could be reduced by 46.48 km, resulting in savings of 9.78%. The transportation cost, originally Rp 607,160, was successfully reduced to Rp 546,706, indicating a cost reduction of approximately 9.95%. These results demonstrate that the application of the exact Branch and Bound method can contribute significantly to savings in operational efficiency and distribution management for IkiTelurQu.

Kata Kunci : TSP, Supply Chain Management, Branch and Bound