MULTIPLE DEPOT VEHICLE ROUTING PROBLEM WITH BACKHAULS ( MDVRPB ) MENGGUNAKAN ALGORITMA CLARK AND WRIGHT DENGAN 2-OPT DAN PENERAPANNYA
Rizka Rahmawati, Susy Kuspambudi Andaini, dan Trianingsih Eni Lestari Universitas Negeri Malang E-mail:
[email protected] ABSTRAK: MDVRPB merupakan pengembangan dari VRP dengan penambahan kendala dengan kondisi depot sebagai pusat distribusi barang terdapat lebih dari satu dan customer dapat melakukan permintaan berupa pengiriman barang atau berupa pengambilan barang. Permasalahan MDVRPB dapat digambarkan dengan suatu graph. Gambar graph tersebut dianggap sebagai peta yang menjelaskan kemungkinan jalur yang dapat dilewati dengan setiap titik mewakili depot dan customer, setiap sisi menunjukkan jalan yang menghubungkan antar titik dan setiap bobot pada sisi mewakili jarak antara kedua titik tersebut. Salah satu algoritma yang mampu menyelesaikan permasalahan MDVRPB adalah Clark And Wright dengan 2-Opt. Dalam implementasi skripsi ini, Clark And Wright dengan 2-Opt akan diterapkan untuk menyelesaikan permasalahan MDVRPB. Clark And Wright dengan 2-Opt merupakan algoritma berbasis saving dalam mencari rute minimum.Tujuan dari penulisan artikel ini adalah mengetahui penerapan Algoritma Clark And Wright dengan 2-Opt untuk permasalahan MDVRPB dan analisa kerja mengenai permasalahan MDVRPB menggunakan algoritma Clark And Wright dengan 2-Opt Kata kunci : Vehicle Routing Problem(VRP),Multiple Depot Vehicle Routing Problem With Backhauls(MDVRPB), Algoritma Clark and Wright, 2-Opt.
Masalah Distribusi merupakan bagian dari permasalahan penyediaan barang atau jasa dari depot untuk dikirim kepada customer. Permasalahan distribusi dapat diselesaikan dengan konsep Teori Graph sehingga dapat digambarkan secara ringkas, karena dapat menggunakan simbol atau lambang sehingga lebih mudah dipahami dan mudah untuk diselesaikan. Salah satu permasalahan yang dapat diterapkan dalam penyelesaian masalah pendistribusian tersebut yaitu Multiple Depot Vehicle Routing Problem With Backhauls (MDVRPB). MDVRPB merupakan salah satu pengembangan dari permasalahan VRP yang berupa gabungan dari MDVRP dengan VRPB yaitu permasalahan dengan kondisi depot sebagai pusat distribusi barang terdapat lebih dari satu dan customer dapat melakukan permintaan berupa pengiriman atau pengambilan barang. (Min Hokey dkk, 1992:262) Pada artikel ini membahas penyelesaian permasalahan MDVRPB dengan menggunakan Clark And Wright dengan 2-Opt. Clark And Wright dengan 2-Opt merupakan algoritma berbasis saving. Secara umum, nilai saving didefinisikan 0, 0, , , dimana 0, adalah jarak dari depot ke sebagai , customer dan , adalah jarak dari customer ke customer . Pembentukan rute kendaraan dimulai dari customer dan yang memiliki nilai saving terbesar. Setelah diperoleh rute maka akan ada perbaikan tiap rute dengan menggunakan algoritma 2-Opt.Sedangkan penentuan depot yang melayani customer berdasarkan pada perbandingan nilai jarak customer pada depot dan nilai saving terkecil yang mungkin terbentuk pada keseluruhan depot. (Blecha and March, 1992:1)
Formulasi MDVRPB Fungsi tujuan : membentuk rute pendistribusian pada masing–masing depot sehingga diperoleh total jarak tempuh yang minimum. Min 1,
! "# !$!!!# !$ %#&'("# )!#*&'#* " %#&'("# -
Parameter yang digunakan adalah:
0, '#+' ,!#* )! ##,!
Dengan batasan – batasan sebagai berikut: Batasan 1: Setiap customer dikunjungi satu kali oleh satu kendaraan 1
i
C
j
C
1
k
K
7S
k
K
Batasan 2 : Setiap titik yang dikunjungi oleh kendaraan, maka titik tersebut ditinggalkan oleh kendaraan yang sama dan juga sebaliknya. D, k
K
Batasan 3 : Setiap kendaraan berawal dari depot dan kembali pada depot yang sama. 34
Batasan 4 : Total barang yang akan dikirim tidak melebihi kapasitas kendaraan, dan juga pada total barang yang akan diambil oleh kendaraan k 6
9
q
q
7S
k
K
Batasan 5 : Hanya customer bakhauls dilayani setelah seluruh barang pada customer linehauls telah dikirimkan. 6
q
9
Batasan 6 : batasan nilai :0,1;
71
Keterangan : Cij = jarak antara titik i dan j D = Himpunan depot L = Himpunan linehaulcustomer B = Himpunan backhaulcustomer C = Himpunan customer, < = K = Himpunan Kendaraan = Permintaan customer ke-i qi = Kapasitas kendaraan k Sk
k
K
Pembahasan Algoritma Clark And Wright dengan 2-Opt pada MDVRPB Penyelesaian permasalahan MDVRPB dengan menggunakan Clark And Wright dengan 2-Opt melalui beberapa langkah. Langkah – Langkah penyelesaian MDVRPB tersebut berbasis saving. Langkah - langkah yang dimaksud yaitu : 1. Pemilihan depot tiap customer dengan menggunakan penyelesaian MDVRP Penentuan depot pelayanan customer ditentukan oleh 2 hal, yaitu : a) Berdasarkan nilai perbandingan jarak antara customer dengan 2 depot terdekat. Nilai pembanding jarak dengan 2 depot terdekat ini ? , @ didefinisikan:> ? , @@ Dimana , AB menyatakan jarak antara customer i dengan depot terdekat pertama dan , ABB menyatakan jarak terhadap depot terdekat kedua. Sebagai batasan seleksi dari nilai µi ditentukan variabel γ yang bernilai 0 < γ < 1, dan kemudian untuk setiap nilai µ dilakukan perbandingan dengan nilai γ. Jika µi ≤ γ, maka customer i akan dihitung berdasarkan nilai saving yang dilakukan pada langkah selanjutnya. b) Berdasarkan nilai saving antar customer yang terletak pada depot yang sama. Langkah ini dilakukan ketika µi ≥ γ, yaitu dengan menghitung nilai saving customer i dengan seluruh customer yang memungkinkan terbentuknya rute pada tiap depot. Si(j,k) = d(i,j) + d(i,k) – d(j,k) Dimana j dan k adalah titik yang mengapit customer i dalam rute yang akan dihasilkan jika dilayani oleh depot tertentu. Nilai saving Si(j,k) menunjukkan tambahan jarak pada rute yang dihasilkan jika customer i berada dalam rute tersebut. Dan penentuan depot pelayanannya berdasarkan pada nilai minimum saving yang terbentuk. 2. Pembentukan rute tiap depot menggunakan Algoritma Clark and Wright Kumpulan nilai , ini disebut sebagai nilai “saving”, yang mana akan menentukan dalam penggabungan antara titik i dan j tidak dapat digabungkan dalam suatu rute, yaitu jika tidak sesuai dengan kendala-kendala yang ada. Penyelesaian VRP dengan Algoritma Clark-Wright “saving” berbentuk tahap-tahap sebagai berikut: tahap 1 : hitung “saving” , =, =, , untuk setiap C tahap 2 : urutkan semua nilai “saving” dimulai dari nilai yang terbesar hingga nilai yang terkecil. tahap 3 : untuk semua nilai “saving” , , hubungkan titik i dan j menjadi suatu rute, jika memenuhi kapasitas maksimal kendaraan dan jika memenuhi salah satu kondisi berikut: a) Tidak ada titik i maupun j yang terhubung dengan rute b) Salah satu titik i maupun j sudah memiliki rute, dan titik yang memiliki rute tersebut merupakan titik eksternal
c) Kedua titik i, j terdapat dalam rute yang berbeda, dan kedua titik tersebut merupakan titik eksternal dari rute yang telah dimiliki. tahap 4 : jika masih terdapat titik yang belum memiliki rute, ulangi langkah 3 dengan mengambil nilai saving terbesar berikutnya. Dan jika semua titik sudah termasuk dalam rute, maka penyelesaian telah didapatkan. 3. Perbaikan tiap rute menggunakan Algoritma 2-Opt Setelah semua rute telah terbentuk maka dilakukan optimalisasi pada algoritma 2-Opt, dalam algoritma ini terdiri dari 2 optimasi yaitu optimasi pengiriman dan pengambilan barang, pada setiap rute pasti memiliki optimasi pengiriman dan optimasi pengambilan, maka ambil sebarang titik , , 1, dan 1 , jika pada salah satu atau kedua optimasi tersebut terdapat perubahan rute dengan syarat memenuhi , 1, 1 D , 1 , 1 maka perubahan rute dilakukan sehingga diperoleh beberapa rute dengan total jarak tempuh yang lebih minimum dari jarak tempuh pada langkah 2. Jika tidak memenuhi syarat tersebut maka tidak dilakukan perubahan jalur pada rute tersebut. (Englert dkk, 2008:31) Contoh Permasalahan MDVRPB Menggunakan Algoritma Clark And Wright dengan 2-Opt Sebagai gambaran pembahasan permasalahan MDVRPB menggunakan algoritma Clark And Wright dengan 2-Opt, diberikan contoh permasalahan beserta penyelesaiannya yaitu : Misalkan jika terdapat 2 depot dan 5 customer dengan kapasitas kendaraan yang digunakan untuk masing-masing depot sama yaitu 25 Tabel 1 Jumlah Permintaan Barang dan Jenis Customer
No Customer Tipe Permintaan Jumlah (qi) 1 Kirim 5 2 Ambil 7 3 Kirim 6 4 Kirim 5 5 Ambil 9 Terdapat 3 parameter untuk penyelesaian MDVRPB yaitu E, F dan G dimana nilai E 0,50 , F 0,25 dan G 0,70 Tabel 2 Jarak Antar Titik Yaitu Depot dengan Customer dan Jarak Antar Customer
D D1 D2 C1 C2 C3 C4 C5
D1 0 41 50 42 28 72 73
D2 41 0 33 18 70 52 52
C1 33 50 0 62 51 47 49
C2 18 42 62 0 25 25 45
C3 28 70 51 25 0 10 9
C4 72 52 30 25 10 0 5
C5 73 52 49 45 9 5 0
Dari Tabel 2 dapat divisualisasikan sebagai berikut: 3 4
1
2 2
5 1
= Depot = Linehaul customer = Backhaul customer
Gambar 1 Permasalahan MDVRPB
Langkah 1: penyelesaian MDVRP dengan algoritma berbasis saving Untuk setiap customer i, jarak customer terhadap depot terdekat pertama d i , DB dan depot kedua d i , DBB adalah: Tabel 3 Jarak Customer dengan Depot Terdekat Pertama dan Depot Kedua
Customer C1 C2 C3 C4 C5 33 18 28 52 52 d i , DB 50 42 70 72 73 d i , DBB Perbandingan jarak terhadap depot terdekat pertama dan depot terdekat kedua Tabel 4 Perbandingan Jarak Customer dengan Depot
customer C1 C2 C3 C4 C5 0,66 0,42 0,40 0,72 0,71 > Ditentukan nilai G 0,70 sehingga untuk tiap customer yang memenuhi nilai μ 7 0,70 maka customer tersebut ikut depot yang terdekat Tabel 5 Hasil Sementara Penerimaan Customer Oleh Depot
customer C1 C2 C3 C4 C5 Ikut depot 1 1 1 …. …. Dengan nilai saving 5,25 sehingga customer 4 akan dilayani oleh depot 2, dan customer 5 akan dilayani oleh depot 2 dengan nilai saving 6,25 Seluruh customer telah memiliki depot pelayanan, sehingga tahap penyelesaian MDVRP telah selesai. Langkah 2 : pembentukan rute Pada tahap ini dilakukan pembentukan rute pada masing-masing depot sebagai penyelesaian VRPB ditentukan nilai E 0,50 a) Pembentukan rute pada depot 1 Sehinga diperoleh nilai saving setelah diurutkan dapat dilihat dalam tabel berikut : ,
Tabel 6 Pengurutan Nilai Saving pada depot 1
No 1 2 3
3,2 3,1 2,1
Saving
105 10 55
Nilai
Pembentukan rute berdasar nilai saving pada depot 1 adalah sebagai berikut : 1. Saat nilai saving 3,2 , customer 3 dan 2 merupakan customer yang berlainan jenis maka penggabungan rute tidak dilakukan 2. Saat nilai saving 3,1 , customer 3 dan 1 merupakan customer yang sejenis memungkinkan dilayani dalam rute yang sama AN OP ON AN karena kapasitas kendaraan depot 1 mencukupi dimana QP QN 7 R S yaitu 6
5 7 25
3. Saat nilai saving 2,1 , customer 1 telah memiliki rute dan berupa titik eksternal (terletak pada ujung rute) serta kedua customer tersebut merupakan customer yang berlainan jenis, Penggabungan kedua rute ini tidak melanggar batasan dari VRPB maka dilakukan penggabungan rute antar keduanya yang dimulai dari rute pengiriman barang. Rute baru yang terbentuk adalah AN OP ON OU AN dengan kapasitas kendaraan QP QN QU 7 R S yaitu 6 5 7 7 25 Semua titik pada depot 1 telah termasuk dalam rute, Maka pembentukan rute pada depot ini telah selesai dilakukan yaitu AN OP ON OU AN b) Pembentukan rute pada depot 2 Customer yang dilayani oleh depot 2 adalah customer nomor 5 dan 4 Sehinga diperoleh nilai saving setelah diurutkan dapat dilihat dalam tabel berikut :
Nilai No , Saving 1 5,4 98,5 Pembentukan rute berdasar nilai saving pada depot 2 adalah sebagai berikut : Saat nilai saving 5,4 merupakan customer yang berlainan jenis, Penggabungan kedua rute ini tidak melanggar batasan dari VRPB yaitu kapasitas kendaraan depot 2 mencukupi dimana QY QZ 7 R [ yaitu 9 5 7 25 maka dilakukan penggabungan rute antar keduanya yang dimulai dari rute pengiriman barang. Rute baru yang terbentuk adalah AU OZ OY AU Pada langkah ini penyelesaian yang dilakukan menghasilkan 2 buah rute kendaraan yaitu: Depot 1 : rute 1 AN OP ON OU AN Depot 2 : rute 1 AU OZ OY AU Langkah 3 : optimasi rute dengan Algoritma 2-Opt Langkah selanjutnya adalah proses optimasi pada masing-masing rute yang telah terbentuk dengan menggunakan Algoritma 2-Opt. • Optimasi rute 1 pada depot 1 AN OP ON OU AN rute ini merupakan rute bertipe campuran karena rute ini melewati 2 jenis customer, dengan perpindahan jenis customernya berada pada titik ON OU Optimasi dilakukan meliputi 2 proses, yaitu optimasi pada rute pengiriman barang ke linehauls customer dan optimasi pada rute pengambilan barang dari backhauls customer. Optimasi rute pengiriman barang, meliputi rute AN OP ON OU dan Optimasi rute pengambilan barang meliputi rute OP OU AN setelah dilakukan proses perbaikan rute sehingga diperoleh rute AN ON OP OU Tabel 7 Pengurutan Nilai Saving pada depot 2
AN .
Optimasi rute 1 pada depot 2 AU OZ OY AU rute ini merupakan rute bertipe campuran karena rute ini melewati 2 jenis customer, dengan perpindahan jenis customernya berada pada titik OZ OY Optimasi dilakukan meliputi 2 proses, yaitu optimasi pada rute pengiriman barang ke linehauls customer dan optimasi pada rute pengambilan barang dari backhauls customer. 1. Optimasi rute pengiriman barang, meliputi rute AU OZ OY Karena hanya terdapat 3 buah titik sehingga Algoritma 2-Opt tidak dapat dilakukan pada jalur ini. 2. Optimasi rute pengambilan barang, meliputi rute OZ OY AU Karena hanya terdapat 3 buah titik sehingga Algoritma 2-Opt tidak dapat dilakukan pada jalur ini. Sehingga rute yang diperoleh pada depot 2 adalah AU OZ OY AU Hasil akhir penyelesaian MDVRPB pada contoh 1 : Diperoleh hasil 2 buah rute kendaraan dengan jarak total 253 Rute tiap kendaraan ditunjukkan sebagai berikut : - Depot 1 : rute 1 AN ON OP OU AN dengan jarak tempuh 144 - Depot 2 : rute 1 AU OZ OY AU dengan jarak tempuh 109 •
3
4
1
2 2 5 1 Gambar 2 Hasil Penyelesaian MDVRPB
Analisa algoritma Clark And Wright dengan 2-Opt pada MDVRPB Permasalahan MDVRPB menggunakan algoritma Clark And Wright dengan 2Opt. Dimulai dengan pengelompokan customer pada tiap depot yaitu dengan membandingkan jarak terdekat pertama dan kedua antara setiap customer dengan depot, masing-masing disimbolkan dengan , AB dan , ABB . Selanjutnya
dihitung nilai > ? , @@ , dipilih nilai G dengan syarat 0 D G D 1 yang memenuhi > 7 G, sehingga pengelompokan customer pada tiap depot tepat dan dapat menghasilkan jarak total rute kendaraan dan jumlah kendaraan yang minimum. Jika telah terpilih G sedemikian sehingga ada > ^ G. Sehingga ada customer yang belum mendapatkan depot, maka customer tersebut dapat ditentukan depotnya dengan melakukan satu langkah lagi yaitu penambahan saving dengan memilih nilai F sedemikian sehingga 0 D F D 1 untuk customer yang berbeda jenis, dan memilih nilai F 0 untuk customer sejenis, dan untuk pemilihan G sedemikian sehingga ada > ^ G dapat menyebabkan pertambahan jarak total rute kendaraan dan jumlah kendaraan yang diperlukan untuk melayani customer, sehingga jarak tempuh kendaraan menjadi tidak optimal. Setelah semua customer mendapat pengelompokan depot, selanjutnya dilakukan pembentukan rute pada masing – masing depot dengan menghitung ?\ , @ ]
nilai saving, baik saving sejenis maupun tidak sejenis, lalu diurutkan dari nilai terbesar ke nilai terkecil. Kemudian dilakukan pembentukan rute sesuai dengan urutan nilai saving, jadi diperoleh rute pada masing – masing depot. Selanjutnya dilakukan perbaikan rute, yang terdiri dari optimasi pengiriman dan pengambilan barang. sehingga diperoleh rute dengan total jarak tempuh minimum. Kesimpulan dan Saran Kesimpulan 1. Permasalahan Multiple Depot Vehicle Routing Problem With Backhauls (MDVRPB) merupakan salah satu pengembangan dari permasalahan VRP yang berupa gabungan dari MDVRP dengan VRPB yaitu permasalahan dengan kondisi depot sebagai pusat distribusi barang terdapat lebih dari satu, dan customer dapat melakukan permintaan berupa pengiriman atau pengambilan barang. Permasalahan tersebut dapat diselesaikan dengan Algoritma Clark And Wright dengan 2-Opt. Pencarian solusi dimulai dengan pengelompokan customer pada depot, dengan cara perbandingan jarak terhadap depot terdekat pertama dan depot terdekat kedua sehingga terbentuk suatu himpunan depot beserta customer – customernya. Setelah semua customer mendapat pengelompokan depot, selanjutnya dilakukan pembentukan rute pada masing – masing depot. Dengan menghitung nilai saving, baik saving sejenis maupun tidak sejenis, lalu diurutkan dari nilai terbesar ke nilai terkecil. Langkah selanjutnya dilakukan pembentukan rute sesuai dengan urutan nilai saving, jadi diperoleh rute pada masing – masing depot. Selanjutnya dilakukan perbaikan rute, yang terdiri dari optimasi pengiriman dan pengambilan barang. sehingga diperoleh rute dengan total jarak tempuh minimum. 2. Analisa mengenai permasalahan Multiple Depot Vehicle Routing Problem With Backhauls menggunakan Algoritma Clark And Wright dengan 2-Opt yaitu nilai > yang dihasilkan mempengaruhi pengelompokan customer pada depot. Jika > D G maka rute menjadi optimal. Jika > C G maka terdapat perbedaan pada pemilihan G terhadap pengelompokan customer akibatnya jumlah customer dengan penentuan depot menggunakan penambah saving semakin banyak sehingga pengelompokan customer dalam menentukan pelayanan depot kurang tepat. Hal tersebut berpengaruh terhadap total jarak tempuh yang diperoleh. Saran 1. Penerapan persoalan MDVRPB dengan Algoritma Clark and Wright dengan 2-Opt pada permasalahan yang lebih kompleks dengan jumlah titik yang banyak, dapat dipermudah dengan menggunakan alat bantu, bagi yang ingin mengembangkannya dapat menggunakan program komputer. 2. Bagi yang ingin menyelesaikan permasalahan MDVRPB dengan menggunakan metode lain dapat menggunakan algoritma Insertion Heuristic dan algoritma Tabu Search serta metode Metaheuristic. 3. Bagi yang ingin mengembangkan penerapan MDVRPB dapat menggunakan permasalahan MP-MDVRPB (Multi Product-Multiple Depot Vehicle Routing Problem With Backhauls) dimana MDVRPB terdapat penambahan kendala lebih dari satu produk, sedangkan pada skripsi ini hanya menggunakan satu
produk saja, sehingga pada perkembangan permasalahan diatas dapat digunakan lebih dari satu produk. Daftar Rujukan Blecha , Jacobs Chrlotte dan March Goetschalckx. 1992. the Vehicle Routing Problem with Backhauls: Properties and Solution Algorithms, (Online), (http://neo.lcc.uma.es/radi-aeb/WebVRP/data/articles/VRPB.pdf, diakses 17 September 2012). Englert, Mattias, Heiko Roglin and Bertold Vocking. 2008. Wort Case and Probabylistic Analysis of the 2-Opf Algoritm the TSP, (Online), (http://www.dcs.warwick.ac.uk/~englert/publications/tsp_soda07_full.pdf, diakses 17 September 2012). Min,H.,J.Current, and D.Schilling. 1992. The Multiple Depot Vehicle Routing Problem With Backhauling, (Online), (http://140.113.119.114/Thesis/thesis/097/1/Literature/VRPB/1992The%20multiple%20depot%20vehicle%20routing%20problem%20with% 20backhauling.pdf, diakses 17 September 2012).
Artikel oleh Rizka Rahmawati ini telah diperiksa dan disetujui pada tanggal Januari 2013
Pembimbing I
Dra. Susy Kuspambudi A., M.Kom. NIP. 19590419 198812 2 001
Pembimbing I I
Trianingsih Eni Lestari, S.Si,M.Si. NIP 19830101 200501 2 001
Mahasiswa
Rizka Rahmawati NIM 308312410095
