Optimasi Multi Compartment Vehicle Routing Problem dengan Karakteristik Multi Product, Split Delivery, dan Time Windows Menggunakan Pendekatan Simulated Annealing

NADIYAH NURUL FAUZI, Ir. Nur Mayke Eka Normasari, S.T., M.Eng., Ph.D., IPM

2022 | Skripsi | S1 TEKNIK INDUSTRI

Kegiatan distribusi dilakukan oleh semua perusahaan agar dapat membagikan produknya kepada konsumen. Dalam proses distribusi produk, perusahaan memerlukan banyak perencanaan termasuk menentukan rute distribusi. Penentuan rute distribusi menjadi hal yang penting karena berkontribusi cukup besar terhadap total biaya yang dikeluarkan perusahaan dan total pendapatannya. Pemilihan rute distribusi biasa disebut dengan VRP (Vehicle Routing Problem). VRP bertujuan untuk menemukan rute yang optimal, meminimalkan total jarak tempuh kendaraan yang mana dimulai dan diakhiri di depot yang sama, serta memenuhi kebutuhan semua konsumen. VRP yang mempertimbangkan kapasitas kendaraan dikenal dengan Capacitated Vehicle Routing Problem (CVRP). CVRP terus dikembangkan agar dapat diaplikasikan dalam berbagai kasus nyata, salah satu pengembangannya adalah Multi-Compartment Vehicle Routing Problem (MC-VRP). MC-VRP memungkinkan satu kendaraan membawa beberapa produk berbeda secara bersamaan tanpa tercampur satu sama lain karena di dalamnya digunakan beberapa kompartemen. Dalam penelitian ini, penulis mencoba mengaplikasikan metode heuristik/metaheuristik menggunakan algoritma Simulated Annealing (SA) untuk menyelesaikan masalah MC-VRP dengan karakteristik multi product, split delivery, dan time windows. Pada awalnya, algoritma SA ditulis dalam bahasa pemrograman Python. Kemudian, dilakukan verifikasi untuk memastikan program dapat berjalan, serta dilakukan validasi dengan membandingkan hasil perhitungan algoritma SA dengan hasil dari metode eksak yang dilakukan oleh peneliti sebelumnya. Salah satu keunggulan SA yaitu mampu menangani data dengan jumlah besar sehingga dilakukan uji large instances agar lebih sesuai dengan sistem nyata pada kasus MC-VRP. Ada 3 instances yang digunakan yaitu Z101, Z102, dan Z103. Hasilnya, algoritma SA yang dibangun telah terverifikasi dan tervalidasi, serta dihasilkan jarak tempuh sebesar 10.238,49 km dan membutuhkan 62 unit kendaraan untuk Z101. Untuk Z102, diperoleh jarak tempuh sebesar 5.189,98 km dan membutuhkan 47 unit kendaraan. Untuk Z103, dihasilkan jarak tempuh sebesar 11.174,62 km dan membutuhkan 62 unit kendaraan.

Distribution is carried out by all companies in order to distribute their products to consumers. In case of product distribution process, companies need a lot of planning including determining distribution routes. Choosing the distribution route is important because it has a significant contribution to the company's total cost and total revenue. The selection of distribution routes is known as VRP (Vehicle Routing Problem). VRP has the objectives to find the optimal route, minimize the total distance traveled by the vehicle which starts and ends at the same depot, and meets the needs of all consumers. Capacitated Vehicle Routing Problem (CVRP) is a VRP that considers vehicle capacity. CVRP is developed continuously so it can be applied in various real cases, one of the CVRP developments is Multi-Compartment Vehicle Routing Problem (MC-VRP). MC-VRP allows one vehicle to carry different products simultaneously without mixing with each other because it uses compartments. This study try to apply the heuristic/metaheuristic method using the Simulated Annealing (SA) algorithm to solve the MC-VRP problem with the characteristics of multi product, split delivery, and time windows. First, the SA algorithm is written with Python programming language. Then, verify the SA algorithm to ensure the program can be run, and perform validation by comparing the results of the SA algorithm with the results of the exact method from previous studies. SA has many advantages, such as being able to handle large data so that large instances are tested to make it more compatible with the real system in the MC-VRP's cases. There are 3 instances used, Z101, Z102, and Z103. As a result, the SA algorithm has been verified and validated. Total distance for Z101 is 10,238.49 km and it takes 62 vehicles. For Z102, the total distance is 5,189.98 km and it takes 47 vehicles. For Z103, total distance is 11,174.62 km and it takes 62 vehicles.

Kata Kunci : Distribusi, Multi Compartment Vehicle Routing Problem, Simulated Annealing