Perancangan Teknik Industri 1 - VRP

Vehicle Routing Problem merupakan permasalahan distribusi yang mencari serangkaian rute untuk sejumlah kendaraan dengan kapasitas tertentu dari satu atau lebih depot untuk melayani konsumen. Toth dan Vigo (2002) mengemukakan tujuan yang ingin dicapai dalam VRP di antaranya:

·         Meminimalkan ongkos perjalanan secara keseluruhan yang dipengaruhi oleh

·         keseluruhan jarak yang ditempuh dan jumlah kendaraan yang digunakan.

·         Meminimalkan jumlah kendaraan yang digunakan untuk melayani semua

·         konsumen.

·         Menyeimbangkan rute.

·         Meminimalkan keluhan pelanggan.

Permasalahan VRP biasanya digambarkan dalam sebuah grafik. Grafik tersebut menggambarkan permasalahan yang terjadi, yaitu berupa penyebaran konsumen yang harus dilayani dan posisi depot yang merupakan pusat pendistribusian berlangsung. Vertex merupakan titik yang menunjukkan posisi depot dan konsumen berada. Vertex depot ditunjukkan oleh Vo dan yang lainnya menunjukkan konsumen yang berjumlah n. Garis yang menghubungkan antar vertex disebut arc. Arc menunjukkan waktu, ongkos perjalanan dan jarak yang digunakan untuk perjalanan dari satu titik ke titik yang lain. Solusi dianggap layak

jika memenuhi beberapa syarat, yaitu rute yang terbentuk harus dapat melayani semua konsumen, semua konsumen hanya bisa dikunjungi satu kali,dan semua rute harus dimulai dan selesai di home depot (Haksever et al., 2000). VRP memiliki karakteristik berupa demand yang berada pada setiap konsumen, memiliki satu depot, dan memiliki lebih dari satu kendaraan dengan kapasitas yang terbatas. VRP diklasifikasikan dalam NP-hard problem, oleh karena itu metode exact optimization sulit untuk menyelesaikan kasus VRP. Untuk mendapatkan solusi yang relevan dengan kondisi real dan sangat dekat dengan solusi yang optimal maka digunakanlah metode heuristic dan meta-heuristic (Kumar dan Panneerselvam, 2012). VRP memiliki banyak varian sesuai dengan karakteristik permasalahan, salah satunya adalah Capacitated Vehicle Routing Problem (CVRP). CVRP pertama kali muncul pada permasalahan permasalahan penentuan rute distribusi dengan kendaraan yang memiliki kapasitas tetap dan sama untuk memenuhi permintaan konsumen dengan komoditi tunggal dari suatu depot dengan ongkos minimum (Ai dan Kachitvichyanukul, 2009). CVRP merupakan varian VRP yang paling sederhana. Kapasitas yang terbatas dan sama untuk semua kendaraan merupakan ciri dari CVRP. CVRP digambarkan dengan sejumlah demand ( ) yang harus dikirimkan ke konsumen i ( i = 1,2,…,n) dari depot tunggal menggunakan armada pengiriman dengan kapasitas C. Dalam CVRP setiap konsumen hanya boleh dikunjungi satu kali dan total pengiriman tidak lebih dari C, dengan tujuan untuk meminimalkan total jarak tempuh semua kendaraan (Borgulya, 2008). VRP merupakan salah satu kisah sukses dari operational research. Hal ini dapat dilihat banyaknya penelitian yang membahas tentang Vehicle Routing Problem dalam 50 tahun terakhir sejak tulisan Danzig dan Ramser keluar. Golden et al. (2008) dalam bukunya merangkum beberapa penelitian yang membahas VRP yang dilakukan oleh peneliti-peneliti lain. Kumpulan penelitian yang dirangkum terdiri dari tiga bagian adalah survey dan gambaran tentang VRP, penerapan VRP, pengembangan model dan algoritma. Perkembangan kasus distribusi di dunia nyata dengan berbagai macam karakteristik membuat banyaknya varian VRP yang merupakan pengembangan dari varian VRP yang sudah ada. Mulai dari VRP dengan single objective hingga multi objective. Hal ini yang membuat banyak peneliti yang merasa tertantang untuk menyelesaikan kasus VRP yang mulai beragam dan lebih up to date seperti yang dilakukan oleh Hempsch dan Irnich (2008) atau mengembangkan metode baru untuk mencari solusi yang lebih baik seperti Baldacci et al. (2008). Hempsch dan Irnich (2008) menyebutkan bahwa kasus distribusi pada dunia nyata memiliki kendala baru berupa Inter-tour constrains. Inter-tour constrains adalah kendala yang melihat bahwa terdapat banyak sifat dalam distribusi yang mempengaruhi solusi yang dihasilkan, seperti proses sorting pada depot, lama maksimum rute, dan terbatasnya kapasitas untuk memproses barang yang datang. Hempsch dan Irnich menggunakan local-search algorithms dalam menyelesaikan kasus tersebut. Sedangkan Baldacci et al. (2008) mengembangkan metode heuristik dalam menyelesaikan varian kasus Heterogeneous Fleet VRP (HFVRP). Tujuan dari penelitian Baldacci et al. adalah membandingkan hasil komputasi dan performansi algoritma heuristik miliknya dengan penelitian terdahulu. Kasus VRP yang bersifat multi objective pernah dilakukan oleh Ueng (1999) yang mencoba membawa beban kerja supir taksi sebagai faktor yang diperhitungkan dan mengembangkan model VRP yang tidak hanya mencari jarak terpendek tetapi juga mempertimbangkan keseimbangan beban kerja yang dibebankan ke supir. Penelitian yang dilakukan Ueng memiliki kesamaan dengan penelitian ini, tetapi hal yang membedakan adalah definisi keseimbangan beban kerja. Ueng mendefinisikan keseimbangan beban kerja dengan meminimumkan nilai varian dari load yang harus diantarkan supir taksi sedangkan pada penelitian ini keseimbangan beban kerja didefinisikan dengan meminimasi rentang load kendaraan . Ueng mengusulkan algoritma heuristik dalam menyelesaikan kasus CVRPLB.