Jurnal Sistem dan Manajemen Industri Vol 2 No 1 Juli 2018, 1-8 Available online at: http://e-jurnal.
org/index.
php/JSMI Jurnal Sistem dan Manajemen Industri ISSN (Prin.
2580-2887 ISSN (Onlin.
2580-2895 Optimasi Rute Pengiriman dengan Heterogeneous Fleet Vehicle Routing Problem with Time Windows Edwin Hendrawan*.
I Gede Agus Widyadana Program Studi Teknik Industri.
Fakultas Teknologi Industri.
Universitas Kristen Petra.
Jl.
Siwalankerto No.
121 -131,
Siwalankerto.
Wonocolo.
Surabaya.
Jawa Timur 60236 Indonesia
ARTICLE INFORMATION
A B S T R A K
Article history:
PT.
X merupakan distributor suku cadang dengan 128 pelanggan untuk Kota Surabaya dan Kota Sidoarjo.
Jumlah kendaraan pengirim yang dimiliki oleh PT.
X adalah 15.
Penentuan rute pengiriman yang dimiliki oleh PT.
dilakukan secara manual, berdasarkan pengalaman pengemudi.
Penelitian ini bertujuan membuat sebuah model penentuan rute dengan biaya minimum dengan mempertimbangkan waktu tempuh dan kapasitas kendaraan.
Pembentukan model dilakukan sesuai dengan kebijakan PT.
X , yaitu setiap kolega hanya dapat dilayani oleh satu kendaraan dalam waktu tempuh pengiriman maksimal selama 7 jam.
Model yang dibentuk merupakan Heterogeneous Fleet Vehicle Routing Problem (HFVRP) with Time Windows.
Metode penyelesaian yang digunakan adalah Evolutionary Algorithm (EA) dengan meninjau 3 kasus.
Jumlah kendaraan yang digunakan oleh model berkurang, dengan selisih rata-rata 1,67 kendaraan.
Biaya pengiriman yang dihabiskan oleh model lebih sedikit, untuk kasus 1 sebesar 3.
155 Rupiah dan kasus 2 sebesar 25.
005 Rupiah.
Kondisi ini menunjukkan model akan menggunakan jumlah kendaraan yang lebih sedikit dengan biaya pengiriman rendah dan utilitas tampung yang besar dalam 2 kasus.
Received: January 19, 2018 Revised: March 21, 2018 Accepted: April 6, 2018 Kata Kunci:
Evolutionary Algorithm
HFVRP with Time Windows Rute
Vehicle Routing Problem
A B S T R A C T
Keywords:
Evolutionary Algorithm HFVRP with Time Windows Rute Vehicle Routing Problem *Corresponding Author Edwin Hendrawan E-mail: hendrawanedwin68@gmail.
PT.
X is a distributor of spare parts with 128 customers for Surabaya City and Sidoarjo City.
Number of delivery vehicles owned by PT.
X is 15.
Determination of delivery route owned by PT.
X is completed manually based on driver experience.
This research is to make a model of determining the route with minimum cost by considering the travel time and the capacity of the Model formation is accomplished in accordance with the PT X policy that each colleague can only be served by one vehicle and the maximum shipping time of 7 hours.
The model formed is Heterogeneous Fleet Vehicle Routing Problem with Time Windows (HFVRPWTW).
The settlement method used is Evolutionary Algorithm (EA) by reviewing 3 cases.
The number of vehicles decreased by the model is with an average difference of 1.
The shipping cost generated by the model is lower than the company for case 1 of 3,155 IDR and case 2 of 25,005 IDR.
This condition indicates the model will use less number of vehicles with low shipping costs and large container utilities in 2 cases.
A 2018 Penerbit UNSERA.
All rights reserved PENDAHULUAN PT.
X merupakan sebuah perusahaan yang bergerak dalam bidang jasa yaitu distributor suku cadang sepeda motor X.
Kegiatan distribusi dilakukan dengan mengirimkan suku cadang kepada pelanggan yang sudah memesan sesuai dengan jadwal yang telah disepakati.
Jumlah pelanggan yang dilayani oleh PT.
X di Kota Surabaya dan Kota Sidoarjo sebanyak 128 Pengiriman suku cadang yang dilakukan PT.
X menggunakan kendaraan operasional perusahaan yang berjumlah 15 Hendrawan dan Widyadana DOI: http://dx.
org/10.
30656/jsmi.
Jurnal Sistem dan Manajemen Industri Vol 2 No 1 Juli 2018, 1-8 Hasil wawancara dengan PT.
X menunjukkan mengirimkan pesanan kepada pelanggan.
Pemesanan yang dilakukan pelanggan tidak secara rutin.
Kondisi ini membuat PT.
X harus menentukan rute pengiriman yang berbeda.
Kebijakan penentuan rute pengiriman yang digunakan ditentukan secara manual.
Kebijakan dilaksanakan berdasarkan pengetahuan dan Kota Surabaya dan Kota Sidoarjo.
Pengetahuan dan menyebabkan penentuan rute tidak memiliki standart tetap, yang berpengaruh pada besarnya biaya pengiriman.
Biaya pengiriman dalam menentukan rute dipengaruhi oleh beberapa hal, yaitu jarak tempuh, waktu total pengiriman, dan kapasitas Jarak tempuh kendaraan merupakan perpindahan antar lokasi.
Nilai jarak perpindahan mempengaruhi penggunaan bahan bakar setiap Kondisi ini memicu peningkatan penggunaan bahan bakar secara berlebih.
Waktu total pengiriman dipengaruhi oleh waktu perpindahan dan waktu bongkar.
Jarak tempuh yang besar juga membuat waktu tempuh menjadi Sedangkan waktu bongkar merupakan aktivitas bongkar produk dari kendaraan pengirim saat di lokasi tujuan.
Kapasitas tampung sangat dipengaruhi oleh penentuan rute yang ada.
Rute yang terbentuk memungkinkan kendaraan untuk menampung suku cadang berlebih atau Pengangkutan yang berlebih akan membuat penataan produk terlalu dipaksakan.
Hal ini akan memicu kerusakan dalam proses Pengangkutan dengan jumlah yang terlalu kecil mengakibatkan penggunaan jumlah kendaraan secara berlebih.
Tujuan penelitian yang akan dicapai adalah membuat cara penentuan rute yang standar mempertimbangkan waktu tempuh dan kapasitas Pencapaian penelitian dibatasi oleh beberapa faktor seperti tidak memperhatikan dampak lingkungan, serta kecepatan perpindahan dan waktu bongkar muat tiap unit konstan.
METODE PENELITIAN
Heterogeneous Fleet Vehicle Routing Problem (HFVRP) with Time windows merupakan metode yang digunakan untuk membantu membentuk model matematis.
HFVVRP with Time windows digunakan untuk meyelesaikan permasalahan DOI: http://dx.
org/10.
30656/jsmi.
yang terdiri terdiri dari menentukan rute kendaraan yang mana pelanggan dikunjungi tepat satu kali oleh kendaraan dalam waktu yang telah ditentukan, semua kendaraan memulai dan mengakhiri rute di titik awal pengiriman dan beban setiap kendaraan tidak melebihi kapasitas kendaraan .
Evolutionary Algorithm merupakan metode penyelesaian yang digunakan untuk menentukan rute HFVRPTW.
Vehicle Routing Problem (VRP) merupakan sebuah penentuan rute sejumlah kendaraan dengan kapasitas tertentu untuk memenuhi permintaan .
Metode VRP sendiri merupakan pengembangan dari Metode Travelling Salesman Probelm (TSP) dimana pengiriman dilakukan oleh 1 kendaraan saja .
Penerapan yang dilakukan dalam menggunakan metode VRP sangat beragam bergantung dari tujuannya.
Salah satu penggunaan VRP adalah mengurangi polusi pada lingkungan .
Metode HFVRPTW merupakan integrasi HFVRP VRPTW.
HFVRP
pengembangan metode VRP yang meninjau penentuan rute dengan jenis kendaraan yang Elemen umum yang membedakan jenis kendaraan adalah kapasitas kendaraan, fixed costs, dan variable costs .
, .
Tujuan umum penggunaan HFVRP adalah untuk menentukan jumlah kendaraan yang dibutuhkan dalam melakukan pengiriman.
VRPTW merupakan pengembangan metode VRP yang meninjau time VRPTW dibagi kedalam dua jenis, yaitu soft time windows dan hard time windows .
Soft time windows menunjukkan bahwa pengiriman dapat melebihi time windows dengan membebankan biaya pengiriman .
Hard time windows menunjukkan bahwa pengiriman tidak boleh dilakukan di luar time windows.
Evolutionary Algorithm (EA) merupakan metode penyelesaian yang digunakan untuk membantu penentuan rute.
Aplikasi EA yang digunakan adalah Evolutionary Programming.
Tahapan penyelesaian terdapat 2 tahap .
dan dijelaskan dalam 4 tahap dengan lebih detail .
Tahap pertama adalah pembentukan populasi awal yang dilakukan secara random.
Populasi merupakan kumpulan individu yang terbentuk untuk diolah lebih lanjut.
Tahap kedua individu yang sudah terbentuk kemudian akan termutasi untuk membentuk offspring.
Tahap ketiga offspring yang sudah terbentuk akan diseleksi dengan individu yang ada.
Seleksi dilakukan dengan tournament selection.
Nilai fitness offspring yang lebih baik daripada nilai fitness Hendrawan dan Widyadana Jurnal Sistem dan Manajemen Industri Vol 2 No 1 Juli 2018, 1-8 menggantikan individu yang ada.
Tahapan terakhir yang dilakukan adalah mengurutkan nilai terbaik setiap individu untuk dijadikan solusi.
yang digunakan ada 2 yaitu satu lokasi hanya boleh dilayani oleh satu kendaraan dan batas waktu total pengiriman selama 7 jam.
Penelitian ini akan menggunakan bantuan Solver Microsoft Excel.
Solver memiliki beberapa parameter yang digunakan untuk membantu penentuan rute.
Parameter yang digunakan adalah convergence, mutation rate, population size, maximum time without improvement, dan requires bound on variables.
Convergence digunakan untuk melihat untuk melihat populasi yang terbentuk sudah mendekati nilai global Mutation rate digunakan sebagai kemampuan mutasi dalam populasi.
Population size digunakan untuk menentukan jumlah individu yang dapat terbentuk dalam 1 populasi.
Maximum time without improvement digunakan sebagai batasan metode EA untuk berhenti mengeksekusi ketika tidak ada peningkatan dalam waktu yang sudah ditentukan.
Requires bound on variables merupakan batasan yang harus dimiliki oleh suatu variabel.
Data jumlah pesanan merupakan pemicu agar suatu lokasi dapat dilayani.
Data pesanan yang digunakan ada 3 yaitu kasus 1 untuk 24 lokasi, kasus 2 dan 3 untuk 39 lokasi.
HASIL DAN PEMBAHASAN
Data produk merupakan ukuran dimensi produk dan kelipatan.
Produk yang digunakan pada penelitian adalah produk A dan produk B.
Produk A memiliki dimensi acuan 0,15 m dengan 9 jenis kelipatan dan produk B memiliki dimensi acuan 0,05 m dengan 28 jenis kelipatan.
Dimensi tiap kelipatan produk akan dikalikan dengan dimensi Data jenis dan spesifikasi kendaraan merupakan data mengenai rincian kendaraan.
Rincian kendaraan dibagi dalam 2 kategori yaitu kapasitas tampung dan kemampuan pembakaran bahan bakar.
Penelitian ini meninjau 15 kendaraan yang akan digunakan dalam menentukan rute.
Jenis kendaraan dengan kapasitas kurang dari 10 m kemampuan pembakaran sebesar 1/7 sebanyak 10 kendaraan.
Jenis kendaraan dengan kapasitas lebih dari 10 m memiliki kemampuan pembakaran sebesar 1/6 sebanyak 5 kendaraan.
Data yang mempengaruhi waktu total pengiriman merupakan waktu bongkar muatan dan kecepatan kendaraan.
Waktu bongkar muatan yang digunakan sebesar 2 menit untuk perpindahan tiap unit.
Data kecepatan kendaraan merupakan data perpindahan antar lokasi sebesar 40 km/jam.
Kebijakan perusahaan merupakan data yang digunakan sebagai batasan model.
Kebijakan Hendrawan dan Widyadana Tabel 1.
Data pesanan Kasus Jumlah pesanan .
) Model Matematis Model matematis yang digunakan merupakan model HFVRPTW .
Pembentukan model perusahaan yang ditinjau.
Model matematis yang digunakan pada penelitian ini adalah sebagai Oc Oc Oc = Total biaya pembakaran yang dihasilkan.
= Biaya pembakaran tiap liter.
= Penggunaan bahan bakar kendaraan v.
= Nilai binary agar kendaraan v tidak melakukan pengulangan perpindahan lokasi i,j.
= Nilai kapasitas kendaraan v.
= Nilai volume pesanan dalam lokasi i.
= Nilai binary menunjukkan bahwa lokasi i sudah dilayani kendaraan v.
= Nilai perpindahan lokasi i, j.
= Nilai unit pesanan dalam lokasi i.
= Nilai kemampuan pembakaran kendaraan v.
= Nilai kecepatan kendaraan .
m/ja.
= Nilai kecepatan waktu bongkar muat.
DOI: http://dx.
org/10.
30656/jsmi.
Jurnal Sistem dan Manajemen Industri Vol 2 No 1 Juli 2018, 1-8 Pers.
merupakan fungsi tujuan dari model yang dibentuk.
Fungsi tujuan dari model adalah menghitung total biaya bahan bakar seluruh kendaraan yang melakukan pengiriman.
Pers.
merupakan batasan agar lokasi i hanya dapat dilayani oleh satu kendaraan.
Pers.
, .
, dan .
merupakan batasan agar perpindahan lokasi i ke lokasi j dilakukan satu Pers.
sebagai perpindahan depo menuju lokasi pelanggan ( 1 ke j ).
Pers.
sebagai perpindahan dari lokasi pelanggan menuju depo ( i ke 1 ), dan Pers.
sebagai perpindahan antar lokasi pelanggan ( i ke j ).
Pers.
merupakan batasan bahwa pengiriman dapat dilakukan ketika kapasitas kendaraan v .
lebih besar dari jumlah pesanan lokasi i (D.
Nilai Di dipengaruhi oleh nilai Yiv.
Pers.
memiliki fungsi untuk menghitung penggunaan bahan bakar kendaraan v.
Penggunaan bahan bakar suatu kendaraan dipengaruhi oleh nilai perpindahan lokasi i ke j (Xi.
dan kemampuan bakar dari kendaraan v (H.
Pers.
merupakan batasan waktu pengiriman total harus lebih kecil dari batas waktu yang ditentukan (T.
Waktu pengiriman total dipengaruhi oleh dua faktor yaitu waktu perpindahan dan waktu bongkar muat tiap unit.
Waktu perpindahan terdiri dari nilai jarak antar lokasi i ke lokasi j (Xi.
dan dibagi dengan kecepatan kendaraan .
Waktu bongkar muatan dipengaruhi dari jumlah pesanan dalam unit (U.
dikali dengan waktu perpindahan tiap unit .
Parameter solver yang digunakan adalah sebagai berikut :
convergence = 1 x 10 mutation rate = 0,075 population size = 100 maximum time without improvement = 300 Penentuan parameter solver bertujuan agar hasil yang terbentuk merupakan hasil yang optimum.
Nilai convergence yang semakin kecil dan max time without improvement yang semakin besar membutuhkan waktu yang lebih lama dalam mencari hasil akhir tetapi dengan hasil yang Solver akan membantu model untuk membentuk kromosom urutan lokasi dan Urutan lokasi dan kendaraan akan menjadi acuan dalam hasil rute yang akan DOI: http://dx.
org/10.
30656/jsmi.
Tabel 2.
Contoh kromosom Urutan Kendaraan Urutan Lokasi Kromosom yang terbentuk akan dimulai sesuai urutan yang ada.
Urutan kendaraan yang akan digunakan adalah kendaraan 1, 2, 3, 4, dan 5.
Urutan lokasi 2, 3, 4, 5, dan 6 akan dilalui oleh setiap kendaraan.
Kendaraan akan memulai pengiriman dari lokasi 1 .
Kendaraan terus melakukan pengiriman ketika syarat persamaan Syarat yang tidak terpenuhi akan membuat kendaraan untuk kembali ke depo dan dibutuhkan kendaraan lain untuk mengirimkan lokasi yang belum terlayani.
Model HFVRPTW Model HFVRPTW yang sudah terbentuk merupakan gabungan dari model matematis dan parameter solver yang sudah dibentuk (Gambar Model HFVRPTW dibagi dalam 3 tahap utama yaitu input, proses, dan output.
Tahap input merupakan proses pengisian data penunjang yang akan diolah.
Data yang akan digunakan adalah jumlah lokasi pelanggan, pelanggan yang memesan, jumlah pesanan tiap pelanggan, dan waktu total pengiriman.
Tahapan input sudah berakhir ketika seluruh data sudah Tahap proses yaitu proses penentuan rute dengan bantuan solver.
Proses pertama yang dilakukan adalah melakukan perhitungan total jumlah pesanan dalam volume dan unit .
Perhitungan dalam volume dihitung dengan menjumlah seluruh pesanan tiap lokasi dengan Selanjutnya, model akan membentuk kromosom untuk menentukan urutan rute untuk dikunjungi terlebih dahulu dan urutan kendaraan untuk digunakan secara random.
Kromosom akan dibentuk sebanyak population size.
Populasi yang sudah terbentuk akan dimutasi dengan jumlah mutasi sebesar 0,075 dari populasi.
Selanjutnya, melakukan perhitungan nilai untuk tiap kromosom awal dan hasil mutasi.
Hendrawan dan Widyadana Jurnal Sistem dan Manajemen Industri Vol 2 No 1 Juli 2018, 1-8 Gambar 1.
Flowchart model HFVRPTW Perhitungan pengecekan ritase lokasi (Pr.
Ritase lokasi akan memiliki nilai 1 jika sudah dikunjungi, dan menyelesaikan urutan rute lokasi selanjutnya.
Ritase lokasi dengan nilai 0 akan dilanjutkan pengiriman dan kapasitas kendaran.
Nilai total waktu perpindahan kendaran ke-w .
dan waktu bongkar lokasi ke-y .
yang sudah dan akan ditempuh kurang dari batas waktu total (T.
akan dilanjutkan pada pengecekkan kapasitas.
Kapasitas kendaraan pada lokasi j (Vk.
lebih besar dari pesanan pada lokasi j rute ke r (Dr.
menunjukkan pengiriman dapat dilakukan dan sisa pesanan (Sr.
bernilai 0 Proses ini akan berulang terus sampai salah satu syarat ini tidak terpenuhi dan membuat kendaraan kembali ke depo .
= .
Selanjutnya dilakukan pemeriksaan terhadap sisa pesanan seluruh lokasi.
Total sisa pesanan (Sr.
O 0, maka kendaraan selanjutnya akan melanjutkan pengiriman pada urutan lokasi yang Hendrawan dan Widyadana sudah terbentuk.
Sebaliknya, perhitungan akan dilanjutkan dengan melakukan perhitungan biaya bahan bakar (O).
Perhitungan yang dilakukan selanjutnya adalah nilai fitness .
/O) tiap kromosom.
Nilai fitness yang sudah dihitung menjadi acuan untuk melakukan seleksi hasil mutasi dengan kromosom pada populasi awal.
Nilai fitness yang lebih baik akan menjadi individu pada populasi Populasi baru yang terbentuk akan dicek nilai konvergensi dan peningkatan yang terjadi.
Populasi yang sudah konvergen dan tidak adanya peningkatan akan membuat proses penentuan rute berakhir.
Sebaliknya, jika tidak terpenuhi maka akan dilakukan mutasi agar syarat terpenuhi.
Model akan dijalankan sebanyak 5 kali untuk melakukan tes konvergensi untuk setiap kasus.
Tujuan tes kovergensi untuk melihat tingkat konvergen dari hasil model HFVRPTW.
Tes konvergensi dilakukan dengan melakukan 5 kali replikasi untuk setiap kasus.
Contoh hasil 5 kali replikasi dapat dilihat pada Tabel 3.
DOI: http://dx.
org/10.
30656/jsmi.
Jurnal Sistem dan Manajemen Industri Vol 2 No 1 Juli 2018, 1-8 Tabel 3.
Contoh hasil 5 kali replikasi Replikasi Biaya (R.
Hasil 5 kali replikasi ini akan dicari nilai coefficients of variations (CV).
Nilai CV merupakan rasio perbedaan antar hasil replikasi yang terbentuk.
Nilai CV didapat dari pembagian nilai standar deviasi dengan rata-rata.
Hasil tes konvergensi dari setiap kasus dapat dilihat pada Tabel 4.
Tabel 4.
Hasil tes konvergensi 3 kasus Kasus 2,2 % Nilai konvergen model yang sudah dibentuk berada diantara 2% - 3%.
Nilai konvergen yang sangat kecil menunjukkan bahwa model dapat Penentuan rute model dilakukan setelah melakukan tes konvergensi.
Nilai replikasi yang digunakan adalah nilai Contoh pemilihan dari hasil replikasi Tabel 2 yang digunakan adalah replikasi kedua.
Rute yang terbentuk akan digambarkan menggunakan bantuan Google Maps.
Rute yang terbentuk akan Hasil penentuan rute dapat dilihat pada Gambar 2.
Hasil penentuan rute model akan dibandingkan dengan rute perusahaan.
Perbandingan ini dilakukan setelah 5 kali replikasi, tes konvergensi, pemilihan nilai replikasi terbaik, dan pembuatan rute menggunakan Google Maps.
Perbandingan kemampuan model menentukan rute.
Gambar 2.
Contoh hasil rute model yang terbentuk DOI: http://dx.
org/10.
30656/jsmi.
Hendrawan dan Widyadana Jurnal Sistem dan Manajemen Industri Vol 2 No 1 Juli 2018, 1-8 Tabel 5.
Hasil penentuan rute model dan perusahaan Penentuan rute Perusahaan Model Kasus Jumlah Rata-rata 86,95 59,56 35,89 90,84 88,59 42,95 Total jarak .
Total bahan bakar .
Biaya bahan bakar (R.
357,45 44,43 59,58 43,86 55,02 82,78 Tabel 5 menunjukkan hasil pembentukkan rute dalam 3 kasus.
Kasus 1 menunjukkan model melakukan penghematan terhadap jumlah kendaraan sebanyak 1 kendaraan serta kasus 2 dan 3 sebanyak 2 kendaraan.
Jumlah kendaraan yang semakin sedikit meningkatkan nilai utilitas tampung kendaraan.
Peningkatan nilai utilitas kapasitas tampung yang lebih maksimal.
Kasus 1 memiliki jarak tempuh dan penggunaan bahan bakar yang lebih sedikit dibanding perusahaan.
Kondisi ini menyebabkan penghematan biaya bahan bakar sebesar Rp 3.
155,00.
kendaraan yang digunakan.
Parameter model menghasilkan nilai konvergen 2-3%.
Hasil penentuan rute model akan menghasilkan penghematan kendaraan dengan selisih rata-rata 1,67 kendaraan.
Model menghasilkan rute yang lebih baik dalam 2 kasus dari 3 kasus Model akan menghasilkan nilai yang lebih baik ketika jumlah pesanan memiliki nilai yang besar.
Pengembangan penelitian yang dapat dilakukan adalah melakukan kluster lokasi.
Kluster pembentukan rute yang lebih sedikit dalam 1 area yang sama.
Kasus peningkatan total jarak tempuh tetapi jumlah bahan bakar yang digunakan lebih sedikit.
Kondisi disebabkan jenis kendaraan yang digunakan pada model lebih baik.
Nilai bahan penghematan biaya bahan bakar sebesar Rp 005,00.
Kasus 3 menunjukkan model memiliki nilai jarak, bahan bakar, dan biaya bahan bakar yang lebih tinggi dibandingkan perusahaan.
Kondisi ini disebabkan model mengharuskan kendaraan melakukan pengiriman hingga kapasitas tampung maksimal.
Penentuan rute perusahaan dilakukan sesuai dengan kebutuhan tanpa ada syarat untuk memenuhi kapasitas.
DAFTAR PUSTAKA