Pengembangan Model Matematika Heterogeneous Vehicle Routing Problem with Multi-Trips and Multi-Products

FRAN SETIAWAN, Nur Aini Masruroh, S.T., M.Sc., Ph.D.

2016 | Tesis | S2 Teknik Industri

INTISARI Biaya transportasi merupakan biaya tertinggi didalam total biaya logistik yang mencapai 29,4% dari total biaya logistik. Biaya transportasi dapat direduksi dengan mengoptimalkan urutan kunjungan kendaraan. Vehicle Routing Problem (VRP) adalah sebuah model untuk menentukan rute optimal dari kendaraan pengangkut untuk melayani sejumlah konsumen dimana batasan operasional terpenuhi. Didalam banyak praktik distribusi, permintaan konsumen dilayani oleh kendaraan yang heterogen (berbeda jenis dan kapasitas). Permasalahan VRP yang demikian disebut Heterogeneous Vehicle Routing Problem (HVRP). Karena lebih sesuai dengan keadaan nyata, penelitian tentang HVRP merupakan penelitian yang menarik. Banyak penelitian dibidang penambahan varian dari HVRP. Penelitian ini bertujuan untuk memperkaya varian dari HVRP yang diinspirasi oleh kasus nyata pada salah satu perusahaan distribusi farmasi di Indonesia yang mengirimkan multi-produk kepada 55 konsumen dengan mengizinkan beberapa kendaraan yang berkapasitas kecil untuk melakukan multi-trips. Permasalahan distribusi ini disebut sebagai Heterogeneous Vehicle Routing Problem with Multi-Trips and Multi-Products (HVRPMTMP). Mixed integer linear programming dikembangkan berdasarkan three-index vehicle flow formulation. Model ini dapat digunakan secara umum pada permasalahan distribusi sejenis. Dua skenario dibuat berdasarkan status kepemilikan kendaraan. Model diuji menggunakan permasalahan kecil dan diselesaikan menggunakan branch and bound pada solver LINGO 16.0. Karena HVRPMTMP merupakan permasalahan NP-hard, waktu komputasi menggunakan branch and bound pada LINGO 16.0 naik secara eksponensial seiring dengan bertambahnya jumlah konsumen. LINGO 16.0 tidak dapat memberikan hasil optimal sampai 8 konsumen dalam waktu 10.800 detik. Algoritma genetika dibangun untuk menyelesaikan kasus nyata. Tiga kromosom pertama di dalam populasi awal dibangkitkan menggunakan algoritma nearest neighbor dan lainnya dibangkitkan secara acak. Hanya solusi yang layak yang dibangkitkan dengan memberikan batasan pada setiap kromosom. Hasil dari algoritma genetika pada penelitian ini dapat mereduksi total biaya dari 554.281 menjadi 208.962 atau sebesar 62,3% dari penelitian sebelumnya. Mengenai permasalahan pertimbangan biaya tetap yang bergantung pada status kepemilikan kendaraan, jika kendaraan dimiliki oleh perusahaan maka tidak ada perbedaan antara menggunakan sedikit kendaraan atau tidak sepanjang jenis kendaraan yang digunakan sama. Jika kendaraan tidak dimiliki sendiri oleh perusahaan maka ada perbedaan menggunakan lebih sedikit kendaraan karena ada biaya untuk menyediakan kendaraan (biaya sewa kendaraan).

Transportation cost is the highest cost in total logistics cost which occupies 29.4% from total logistic cost. Transportation cost can be reduced by optimizing the sequence of vehicle route. Vehicle routing problem (VRP) is a model to determine an optimal routing plan for a fleet of homogeneous vehicles to serve a set customer which some operational constraints are satisfied. In most practical distribution problems, customer demands are served using heterogeneous fleet of vehicles. This kind of VRP is called Heterogeneous Vehicle Routing Problem (HVRP). Because of its practical, HVRP has evolved into a rich research area. There were many studies of rich extensions of the standar HVRP. This research aims to enrich the extentions of HVRP which is motivated by real case in one of pharmacy distribution company in Indonesia which is delivered multi-products to its 55 customers by allowing some vehicles which has a small capacity to perform multi-trips. This problem is called Heterogeneous Vehicle Routing Problem with Multi-Trips and Multi-Products (HVRPMTMP). The mixed integer linear programming is developed based on three-index vehicle flow formulation. The model can be used generally in the same context of distribution problem. Two scenarios are made based on the ownership status of the vehicle. The model is tested using a small arificial data and solved using branch and bound in LINGO 16.0 solver. Because HVRPMTMP is generally NP-Hard problem, the computational time using branch and bound in LINGO 16.0 is increasing exponentially by increasing the number of customers. LINGO 16.0 cannot solve optimally until 8 customers within 10,800 seconds. Genetic algorithm is proposed to solve the real case. The first three chromosomes in initial population is constructed using nearest neighbor algorithm while the others are by random procedure. Only feasible solution is generated by handling constraints first in every chromosome. The result of the proposed GA can reduce the total cost from 554,281 to 208,962 or 62.3% from the previous research. In term of fixed cost that is depend on the ownership status of vehicle, if the vehicles are owned by the company then there is no difference between using fewer vehicles or not as long as the vehicle types are same (same variable cost). If the vehicles are not owned by the company then there is a difference using fewer vehicles because there is effort required to provide a vehicle (fixed cost to rent vehicles).

Kata Kunci : Heterogeneous Vehicle Routing Problem, Multi-Trips, Multi-Products, Mixed Integer Linear Programming, Genetic Algorithm