ALGORITMA HARMONY SEARCH DALAM OPTIMALISASI VEHICLE ROUTING PROBLEM WITH TIME WINDOW (VRPTW) Irinne Puspitasari1 , Purwanto2 Email :
[email protected] JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI MALANG
ABSTRAK Masalah pendistribusian yang sering digunakan oleh masyarakat dewasa ini adalah permasalahan mengenai Vehicle Routing Problem (VRP). Menurut Machado dkk.(2002), Vehicle Routing Problem merupakan penggabungan dari dua model yaitu Travelling Salesman Problem (TSP) dengan Bin Packing Problem (BPP).Salah satu cabang dari VRP adalah VRPTW ( Vehicle Routing Problem with Time Window). VRPTW merupakan perluasan dari permasalahan VRP yang diberi tambahan time window. Harmony Search merupakan suatu algoritma metaheuristic yangterispirasi oleh pencarian harmoni terbaik oleh para pemain musik. Penelitian tentang aplikasi Harmony Search untuk VRP telah dilakukan oleh , namun pada penelitian tersebut belum dijelaskan secara detail bagaimana model dan bentuk penyelesaian algoritma yang dibangun. Pada penelitian ini akan dijelaskan secara detail tentang algoritma Harmony Search dalam proses penyelesaian Vehicle Routing Problem with Time Window. Penerapan yang dilakukan terhadap beberapa contoh kasus VRPTW yang diberikan yakni contoh kasus dengan 8 titik dan 10 titik, Harmony Search mampu memberikan hasil akhir rute yang lebih beragam sehingga kemungkinan menemukan solusi optimal akan lebih besar, akan tetapi tidak mampu memberikan jaminan akan menemukan rute akhir yang paling optimum dengan kata lain tidak mampu menjamin penemuan global optimum.
Kata Kunci : metaheuristic, Harmony Search, memori harmoni.
Masalah pendistribusian yang sering digunakan oleh masyarakat dewasa ini adalah permasalahan mengenai Vehicle Routing Problem (VRP). Menurut Machado dkk.(2002), VRP merupakan penggabungan dari dua model yaitu Travelling Salesman Problem (TSP) dengan Bin Packing Problem (BPP). TSP adalah model yang digunakan untuk mencari biaya dari jarak tempuh minimum pada perjalanan dari depot ke pelanggan. Sedangkan BPP adalah model penyelesaian tentang pengaturan penempatan barang pada suatu penyimpan barang. Tujuan yang ingin dicapai adalah mencari biaya transportasi minimum dengan armada kendaraan yang memiliki kapasitas yang bervariasi dengan tujuan pengiriman yang bervariasi sesuai dengan permintaan pelanggan. Salah satu cabang dari VRP adalah VRPTW ( Vehicle Routing Problem with Time Window). VRP ini memiliki perbedaan lain dengan VRP lain dikarenakan adanya penambahan time window pada masing-masing customer untuk dapat menerima barang.
1. Irinne Puspitasari adalah mahasiswa jurusan Matematika FMIPA Universitas Negeri Malang 2. Purwanto adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang
Harmony Search merupakan suatu algoritma metaheuristic yang terinspirasi oleh proses pencarian harmoni terbaik oleh para pemain musik. Dalam proses pencarian harmoni terbaik, algoritma Harmony Search memiliki langkah inisialisasi memori harmoni. Tahap ini memiliki kelebihan yaitu mampu secara serempak menemukan beberapa susunan kombinasi titik dari rute awal yang mungkin didapatkan dari rute awal yang diberikan. Penelitian yang telah dilakukan tentang aplikasi Harmony Search untuk VRP (Geem et al,2005), belum menjelaskan secara mendetail tentang model dan bentuk penyelesaian algoritma yang dibangun. Pada penelitian ini akan diidentifikasi langkah-langkah algoritma Harmony Search untuk VRPTW secara rinci dan diterapkan dalam beberapa contoh kasus yang selanjutnya akan dibandingkan dengan algoritma Tabu Search. Perbandingan dilakukan terhadap algoritma Tabu Search karena pada penelitian tentang VRPTW (Vehicle Routing Problem With Time Window) yang sudah dilakukan sebelumnya dengan menggunakan beberapa algoritma diantaranya adalah algoritma Nearest Insertion Heuristic dan Clark and Wright, Tabu Search mampu memberikan hasil yang lebih baik. HASIL DAN PEMBAHASAN Pada tulisan ini, istilah dan definisi yang digunakan merujuk pada Aldous(2004). Graph adalah sekumpulan himpunan titik, yang disebut verteks dan himpunan garis yang disebut sisi. Setiap sisi menghubungkan tepat dua titik. Titik – titik pada graph dapat merupakan obyek sembarang seperti kota, atomatom suatu zat, nama anak, jenis buah, komponen alat elektronik dan sebagainya. Busur dapat menunjukkan hubungan (relasi) sembarang seperti rute penerbangan, jalan raya, sambungan telepon, ikatan kimia, dan lain-lain. Notasi graph: artinya graph memiliki himpunan titik dan himpunan sisi. Graph yang digunakan untuk menyelesaikan permasalahan VRPTW adalah graph komplit yakni suatu graph dimana setiap titik berbeda terhubung oleh tepat satu sisi. Vehicle Routing Problem with Time Window (VRPTW) VRPTW adalah permasalahan tentang depot sebagai pusat distribusi barang, dengan sejumlah kendaraan berkapasitas tertentu melayani sejumlah customer pada titik-titik lokasi terpisah, dengan permintaan dan batasan time window tertentu, dengan tujuan meminimalkan total biaya perjalanan, tanpa mengabaikan batasan kapasitas kendaraan dan time window depot. Desain rute dilakukan sedemikian hingga setiap customer hanya dikunjungi sekali oleh satu kendaraan, dan setiap kendaraan memulai dan mengakhiri rutenya pada depot. Vehicle Routing Problem with Time Windows (VRPTW) dapat didefinisikan pada graph sebagai berikut: Misal adalah suatu graph komplit dimana adalah himpunan titik dan adalah himpunan sisi, dengan . Jika , maka mungkin untuk melakukan perjalanan dari ke , dengan waktu tempuh tij.Titik 0 adalah suatu depot. Dalam permasalahan distribusi adalah himpunan kendaraan yang digunakan. Sedangkan titik pada himpunan merepresentasikan himpunan customer yang akan dilayani. Setiap dari customer
tersebut memiliki permintaan dan merupakan maximum waktu tempuh yang disediakan oleh perusahaan. Untuk mempermudah dalam memahami permasalahan rute kendaraan pada periode perencaan tertentu dengan time windows, maka akan dijelaskan beberapa deskripsi permasalahnya. Objective/Sasaran : Sasaran dalam VRPTW adalah untuk menentukan rute optimum kendaraan sehingga dapat meminimalisasikan jumlah waktu pengiriman barang dari semua rute. Feasibility/Kelayakan : Jumlah permintaan tiap rute tidak boleh melampaui kapasitas kendaraan, waktu tempuh setiap rute tidak boleh melampaui waktu yang telah ditentukan. Algoritma Harmony Search Untuk VRPTW Algoritma HS disusun dengan merumuskan 5 langkah yang terinspirasi oleh proses pencarian harmoni terbaik oleh para pemain musik yaitu, inisialisasi parameter, inisialisasi memori harmoni, improvisasi harmoni baru, update memori harmoni, dan cek kriteria pemberhentian. Berikut adalah langkah-langkah Harmony Search untuk menyelesaikan VRPTW. 1. Inisialisasi parameter Pada tahap ini akan dicari jarak dari depot ke pelanggan ataupun pelanggan ke pelanggan, waktu total melayani setiap pelayanan ,time window,kapasitas maksimum kendaraan,kecepatan rata-rata kendaraan,rute kluster yakni rute solusi awal yang dibangun dengan algoritma Clark and Wright,HMS (Harmony Memory Size),HMCR (Harmony Memory Consideration Rate) ,PAR (Pitch Adjustment Rate) dan NI (Nilai Iterasi). 2. Inisialisasi memori rute Dalam tahap penentuan memori rute, yang dilakukan adalah menghasilkan rute-rute yang diacak dari rute kluster yang sudah dihasilkan pada tahap pembangkitan rute kluster. Memori rute (HM) sendiri adalah kumpulan dari hasil random rute kluster yang masing – masing hasil random tersebut dinamakan dengan vektor rute memori. 3. Improvisasi rute baru Pada tahap ini yang dilakukan adalah mengimprovisasi rute yang sudah dibentuk dalam HM, yakni dengan jalan membentuk vektor memori rute baru dengan menggunakan parameter HMCR dan PAR dengan ketentuan sebagai berikut : a. b.
(3) (4)
4. Update memori rute Pada tahap ini dilakukan perhitungan nilai fungsi objektif pada vektor memori rute baru. Jika hasil perhitungan vektor rute baru menghasilkan nilai fungsi objektif yang lebih baik daripada vektor memori rute terburuk di HM, maka vektor memori rute baru akan dimasukkan ke dalam HM dan vektor memori rute terburuk dalam HM dikeluarkan dari HM. 5. Pembehentian
Pemberhentian merupakan langkah dimana jika jumlah iterasi (NI) sudah dipenuhi, maka perhitungan berhenti, jika tidak dilanjutkan ke langkah ke – 3 dan ke – 4. Contoh Vehicle Routing Problem With Time Window (VRPTW) dengan Algoritma Harmony Search PT Ongkowidjojo melakukan pendistribusian dengan PT Ongkowidjojo sebagai titik pusat pengiriman (depot), sedangkan agen-agen sebagai titik yang lainnya. Dari semua titik tersebut saling terhubung. Kapasitas kendaraan adalah 275 dus, pelayanan untuk setiap satuan barang adalah 15 detik atau 0,004167 jam, dan waktu maksimal pendistribusian adalah 168 jam. Kecepatan kendaraan yang digunakan adalah 60 km /jam. Berikut data permintaan pelanggan, jarak dari depot ke pelanggan atau pelanggan ke pelanggan dan waktu pelayanan yang diperlukan. Tabel 1. Permintaan pelanggan Lokasi Jumlah permintaan(dalam Dus) Jember 30 Surabaya 100 Kraksaan 120 Bangkalan 275 Sumenep 1 275 Sumenep 2 25 Pamekasan 230 Tabel 2. Jarak antar depot dan pelanggan 0 1 2 3 0 176 97,2 114 0 176 0 199 107 1 97,2 199 0 128 2 114 107 128 0 3 131 228 36,1 157 4 264 362 170 291 5 265 363 171 292 6 211 308 116 238 7 Tabel 3. Waktu pelayanan 0 1 2 0 3,3 2,04 0 3,3 0 3,73 1 2,04 3,73 0 2 1,77 2,28 2,63 3 3,33 4,95 1,75 4 5,35 7,18 3,98 5 4,52 6,15 2,95 6 4,48 6,09 2,59 7
3 1,77 2,28 2,63 0 3,76 5,99 4,97 4,93
4 131 228 36,1 157 0 147 148 94,8
4 3,33 4,95 1,75 3,76 0 3,96 2,57 2,54
5 5,35 7,18 3,98 5,99 3,96 0 0,12 1,86
5 264 362 170 291 147 0 1 53,6
6 4,52 6,15 2,95 4,97 2,57 0,12 0 1,87
6 265 363 171 292 148 1 0 54,6
7 4,48 6,09 2,59 4,93 2,54 1,86 1,87 0
7 211 308 116 238 94,8 53,6 54,6 0
Dengan rute kluster yang diperoleh menggunakan algoritma Clark and Wright.(Arifin, 2012). HMCR 0,4, PAR 0,016, HMS = 4, NI atau jumlah iterasi yang digunakan satu iterasi dan fungsi objektif yang menghitung total jarak, diperoleh solusi berikut : 1) dengan total jarak 530,6 km dan waktu pelayanan 6,39 jam. 2) dengan total jarak 508,2 km dan waktu pelayanan 7,97 jam 3) dengan total jarak 262 km dan waktu pelayanan 3,33 jam. 4) dengan total jarak 52 km dan waktu pelayanan 5,35 jam. Sehingga total jarak yang ditempuh oleh kendaraan pengangkut adalah 1352,8km, dengan total waktu yang diperlukan adalah 23,04 jam. Selain contoh di atas, terdapat contoh lain yakni contoh dengan 8 pelanggan dan 10 pelanggan yang dibandingkan, hasil yang didapatkan diberikan pada tabel berikut : Tabel 4. Perbandingan solusi dengan algoritma Harmony Search dan Tabu Search
contoh algoritma
rute
HS
0-6-2-1-0 0-5-4-3-0 0-7-0 0-8-0 0-6-1-5-4-0 0-3-2-0 0-7-0 0-8-0 0-6-7-1-3-8-4-10-0 0-2-5-9-0
TS
0-10-9-5-2-6-7-1-30-8-4-0
HS 2 TS
3
Total jarak
Waktu
3,96 jam 1,11 jam 257,02 km 9,19 jam 9,29 jam 3,63 jam 1,22 jam 270,68 km 9,19 jam 9,29 jam 0,82 jam 21,3 km 0,29 jam 0,7 jam 24,4 km 0,3 jam
Total waktu 23,55 jam
23,33 jam
1,11 jam
1 jam
Dari tabel di atas bisa dilihat bahwa pada kedua contoh, baik contoh 1 maupun contoh 2, jika dilihat dari waktu total pelayanan, algoritma Harmony Search tidak memberikan hasil yang lebih baik dari algoritma Tabu Search. Hal ini disebabkan oleh proses iterasi yang dilakukan sedikit, sehingga hasil random rute yang diperoleh menjadi terbatas. Akan tetapi jika dilihat dari jarak tempuh total algoritma Harmony Search memberikan hasil yang lebih baik dari algoritma Tabu Search. PENUTUP Kesimpulan Berdasarkan pembahasan diperoleh kesimpulan sebagai berikut: Langkah – langkah Algoritma Harmony Search yang digunakan untuk menyelesaikan VRPTW adalah pertama inisialisasi parameter, yakni proses penentuan semua parameter yang akan digunakan dalam Harmony Search dan pembangkitan rute kluster atau rute solusi awal dengan menggunakan Clark and
Wright. Kedua inisialisasi memori rute, yakni proses perandoman rute kluster yang akan disimpan dalam memori rute untuk diproses pada tahap berikutnya. Ketiga adalah improvisasi memori rute, yakni proses pembentukan vektor memori rute baru dengan menggunakan parameter HMCR dan PAR. Keempat adalah update atau memperbarui memori rute dengan cara menghitung nilai fungsi obyektif dari vektor memori rute baru dan kemudian membandingkannya dengan vektor memori rute terburuk dalam memori rute. Jika lebih baik, maka vektor memori rute baru akan menggantikan vektor memori rute terburuk. Terakhir adalah pemberhentian, yakni tahap jika nilai iterasi maksimum sudah terpenuhi, maka perhitungan berhenti. Perbandingan hasil perhitungan dengan menggunakan algoritma Harmony Search dan Tabu Search pada penerapan terhadap dua contoh, pertama dengan contoh kasus pada 8 pelanggan dan kedua contoh kasus dengan 10 pelanggan, Harmony Search belum memberikan rute solusi dengan waktu pelayanan lebih pendek jika dibandingkan dengan algoritma Tabu Search. Penyebab dari hal tersebut adalah proses iterasi yang singkat. Akan tetapi dengan adanya penambahan fungsi obyektif pada Harmony Search mampu memberikan hasil yakni total jarak tempuh yang lebih baik dari Tabu Search Saran Algoritma Harmony Search merupakan algoritma evolusioner yang ditemukan pada tahun 2005 dan sudah banyak diterapkan dalam berbagai permasalahan sehari-hari dan ternyata mampu menghasilkan hasil yang lebih optimum. Dalam kesempatan ini penulis mencoba untuk menggunakan algoritma ini untuk menyelesaikan permasalahan VRPTW, akan tetapi masih banyak permasalahan lain seperi Job Schedulling, Matching, Project Schedulling, dan sebagainya yang pernah dijelaskan dalam mata kuliah Penerapan Teori Graph. Dalam tulisan ini belum dikaji tentang imlementasi algoritma pada bahasa pemrograman, sehingga bisa dilanjutkan untuk penelitian lebih lanjut yang mengacu ke bahasa pemrograman untuk algoritma Harmony Search. DAFTAR PUSTAKA Aldous, M Joan. 2004. Graph And Applications : An Introduction Approach. Great Britain. Springer. Arifin, Rian. 2012. Optimalisasi Pendistribusian Rokok Pada Pt. Ongkowidjojo Malang Dengan Algoritma Clark And Wright. Laporan PKL tidak diterbitkan. Malang : Universitas Negeri Malang. Geem, Z.W., Kang Seok Lee,& Park, Yongjin, (2005). Application of Harmony Search to vehicle Routing Problem. American Journal of Applied Sciences, vol 2(12) :1552-1557 . P. Machado, J. Tavares, F. B. Pereira, and E. Costa, “Vehicle Routing Problem: Doing it the Evolutionary Way” .GECCO.Proceedings, 2002 Rosen, K.H. 1995. Discrete Mathematic and Its Application Third Edition. New York: mcGraw Hill,Inc.
