PENYELESAIAN CAPACITATED VEHICLE ROUTING PROBLEM MENGGUNAKAN GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE
VIVIANISA WAHYUNI
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2015
PERNYATAANSKRIPSI DANSUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Penyelesaian Capacitated Vehicle Routing Problem Mengggunakan Greedy Randomized Adaptive Search Procedureadalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir karya ilmiah ini. Dengan ini saya melimpahkan hak cipta dari karya ilmiah saya kepada Institut Pertanian Bogor. Bogor, Februari 2015 Vivianisa Wahyuni NIM G54100035
ABSTRAK VIVIANISA WAHYUNI. Penyelesaian Capacitated Vehicle Routing Problem Mengggunakan Greedy Randomized Adaptive Search Procedure. Dibimbing oleh FARIDA HANUM dan PRAPTO TRI SUPRIYO. Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu variasi dari Vehicle Routing Problem (VRP), yang secara khusus merupakan masalah penentuan rute kendaraan dengan penambahan kendala kapasitas kendaraan. Tujuan CVRP yaitu meminimumkan jarak tempuh atau waktu tempuh kendaraan. Pada karya ilmiah ini, masalah CVRP diselesaikan dengan sebuah metode heuristik yaitu Greedy Randomized Adaptive Search Procedure (GRASP) dengan prinsip cluster first-route second. GRASP merupakan metode dua fase. Fase pertama ialah penentuan solusi awal dan fase kedua peningkatan kualitas solusi. Penentuan solusi awal bekerja dengan cara mengelompokkan setiap pelanggan ke dalam beberapa grup untuk kemudian dirancang rute yang meminimumkan jarak tempuh. Selanjutnya dilakukan peningkatan kualitas solusi menggunakan metode 2-opt agar hasil yang didapatkan lebih baik. Contoh aplikasi CVRP dalam karya ilmiah ini ialah penentuan rute pengiriman produk roti dengan jarak minimum. Kata kunci: CVRP, metode heuristik, metode 2-opt , GRASP, VRP.
ABSTRACT VIVIANISA WAHYUNI. Determination of Capacitated Vehicle Routing Problem Using Greedy Randomized Adaptive Search Procedure. Supervised by FARIDA HANUM and PRAPTO TRI SUPRIYO. Capacitated Vehicle Routing Problem (CVRP) is a variation of Vehicle Routing Problem (VRP), which is intended is the problem to determine the route of vehicle with increasing its capacity. The goal of CVRP is either to minimize the mileage or delivery time of shipping product. In this paper, the CVRP problem will be solved by using a heuristic method, namely Greedy Randomized Adaptive Search Procedure (GRASP).This method has two phases, firstly is determining the initial solution and secondly is improving the quality of the solution. Determination of initial solution was carried out by classifying customers into groups and then designing the routes to minimize distances. Further, the initial solutions are improved by using the 2-opt method. The application of CVRP is showed as an ilustration in determining the minimum distance route of bread product delivery. Keywords: CVRP, heuristic method, GRASP, VRP, 2-opt method
PENYELESAIAN CAPACITATED VEHICLE ROUTING PROBLEM MENGGUNAKAN GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE
VIVIANISA WAHYUNI
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2015
Judul Skripsi : Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Greedy Randomized Adaptive Search Procedure Nama : Vivianisa Wahyuni NIM : G54100035
Disetujui oleh
Dra Farida Hanum, MSi Pembimbing I
Drs Prapto Tri Supriyo, MKom Pembimbing II
Diketahui oleh
Dr Toni Bakhtiar, MSc Ketua Departemen
Tanggal Lulus:
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa taβala atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih ialah Riset Operasi, dengan judul Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Greedy Randomized Adaptive Search Procedure. Terima kasih penulis ucapkan kepada Ibu Dra Farida Hanum, MSi dan Bapak Drs Prapto Tri Supriyo, MKom selaku pembimbing dan Bapak Dr Ir Amril Aman, MSc selaku penguji yang telah memberikan saran, motivasi dan bimbingan dalam penulisan karya ilmiah ini. Di samping itu, penghargaan penulis sampaikan kepada Bapak Dr Ir Irmansyah, MSi selaku Kepala Asrama IPB 2014 dan Ibu Dr Megawati Simanjuntak, Spi.Msi selaku Kepala Sub Direktorat Kesejahteraan Mahasiswa yang telah memberikan saran, motivasi, dan beasiswa penelitian kepada penulis. Ungkapan terima kasih juga disampaikan kepada ayah, ibu, serta seluruh keluarga dan teman-teman Sospol Asrama, Senior Resident dan Matematika 47, atas segala doa dan kasih sayangnya. Semoga karya ilmiah ini bermanfaat.
Bogor, Februari 2015 Vivianisa Wahyuni
DAFTAR ISI DAFTAR TABEL
x
DAFTAR GAMBAR
x
DAFTAR LAMPIRAN
x
PENDAHULUAN
1
Latar Belakang
1
Tujuan
1
LANDASAN TEORI
2
Travelling Salesman Problem
2
Vehicle Routing Problem
3
Capacitated Vehicle Routing Problem
4
Generalised Assignment Problem
5
Greedy Randomized Adaptive Search Proccedure
6
Minimum Spanning Tree
6
Double Minimum Spanning Tree
7
Metode 2-opt
8
PEMBAHASAN
8
Deskripsi dan formulasi masalah
8
Algoritme GRASP untuk CVRP
10
IMPLEMENTASI MODEL Penyelesaian masalah dengan menggunakan Greedy Randomized Adaptive Search Procedure SIMPULAN DAN SARAN
11 13 20
Simpulan
20
Saran
21
DAFTAR PUSTAKA
21
LAMPIRAN
23
RIWAYAT HIDUP
35
DAFTAR TABEL 1 2 3 4 5 6 7 8
Data permintaan pelanggan Nilai πππ dengan perhitungan ππ,3 , ππ,10 dan ππ,19 Hasil klasifikasi pelanggan Data jarak pelanggan di Grup 1 Data jarak pelanggan di Grup 2 Data jarak pelanggan di Grup 3 Data jarak dalam fase local search dengan metode 2-opt Hasil akhir total jarak tempuh untuk setiap grup
12 13 14 14 15 16 18 20
DAFTAR GAMBAR 1 Contoh rute dalam Travelling Salesman Problem (TSP) 2 Contoh rute dalam Vehicle Routing Problem (VRP) dengan tiga kendaraan 3 Contoh Graf πΊ dan MST Graf πΊ dengan bobot 15 4 Contoh ilustrasi MST dan Double Minimum Spanning Tree 5 Contoh hasil rute tempuh dari Double Minimum Spanning Tree 6 Contoh 2-opt 7 Lokasi depot dan semua pelanggan 8 MST Grup 1 dan Double Minimum Spanning Tree pada Grup 1 9 Rute Grup 1 hasil Double Minimum Spanning Tree 10 MST Grup 2 dan Double Minimum Spanning Tree pada Grup 2 11 Rute Grup 2 hasil Double Minimum Spanning Tree 12 MST Grup 3 danDouble Minimum Spanning Tree pada Grup 3 13 Rute Grup 3 hasil Double Minimum Spanning Tree 14 Rute tempuh gabungan pelangganGrup 1, 2, dan 3 15 Pergantian sisi pada Grup 1. (a) merupakan rute awal dan (b) rute setelah 2-opt 16 Rute gabungan semua pelanggan setelah 2-opt lima kali iterasi
3 4 6 7 7 8 12 15 15 16 16 17 17 17 19 19
DAFTAR LAMPIRAN 1 2 3 4
Data jarak antar pelanggan Data depot dan pelanggan Perhitungan nilai πππ Sintaks program LINGO 11.0 untuk menyelesaikan contoh kasus Generalised Assignment Problem 5 Ilustrasi pergantian rute setiap grup dengan menggunakan metode 2-opt
23 24 25 29 32
PENDAHULUAN Latar Belakang Masalah transportasi dan distribusi produk dalam kehidupan sehari-hari dapat dimodelkan sebagai vehicle routing problem (VRP). Model VRP akan menghasilkan sejumlah rute kendaraan untuk mengunjungi konsumen. Setiap rute berawal dan berakhir di tempat yang sama yang disebut depot. Selain itu, model VRP juga memastikan agar total permintaan pada suatu rute tidak melebihi kapasitas kendaraan yang beroperasi. Penggunaan model VRP diharapkan dapat meminimumkan total jarak tempuh dan jumlah kendaraan. Salah satu variasi dari VRP ialah capacitated vehicle routing problem (CVRP). Pada CVRP ditambahkan kendala kapasitas pada kendaraan untuk melayani permintaan pelanggan. VRP merupakan permasalahan integer programming yang termasuk kategori NP-Hard Problem (Nondeterministic Polynomial - Hard Problem), yang berarti usaha komputasi yang digunakan akan semakin besar dan banyak seiring dengan meningkatnya ruang lingkup masalah. Untuk masalah seperti ini, biasanya yang dicari adalah aproksimasi solusi yang terdekat dengan solusi optimal. Salah satu cara untuk menyelesaikannya ialah dengan metode heuristik (Pradhana et al. 2012). Dalam karya ilmiah ini, metode heuristik yang digunakan untuk mencari solusi CVRP ialah algoritme greedy randomized adaptive search procedure (GRASP). Prosedur GRASP ini adalah sebuah metode metaheuristik berulang yang terdiri dari dua fase dalam setiap iterasinya. Fase pertama merupakan fase penentuan solusi awal dan fase kedua adalah fase local search. Pada fase pertama, proses penentuan solusi dimulai dengan membangkitkan grup untuk setiap titik yang ada dan banyaknya grup yang sudah ditentukan. Selanjutnya dalam fase local search mencari rute terpendek dari setiap grup yang telah didapatkan (Festa 2002). Sumber utama karya ilmiah ini ialah artikel berjudul Optimizing vehicle routes in bakery company allowing flexibility in delivery dates karangan J Pacheco A Alvarez I Garcia dan F Angel-Bello yang diterbitkan pada tahun 2012 dan Laporte G Gendreau M Potvin JY Semet F yang berjudul Classical and modern heuristics for the vehicle routing problem yang diterbitkan pada tahun 2000.
Tujuan Tujuan karya ilmiah ini ialah: 1 menerapkan metode heuristik greedy randomized adaptive search procedure (GRASP) cluster first-route second untuk mencari jarak terpendek dari rute kendaraan, 2 mengimplementasikan model capacitated vehicle routing problem dalam mencari jarak terpendek dari rute kendaraan pada PT Nippon Indosari Corpindo.
2
LANDASAN TEORI Dalam bab ini akan dijelaskan tentang travelling salesman problem (TSP) yang merupakan dasar dari vehicle routing problem, kemudian akan dijelaskan penggunaan metode heuristik yang mendasari penyelesaian capacitated vehicle routing problem menggunakan algoritme greedy randomized adaptive search procedure, double minimum spanning tree, dan 2-opt.
Travelling Salesman Problem Dalam travelling salesman problem (TSP), seorang salesman akan berangkat dari satu pelanggan kemudian mengunjungi semua pelanggan yang ada dan pada akhir perjalanannya, salesman tersebut kembali ke pelanggan awal atau depot. Tujuan dari TSP ialah menentukan rute dan melalui setiap pelanggan satu kali yang meminimumkan jarak tempuh. Model TSP untuk π buah pelanggan dapat dituliskan sebagai berikut: Misalkan, πππ = besarnya biaya yang dikeluarkan untuk melakukan perjalanan dari pelanggan i ke pelanggan j Variabel keputusan 1, jika pelanggan ke- j dikunjungi setelah pelanggan ke-i π₯π,π = 0, selainnya Fungsi objektif untuk TSP tersebut adalah:
π
π
minimumkan π =
ππ,π π₯π,π π =1 π=1
terhadap kendala sebagai berikut: 1 Setiap pelanggan tepat dikunjungi satu kali, π
π₯π,π = 1;
βπ = 1,2, β¦ , π,
π₯π,π = 1;
βπ = 1,2, β¦ , π,
π =1 π
π=1
2 Tidak terdapat subtour pada rute tersebut, π₯π,π β€ π β 1;
βπ β 1,2, β¦ , π ,
π βπ πβπ
3 Variabel π₯π,π bernilai 0 atau 1, π₯π,π β 0,1 ; βπ, π = 1,2, β¦ π, (Nemhauser 1999).
3 Konsumen
Rute Depot Gambar 1 Contoh rute dalam Travelling Salesman Problem (TSP)
Vehicle Routing Problem Masalah yang berhubungan dengan pencarian rute yang optimal pada kendaraan dari suatu tempat ke tempat yang lain untuk melayani permintaan pelanggan disebut dengan vehicle routing problem (VRP). Dalam praktiknya, VRP banyak digunakan pada masalah distribusi logistik pada suatu wilayah. Karakteristik model VRP di antaranya ialah terdapat satu depot yang memiliki sebanyak πΎ kendaraan untuk melakukan pengiriman, dengan kapasitas setiap kendaraan sebanyak π. Kendaraan mengirim permintaan untuk π pelanggan masing-masing sebesar ππ untuk pelanggan π, dengan i=1,2,...,n. Jarak yang ditempuh dari setiap kendaraan sebisa mungkin adalah jarak yang terpendek antara pelanggan i ke pelanggan j. Penyelesaian yang didapat merupakan anggota dari {π
1 , π
2 , β¦ , π
π } yang mengirimkan permintaan melalui π buah rute dan permintaan yang dikirim tidak melebihi kapasitas kendaraan yang tersedia untuk setiap rute (Machado et al. 2002). Tujuan dari VRP ialah menentukan sejumlah rute untuk melakukan pengiriman pada setiap konsumen, dengan mengikuti beberapa ketentuan, antara lain: (1) setiap rute berawal dan berakhir di depot, (2) setiap konsumen dikunjungi tepat satu kali oleh tepat satu kendaraan, (3) jumlah permintaan tiap rute tidak melebihi kapasitas kendaraan dan (4) meminimumkan biaya perjalanan (Cordeau et al. 2002). Formulasi Matematika VRP Didefinisikan πΊ = (π, π΄) merupakan graf lengkap yaitu graf dengan setiap verteksnya tersambung dengan satu sisi dengan π = {0,1, β¦ , π} dan π΄ adalah himpunan sisi di πΊ. Verteks 0 menyatakan depot dan verteks lainnya menyatakan pelanggan. Misalkan bahwa π menunjukkan himpunan pelanggan dengan π β π β {0}, πππ menunjukkan besarnya biaya yang dikeluarkan untuk melakukan perjalanan dari pelanggan i ke pelanggan j, πΎ menunjukkan banyaknya kendaraan yang digunakan untuk melayani pelanggan, dan π(π ) menunjukkan banyaknya minimum kendaraan yang dibutuhkan untuk melayani pelanggan di π. Variabel keputusan: 1, jika terjadi kunjungan dari pelanggan i ke pelanggan j π₯π,π = 0, selainnya
4 Fungsi objektif minimumkan π =
ππ,π π₯π,π πβπ π βπ
dengan kendala sebagai berikut: 1 tepat satu kendaraan yang datang dan pergi dari lokasi π, π₯π,π = 1 ,
βπ β π β 0 ,
π₯π,π = 1 ,
βπ β π β 0 ,
πβπ
π βπ
3 terdapat πΎ kendaraan yang masuk dan keluar depot, π₯π,0 = πΎ, πβπ
π₯0,π = πΎ , π βπ
4 banyak kunjungan yang terjadi bernilai lebih besar atau sama dengan banyaknya kendaraan yang tersedia, π₯π,π β₯ π π , βπ β π β 0 , π β β
, π βπ π βπ
5 variabel kunjungan bernilai biner, π₯π,π β 0,1 , βπ, π β π, (Toth dan Vigo 2002).
Rute Rute Konsumen Konsumen
Depot Depot
Gambar 2 Contoh rute dalam Vehicle Routing Problem (VRP) dengan tiga kendaraan. Capacitated Vehicle Routing Problem Capacitated vehicle routing problem (CVRP) adalah salah satu variasi dari VRP yang memiliki kendala kapasitas pada kendaraan untuk melayani sejumlah permintaan konsumen. Sebelumnya jumlah permintaan konsumen untuk suatu barang telah diketahui dari sebuah depot. Oleh karena itu, CVRP sama seperti
5 VRP dengan faktor tambahan yaitu tiap kendaraan punya kapasitas tersendiri untuk suatu barang yang akan dikirim. CVRP bertujuan meminimumkan banyak kendaraan dan total waktu perjalanan. Selain itu, total permintaan barang untuk tiap rute tidak boleh melebihi kapasitas kendaraan yang melewati rute tersebut. Solusi CVRP dikatakan fisibel jika jumlah total barang yang diatur untuk setiap rute tidak melebihi kapasitas kendaraan yang melewati rute tersebut. Sebagai contoh, misalkan π melambangkan kapasitas sebuah kendaraan. Secara matematis, solusi untuk CVRP sama dengan VRP, tetapi dengan batasan tambahan total permintaan pelanggan pada rute π
π tidak boleh melebihi kapasitas kendaraan π atau ππ=1 ππ β€ π dengan ππ adalah banyaknya permintaan pada pelanggan π. Generalised Assignment Problem Generalised assignment problem atau GAP merupakan masalah penempatan yang melibatkan sejumlah barang dan wadah dengan menempatkan setiap barang tepat pada satu wadah yang bertujuan memaksimumkan keuntungan. Setiap berat barang yang ditempatkan pada wadah tidak lebih besar dari kapasitas wadah itu sendiri. Model GAP untuk permintaan dapat dinyatakan sebagai berikut: Misalkan, ππ,π adalah jarak dari pelanggan π ke pelanggan π, ππ menunjukkan banyaknya permintaan pelanggan π, π menunjukkan kapasitas kendaraan, dan πΎ menunjukkan banyaknya kendaraan yang tersedia dengan π merupakan indeks kendaraan serta π, π merupakan indeks pelanggan. π₯π,π
=
1, jika barang permintaan pelanggan π ditempatkan pada kendaraan π 0, selainnya
Fungsi objektif π
π
πΎ
minimumkan π =
ππ,π π₯π,π π=1 π =1 π=1
dengan kendala: 1 banyaknya permintaan tidak melebihi kapasitas kendaraan, π
ππ π₯π,π β€ π
π = 1,2, β¦ πΎ,
π=1
2 setiap pelanggan hanya diantar satu kali oleh satu kendaraan, πΎ
π₯π,π = 1
π = 1,2, β¦ , π,
π =1
3 nilai π₯π,π bernilai 0 atau 1, π₯π,π β 0,1 ; βπ = 1,2, β¦ πΎ , π = 1,2, β¦ π, (Wilson 1997).
6 Dalam karya ilmiah ini, GAP digunakan untuk mengklasifikasi grup pada pelanggan sesuai dengan kapasitas kendaraan. Greedy Randomized Adaptive Search Procedure Greedy randomized adaptive search procedure atau biasa disebut algoritme GRASP merupakan salah satu algoritme iteratif untuk menyelesaikan masalah kombinatorial dengan dua fase. Fase pertama merupakan fase penentuan solusi awal dan fase kedua ialah local search. Pada implementasinya, ada banyak jenis algoritme GRAPS, di antaranya ialah GRASP dengan prinsip cluster first-route second. Pada prinsip ini, pelanggan dikelompokkan ke dalam beberapa grup terlebih dahulu (cluster first), kemudian dirancang rute yang paling efisien dari setiap grup yang telah terbentuk (route second) (Simchi-Levi et al. 2005). Minimum Spanning Tree Tree (π) merupakan salah satu graf terhubung yang tidak mempunyai cycle. Suatu graf πΊ dikatakan terhubung apabila setiap dua simpul dari graf πΊ selalu terdapat jalur yang menghubungkan kedua simpul tersebut. Spanning tree atau pohon rentang merupakan graf yang mencakup semua simpul pada graf πΊ dan merupakan tree. Minimum spanning tree (MST) atau pohon rentang minimum adalah spanning tree dengan jarak minimum. Minimum spanning tree merupakan salah satu cara untuk mencari rute penghubung dari semua tempat pelanggan dalam jaringan secara bersamaan dengan jarak minimum (Nemhauser 1999). Salah satu algoritme yang umum digunakan untuk membuat minimum spanning tree ialah algoritme Prim. Langkah-langkah untuk mencari bobot minimum yaitu: 1 mengambil sisi graf πΊ yang berbobot minimum dan dimasukkan kedalam π yang merupakan graf kosong, 2 menambahkan sisi minimum yang bersisian dengan π tetapi sisi tersebut tidak membentuk cycle di π, kemudian ditambahkan sisi tersebut ke dalam π, 3 langkah 2 diulangi hingga semua verteks masuk ke dalam π (Siang 2002). Pada Gambar 3 terdapat sebuah graf terhubung. Gambar b) menunjukkan MST dari graf tersebut. 5 4
4 2 5
3
2
2
4
3
3
4 10 (a)
2
(b)
Gambar 3 (a) Contoh Graf πΊ dan (b)MST Graf πΊ dengan bobot 15.
7 Double Minimum Spanning Tree Double minimum spanning tree merupakan salah satu metode heuristik untuk menentukan solusi dari TSP. Solusi yang didapatkan merupakan solusi pendekatan sehingga solusi tersebut tidak dijamin optimal. Namun dengan nilai pendekatan, diharapkan hasil yang diperoleh menjadi lebih baik dari sebelumnya. Langkah-langkah penentuan rute dengan double minimum spanning tree ialah sebagai berikut: 1 membuat MST dari graf πΊdengan algoritme Prim, 2 menggandakan setiap edge pada MST tersebut, 3 membuat urutan titik yang akan dikunjungi mulai dari depot sampai kembali lagi ke depot, 4 menghapus atau menghilangkan titik selain depot yang muncul lebih dari satu kali, 5 membuat rute baru dari setiap urutan titik yang didapat dari Langkah 4. Sebagai contoh, pada Gambar 4(a) terdapat sebuah MST. Kemudian, setiap edge pada MST tersebut digandakan seperti pada Gambar 4(b). Misalkan MST pada Gambar 4(b) dimulai dari titik 1, maka rute dari titik 1 kembali ke 1 adalah 1,2,3,2,4,2,5,2,6,7,8,7,9,7,6,2,1. Dari urutan tersebut terlihat bahwa terdapat lokasi yang dilewati lebih dari satu kali, titik 2, 6, dan 7 . Selanjutnya, titik yang muncul lebih dari dua kali selain titik awal dihapus hingga menghasilkan sebuah rute baru. Rute baru setelah penghapusan titik yang muncul lebih dari satu kali menjadi 1,2,3,4,5,6,7,8,9,1 seperti pada Gambar 5 (Nemhauser 1999). 5 5 5 5 6 4
4
2
6 7
6
7 4 8
2 8
3
3 1
(a)
1
2
7
2 8
3
9
9
4
6 7
3
1
(b)
1
9
9
Gambar 4 (a) Contoh ilustrasi MST dan (b) Double Minimum Spanning Tree 5
5 6
4
4
2
6 7
7
2 8
3
3
1
1
9
8
9
Gambar 5 Contoh hasil rute tempuh dari Double Minimum Spanning Tree
8
8 Metode 2-opt Suatu rute yang akan diminimumkan jaraknya dapat ditentukan dengan beberapa cara. Salah satu cara yang dapat digunakan ialah menggunakan metode local search. Dalam karya ilmiah ini salah satu metode local searh yang digunakan ialah metode 2-opt. Pada dasarnya metode 2-opt memindahkan dua jalur pada rute yang ada, kemudian menghubungkan kembali jalur tersebut dengan pasangan pelanggan yang berbeda. Metode 2-opt hanya dapat dilakukan jika rute baru yang dihasilkan lebih baik daripada rute awal (Nilsson 2003). Sebagai contoh, pada Gambar 6 terdapat rute 0,1,3,2,4,0. Sisi (1,3) dan sisi (2,4) dihapus dan ditambahkan sisi baru yang menghubungkan pelanggan 1 dengan pelanggan 2 dan pelanggan 3 dengan pelanggan 4. Perpindahan ini mengubah rute tempuh menjadi 0,1,2,3,4,0 (Idaman 2013). 2
1
2
1
0 3
4
0 3
4
Path di antara dua verteks Sisi yang dihilangkan Sisi yang ditambahkan Gambar 6 Contoh 2-opt
PEMBAHASAN Deskripsi dan Formulasi Masalah Perusahaan yang memproduksi produk yang cepat rusak, misalkan perusahaan makanan, memiliki beberapa kendala dalam distribusinya. Produk yang diproduksi biasanya memiliki waktu kadaluarsa yang tidak lama. Oleh karena itu, setiap distributor memerlukan keefisienan waktu dalam mengirimkan produk tersebut sampai kepada pelanggan. Meminimumkan jarak tempuh merupakan salah satu cara untuk mengatur agar produk yang dikirim cepat sampai dan dapat meminimumkan biaya pengiriman serta waktu tempuh kendaraan. Pada karya ilmiah ini, dalam perhitungan pendistribusian produk kepada pelanggan, ada beberapa aturan yang dibuat. Aturan-aturan tersebut antara lain: 1 terdapat beberapa pelanggan yang tersebar dalam suatu wilayah di sekitar depot, 2 terdapat beberapa kendaraan yang tersedia untuk melayani setiap pelanggan, 3 banyaknya permintaan tidak melebihi kapasitas kendaraan yang tersedia,
9 4 kendaraan memiliki waktu tempuh maksimum dalam sekali perjalanan melayani pelanggan, 5 setiap perjalanan dimulai dan diakhiri pada depot yang sama pada hari yang sama, 6 setiap pelanggan hanya boleh dikunjungi oleh satu kendaraan. Beberapa asumsi yang digunakan dalam perhitungan ini ialah: 1 banyaknya kendaraan yang tersedia setiap hari sama, 2 waktu tempuh dianggap homogen (lewat jalan tol atau lewat jalan biasa dianggap sama), 3 kapasitas setiap kendaraan yang digunakan sama, Model matematik untuk masalah tersebut adalah sebagai berikut: π dan π : indeks untuk lokasi pelanggan π : indeks untuk kendaraan. Notasi π : banyaknya lokasi pelanggan. π : himpunan lokasi pelanggan 0,1, β¦ , π dengan 0 merupakan depot dan π merupakan tempat yang sesuai dengan pelanggan ke π, βπ β {1,2, β¦ , π}. : jarak antara pelanggan π dan π, βπ, π β π. ππ,π ππ : banyaknya permintaan pelanggan π, βπ = 1,2, β¦ π. π : kapasitas kendaraan. πΎ : banyaknya kendaraan. π‘π,π : waktu tempuh kendaraan π melayani pelanggan π. Variabel keputusan: 1, jika lokasi π dilayani tepat setelah lokasi π dilayani pada rute yang sama, π₯π,π = 0, selainnya. Fungsi objektif dari masalah ini ialah meminimumkan total jarak tempuh setiap kendaraan: minimumkan π =
ππ,π π₯π,π πβπ π βπ
terhadap kendala-kendala berikut: 1 tepat satu kendaraan yang datang dan pergi dari lokasi π, π
π₯π,π = 1; βπ β π, π=1 π
π₯π,π = 1; βπ β π, π =1
2 banyaknya kendaraan yang meninggalkan depot sama dengan banyaknya kendaraan yang kembali ke depot, π₯π,0 = πβπ
π₯0,π , π βπ
3 waktu tempuh yang digunakan dalam melayani pelanggan dalam satu kelompok tidak lebih dari satu hari (24 jam),
10 π‘π,π β€ 24 , πβπ πβπΎ
4 total permintaan pelanggan tidak melebihi dari total kapasitas kendaraan yang beroperasi, ππ β€ πΎπ, πβπ
5 π₯π,π bernilai 1 atau 0, π₯π,π β 0,1 ; βπ, π β π.
Algoritme GRASP untuk CVRP Algoritme GRASP pada umumnya diselesaikan dengan bantuan software.Pada prinsipnya, GRASP merupakan metode heuristik yang bekerja secara bertahap dengan memilih setiap kemungkinan solusi yang ada tanpa memikirkan akibat yang terjadi pada langkah selanjutnya. Khusus pada karya ilmiah ini, prinsip GRASP yang digunakan adalah GRASP dengan metode cluster first-route second. Prinsip ini membagi metode GRASP menjadi dua bagian: mengelompokkan terlebih dahulu, kemudian merancang rute tempuh yang optimal. Metode cluster first-route second pada GRASP memiliki beberapa tahapan penting yang mendasari setiap langkah dalam algoritme. Tahapan-tahapan tersebut ialah: 1 penentuan seedpoint, 2 penghitungan jarak antartitik dan mencari minimum dari jarak tersebut, 3 penentuan grup menggunakan GAP, 4 pencarian solusi jarak terpendek menggunakan travelling salesman problem, 5 mencari kembali jarak terpendek menggunakan metode local search hingga solusi terdekat dipenuhi, 6 penghentian algoritme, (Laporte et al. 2000). Penentuan seedpoint Pada karya ilmiah ini, dipilih titik yang akan mewakili setiap grup sebagai seedpoint. Seedpoint merupakan titik yang diambil sebagai titik acuan utama pada setiap grup. Titik diasumsikan sebagai tempat lokasi pelanggan. Sebelum menentukan titik yang akan dikelompokkan, ditentukan terlebih dahulu banyaknya grup yang diinginkan. Dalam karya ilmiah ini, banyaknya grup yang ditentukan disesuaikan dengan banyaknya kendaraan yang tersedia setiap hari. Penghitungan jarak antartitik Jarak antartitik yang berkorespondensi dengan seedpointπ½π dinotasikan sebagai ππ,π . Pada metode ini jarak ππ,π dihitung dengan cara yaitu, ππ,π = min π0,π + ππ,π½ π + ππ½ π ,0 , π0,π½ π + ππ½ π ,π + ππ,0 β (π0,π½ π + ππ½ π ,0 ), dengan ππ,π menyatakan jarak antara lokasi π dan π.
11
Penentuan grup menggunakan Generalised Assignment Problem Pada karya ilmiah ini, penyelesaian GAP untuk mengklasifikasi pelanggan ke dalam grup-grup dihitung menggunakan bantuan software LINGO 11.0 dengan fungsi objektif meminimumkan jarak tempuh rute setiap kendaraan dengan kendala banyaknya permintaan tidak melebihi kapasitas kendaraan. Pencarian solusi terpendek dari Travelling Salesman Problem Saat lokasi pelanggan telah terklasifikasi dalam beberapa grup, digunakan double minimum spanning tree hingga diperoleh membentuk cycle (solusi dari TSP). Jika grup yang dipilih sebanyak π grup, maka terdapat π rute (cycle) yang terbentuk. Penggunaan local search Jenis-jenis local search beragam namun pada karya ilmiah ini metode yang dipakai adalah metode 2-opt. Setiap rute yang terbentuk dicari kembali bobot minimumnya menggunakan 2-opt sebanyak iterasi tertentu. Kriteria penghentian algoritme Penghentian algoritme local search 2-opt dalam karya ilmiah ini ditentukan dengan membatasi banyak iterasi yang akan dilakukan.
IMPLEMENTASI MODEL Perusahaan roti memiliki kendala dalam pendistribusian produk rotinya. Perusahaan tersebut memiliki produk yang cepat rusak dengan masa kadaluarsa yang cepat. Perusahaan menginginkan jarak rute tempuh minimum untuk kendaraan yang akan mendistribusikan produknya dengan kecepatan rata-rata tertentu, agar roti yang dikirim cepat sampai kepada pelanggan. Barang yang dikirim sesuai dengan hari permintaan dan masih ada waktu beberapa hari bagi roti tersebut sampai kepada pelanggan sebelum masa kadaluarsanya. Karya ilmiah ini mengambil studi kasus pendistribusian roti pada PT Nippon Indosari Corpindo yang dikenal dengan produknya bermerek βSari Rotiβ. Perusahaan tersebut kemudian disebut sebagai depot yang menjadi awal keberangkatan dan akhir proses distribusi. Dalam masalah ini terdapat beberapa ketentuan sebagai berikut: 1 terdapat 24 pelanggan yang akan dilayani dengan ketersediaan kendaraan setiap hari sebanyak tiga kendaraan, 2 kecepatan rata-rata kendaraan yang digunakan sebesar 50km/jam, 3 kendaraan tersebut dapat mengangkut sebanyak 135 boks dalam satu kali angkut sehingga total barang yang dikirim ke pelanggan tidak melebihi kapasitas kendaraan, 4 perusahaan tersebut membatasi jarak maksimal yang boleh ditempuh setiap kendaraan yang beroperasi sejauh 120 km, 5 total waktu tempuh kendaran dalam melayani setiap pelanggan termasuk waktu bongkar muat barang tidak lebih dari 24 jam,
12 6 satu pelanggan hanya boleh dikunjungi satu kali oleh kendaraan dan setelah pelanggan tersebut dikunjungi, maka kendaraan harus meninggalkan pelanggan tersebut. Lokasi pelanggan dan depot dapat dilihat pada Gambar 7. Data permintaan pelanggan dapat dilihat pada Tabel 1 dan data pelanggan dapat dilihat pada Lampiran 1.
Gambar 7 Lokasi depot dan semua pelanggan Tabel 1 Data permintaan pelanggan Pelanggan (π) 1 2 3 4 5 6 7 8 9 10 11 12 a
Sumber: Aji (2009)
Permintaan (boks) 17 3 7 17 8 12 19 17 2 19 37 16
Pelanggan (π) 13 14 15 16 17 18 19 20 21 22 23 24
Permintaan (boks) 12 22 15 9 4 11 18 18 37 18 25 18
13 Penyelesaian Masalah dengan Algoritme Greedy Randomized Adaptive Search Procedure Penentuan seedpoint Misalkan π adalah himpunan semua pelanggan dengan π = {1,2, β¦ ,24}, verteks 0 adalah depot, π adalah indeks untuk grup, dan π½π adalah seedpoint pada grupπ. Terlebih dahulu ditentukan banyaknya grup yang akan dibuat, misalkan tiga grup, maka terdapat tiga π½π sesuai dengan banyak grup π. Misalkan π½1 = 3, π½2 = 10, π½3 = 19. Penghitungan jarak antartitik Setelah π½1 , π½2 dan π½3 dipilih, langkah selanjutnya adalah menghitung jarak rute tempuh yang berkorespondensi ke setiap π½π dan depot. Jika disajikan dalam tabel, maka hasil perhitungan jarak πππ dapat dilihat pada Tabel 2. Perhitungan nilai πππ½ π dapat dilihat pada Lampiran 3. Tabel 2 Nilai πππ dengan perhitungan ππ,3 , ππ,10 dan ππ,19 Pelanggan (π) 1 2 3 4 5 6 7 8 9 10 11 12
π
π,π 1 10 0 2 7 7 9 7 4 16 16 26
π
π,ππ
π
π,ππ
2 9 2 5 3 6 3 6 4 0 10 22
2 10 3 5 4 5 9 6 3 8 15 24
Pelanggan (π) 13 14 15 16 17 18 19 20 21 22 23 24
π
π,π
π
π,ππ
26 13 19 16 15 28 23 29 26 21 26 27
20 1 10 5 3 14 14 23 13 9 12 14
π
π,ππ 22 10 12 3 6 6 0 6 3 4 4 5
Penentuan grup menggunakan Generalised Assignment Problem Nilai πππ yang sudah didapat selanjutnya diinput menggunakan software LINGO 11.0 untuk mengklasifikasi pelanggan ke dalam tigagrup berdasarkan permintaan. Sintaks input dalam LINGO 11.0 dapat dilihat dalam Lampiran 4. Berikut adalah hasil klasifikasi 24 pelanggan dalam tiga grup menggunakan LINGO 11.0.
14 Tabel 3 Hasil klasifikasi pelanggan Grup 1 1 2 3 4 6 8 9 11 -
Grup 2 7 10 12 13 14 15 16 17 22
Grup 3 5 18 19 20 21 23 24 -
Dari Tabel 3 dapat dilihat terdapat 8 pelanggan pada Grup 1, 9 pelanggan pada Grup 2, dan 7 pelanggan pada Grup 3. Hasil perhitungan menggunakan LINGO 11.0 didapat nilai objektif sebesar 148 dengan total iterasi 93 kali (dapat dilihat di Lampiran 4). Pencarian solusi terpendek dengan Double Minimum Spanning Tree Dari grup yang sudah didapat pada tahap sebelumnya, ditentukan rute terpendek menggunakan double minimum spanning tree. Perhitungan rute dilakukan pada setiapgrup sehingga akan ada tiga rute tempuh untuk tiga kendaraan berbeda pada setiap grup. Tahap perhitungan jarak tiap grup dimulai dengan membuat MST untuk setiap grup. Selanjutnya, setiap sisi pada MST digandakan dan dibuat urutan titik tujuan tempuh dimulai dari titik π½π . Artinya, urutan destinasi kendaraan dimulai dari titik 3 pada Grup 1, titik 10 pada Grup 2 dan titik 19 pada Grup 3. Setelah semua titik dikunjungi, maka urutan destinasi kembali ke tempat semula. Titik yang muncul lebih dari satu kali dihilangkan sehingga graf membentuk cycle dan didapatkan rute baru. Tabel 4 Data jarak pelanggan di Grup 1 Pelanggan (π) 1 2 3 4 6 8 9 11
1
2
3
4
6
8
9
11
0
7 0
3 7 0
3 8 2 0
5 11 5 5 0
3 8 4 4 3 0
12 18 14 13 19 15 0
11 8 7 10 11 9 22 0
Dari Tabel 4 selanjutnya dibuat MST untuk Grup 1 yang diberikan pada Gambar 8a). Pada Grup 1, urutan tempuh kendaraan dari graf pada Gambar 8b) adalah 3,11,3,4,1,2,1,9,8,6,8,9,1,4,3. Titik yang muncul lebih dari dua kali dihilangkan sehingga membentuk rute baru 3,11,4,1,2,9,8,6,3. Namun karena
15 pelanggan 3 bukan merupakan depot maka rute tempuh kendaraan menjadi 0,3,11,4,1,2,9,8,6,0 dengan total tempuh kendaraan sejauh 105 km. 1 1 1 1 4 4 4 4 2 2 2 2 11 1 11 1 8 1 8 1 9 8 9 8 9 9 3 3 3 3 6 6 6 6 (b) (a) Gambar 8 (a) MST Grup 1, (b) Double Minimum Spanning Tree pada Grup 1 1 1 4 4 2 2 1 11 1 8 8 9 9 3 : Seedpoint 3 6 6 Gambar 9 Rute Grup 1 hasil Double Minimum Spanning Tree Sama seperti Grup 1, data jarak dan perhitungan graf pada Grup 2 disajikan pada Tabel 5 dan Gambar 10 sedangkan Grup 3 dapat dilihat pada Tabel 6 dan Gambar 12. Tabel 5 Data jarak pelanggan di Grup 2 Pelanggan (π) 7 10 12 13 14 15 16 17 22
7
10
12
13
14
15
16
17
22
0
5 0
6 13 0
7 12 1 0
4 2 12 13 0
5 7 6 10 7 0
6 4 12 13 4 4 0
5 3 12 10 3 6 1 0
8 6 11 18 9 7 7 7 0
16
17
10
13
15
17
7
16
10
13
15 7
16
14
14
22
22
12
12
(b)
(a)
Gambar 10 (a) MST Grup 2, (b) Double Minimum Spanning Tree pada Grup 2 10
17
13
15 7
16 14
: Seedpoint
22
12
Gambar 11 Rute Grup 2 hasil Double Minimum Spanning Tree Dari Gambar 10 didapat rute tempuh kendaraan yaitu 10, 17, 16, 15, 16, 17, 22, 17, 10, 14, 7, 12, 13, 12, 7, 14, 10 dan dengan menghilangkan titik yang sama didapatkan rute tempuh Grup 2 yaitu 10, 17, 16, 15, 22, 14, 7, 12, 13, 10. Depot 0 ditambahkan dalam rute kendaraan Grup 2 sehingga rute tempuh berubah menjadi 0, 10, 17, 16, 15, 22, 14, 7, 12, 13, 0 dengan total jarak tempuh 93 km. Tabel 6 Data jarak pelanggan di Grup 3 Pelanggan (π) 5 18 19 20 21 23 24
5
18
19
20
21
23
24
0
14 0
11 4 0
14 1 3 0
12 6 2 6 0
12 6 3 6 1 0
13 7 3 6 1 3 0
Grup 3 memiliki tujuh titik dengan rute tempuh setelah double minimum spanning tree adalah 19, 5, 20, 18, 21, 23, 24, 19. Penambahan depot 0 pada rute tempuh menjadi 0, 19, 5, 20, 18, 21, 23, 24, 0 dengan total jarak tempuh keseluruhan sebesar 100 km.
17
20
5
20
5 21 18
21
19
24
18
21
19
24
23
23
(a)
(b)
Gambar 12 (a) MST Grup 3, (b) Double Minimum Spanning Tree pada Grup 3 20
5 21
18
21
19
24
: Seedpoint
23
Gambar 13 Rute Grup 3 hasil Double Minimum Spanning Tree Secara umum, jika setiap grup sudah memiliki rute, maka jika disatukan depot dan rute dari grup 1, 2 dan 3 dapat dilihat sebagai berikut: 12 20
22
5 7 21
19
14
13
16
18 17
10 Depot
24 23
Grup 2
Grup 3 6 3 8
11 Keterangan: Seedpoint Rute Rute akhir TSP setiap grup
9 Grup 1 2
4 1
Gambar 14 Rute tempuh gabungan pelangganGrup 1, 2, dan 3
15
18
Gambar 14 menunjukkan bahwa setiap kendaraan yang keluar dari depot selalu menuju seedpoint sebagai tujuan awal pada setiap grup dan kembali ke depot setelah pelanggan terakhir dikunjungi dari setiap grup tersebut. Garis putusputus pada setiap grup menyatakan bagian akhir rute dari perhitungan TSP, namun kendaraan tidak perlu kembali ke seedpoint karena seedpoint sudah dilewati pertama kali sehingga setelah pelanggan terakhir dikunjungi, kendaraan dari setiap grup langsung kembali menuju depot. Penggunaan local search 2-opt Pada tahap ini, algoritme GRASP sudah masuk dalam fase kedua yaitu fase local search. Dari langkah sebelumnya didapat total jarak dari setiap grup masingmasing adalah 105 km, 93 km dan 100 km. Jarak tersebut kemungkinan bukan merupakan jarak optimal sehingga pada tahap ini, rute yang sudah didapat dicari kembali jarak yang lebih pendek menggunakan algoritme 2-opt. Algoritme ini bekerja dengan cara mengganti dua rute tertentu dengan dua rute baru dengan jarak yang lebih kecil. Pada karya ilmiah ini iterasi perhitungan 2-opt dibatasi sampai lima kali iterasi. Tabel 7 Data jarak dalam fase local search dengan metode 2-opt Iterasi ke-
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
Sisi yang dihilangkan
Sisi yang ditambahkan
Panjang sisi yang dihilangka n (km)
Grup 1 (0,1,2,3,4,6,8,9,11) (1,4), (6,8) (1,6), (4,8) 6 (6,8), (4,11) (4,6), (8,11) 13 (1,2), (8,9) (1,9), (2,8) 22 (4,11), (0,3) (0,11), (3,4) 30 (2,9), (6,8) (2,8), (6,9) 21 Grup 2 (0,7,10,12,13,14,15,16,17,22) (10,17), (16,15) (10,16), (15,17) 9 (15,16), (14,22) (14,15), (16,22) 12 (0,10), (7,14) (0,14), (7,10) 31 (0,10), (7,12) (0,7), (10,12) 33 (16,17), (14,22) (14,16), (17,22) 7 Grup 3 (0,5,18,19,20,21,23,24) (5, 20), (18,21) (5,18), (20,21) 20 (18,21), (23,24) (18,23), (21,24) 8 (0,19), (18,21) (0,18), (19,21) 36 (0,19), (5,20) (0,5), (19,20) 44 (0,19), (23,24) (0,23). (19,24) 32
Panjang sisi yang ditambah -kan (km)
Selisi h nilai jarak (km)
9 14 20 29 9
-3 -1 2 1 12
8 11 31 38 7
1 1 0 -5 0
16 7 40 26 34
4 1 -4 18 -2
Berdasarkan Tabel 7 pada Grup 1, selisih hasil 2-opt terbesar yaitu 12 km, maka rute tempuh yang awalnya 105 km berubah menjadi 93km. Untuk Grup 2, terdapat dua hasil yang sama pada iterasi 1 dan 2 sehingga pilih salah satu di
19 antara keduanya, dalam karya ilmiah ini diambil hasil dari iterasi 2. Total rute tempuh untuk Grup 2 setelah 2-opt adalah 92 km, sedangkan untuk Grup 3 selisih perpindahan jarak terbesar ada pada iterasi ke-4 dengan selisih 18 km dan mengubah total rute tempuh dari 100 km menjadi 82 km. Dengan demikian, rute tempuh kendaraan sudah lebih pendek dari rute sebelumnya dan iterasi algoritme berhenti. Berikut adalah contoh pergantian rute dari Grup 1 pada iterasi pertama menggunakan 2-opt. Untuk ilustrasi lebih lengkap lihat dapat dilihat pada Lampiran 5. 1 1 1 1 4 4 4 4 2 2 2 2 1 1 11 11 1 1 8 8 9 8 9 9 8 9 3 3 3 3 6 6 6 6 (b) (a) Gambar 15 Pergantian sisi pada Grup 1. (a) merupakan rute awal dan (b) rute setelah 2-opt Rute gabungan seluruh grup setelah dilakukan 2-opt dengan hasil jarak terpendek pada setiap grup dapat dilihat pada Gambar 16. 12 20
22
5 7 21
19
14
13
16
18 17
10 Depot
24 23
15
Grup 2
Grup 3 6 3 8
9
11 Keterangan: Seedpoint Rute akhir
Grup 1 2
4 1
Gambar 16 Rute gabungan semua pelanggan setelah 2-opt lima kali iterasi.
20
Saat nilai selisih jarak pada metode 2-opt sudah mencapai lima kali iterasi, maka diambil nilai selisih terbesar pada setiap grup. Nilai tersebut kemudian diakumulasikan pada total jarak tempuh setiap grup sehingga nilai yang didapat merupakan nilai dengan jarak tempuh kendaraan minimum. Setelah itu, dihitung total waktu tempuh yang digunakan dengan menjumlahkan waktu tempuh kendaraan dan waktu bongkar muat setiap pelanggan pada setiap grup. Hasil akhir setiap grup dapat dilihat pada Tabel 8. Tabel 8 Hasil akhir total jarak tempuh untuk setiap grup Total jarak rute awal (km)
Total jarak rute akhir (km)
105
93
93
92
100
82
Waktu bongkar muat (jam) Grup 1 5.45 Grup 2 4.85 Grup 3 7.10
Waktu tempuh (jam)
Total waktu tempuh keseluruhan (jam)
1.86
7.31
1.84
6.69
1.64
8.74
SIMPULAN DAN SARAN Simpulan Penyelesaian masalah CVRP menggunakan algoritme GRASP dengan prinsip cluster first-route second memiliki lima tahapan. Tahapan-tahapan tersebut yaitu, penentuan jumlah grup yang akan dibuat, penentuan seedpoint, menghitung jarak antartitik yang berkorespondensi dengan seedpoint dan depot, mengklasifikasikan grup menggunakan generalised assignment problem dan pencarian solusi jarak menggunakan TSP double minimum spanning tree. Selanjutnya solusi yang sudah didapat dicari kembali menggunakan metode 2-opt hingga beberapa iterasi sampai solusi yang didapatkan seminimum mungkin. Dalam studi kasus masalah distribusi permintaan roti pada perusahaan roti, total pelanggan dikelompokkan menjadi tiga grup dengan pengklasifikasian grup menggunakan prinsip generalised assignment problem dengan bantuan software LINGO 11.0. Dari 24 pelanggan, sebanyak 8 pelanggan masuk ke dalam Grup 1, 9 pelanggan untuk Grup 2 dan 7 pelanggan untuk Grup 3. Dengan metode double minimum spanning tree dihasilkan total jarak tempuh rute Grup 1 sampai 3 berturut turut yaitu 105 km, 93 km dan 100 km. Setelah itu, solusi yang didapat diperbaiki menggunakan metode 2-opt. Metode ini dilakukan sebanyak lima kali iterasi dengan hasil selisih perubahan jarak untuk tiap grup berturut turut 12 km, 1 km, dan 18 km. Untuk Grup 1, nilai selisih perubahan jarak terbesar terdapat pada iterasi 5, sedangkan untuk Grup 2 nilai selisih perubahan jarak yang diambil yaitu pada iterasi 2 dan untuk Grup 3 nilai selisih perubahan jarak yang terbesar ada pada iterasi 4 sehingga total rute kendaraan berubah menjadi 93 km, 92 km dan 82 km dengan waktu tempuh setiap grup yaitu 7.31 jam, 6.69 jam, dan 8.74 jam.
21 Saran Pencarian rute kendaraan menggunakan GRASP dengan metode heuristik menghasilkan solusi yang belum optimal, disarankan jika ada yang ingin menentukan rute kendaraan dengan menggunakan metode heuristik untuk menambah metode tambahan seperti path relinking agar solusi yang didapat semakin mendekati solusi yang optimal.
DAFTAR PUSTAKA Cordeau J-F, Gendreau M, Laporte G, Potvin JY, Semet F. 2002. A guide to vehicle routing heuristics. Journal of Operation Research Society. 53:512522. Feo TA, Resende MGC. 1995. Greedy randomized adaptive search procedures. Journal of Global Optimization. 6: 109-134. Festa P. 2002. Greedy randomized adaptive search procedure [Internet]. 7(4):7-11. [diunduh 2014 April 10]. Tersedia Pada: http://crema.di.unimi.it/ ~righini/ Didattica/Algoritmi Euristici/MaterialeAE/GRASPPaolaFesta.pdf Idaman S. 2013. Penyelesaian vehicle routing problem with simultaneous pick-up and delivery service menggunakan algoritme tabu search [skripsi]. Bogor (ID): Institut Pertanian Bogor. Laporte G, Gendreau M, Potvin JY, Semet F. 2000. Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research. 285-300. PII: S0969-6016(00)00003-4. Machado P, Tavares J, Pereira BF, Costa E. 2002. Vehicle routing problem: Doing it The Evolutionary Way [Internet]. [diunduh 2014 Oktober 2]. Tersedia pada: http: //. aminer. org/ 000/ 366/ 914/ a_ new_ ga_ approach_ for_the_vehicle_routing_problem.pdf Nemhauser G. 1999. Integer and Combinatorial Optimization. New York (US): John Wiley & Sons. Nilsson C. 2003. Heuristics for The Travelling Salesman Problem [Internet]. Linkoping University. [diunduh 2014 Oktober 2]. Tersedia pada: http://web.tuke.sk/fei-cit/butka/hop/htsp.pdf Pacheco J, Alvarez A, GarcΓa I, Angel-Bello F. 2011. Optimizing vehicle routes in bakery company allowing flexibility in delivery dates. Journal of Operational Research Society. 63: 569-581. doi: 10.1057/jors.2011.51. Pradhana FE, Sugiharti E, Kharis M. 2012. Penerapan algoritma tabu search untuk menyelesaikan vehicle routing problem. UJM. 1(1):1-6. Prama RA. 2007. Aplikasi kombinatorial pada vehicle routing problem [Internet]. Bandung (ID): Institut Teknologi Bandung. hlm: 3; [diunduh 2014 Juli 24]. Tersediapada:http:/informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/20072008/ Makalah/MakalahIF2153-0708-027.pdf. Raditya A. 2009. Penggunaan metode heuristik dalam permasalahan vehicle routing problem dan implementasinya di PT Nippon Indosari Corpindo [skripsi]. Bogor (ID): Institut Pertanian Bogor.
22 Siang, JJ. 2002. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta (ID): Andi. Simchi-Levi D, Chen X, Bramel J. 2005. The Logic of Logistics. Algorithms and Applications for Logistics and Supply Chain Management. Berlin (DE): Springer. Toth P, Vigo D. 2002. An overview of vehicle routing problems. Di dalam: Toth P, Vigo D, editor. The Vehicle Routing Problem. Philadelphia (US): Siam. hlm 1-26. Wilson JM. 1997. A simple dual algorithm for the generalised assignment problem. Journal of Heuristic. 2:303-311.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
18 0
23 7 0
20 3 7 0
20 3 8 2 0
23 4 6 4 4 0
22 5 11 5 5 4 0
25 7 8 4 6 3 7 0
23 3 8 4 4 2 3 4 0
10 12 18 14 13 15 19 18 15 0
27 11 13 9 12 7 11 5 10 21 0
29 11 8 7 10 7 11 5 9 22 8 0
36 20 9 10 21 9 19 6 19 29 13 4 0
35 19 10 11 20 10 19 7 13 28 12 5 1 0
26 8 11 7 7 4 6 4 6 19 2 5 12 13 0
30 4 13 9 15 11 13 5 13 23 7 7 6 10 7 0
28 9 12 8 9 6 8 6 8 21 4 7 12 13 4 6 0
27 9 12 8 8 5 9 5 7 21 3 6 12 10 3 4 1 0
32 17 20 16 17 14 16 16 16 26 9 18 21 20 9 10 8 7 0
30 14 17 13 15 11 13 14 13 23 11 16 18 17 14 12 5 9 4 0
33 17 20 16 18 14 16 17 16 26 17 19 24 22 17 15 8 12 1 3 0
31 15 19 15 16 12 15 15 14 24 9 17 12 18 9 7 7 5 6 2 6 0
30 11 14 11 11 8 11 8 10 23 6 9 11 13 6 4 4 3 7 4 8 3 0
31 15 19 15 16 12 15 11 14 25 8 11 11 12 8 6 7 4 6 3 6 1 2 0
32 16 19 15 17 13 15 15 15 25 9 13 12 19 9 6 7 6 7 3 6 1 3 2 0
23
1
Data jarak antar pelanggan (km)
0
Lampiran 1
Pelanggan (π) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
24 Lampiran 2
Data depot dan pelanggan
No
Nama tempat
Waktu bongkar muat (menit)
0
PT NIPPON INDOSARI CORPINDO
1
HARI-HARI BEKASI TRADE CENTRE
2
MITRA WISMA ASRI
3
LION SUPERINDO BOROBUDUR BEKASI
34
4
PT CONTIMAS UTAMA IND. (BLUE MALL)
69
5
CARREFOUR BEKASI SQUARE
91
6
HERO KEMANG PRATAMA
37
7
GIANT HYPERMARKET BEKASI
28
8
LION SUPERINDO METROPOLITAN MALL
41
9
MAKRO BEKASI 2
32
10
HARI-HARI BEKASI CYBER PARK
15
11
CV NAGA SWALAYAN (Pondok Ungu)
69
12
GIANT UJUNG MENTENG
42
13
CARREFOUR CAKUNG
54
14
LION SUPERINDO KALIMALANG BEKASI
21
15
GIANT PONDOK KOPI SPM
18
16
GIANT JATI BENING
47
17
STAR MART PERSADA GOLF
18
TIP-TOP PONDOK GEDE
60
19
GIANT PONDOK GEDE
35
20
CV NAGA SWALAYAN (Jatiwaringin)
20
21
TIP-TOP PONDOK BAMBU
81
22
GIANT KALIMALANG
58
23
SUPERINDO PONDOK BAMBU
66
24
YOGYA PONDOK BAMBU TOSERBA
73
a
Sumber: Aji (2009)
38 7
8
25 Lampiran 3 Perhitungan nilai πππ a.
ππ,π½1 = ππ,3 = min π0,π + ππ,3 + π3,0 , π0,3 + π3,π + ππ,0 β (π0,3 + π3,0 ) ο· π = 1; π1,3 = min π0,1 + π1,3 + π3,0 , π0,3 + π3,1 + π1,0 β π0,3 + π3,0 = min 18 + 3 + 20, 20 + 3 + 18 β (20 + 20) =1 ο· π = 2; π2,3 = min π0,2 + π2,3 + π3,0 , π0,3 + π3,2 + π2,0 β π0,3 + π3,0 = min 23 + 7 + 20, 20 + 7 + 23 β (20 β 20) = 10 ο· π = 3; π3,3 = min π0,3 + π3,3 + π3,0 , π0,3 + π3,3 + π3,0 β π0,3 + π3,0 = min 20 + 0 + 20, 20 + 0 + 20 β (20 + 20) =0 ο· π = 4; π4,3 = min π0,4 + π4,3 + π3,0 , π0,3 + π3,4 + π4,0 β π0,3 + π3,0 = min 20 + 2 + 20, 20 + 2 + 20 β (20 + 20) =2 ο· π = 5; π5,3 = min π0,5 + π5,3 + π3,0 , π0,3 + π3,5 + π5,0 β π0,3 + π3,0 = min 23 + 4 + 20, 20 + 4 + 23 β (20 + 20) =7 ο· π = 6; π6,3 = min π0,6 + π6,3 + π3,0 , π0,3 + π3,6 + π6,0 β π0,3 + π3,0 = min 22 + 5 + 20, 20 + 5 + 22 β (20 + 20) =7 ο· π = 7; π7,3 = min π0,7 + π7,3 + π3,0 , π0,3 + π3,7 + π7,0 β π0,3 + π3,0 = min 25 + 4 + 20, 20 + 4 + 25 β (20 + 20) =9 ο· π = 8; π8,3 = min π0,8 + π8,3 + π3,0 , π0,3 + π3,8 + π8,0 β π0,3 + π3,0 = min 23 + 4 + 20, 20 + 4 + 23 β (20 + 20) =7 ο· π = 9; π9,3 = min π0,9 + π9,3 + π3,0 , π0,3 + π3,9 + π9,0 β π0,3 + π3,0 = min 10 + 14 + 20, 20 + 14 + 10 β (20 + 20) =4 ο· π = 10; π10,3 = min π0,10 + π10,3 + π3,0 , π0,3 + π3,10 + π10,0 β π0,3 + π3,0 = min 27 + 9 + 20,20 + 9 + 27 β (20 + 20) = 16 ο· π = 11;π11,3 = min π0,11 + π11,3 + π3,0 , π0,3 + π3,11 + π11,0 β π0,3 + π3,0 = min 29 + 7 + 20, 20 + 7 + 29 β (20 + 20) = 16 ο· π = 12;π12,3 = min π0,12 + π12,3 + π3,0 , π0,3 + π3,12 + π12,0 β π0,3 + π3,0 = min 36 + 10 + 20, 20 + 10 + 36 β (20 + 20) = 26 ο· π = 13;π13,3 = min π0,13 + π13,3 + π3,0 , π0,3 + π3,13 + π13,0 β π0,3 + π3,0 = min 35 + 11 + 20, 20 + 11 + 35 β (20 + 20) = 26 ο· π = 14;π14,3 = min π0,14 + π14,3 + π3,0 , π0,3 + π3,14 + π14,0 β π0,3 + π3,0 = min 26 + 7 + 20, 20 + 7 + 26 β (20 + 20) = 13 ο· π = 15;π15,3 = min π0,15 + π15,3 + π3,0 , π0,3 + π3,15 + π15,0 β π0,3 + π3,0 = min 30 + 9 + 20, 20 + 9 + 30 β (20 + 20) = 16 ο· π = 16;π16,3 = min π0,16 + π16,3 + π3,0 , π0,3 + π3,16 + π16,0 β π0,3 + π3,0 = min 28 + 8 + 20, 20 + 8 + 28 β (20 + 20) = 16 ο· π = 17;π17,3 = min π0,17 + π17,3 + π3,0 , π0,3 + π3,17 + π17,0 β π0,3 + π3,0 = min 27 + 8 + 20, 20 + 8 + 27 β (20 + 20) = 15 ο· π = 18;π18,3 = min π0,18 + π18,3 + π3,0 , π0,3 + π3,18 + π18,0 β π0,3 + π3,0 = min 32 + 16 + 20, 20 + 16 + 32 β (20 + 20)
26
ο· ο· ο· ο· ο· ο·
b.
= 28 π = 19;π19,3 = min π0,19 + π19,3 + π3,0 , π0,3 + π3,19 + π19,0 β π0,3 + π3,0 = min 30 + 13 + 20, 20 + 13 + 30 β 20 + 20 = 23 π = 20;π20,3 = min π0,20 + π20,3 + π3,0 , π0,3 + π3,20 + π20,0 β π0,3 + π3,0 = min 33 + 16 + 20, 20 + 16 + 33 β (20 + 20) = 29 π = 21;π21,3 = min π0,21 + π21,3 + π3,0 , π0,3 + π3,21 + π21,0 β π0,3 + π3,0 = min 31 + 15 + 20, 20 + 15 + 31 β (20 + 20) = 26 π = 22;π22,3 = min π0,22 + π22,3 + π3,0 , π0,3 + π3,22 + π22,0 β π0,3 + π3,0 = min 30 + 11 + 20, 20 + 11 + 30 β (20 + 20) = 21 π = 23;π23,3 = min π0,23 + π23,3 + π3,0 , π0,3 + π3,23 + π23,0 β π0,3 + π3,0 = min 31 + 15 + 20, 20 + 15 + 31 β (20 + 20) = 26 π = 24;π24,3 = min π0,24 + π24,3 + π3,0 , π0,3 + π3,24 + π24,0 β π0,3 + π3,0 = min 32 + 15 + 20, 20 + 15 + 32 β (20 + 20) = 27
ππ,π½2 = ππ,10 = min π0,π + ππ ,10 + π10,0 , π0,10 + π10,π + ππ,0 β (π0,10 + π10,0 ) ο· π = 1;π1,10 = min π0,1 + π1,10 + π10,0 , π0,10 + π10,1 + π1,0 β π0,10 + π10,0 = min 18 + 11 + 27, 27 + 11 + 18 β (27 + 27) =2 ο· π = 2;π2,10 = min π0,2 + π2,10 + π10,0 , π0,10 + π10,2 + π2,0 β π0,10 + π10,0 = min 23 + 13 + 27, 27 + 13 + 23 β (27 + 27) =9 ο· π = 3;π3,10 = min π0,3 + π3,10 + π10,0 , π0,10 + π10,3 + π3,0 β π0,10 + π10,0 = min 20 + 9 + 27, 27 + 9 + 20 β (27 + 27) =2 ο· π = 4;π4,10 = min π0,4 + π4,10 + π10,0 , π0,10 + π10,4 + π4,0 β π0,10 + π10,0 = min 20 + 12 + 27, 27 + 12 + 20 β 27 + 27 =5 ο· π = 5;π5,10 = min π0,5 + π5,10 + π10,0 , π0,10 + π10,5 + π5,0 β π0,10 + π10,0 = min 23 + 7 + 27, 27 + 7 + 23 β (27 + 27) =3 ο· π = 6;π6,10 = min π0,6 + π6,10 + π10,0 , π0,10 + π10,6 + π6,0 β π0,10 + π10,0 = min 22 + 11 + 27, 27 + 11 + 22 β (27 + 27) =6 ο· π = 7;π7,10 = min π0,7 + π7,10 + π10,0 , π0,10 + π10,7 + π7,0 β π0,10 + π10,0 = min 25 + 5 + 27, 27 + 5 + 25 β (27 + 27) =3 ο· π = 8;π8,10 = min π0,8 + π8,10 + π10,0 , π0,10 + π10,8 + π8,0 β π0,10 + π10,0 = min 23 + 10 + 27, 27 + 10 + 23 β (27 + 27) = 6 ο· π = 9;π9,10 = min π0,9 + π9,10 + π10,0 , π0,10 + π10,9 + π9,0 β π0,10 + π10,0 = min 10 + 21 + 27, 27 + 21 + 10 β (27 + 27) =4 ο· π = 10;π10,10 = min π0,10 + π10,10 + π10,0 , π0,10 + π10,10 + π10,0 β π0,10 + π10,0 = min 27 + 0 + 27, 27 + 0 + 27 β (27 + 27) =0 ο· π = 11;π11,10 = min π0,1 + π1,10 + π10 ,0 , π0,10 + π10,1 + π1,0 β π0,10 + π10,0 = min 29 + 8 + 27, 27 + 8 + 29 β (27 + 27) = 10 ο· π = 12;π12,10 = min π0,12 + π12,10 + π10,0 , π0,10 + π10,12 + π12,0 β π0,10 + π10,0 = min 36 + 13 + 27, 27 + 13 + 36 β (27 + 27)
27
ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο·
c.
= 22 π = 13;π13,10 = min π0,13 + π13,10 + π10,0 , π0,10 + π10,13 + π13,0 β = min 35 + 12 + 27, 27 + 12 + 35 β (27 + 27) = 20 π = 14;π14,10 = min π0,14 + π14,10 + π10,0 , π0,10 + π10,14 + π14,0 β = min 26 + 2 + 27, 27 + 2 + 26 β (27 + 27) =1 π = 15;π15,10 = min π0,15 + π15,10 + π10,0 , π0,10 + π10,15 + π15,0 β = min 30 + 7 + 27, 27 + 7 + 30 β (27 + 27) = 10 π = 16;π16,10 = min π0,16 + π16,10 + π10,0 , π0,10 + π10,16 + π16,0 β = min 28 + 4 + 27, 27 + 4 + 28 β (27 + 27) =5 π = 17;π17,10 = min π0,17 + π17,10 + π10,0 , π0,10 + π10,17 + π17,0 β = min 27 + 3 + 27, 27 + 3 + 27 β (27 + 27) =3 π = 18;π18,10 = min π0,18 + π18,10 + π10,0 , π0,10 + π10,18 + π18,0 β = min 32 + 9 + 27, 27 + 9 + 32 β (27 + 27) = 14 π = 19;π19,10 = min π0,19 + π19,10 + π10,0 , π0,10 + π10,19 + π19,0 β = min 30 + 11 + 27, 27 + 11 + 30 β (27 + 27) = 14 π = 20;π20,10 = min π0,20 + π20,10 + π10,0 , π0,10 + π10,20 + π20,0 β = min 33 + 17 + 27, 27 + 17 + 33 β (27 + 27) = 23 π = 21;π21,10 = min π0,21 + π21,10 + π10,0 , π0,10 + π10,21 + π21,0 β = min 31 + 9 + 27, 27 + 9 + 31 β (27 + 27) = 13 π = 22;π22,10 = min π0,22 + π22,10 + π10,0 , π0,10 + π10,22 + π22,0 β = min 30 + 6 + 27, 27 + 6 + 30 β (27 + 27) =9 π = 23;π23,10 = min π0,23 + π23,10 + π10,0 , π0,10 + π10,23 + π23,0 β = min 31 + 8 + 27, 27 + 8 + 31 β (27 + 27) = 12 π = 24;π24,10 = min π0,24 + π24,10 + π10,0 , π0,10 + π10,24 + π24,0 β = min 32 + 9 + 27, 27 + 9 + 32 β (27 + 27) = 14
π0,10 + π10,0 π0,10 + π10,0 π0,10 + π10,0
π0,10 + π10,0 π0,10 + π10,0 π0,10 + π10,0 π0,10 + π10,0 π0,10 + π10,0 π0,10 + π10,0
π0,10 + π10,0 π0,10 + π10,0 π0,10 + π10,0
πππ½ 3 = ππ19 = min π0,π + ππ,19 + π19,0 , π0,19 + π19,π + ππ,0 β (π0,19 + π19,0 ) ο· π = 1;π1,19 = min π0,1 + π1,19 + π19,0 , π0,19 + π19,1 + π1,0 β π0,19 + π19,0 = min 18 + 14 + 30, 30 + 14 + 18 β (30 + 30) =2 ο· π = 2;π2,19 = min π0,2 + π2,19 + π19,0 , π0,19 + π19,2 + π2,0 β π0,19 + π19,0 = min 23 + 17 + 30, 30 + 17 + 23 β (30 + 30) =10 ο· π = 3;π3,19 = min π0,3 + π3,19 + π19,0 , π0,19 + π19,3 + π3,0 β π0,19 + π19,0 = min 20 + 13 + 30, 30 + 13 + 20 β (30 + 30) =3 ο· π = 4;π4,19 = min π0,4 + π4,19 + π19,0 , π0,19 + π19,4 + π4,0 β π0,19 + π19,0 = min 20 + 15 + 30, 30 + 15 + 20 β (30 + 30) =5 ο· π = 5;π5,19 = min π0,5 + π5,19 + π19,0 , π0,19 + π19,5 + π5,0 β π0,19 + π19,0 = min 23 + 11 + 30, 30 + 11 + 23 β (30 + 30) =4 ο· π = 6;π6,19 = min π0,6 + π6,19 + π19,0 , π0,19 + π19,6 + π6,0 β π0,19 + π19,0 = min 22 + 13 + 30, 30 + 13 + 22 β (30 + 30)
28
ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο· ο·
=5 π = 7;π7,19 = min π0,7 + π7,19 + π19,0 , π0,19 + π19,7 + π7,0 β π0,19 + π19,0 = min 25 + 14 + 30, 30 + 14 + 25 β (30 + 30) =9 π = 8;π8,19 = min π0,8 + π8,19 + π19,0 , π0,19 + π19,8 + π8,0 β π0,19 + π19,0 = min 23 + 13 + 30, 30 + 13 + 23 β (30 + 30) =6 π = 9;π9,19 = min π0,9 + π9,19 + π19,0 , π0,19 + π19,9 + π9,0 β π0,19 + π19,0 = min 10 + 23 + 30, 30 + 23 + 10 β (30 + 30) =3 π = 10;π10,19 = min π0,10 + π10,19 + π19,0 , π0,19 + π19,10 + π10,0 β π0,19 + π19,0 = min 27 + 11 + 30, 30 + 11 + 27 β (30 + 30) =8 π = 11;π11,19 = min π0,11 + π11,19 + π19,0 , π0,19 + π19,11 + π11,0 β π0,19 + π19,0 = min 29 + 16 + 30, 30 + 16 + 29 β (30 + 30) = 15 π = 12;π12,19 = min π0,12 + π12,19 + π19,0 , π0,19 + π19,12 + π12,0 β π0,19 + π19,0 = min 36 + 18 + 30, 30 + 18 + 36 β (30 + 30) = 24 π = 13;π13,19 = min π0,13 + π13,19 + π19,0 , π0,19 + π19,13 + π13,0 β π0,19 + π19,0 = min 26 + 14 + 30, 30 + 14 + 26 β (30 + 30) = 22 π = 14;π14,19 = min π0,14 + π14,19 + π19,0 , π0,19 + π19,14 + π14,0 β π0,19 + π19,0 = min 26 + 14 + 30, 30 + 14 + 26 β (30 + 30) = 10 π = 15;π15,19 = min π0,15 + π15,19 + π19,0 , π0,19 + π19,15 + π15,0 β π0,19 + π19,0 = min 30 + 12 + 30, 30 + 12 + 30 β (30 + 30) =12 π = 16;π16,19 = min π0,16 + π16,19 + π19,0 , π0,19 + π19,16 + π16,0 β π0,19 + π19,0 = min 28 + 5 + 30, 30 + 5 + 28 β (30 + 30) =3 π = 17;π17,19 = min π0,17 + π17,19 + π19,0 , π0,19 + π19,17 + π17,0 β π0,19 + π19,0 = min 27 + 9 + 30, 30 + 9 + 27 β (30 + 30) =6 π = 18;π18,19 = min π0,18 + π18,19 + π19,0 , π0,19 + π19,18 + π19,0 β π0,19 + π19,0 = min 32 + 4 + 30, 30 + 4 + 32 β (30 + 30) =6 π = 19;π19,19 = min π0,19 + π19,19 + π19,0 , π0,19 + π19,19 + π19,0 β π0,19 + π19,0 = min 30 + 0 + 30, 30 + 0 + 30 β (30 + 30) =0 π = 20;π20,19 = min π0,20 + π20,19 + π19,0 , π0,19 + π19,20 + π20,0 β π0,19 + π19,0 = min 33 + 3 + 30, 30 + 3 + 33 β (30 + 30) =6 π = 21;π21,19 = min π0,21 + π21,19 + π19,0 , π0,19 + π19,21 + π21,0 β π0,19 + π19,0 = min 31 + 2 + 30, 30 + 2 + 31 β (30 + 30) =3 π = 22;π22,19 = min π0,22 + π22,19 + π19,0 , π0,19 + π19,22 + π22,0 β π0,19 + π19,0 = min 30 + 4 + 30, 30 + 4 + 30 β (30 + 30) =4 π = 23;π23,19 = min π0,23 + π23,19 + π19,0 , π0,19 + π19,23 + π23,0 β π0,19 + π19,0 = min 31 + 3 + 30, 30 + 3 + 31 β (30 + 30) =4 π = 24;π24,19 = min π0,24 + π24,19 + π19,0 , π0,19 + π19,24 + π24,0 β π0,19 + π19,0 = min 32 + 3 + 30, 30 + 3 + 32 β (30 + 30) =5
29
Lampiran 4 Sintaks program LINGO 11.0 untuk menyelesaikan contoh kasus Generalised Assignment Problem MODEL: SETS: TITIK1/1..24/:Q; TITIK2/1..3/:; RUTE(TITIK1, TITIK2):MATD, X; ENDSETS DATA: MATD=@OLE('C:\Users\User\Documents\skripsi vivi\data_jarak1.xlsx','DATA_D'); Q=@OLE('C:\Users\User\Documents\skripsi vivi\data_jarak.xlsx','demand_q'); ENDDATA !fungsi objektif MIN = @SUM(RUTE: X * MATD); !kendala @FOR(TITIK1(I): @SUM(TITIK2(J): X(I, J)) = 1); @FOR(TITIK2(j):@SUM(TITIK1(I):Q(I)*X(I,J))<=135); @FOR(RUTE(I,J):@BIN(X(I,J))); END
Hasil yang diperoleh:
Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Variable
Value
Reduced Cost
148.0000 148.0000 0.000000 0 93
30
Q( Q( Q( Q( Q( Q( Q( Q( Q( Q( Q( Q(
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12)
17.00000 3.000000 7.000000 17.00000 8.000000 12.00000 19.00000 17.00000 2.000000 19.00000 37.00000 16.00000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Q( Q( Q( Q( Q( Q( Q( Q( Q( Q( Q( Q(
13) 14) 15) 16) 17) 18) 19) 20) 21) 22) 23) 24)
MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD(
1, 1)1.000000 1, 2)2.000000 1, 3)2.000000 2, 1)10.00000 2, 2)9.000000 2, 3)10.00000 3, 1)0.000000 3, 2)2.000000 3, 3)3.000000 4, 1)2.000000 4, 2)5.000000 4, 3)5.000000 5, 1)7.000000 5, 2)3.000000 5, 3)4.000000 6, 1)7.000000 6, 2)6.000000 6, 3)5.000000 7, 1)9.000000 7, 2)3.000000 7, 3)9.000000 8, 1)7.000000 8, 2)6.000000 8, 3)6.000000 9, 1)4.000000 9, 2)4.000000 9, 3)3.000000 10, 1)16.00000 10, 2)0.000000 10, 3)8.000000 11, 1)16.00000 11, 2)10.00000 11, 3)15.00000 12, 1)26.00000 12, 2)22.00000 12, 3)24.00000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD( MATD(
13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24,
X( X( X( X( X( X( X( X( X(
1) 2) 3) 1) 2) 3) 1) 2) 3)
1.000000 2.000000 2.000000 10.00000 9.000000 10.00000 0.000000 2.000000 3.000000
X( X( X( X( X( X( X( X( X(
1) 2) 3) 1) 2) 3) 1) 2) 3)
1, 1, 1, 2, 2, 2, 3, 3, 3,
1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000
4, 4, 4, 5, 5, 5, 6, 6, 6,
12.00000 22.00000 15.00000 9.000000 4.000000 11.00000 18.00000 18.00000 37.00000 18.00000 25.00000 18.00000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
1)26.00000 2)20.00000 3)22.00000 1)13.00000 2)1.000000 3)10.00000 1)19.00000 2)10.00000 3)12.00000 1)16.00000 2)5.000000 3)3.000000 1)15.00000 2)3.000000 3)6.000000 1)28.00000 2)14.00000 3)6.000000 1)23.00000 2)14.00000 3)0.000000 1)29.00000 2)23.00000 3)6.000000 1)26.00000 2)13.00000 3)3.000000 1)21.00000 2)9.000000 3)4.000000 1)26.00000 2)12.00000 3)4.000000 1)27.00000 2)14.00000 3)5.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000
2.000000 5.000000 5.000000 7.000000 3.000000 4.000000 7.000000 6.000000 5.000000
31
X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X(
7, 1) 0.000000 7, 2) 1.000000 7, 3) 0.000000 8, 1) 1.000000 8, 2) 0.000000 8, 3) 0.000000 9, 1) 1.000000 9, 2) 0.000000 9, 3) 0.000000 10, 1)0.000000 10, 2)1.000000 10, 3)0.000000 11, 1)1.000000 11, 2)0.000000 11, 3)0.000000 12, 1)0.000000 12, 2)1.000000 12, 3)0.000000 13, 1)0.000000 13, 2)1.000000 13, 3)0.000000 14, 1)0.000000 14, 2)1.000000 14, 3)0.000000 15, 1)0.000000 15, 2)1.000000 15, 3)0.000000
9.000000 3.000000 9.000000 7.000000 6.000000 6.000000 4.000000 4.000000 3.000000 16.00000 0.000000 8.000000 16.00000 10.00000 15.00000 26.00000 22.00000 24.00000 27.00000 20.00000 22.00000 13.00000 1.000000 10.00000 19.00000 10.00000 12.00000
X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X(
16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24,
1)0.000000 2)1.000000 3)0.000000 1)0.000000 2)1.000000 3)0.000000 1)0.000000 2)0.000000 3)1.000000 1)0.000000 2)0.000000 3)1.000000 1)0.000000 2)0.000000 3)1.000000 1)0.000000 2)0.000000 3)1.000000 1)0.000000 2)1.000000 3)0.000000 1)0.000000 2)0.000000 3)1.000000 1)0.000000 2)0.000000 3)1.000000
16.00000 5.000000 3.000000 15.00000 3.000000 6.000000 28.00000 14.00000 6.000000 23.00000 14.00000 0.000000 29.00000 23.00000 6.000000 26.00000 13.00000 3.000000 21.00000 9.000000 4.000000 26.00000 12.00000 4.000000 27.00000 14.00000 5.000000
32
Lampiran 5 2-opt.
Ilustrasi pergantian rute setiap grup dengan menggunakan metode
Grup 1 Sebelum 2-opt
Setelah 2-opt Iterasi 2
1
4
1
4
2
2 11
11
8
8
9
9 3
3
6
6 Iterasi 3
1
4
1
4
2
2 11
11
8
8
9
9 3
3
6
6 Iterasi 4
1
4
1
4
2
2 11
11
8
8
9
9 3
3
6
6 Iterasi 5
1
4
1
4
2
2 11
11
8
8
9
9 3
3 6
6
33
Grup 2 Sebelum 2-opt
Setelah 2-opt Iterasi 1
17
10
17
13
15
13
15
7
16
10
7
16
14
14
22
22
12
12
Iterasi 2 17
10
17
13
15
13
15
7
16
10
7
16
14
14
22
22
12
12
Iterasi 3 17
10
17
13
15
13
15
7
16
10
7
16
14
14
22
22
12
12
Iterasi 4 17
10
17
13
15
13
15
7
16
10
7
16
14
14
22
22
12
12
Iterasi 5 17
10
13
15 7
16
17
13
15 7
16
14 22
10
14 12
22
12
34
Grup 3 Sebelum 2-opt
Setelah 2-opt Iterasi 1 20
5
20
5
21
21 18
21
19
24
18
21
19
24
23
23
Iterasi 2 20
5
20
5
21
21 18
21
19
24
18
21
19
24
23
23
Iterasi 3 20
5
20
5
21
21 18
21
19
24
18
21
19
24
23
23
Iterasi 4 20
5
20
5
21
21 18
21
19
24
18
21
19
24
23
23
Iterasi 5 20
5
20
5
21 21
19
24
21 18
23
21
19
24
18
23
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 11 Juni 1992 sebagai anak pertama dari pasangan Amril dan Suarni. Tahun 2010 penulis lulus dari SMA Negeri 112 Jakarta dan pada tahun yang sama penulis lulus seleksi masuk Institut Pertanian Bogor (IPB) melalui jalur Undangan Seleksi Masuk IPB (USMI) dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam dengan memperoleh beasiswa Bidik Misi. Selama mengikuti perkuliahan, penulis pernah menjadi asisten mata kuliah Agama Islam program S1 pada semester ganjil tahun ajaran 2013/2014. Penulis juga aktif berorganisasi sebagai sekretaris Departemen Pengembangan Sumber Daya Mahasiswa GUMATIKA pada tahun 2011 dan sebagai anggota Paguyuban Bidik Misi pada tahun 2012. Penulis juga menjadi Senior Resident Asrama Putri TPB IPB selama dua tahun sejak 2012 sampai 2014. Selain itu, penulis juga pernah aktif mengajar di Lembaga Bimbingan Kumon pada tahun 2014.
