A. BACKGROUNDPada saat ini, banyak perusahaan besar mulai menyadari pentingnya penerapan Supply Chain Management. SCM merupakan suatu konsep yang menyangkut pola pendistribusian produk yang mampu menggantikan pola-pola pendistribusian produk secara tradisional. Pola baru ini menyangkut aktivitas pendistribusian, jadwal produksi, dan logistik. Perusahaan mampu mengurangi biaya yang harus mereka keluarkan melalui penggunaan subcontractors dan shared transportation. Hal ini dilakukan karena standar hidup konsumen yang semakin tinggi, yang menyebabkan konsumen semakin menuntut ketepatan pengiriman produk. Untuk itu, perencanaan rute pengiriman produk harus dilakukan secara tepat. Selain itu, perencanaan rute pengiriman juga harus mempertimbangkan time windows konsumen untuk menghindari waktu tunggu hingga time windows yang diizinkan. Untuk itu perlu dilakukan perhitungan Vehicle Routing Problems with Time Window (VRPTW) untuk mendapatkan pemilihan rute terpendek dan jumlah kendaraan distribusi yang minimal, dengan memperhatikan batasan kapasitas kendaraan distribusi dan time windows konsumen. VRPTW merupakan permasalahan yang kompleks karena melibatkan banyak faktor yang harus dipertimbangkan dan terdapat sejumlah kemungkinan permutasi dan kombinasi. Untuk itu perlu dikembangkan model yang mampu menyelesaikan permasalahan tersebut secara cepat dan efisien, serta tanpa terjebak dalam solusi local optimal, yaitu melalui Simulated Annealing yang dikombinasikan dengan local search.

B. PROBLEM DEFINITIONPada penelitian ini dilakukan perhitungan pencarian rute terpendek dari satu depot ke sejumlah 100 konsumen dengan mempertimbangkan kapasitas kendaraan distribusi dan time windows konsumen. Metode yang digunakan adalah metode metaheuristik dengan algoritma Simulated Annealing yang dikombinasikan dengan local search untuk penyelesaian permasalahan VRPTW ini. Hasil penelitian yang didapatkan akan dibandingkan dengan penelitian-penelitian sebelumnya.

C. THEORY1. VEHICLE ROUTING PROBLEMPermasalahan penentuan rute distribusi sering disebut sebagai Vehicle Routing Problem diperkenalkan pertama kali oleh Dantzig dan Ramzer, yaitu sejumlah kuantitas demand di dikirimkan untuk masing-masing konsumen i N = {1, ..., n} dari depot pusat {0} menggunakan k kendaraan distribusi independen dengan kapasitas yang sama C. Pengiriman diselesaikan dengan total biaya yang minimum, yaitu cij 0, yang ditunjukkan oleh biaya transit dari i ke j, untuk 0 i, j n. Struktur biaya diasumsikan simetris, yaitu cij = cji dan cii = 0. Varian dari VRP di antaranya adalahVRP dengan Time windows (VRPTW), yaitu permasahan VRP dengan batasan kapasitas kendaraan distribusi dan time windows konsumen. Jika waktu kedatangan kendaraan distribusi lebih awal dari time windows, maka kendaraan distribusi harus menunggu pengiriman hingga time windows konsumen. Sedangkan total berat yang diangkut kendaraan distribusi tidak boleh melampui kapasitas maksimal kendaraan distribusi, serta kendaraan distribusi harus kembali ke depot dalam rentang waktu yang sudah ditetapkan.

2. SIMULATED ANNEALINGSimulated Annealing adalah salah satu algoritma di dalam metode metaheuristik. Simulated Annealing merupakan optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir kristal atau logam. Ide dasar dari dari algoritma SA ini bermula dari konsep Annealing, yaitu jika suatu materi dipanaskan hingga mencair, kemudian didinginkan secara perlahan maka akan dihasilkan kristal kristal dengan kualitas baik. Sebaliknya, jika materi didinginkan terlalu cepat, maka kristal yang dihasilkan pun tidak akan sempurna. Konsep ini yang kemudian diadaptasi oleh SA untuk menyelesaikan beragam permasalahan optimasi.SA juga menggunakan persamaan Boltzman dalam sistem termodinamika. Persamaan ini merepresentasikan probabilitas suatu new state lebih buruk dari current state masih mungkin terpilih sebagai next state. Berikut adalah persamaan dari probabilitas yang digunakan :

Dalam persamaan tersebut, k adalah konstanta Boltzman, T adalah temperatur dan r adalah bilangan acak antara 0 dan 1. Sedangkan fungsi biaya, direpresentasikan dengan nilai delta energi. Semakin kecil temperatur (T), maka probabilitasnya pun akan semakin kecil. Berbeda dengan temperatur, nilai delta energi yang semakin besar akan membuat probabilitas semakin kecil. Probabilitas yang semakin kecil menandakan bahwa kemungkinan terpilihnya suatu new state dengan biaya yang lebih besar dari current state akan semakin kecil.

D. METHODOLOGYModel matematis dari permasalahan VRPTW adalah sebagai berikut :......(1)

......(2)

......(3)

......(4)

......(5)

......(6)

......(7)......(8)

......(9)....(10)

Keterangan :Variabel keputusan :ti = arrival time pada customer iwi= waiting time pada customer ixijk = 1 jika vehicle k melakukan pengiriman dari customer i ke customer dan 0 jika sebaliknya (i j; i,j=0; 1, ..., N)Parameter :V= total jumlah vehiclesN= total jumlah customerci= customer ke i (i=1, ..., N)c0= delivery depotcij= jarak pengiriman dari customer i ke customer jtij= waktu pengiriman dari customer i ke customer jmi= demand customer iqi= kapasitas vehicle vPersamaan 1 menunjukkan fungsi tujuan dari permasalahan yaitu meminimalkan total jarak pengiriman. Persamaan 2 merupakan batasan maksimal jumlah rute V yang dapat dilakukan karena adanya batasan vehicle yang dimiliki. Persamaan 3 merupakan batasan yang memastikan setiap rute dimulai dan diakhiri pada depot pusat. Persamaan 4 dan 5 membatasi penugasan untuk setiap customer hanya dilayani satu vehicle dalam satu rute. Persamaan 6 menunjukkan batasan kapasitas vehicle yang tidak dapat dilanggar. Persamaan 7 menunjukkan batasan maksimal waktu perjalanan. Persamaan 8, 9, dan 10 meunjukkan batasan time windows yang harus dipenuhi.Untuk analisa penggunaan Simulated Annealing (SA) yang dikombinasikan dengan pencarian lokal dimulai dengan melakukan sequential insertion heuristik sebagai solusi awal. Kemudian dengan menggunakan algoritma pencarian lokal untuk optimasi rute. Metode pencarian lokal yang dapat digunakan adalah dengan 2 optional exchange atau insertion. Pemilihan salah satu metode pencarian lokal ini berdasarkan nilai probabilitas dari informasi yang diperoleh (Certainty Probability) sehingga ditemukan sebuah solusi baru. Solusi baru yang diperoleh akan dievaluasi apakah melanggar ketentuan yang ditetapkan mengenai time window dan kapasitas kendaraan. Apabila tidak melanggar ketentuan yang ditetapkan maka dapat kita simpan sebagai feasible solution, tetapi bila sebaliknya maka akan dilakukan modifikasi dari fungsi tujuan untuk memperoleh feasible solution yang telah ditetapkan menjadi Cost(S) = C1N + C2P(S) + C3Dist(S)Weight Factor C1 >> C2 >> C3Dimana N merupakan jumlah kendaraan yang digunakan, P(S) merupakan derajat pelanggaran yang dilakukan terhadap constraint, dan Dist(S) merupakan jarak yang ditempuh kendaraan. Sedangkan C1, C2, dan C3 merupakan faktor penalty.Feasible solution yang telah diperoleh akan dibandingkan dengan solusi awal. Apabila lebih baik dibandingkan solusi awal maka akan menjadi kandidat untuk solusi selanjutnya, tetapi bila sebaliknya akan dilakukan uji metropolis dengan menetapkan nilai r dari bilangan random dan mengkaji probabilitas dengan persamaan berikutP(E) = exp (-E/T)Probabilitas merupakan nilai eksponensial dari selisih energy yang berbanding terbalik dengan temperatur. Selanjutnya apabila nilai probabilitas yang diperoleh lebih baik dibandingkan dengan nilai r yang ditetapkan maka akan menjadi kandidat untuk solusi selanjutnya, tetapi bila sebaliknya maka digunakan solusi awal dan akan dievaluasi kembali apakah telah memenuhi kriteria, apabila telah mencapai kriteria maka proses selesai, tetapi bila sebaliknya belum mencapai kriteria yang ditetapkan maka ulangi kembali ke tahapan awal dengan pencarian lokal. Disamping itu juga dilakukan kajian untuk solusi selanjutnya dan akan terjadi proses replacing untuk mempertahankan solusi selanjutnya yang memiliki nilai terbaik dan proses pencarian selesai.Flowchart penggunaan SA yang dikombinasikan dengan local search dapat dilihat pada gambar 1.

Gambar 1 Flowchart SA dan Local Search

Gambar 1 Flowchart SA dan Local Search (lanjutan)

E. RESULTModel yang dikembangkan yaitu menggunakan bahasa pemrograman C yang dioperasikan dengan komputer Pentium IV 3,0G MHz CPU, 512 MB memory, dan Windows XP Operating System. Untuk menguji tingkat keefektivitasan model yang dikembangkan maka dilakukan benchmark dengan menggunakan penelitian dari Solomon sebagai contoh. Hasil yang didapatkan kemudian dibandingkan dengan hasil dari penelitian-penelitian sebelumnya. Contoh permasalahan yang diambil pada Solomon dibagi menjadi ke dalam 6 dataset, yaitu C1, C2, R1, R2, RC1, dan RC2. Dalam set C, permasalahan sudah dilakukan clustering pada konsumen berdasarkan time windows. Dalam set R, lokasi konsumen dibangkitkan secara random uniform. Dalam set RC, merupakan kombinasi secara random dari lokasi dan cluster konsumen berdasarkan time windows. Problem set jenis 1 memiliki time windows dan kapasitas vehicle yang lebih kecil, sedangkan problem set 2 memiliki time windows dan kapasitas vehicle yang lebih besar. Pada eksperimen awal, parameter yang digunakan adalah T0=100, C iter=10.000, =0,99, dan TF=0,1. Tiap permasalahan diselesaikan sebanyak 15 kali running, kemudian dipilih salah satu yang memiliki nilai fungsi tujuan terbaik. Waktu komputasi yang dibutuhkan dalam sekali running yaitu antara 220 hingga 240 detik.Hasil penelitian yaitu jumlah vehicles dan travel distance dibandingkan dengan penelitian-penelitian terdahulu yang menggunakan metode metaheuristik lainnya, seperti yang ditunjukkan pada tabel 1. Berdasarkan perbandingan yang dilakukan, diketahui bahwa model yang dikembangkan mampu menyelesaikan permasalahan VRPTW dengan efektif. Dari model yang dikembangkan didapatkan hasil terbaik pada semua permasalahan dalam set C1 dan set C2, dibandingkan hasil penelitian lainnya. Sedangkan pada set R1, R2, RC1, dan RC2, hasil perhitungan jumlah vehicle dan travel distance sama dengan atau mendekati hasil penelitian lainnya.

Tabel 1 Perbandingan Rata-Rata Hasil Terbaik

F. CONCLUSIONPenelitian yang dilakukan mencoba mengembangkan model, melalui penggunaan sequential insertion heuristic untuk mencapai initial feasible solution pada VRPTW, kemudian digunakan algoritma SA yang dikombinasikan dengan local search untuk mencapai solusi global optimal. Hasil dari penggunaan model untuk contoh permasalahan pada Solomon didapatkan set C1 dan C2 mampu mencapai hasil terbaik dibandingkan dengan penelitian-penelitian dengan metode metaheuristik lainnya. Sehingga dapat disimpulkan bahwa model yang dikembangkan mampu mencapai nilai solusi yang mendekati global optimal secara efektif dalam rentang waktu yang masuk akal. Untuk selanjutnya, teknik local search dari model yang dikembangkan dapat juga diaplikasikan pada varian masalah VRP lainnya maupun untuk algoritma metode metaheuristik lainnya.

G. REFERENCELin, S. W., Ying, K. C., Lee., Z. J., dan Chen, H. S., 2006, Vehicle Routing Problems with Time windows Using Simulated Annealing, IEEE International Conference on Systems, Man, and Cybernetics, October 8-11, 2006, Taipei, Taiwan.Hindriyanto, D. P., 2014, Cara Mudah Belajar Metode Optimisasi Metaheuristik Menggunakan MATLAB, Gava Media, Yogyakarta.

TUGAS MATA KULIAH METAHEURISTIKJOURNAL REVIEWVEHICLE ROUTING PROBLEMS WITH TIME WINDOWS USING SIMULATED ANNEALING(Oleh : S.-W. Lin, K.-C. Ying, Z.-J. Lee and H.-S. Chen)

Disusun oleh :

1. AHMAD F.A 3594071. MHD. ANDRY KURNIAWAN31. OGGIE ALIF A.31. WANDHANSARI SEKAR J359543

PROGRAM STUDI PASCASARJANA TEKNIK INDUSTRIJURUSAN TEKNIK MESIN DAN INDUSTRIFAKULTAS TEKNIK UNIVERSITAS GADJAH MADAYOGYAKARTA 2014