12
3 METODE HEURISTIK UNTUK VRPTW
3.1 Metode Heuristik Metode heuristik merupakan salah satu metode penentuan solusi optimal dari permasalahan optimasi kombinatorial.
Berbeda dengan solusi eksak yang
menentukan nilai solusi secara tepat, metode ini menghampiri solusi permasalahan utama dengan cara mencari nilai optimal suatu bagian tertentu atau irisan dari masalah utamanya. Dalam hal ini, perolehan solusi fisibel secara cepat dari segi komputasi lebih ditekankan meskipun tidak dijamin solusi tersebut optimal. Menurut Laporte dan Semet (2002), metode heuristik untuk menyelesaikan VRP dapat dikategorikan dalam tiga kelompok, yaitu metode heuristik konstruktif (constructive heuristic), metode dua fase, dan metode perbaikan (improvement). Pada umumnya metode heuristik konstruktif dan metode perbaikan dilakukan secara bersamaan. Metode heuristik konstruktif, secara bertahap memilih simpul atau sisi untuk membangun suatu solusi atau rute fisibel awal dengan memperhatikan batasanbatasan seperti kapasitas atau time windows. Metode perbaikan atau local search selanjutnya melakukan perbaikan solusi sebelumnya untuk mengurangi biaya dengan melakukan serangkaian pertukaran simpul atau sisi baik di dalam rute (intra route) maupun antarrute (inter route).
3.2 Metode Heuristik Konstruktif Menurut Bräysy dan Gendreau (2005), metode heuristik konstruktif atau konstruksi rute, melakukan pemilihan simpul atau sisi secara berurutan hingga terbentuk suatu solusi fisibel awal.
3.2.1 Metode Saving Metode saving disebut juga metode Clarke-Wright karena diperkenalkan oleh Clarke dan Wright pada tahun 1964. Metode ini merupakan metode heuristik yang paling banyak digunakan untuk mengonstruksi rute. Metode ini diawali
13
dengan suatu solusi yang setiap pelanggannya dilayani secara individu oleh satu rute secara terpisah. Selanjutnya dilakukan penggabungan dua rute pelanggan i dan j sehingga menghasilkan penghematan (saving) berupa jarak tempuh sebesar sij = ci0 + c0j – cij dengan cij = jarak dari pelanggan i ke pelanggan j. Secara umum, jika dua rute (0, …, i, 0) dan (0, j,…, 0) secara fisibel dapat digabungkan menjadi rute tunggal (0, …, i, j, 0) maka akan terdapat penghematan jarak sebesar sij = (c0i + ci0 + c0j + cj0) – (c0i + cj0 + cij) = ci0 + c0j – cij (Altinel & Öncan 2005). Algoritme metode ini adalah sebagai berikut: 1. Pada awalnya, setiap pelanggan dilayani oleh satu kendaraan secara terpisah. Jadi diperoleh rute (0, i, 0) untuk setiap pelanggan i. 2. Untuk setiap pasang pelanggan i, j; i ≠ j, dihitung fungsi penghematan yang didefinisikan sebagai: sij = ci0 + c0j – cij yang diperoleh dengan cara menggabungkan dua rute pelanggan tersebut yaitu dengan membuat sisi (i,j). 3. Mengurutkan sisi (i, j) berdasarkan nilai sij secara takturun dalam sebuah daftar L. 4. Dimulai dari nilai sij terbesar, perluas setiap rute pada L dengan melakukan penggabungan dengan rute lainnya tanpa melanggar kendala. 5. Langkah (4) diulang sampai daftar L kosong. (ILOG 1999). Contoh metode ini diberikan pada Gambar 3.1.
j
i
c0j
ci0
c0i
cj0 0
i
cij
c0i
c0j 0
Depot
Depot
(1)
j
(2)
Gambar 3.1 Contoh metode saving. heuristic
14
Pada Gambar 3.1 bagian (1), pelanggan i dan pelanggan j dilayani oleh rute terpisah sedangkan pada bagian (2), kedua rute pelanggan tersebut digabungkan untuk dilayani oleh satu rute dengan cara menyelipkan pelanggan j setelah pelanggan i yaitu dengan membuat sisi berarah baru (i, j) yang fisibel sehingga memperoleh penghematan sebesar sij = ci0 + c0j – cij.
3.2.2 Metode Sweeping Metode ini diperkenalkan oleh Gillet dan Miller tahun 1974.
Misalkan
diasumsikan setiap pelanggan i ditempatkan pada suatu bidang dalam koordinat polar dengan sudut qi dari garis horizon yang berawal dari depot ke arah kanan. Berawal dari pelanggan dengan nilai qi terkecil, ditempatkan sebanyak mungkin pelanggan pada tiap-tiap kendaraan dengan urutan qi yang menaik sampai kapasitas kendaraan terpenuhi (Kyung et al. 2008). Beberapa penulis seperti Laporte dan Semet (2002), mengelompokkan metode ini ke dalam metode dua fase. Fase pertama adalah pengelompokan berdasarkan sudut qi. Pada fase kedua, tiap-tiap kelompok dipandang sebagai TSP yang akan ditentukan rute optimalnya. Pada software ILOG Dispatcher, penentuan rute dengan metode ini mengikuti algoritme sebagai berikut: 1. Misalkan O adalah posisi depot tempat kendaraan berawal dan A merupakan suatu posisi yang lain yang dianggap sebagai starting point. 2. Posisi setiap pelanggan S diurutkan berdasarkan besarnya sudut AOS secara menaik dan ditempatkan dalam daftar L. 3. Pelanggan ditempatkan pada kendaraan berdasarkan urutan tersebut tanpa melanggar kendala kapasitas kendaraan. 4. Jika kapasitas kendaraan telah dipenuhi, maka diambil kendaraan baru. 5. Proses berulang sampai semua pelanggan dalam daftar L ditempatkan pada kendaraan. (ILOG, 1999). Contoh metode ini dapat dilihat pada Gambar 3.2. Pada gambar tersebut bagian (1), dilakukan pengelompokan pelanggan ke dalam n kendaraan
15
berdasarkan sudut qi kemudian pada bagian (2), setiap kelompok ditentukan rute fisibelnya.
Kelompok ...
Kelompok n Kelompok 3
Kelompok 1
Kelompok 2 (1)
Rute …
Rute n Rute 3
Rute 1
Rute 2 (2)
Gambar 3.2 Contoh metode sweeping.
3.2.3 Metode Nearest-to-depot Metode ini membangun rute dengan cara menambahkan kunjungan yang terdekat dengan depot.
Pada setiap iterasinya, setelah diawali dari depot, dilakukan
pencarian pelanggan terdekat dengan depot untuk ditambahkan pada akhir rute tersebut. Rute baru dimulai dengan cara yang sama, jika tidak terdapat posisi
16
yang fisibel untuk menempatkan pelanggan baru karena kendala kapasitas atau time windows tidak dipenuhi. Algoritme metode ini adalah sebagai berikut: 1. Misalkan kendaraan yang tersedia dilambangkan dengan w. 2. Mulailah suatu rute yang berawal dari depot. 3. Temukan pelanggan berikutnya v yang terdekat dengan titik awal dari rute w. Jika tidak ada pelanggan yang memungkinkan, tutup rute w dan pilih kendaraan baru lainnya lalu kembali ke langkah 2. Jika tidak ada lagi kendaraan maka proses selesai. 4. Tambahkan v pada akhir dari rute tersebut. 5. Kembali ke langkah 3. (ILOG, 1999). Gambar 3.3 memberikan deskripsi tentang metode ini. Pada gambar tersebut, setelah diawali dari depot, dilakukan pencarian pelanggan yang terdekat dengan depot yaitu pelanggan i. Selanjutnya dari semua pelanggan lainnya yang tersisa, dicari yang terdekat dengan depot yaitu pelanggan j, untuk ditambahkan pada rute yang ada atau setelah pelanggan i. Pelanggan pada kasus VRPTW dipilih yang tidak melanggar kendala kapasitas dan time windows. Jika kapasitas kendaraan telah terpenuhi, mulai dengan rute baru sampai semua pelanggan terlayani.
…
i
j n
depot
Gambar 3.3 Contoh metode nearest-to-depot.
3.2.4 Metode Nearest Addition Metode nearest addition sangat mirip dengan metode nearest-to-depot. Jika pada setiap iterasinya, metode nearest-to-depot menambahkan pelanggan yang terdekat
17
dengan titik awalnya maka pada metode ini ditambahkan pelanggan yang terdekat dengan titik akhir dari rute (ILOG 1999). Metode nearest addition juga dinamakan metode nearest neighbor. Pada setiap iterasinya, dilakukan pencarian pelanggan terdekat dengan pelanggan yang terakhir untuk ditambahkan pada akhir rute tersebut. Rute baru dimulai dengan cara yang sama jika tidak terdapat posisi yang fisibel untuk menempatkan pelanggan baru karena kendala kapasitas atau time windows (Bräysy & Gendreau 2005). Metode ini dimulai dengan menentukan banyaknya kendaraan yang tersedia di depot.
Lokasi yang terdekat dengan depot akan dikunjungi pertama kali,
kemudian lokasi yang dikunjungi selanjutnya adalah lokasi yang memiliki jarak terdekat dengan lokasi pelanggan sebelumnya, demikian seterusnya hingga kapasitas kendaraan terpenuhi. Jika kapasitas kendaraan telah terpenuhi maka kendaraan tersebut harus kembali ke depot. Selanjutnya kendaraan berikutnya dioperasikan dengan aturan yang sama seperti kendaraan pertama, sampai seluruh lokasi dikunjungi oleh kendaraan yang tersedia di depot. Algoritme metode ini adalah sebagai berikut: 1. Misalkan banyaknya pelanggan adalah n. Rute dimulai dari depot/simpul 0 2. Tetapkan p = 1 dan U = {0}, yaitu himpunan simpul/pelanggan yang telah dilayani. 3. Jika p < n, maka: i.
pilih pelanggan i berikutnya untuk dikunjungi sedemikian hingga c0i = min c0 j dan (0,i) fisibel. j∉U
ii.
update U = U ∪ {i}, tetapkan simpul 0 = i dan p = p + 1
4. Jika (0, i) tidak fisibel maka mulai dengan rute baru sampai |U| = n + 1 Contoh metode ini diberikan pada Gambar 3.4. Pada gambar tersebut, kunjungan berikutnya setelah depot adalah pelanggan yang terdekat dengan depot yaitu pelanggan i; dilanjutkan dengan pelanggan berikutnya yang terdekat dengan pelanggan i, yaitu pelanggan j dengan syarat sisi berarah (i, j) fisibel.
Jika
18
kapasitas kendaraan telah terpenuhi, mulai dengan rute baru. Proses berlanjut sampai semua pelanggan terlayani.
i n
j
…
depot
Gambar 3.4 Contoh metode nearest addition.
3.2.5 Metode Insertion Metode ini bekerja dengan menyisipkan setiap kunjungan pada posisi terbaik dari suatu rute berdasarkan biaya minimum. Algoritme metode ini adalah sebagai berikut: 1. Diawali dengan membuat rute T dari depot ke sembarang pelanggan i yang belum dikunjungi. 2. Selama T belum memuat semua pelanggan yang ada, maka i.
Temukan dua pelanggan yaitu l œ T dan m – T sedemikian hingga biaya clm minimum.
ii.
Temukan posisi terbaik antara pelanggan l dan n pada T, untuk menyisipkan pelanggan k sehingga diperoleh sisi (l,k) dan (k,n). Pelanggan k dipilih
3. Ulangi langkah (2) sampai semua pelanggan dikunjungi. (Gambardella 2000) Contoh metode ini diberikan pada Gambar 3.5.
Pada gambar tersebut, rute
dimulai dari 0 menuju ke m karena biaya c0m minimum. Karena ckm minimum maka dibentuk sisi baru (0,k) dan (k,m) menggantikan sisi (0,m). Pelanggan terakhir n, diselipkan menggantikan sisi (m,0) menjadi sisi (m,n) dan (n,0).
19
k
m
0
n
Gambar 3.5 Contoh metode insertion.
3.3 Metode Perbaikan (improvement) Metode ini memperbaiki solusi fisibel dengan melakukan serangkaian pertukaran sisi dan simpul dalam rute atau antarrute kendaraan dengan tujuan mengurangi biaya solusi. Metode perbaikan antarrute dapat digunakan pada perbaikan dalam rute (Laporte & Semet 2002).
3.3.1 Perbaikan Dalam Rute Perbaikan dalam rute (intra-route improvement) adalah perbaikan yang melibatkan serangkaian pertukaran simpul dan sisi dalam satu rute. Metode ini terdiri atas 2-opt dan Or-opt.
3.3.1.1 Metode 2-opt Algoritme 2-opt merupakan salah satu algoritme local search yang mengeliminasi arc/jalur yang bersilangan pada suatu rute tunggal dengan cara mengambil 2 jalur lalu menghubungkan kembali keempat vertex/lokasi pelanggan yang berdekatan. Misalkan diberikan suatu rute c0, c1, c2, … , ck, c0. Untuk setiap kombinasi pelanggan ci, cj dengan i<j; i, j œ {1,…,k−1} akan diperiksa apakah jalur dari ci−1 ke cj dan dari ci ke cj+1 lebih baik daripada jalur awal dari ci−1 ke ci dan dari cj ke cj+1.
Jika demikian, bentuk jalur baru dari ci ke cj dan dilanjutkan untuk
kombinasi lainnya yang tersisa. Setelah semua kombinasi diperiksa, maka urutan kunjungan diperbaiki sesuai urutan perbaikan yang diperoleh. Jadi, jika urutan sebelum perbaikan adalah sebagai berikut:
20
c0, c1, c2, … , ci−1, ci, ci+1, ci+2,… , cj−1, cj, cj+1, …, ck, c0 maka setelah perbaikan menjadi c0, c1, c2, … , ci−1, cj, cj−1, cj−2,… , ci+1, ci, cj+1, cj+2,…, ck, c0 (Konig 2008) Jadi pada dasarnya metode 2-opt memindahkan dua jalur pada rute yang ada, kemudian menghubungkan kembali jalur tersebut dengan pasangan konsumen yang berbeda. Algoritmenya adalah sebagai berikut: 1. Berawal dari rute awal, 2. dua jalur yang menghubungkan 4 konsumen yang berbeda, dihapus kemudian keempat pelanggan dihubungkan kembali dengan pasangan yang berbeda, 3. jika biaya berkurang dan tidak melanggar kendala yang ada maka kembali ke langkah (2), 4. selesai. (ILOG 1999). i
j
j+1
i+1
i
j+1
j
i+1
Gambar 3.6 Contoh metode 2-opt. Contoh metode 2-opt dapat dilihat pada Gambar 3.6. Pada gambar tersebut, pelanggan i+1 yang dilayani setelah pelanggan i diubah menjadi pelanggan yang dilayani setelah pelanggan j+1, sedangkan pelanggan setelah j+1 yaitu j dilayani setelah pelanggan i+1. Hal ini dilakukan dengan mengganti sisi (i, i+1) dan (j+1, j) berturut-turut dengan sisi (i, j+1) dan (i+1, j).
3.3.1.2 Metode Or-opt Metode Or-opt identik dengan metode 2-opt, tetapi banyaknya jalur yang dapat dihapus dan ditambahkan lebih dari dua. Metode ini diperkenalkan oleh Or
21
pada tahun 1976 untuk menyelesaikan TSP. Ide dasar dari metode ini adalah merelokasi beberapa simpul (pelanggan) yang berdekatan.
Contohnya dapat
dilihat pada Gambar 3.7. Pada gambar tersebut, relokasi simpul dilakukan dengan cara mengganti tiga sisi pada rute asal dengan 3 sisi yang baru tanpa mengubah arah rute. Pelanggan i dan i+1 yang sebelumnya dilayani setelah i−1 dan sebelum i+2 diubah untuk dilayani setelah pelanggan j dan sebelum j+1. Jadi sisi (i−1, i), (i+1, i+2) dan (j, j+1) diganti berturut-turut dengan (i−1, i+2), (j, i) dan (i+1, j+1) namun tetap mempertahankan arah rute (Bräysy & Gendreau 2005).
i−1
i −1
i+2
i+2
i+1 i+1
i
i
j+1
j
j+1
j
Gambar 3.7 Contoh metode Or-opt.
3.3.2 Perbaikan Antarrute Metode perbaikan antarrute (inter-route improvement), merupakan proses pertukaran himpunan pelanggan untuk dilayani oleh tiap-tiap kendaraan. Satu pelanggan atau dua pelanggan yang berdekatan dan terhubung dipilih dari suatu rute dan dipindahkan dari posisi sekarang dengan menyisipkannya pada suatu rute yang lain. Metode ini terdiri atas metode relocate, exchange dan cross (Kyung et al. 2008).
3.3.2.1 Metode Relocate Pada metode relocate, suatu pelanggan dapat dipindahkan dari satu rute dan pelanggan tersebut ditambahkan ke rute lainnya dengan syarat biaya rute berkurang dan tidak melanggar kendala. Contoh metode relocate ini dapat dilihat pada Gambar 3.8. Pada gambar tersebut, sisi (i−1, i), (i, i+1) dan (j, j+1) diganti berturut-turut dengan sisi (i−1, i+1), (j, i) dan (i, j+1) (Bräysy & Gendreau, 2005).
22
i −1
i −1
i+1
i+1
i i j
j+1
j
j+1
Gambar 3.8 Contoh metode relocate.
3.3.2.2 Metode Exchange Pada metode exchange, dua pelanggan dari dua rute yang berbeda saling dipertukarkan tanpa melanggar kendala. Contohnya dapat dilihat pada Gambar 3.9. Pada gambar tersebut, pelanggan i dan j saling dipertukarkan. Hal ini dilakukan dengan cara mengganti sisi (i−1, i), (i, i+1), (j−1, j) dan (j, j+1) berturut-turut dengan (i−1, j), (j, i+1), (j−1, i) dan (i, j+1) (Bräysy & Gendreau 2005).
i−1
i−1
i+1
i+1
j j i j−1
i j+1
j−1
j+1
Gambar 3.9 Contoh metode exchange.
3.3.2.3 Metode Cross Metode cross saling mempertukarkan pelanggan yang ada pada akhir rute dari dua rute yang berbeda. Contoh dari metode cross terlihat pada Gambar 3.10.
23
i−1
k+1 j
i j−1
i−1
k+1
j
l
l
k
i
l+1
j−1
k l+1
Gambar 3.10 Contoh metode cross. Pada Gambar 3.10, sisi (i, k) pada rute pertama diselipkan pada rute kedua dan sisi (j, l) pada rute kedua diselipkan pada rute pertama secara bersamaan. Hal ini dilakukan dengan mengganti sisi (i−1, i), (k, k+1), (j−1, j) dan (l, l+1) dengan sisi (i−1, j), (l, k+1), (j−1, i) dan (k, l+1) (Bräysy & Gendreau 2005).
