PENYELESAIAN VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICK-UP AND DELIVERY SERVICE MENGGUNAKAN ALGORITME TABU SEARCH
SYUKRIO IDAMAN
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
PERNYATAAN SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Penyelesaian Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service Menggunakan Algoritme Tabu Search adalah 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 skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor.
Bogor, November 2013 Syukrio Idaman NIM G54090047
ABSTRAK SYUKRIO IDAMAN. Penyelesaian Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service Menggunakan Algoritme Tabu Search. Dibimbing oleh FARIDA HANUM dan PRAPTO TRI SUPRIYO. Vehicle Routing Problem with Simultaneous Pick-up and Delivery (VRPSPD) merupakan variasi dari Vehicle Routing Problem (VRP). VRPSPD merupakan masalah menentukan rute kendaraan untuk melakukan kegiatan pengambilan dan pengantaran produk secara bersamaan. Tujuan dari VRPSPD yaitu meminimumkan jarak tempuh atau biaya pengiriman produk. Pada karya ilmiah ini, masalah VRPSPD diselesaikan dengan sebuah metode heuristik yaitu algoritme tabu search. Algoritme tabu search merupakan salah satu metode optimisasi matematik yang menuntun pencarian solusi secara iteratif dengan memberikan status tabu terhadap solusi yang telah ditemukan. Algoritme tabu search menggunakan dua struktur memori yang memiliki fungsi yang berbeda. Algoritme tabu search memiliki beberapa tahapan yang mendasari setiap langkah dalam algoritme, yaitu penentuan solusi awal, pencarian solusi neighborhood, penggunaan struktur memori, dan penghentian algoritme. Contoh aplikasi VRPSPD dalam karya ilmiah ini adalah penentuan rute pengiriman produk air minum dengan jarak minimum. Kata kunci: metode heuristik, pick-up and delivery, tabu search, VRP, VRPSPD.
ABSTRACT SYUKRIO IDAMAN. The Solution of Vehicle Routing Problems with Simultaneous Pick-up and Delivery Services Using Tabu Search Algorithms. Supervised by FARIDA HANUM and PRAPTO TRI SUPRIYO. Vehicle Routing Problems with Simultaneous Pick-up and Delivery (VRPSPD) are the variation of Vehicle Routing Problems (VRP). VRPSPD is a problem to determine the route of vehicle to pick-up and delivery the product at the same time. The goal of VRPSPD is either to minimize the mileage or the cost of shipping the product. In this paper, the VRPSPD problem will be solved by using a heuristic method, namely Tabu search algorithm. Tabu search algorithm is a mathematical optimization method that guides the search for solutions iteratively by providing taboo status to the existing solution. It uses two memory structures that have different functions. It consists several stages that underlie each step in the algorithm, namely the determination of the initial solution, the search of the neighborhood solution, the use of the memory structures, and the termination of the algorithm. The application of VRPSPD is ilustrated in establishing the minimum distance route of drinking water product delivery. Key word : heuristic methods, pick-up and delivery, tabu search, VRP, VRPSPD
PENYELESAIAN VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICK-UP AND DELIVERY SERVICE MENGGUNAKAN ALGORITME TABU SEARCH
SYUKRIO IDAMAN
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 2013
Judul Skripsi Nama NIM
: Penyelesaian Vehicle Routing Problem with Simultaneous Pickup and Delivery Service Menggunakan Algoritme Tabu Search : Syukrio Idaman : G54090047
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 SWT yang selalu melimpahkan rahmat dan karunia-Nya sehingga karya ilmiah ini dapat diselesaikan. Judul dari karya ilmiah ini adalah Penyelesaian Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service Menggunakan Algoritme Tabu Search. Terima kasih penulis ucapkan kepada Ibu Dra Farida Hanum, MSi dan Drs Prapto Tri Supriyo, MKom selaku pembimbing, serta bapak Drs Siswandi, MSi selaku dosen penguji yang telah banyak memberikan saran, motivasi dan bimbingan dalam penulisan karya ilmiah ini. Terima kasih kepada mama dan Alm. papa serta seluruh keluarga yang selalu mendukung penulis dalam penulisan karya ilmiah ini. Terima kasih kepada Annisa Bahar, teman-teman Matematika angkatan 45, 46 dan 47 yang selalu memberikan dukungan kepada penulis. Penulis menyadari bahwa dalam penulisan skripsi ini masih jauh dari kesempurnaan. Kritik, saran, dan masukan yang bersifat membangun sangat penulis harapkan demi penyempurnaan di masa mendatang. Semoga skripsi ini dapat memberikan informasi yang bermanfaat bagi pembaca. Semoga karya ilmiah ini bermanfaat. Bogor, November 2013
Syukrio Idaman
DAFTAR ISI DAFTAR TABEL
xii
DAFTAR GAMBAR
xii
DAFTAR LAMPIRAN
xii
PENDAHULUAN
1
Latar Belakang
1
Tujuan
1
LANDASAN TEORI
2
Relokasi
2
Interchange
2
Crossover
3
2-opt
3
PEMBAHASAN
4
Deskripsi dan Formulasi Masalah
4
Algoritme Tabu Search untuk VRPSPD
6
APLIKASI MASALAH Penyelesaian Masalah dengan Algoritme Tabu Search SIMPULAN DAN SARAN
11 12 19
Simpulan
19
Saran
19
DAFTAR PUSTAKA
19
LAMPIRAN
20
RIWAYAT HIDUP
32
DAFTAR TABEL 1 2 3 4 5 6 7 8 9 10 11 12
Data jarak, permintaan pick-up dan delivery pelanggan Grup dan rute kendaraan berdasarkan smallest maximum load Jalur dan jarak solusi awal berdasarkan IGR1 Jalur dan jarak solusi neighborhood pada iterasi ke-1 Jalur dan jarak solusi neighborhood pada iterasi ke-2 Jalur dan jarak solusi neighborhood yang bersifat tabu pada iterasi ke-3 Jalur dan jarak solusi neighborhood pada iterasi ke-3 Jalur dan jarak solusi neighborhood pada fase intensifikasi Jalur dan jarak solusi neighborhood pada fase diversifikasi Grup dan rute kendaraan berdasarkan largest maximum load Grup dan rute kendaraan berdasarkan SGR2 Jalur dan jarak solusi awal berdasarkan SGR2
12 12 13 14 14 15 16 17 17 18 18 18
DAFTAR GAMBAR 1 2 3 4 5 6 7 8
Contoh relokasi Contoh interchange Contoh crossover Contoh 2-opt Rute solusi awal menggunakan IGR1 Solusi awal dan solusi neighborhood-nya Solusi yang diperoleh dari iterasi 1 dan solusi neighborhood-nya Solusi yang diperoleh dari iterasi 2 dan solusi neighborhood-nya
2 3 3 4 13 13 14 15
DAFTAR LAMPIRAN 1 Move_value, eco_movei, dan eco_moved untuk interchange, crossover dan 2-opt 2 Skema algoritme tabu search 3 Nilai move_value untuk move yang fisibel terhadap batas daya angkut kendaraan 4 Rangkuman solusi dengan penentuan solusi awal menggunakan IGR1 5 Frekuensi penggunaan sisi pada 5 iterasi pertama dengan penentuan solusi awal menggunakan IGR1 6 Nilai eco_movei untuk move yang fisibel terhadap batas daya angkut kendaraan 7 Tabu list dengan penentuan solusi awal menggunakan IGR1 8 Rangkuman solusi dengan penentuan solusi awal menggunakan SGR2 9 Frekuensi penggunaan sisi pada 5 iterasi pertama dengan penentuan solusi awal menggunakan SGR2 10 Tabu list dengan penentuan solusi awal menggunakan SGR2
20 22 23 25 26 26 28 29 30 30
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 yang mengunjungi setiap pelanggan. Model VRP memastikan agar total permintaan pada suatu rute tidak melebihi kapasitas kendaraan yang beroperasi. Penggunaan model ini diharapkan dapat meminimumkan total jarak tempuh dan banyaknya kendaraan yang beroperasi. Dalam perkembangannya, VRP ini mengalami berbagai variasi. Salah satu variasi VRP ialah vehicle routing problem with simultaneous pick-up and delivery service (VRPSPD). VRPSPD merupakan salah satu variasi dari Vehicle Routing Problem (VRP) yang melakukan pengambilan dan pengantaran produk secara bersamaan kepada pelanggan. VRP merupakan permasalahan integer programming yang termasuk kategori NP-Hard Problem (Nondeterministic Polynomial – Hard) yang berarti usaha komputasi yang digunakan akan semakin besar seiring dengan meningkatnya ruang lingkup masalah. Untuk masalah seperti ini biasanya yang dicari adalah solusi yang mendekati solusi optimal dengan waktu komputasi yang relatif cepat. Salah satu cara untuk menyelesaikannya ialah dengan metode heuristik (Pradhana et al. 2012). Dalam karya ilmiah ini, metode heuristik yang akan digunakan untuk mencari solusi dari VRPSPD yaitu algoritme tabu search. Tabu search adalah sebuah metode optimisasi matematik yang menuntun prosedur local search untuk melakukan eksplorasi di daerah solusi di luar titik optimal dengan memberikan status tabu pada solusi yang telah ditemukan. Algoritme tabu search sangat menjanjikan untuk menyelesaikan masalah optimisasi NP-Hard. Menurut Glover dan Laguna (1997) kata tabu atau “taboo” berasal dari bahasa Tongan, suatu bahasa Polinesia yang digunakan oleh suku Aborigin pulau Tonga untuk mengindikasikan suatu hal yang tidak boleh “disentuh” karena kesakralannya. Konsep dasar dari tabu search ialah mencegah terjadinya pengulangan solusi yang telah ditemukan pada iterasi sebelumnya. Sumber utama karya ilmiah ini ialah artikel berjudul A tabu search algorithm for vehicle routing problem with simultaneous pick-up and delivery service karangan Fermin Alfredo Tang Montane dan Roberto Dieguez Galvao yang diterbitkan pada tahun 2006. Tujuan Karya ilmiah ini disusun dengan tujuan dapat menerapkan algoritme tabu search pada vehicle routing problem with simultaneous pick-up and delivery service untuk menentukan himpunan rute yang meminimumkan total jarak tempuh.
LANDASAN TEORI Kata heuristic berasal dari bahasa yunani „eureka‟ yang artinya menemukan. Dalam masalah optimisasi, metode heuristik merupakan teknik penyelesaian yang dapat mengarahkan pemecahan masalah untuk menemukan penyelesaian yang efisien dalam mendapatkan solusi tetapi tidak menjamin tercapainya solusi yang optimal. Dalam bab ini, dijelaskan beberapa metode heuristik yang mendasari penyelesaian VRPSPD menggunakan algoritme tabu search. Beberapa metode heuristik tersebut ialah metode relokasi, interchange, crossover, dan 2-opt. Relokasi Relokasi dilakukan dengan memindahkan suatu pelanggan pada satu rute ke rute yang lain (perpindahan antar-rute). Pada Gambar 1 terdapat dua buah rute yaitu rute dan rute . Pelanggan yang berada pada rute dipindahkan ke rute , sehingga rute dan rute . yang ditempuh menjadi rute
Path di antara dua verteks Sisi yang dihilangkan Sisi yang ditambahkan Gambar 1 Contoh relokasi
Interchange Interchange dilakukan dengan saling menukar dua pelanggan pada dua rute. Pada Gambar 2 terdapat dua buah rute yaitu rute dan rute . Pelanggan yang berada pada rute dan pelanggan yang berada pada rute saling ditukar rute kunjungannya. Perpindahan ini mengubah rute yang ditempuh menjadi rute dan rute .
3
Path di antara dua verteks Sisi yang dihilangkan Sisi yang ditambahkan Gambar 2 Contoh interchange
Crossover Crossover dilakukan dengan menyilangkan urutan kunjungan pelanggan pada dua rute yang berbeda yaitu dengan menghilangkan sisi dari dua buah rute dan menambahkan dua sisi yang baru untuk menghubungkan kembali jalur tersebut dengan pelanggan yang berbeda. Pada Gambar 3 terdapat dua buah rute ) yaitu rute dan rute . Sisi ( ) dan sisi ( dihapus dan ditambahkan sisi baru yang menghubungkan pelanggan dengan pelanggan dan pelanggan dengan pelanggan . Perpindahan ini mengubah rute yang ditempuh menjadi rute dan rute .
Path di antara dua verteks Sisi yang dihilangkan Sisi yang ditambahkan Gambar 3 Contoh crossover
2-opt Pada dasarnya 2-opt dilakukan dengan menghilangkan dua jalur pada rute yang ada kemudian menghubungkan kembali jalur tersebut dengan pasangan
4
pelanggan yang berbeda. Pada Gambar 4 terdapat rute . ) dan sisi( Sisi ( ) dihapus dan ditambahkan sisi baru yang menghubungkan pelanggan dengan pelanggan dan pelanggan dengan pelanggan . Perpindahan ini mengubah rute yang ditempuh menjadi rute .
Path di antara dua verteks Sisi yang dihilangkan Sisi yang ditambahkan Gambar 4 Contoh 2-opt
PEMBAHASAN Deskripsi dan Formulasi Masalah Misalkan sebuah perusahaan mempunyai produk yang dapat digunakan kembali (reuseable). Perusahaan tersebut tentunya akan mengambil kembali produk dari pelanggan agar dapat diisi ulang (digunakan kembali) dan mendistribusikan produk yang telah diisi ulang (diolah) ke pelanggan. Misalkan perusahaan mempunyai sejumlah kendaraan, sejumlah pelanggan, dan satu gudang. Perusahaan tersebut mempunyai aturan-aturan dalam mendistribusikan produk yang dibuat. Aturan-aturan tersebut antara lain 1 rute perjalanan dalam pengambilan dan pengiriman selalu diawali dan diakhiri di gudang, 2 setiap pelanggan hanya boleh dikunjungi oleh tepat satu kendaraan; setelah pelanggan dikunjungi, kendaraan harus meninggalkan pelanggan tersebut, 3 kendaraan yang digunakan memiliki kapasitas daya angkut yang terbatas, 4 banyaknya kendaraan yang berangkat dari gudang tidak boleh melebihi banyaknya kendaraan yang tersedia, 5 total barang yang telah diambil dari pelanggan dan total barang yang akan dikirim ke pelanggan tidak boleh melebihi kapasitas kendaraan, 6 jarak yang ditempuh oleh setiap kendaraan tidak boleh melebihi jarak maksimum yang telah ditentukan untuk setiap kendaraan. Pemasalahan perusahaan tersebut dapat dimodelkan dalam VRPSPD (Vehicle Routing Problem with Simultaneous Pick-up and Delivery) yaitu suatu masalah penentuan rute beberapa angkutan barang (kendaraan) yang terdiri atas
5
dua kegiatan yaitu mengirim barang dari gudang ke lokasi pelanggan (delivery) dan mengambil barang (pick-up) dari pelanggan untuk dibawa ke gudang dalam satu kali perjalanan dengan tujuan meminimumkan jarak tempuh kendaraan. Beberapa asumsi yang digunakan pada VRPSPD ialah: 1 waktu bongkar muat barang dan waktu tempuh untuk pengiriman diabaikan, 2 biaya pengiriman barang diabaikan, 3 pengambilan (pick-up) dan pengiriman (delivery) dilakukan di tempat yang sama. Model matematik untuk permasalahan VRPSPD adalah sebagai berikut: Notasi: V : himpunan lokasi pelanggan : himpunan lokasi pelanggan dan gudang : banyaknya pelanggan = |V| : jarak antara lokasi pelanggan dengan pelanggan : banyaknya barang yang diminta diambil di lokasi : banyaknya barang yang diminta dikirim di lokasi : kapasitas kendaraan : jarak maksimum yang boleh ditempuh oleh setiap kendaraan ̅ : banyaknya kendaraan yang tersedia Indeks : i dan j : indeks untuk gudang dan pelanggan, i, j = 0 menyatakan gudang
*
+,
Variabel keputusan : 1, jika kendaraan k melalui lokasi pelanggan i menuju lokasi pelanggan j = 0, selainnya : banyaknya barang yang diambil dari awal lokasi pengambilan sampai ke lokasi dan diangkut pada sisi ( ) : banyaknya barang yang dikirim dari awal lokasi pengambilan sampai ke lokasi dan diangkut pada sisi ( )
{
Fungsi
objektif
̅
yaitu
meminimumkan
total
jarak
tempuh
kendaraan:
satu
kendaraan
∑∑∑
Kendala : Setiap
1
̅
pelanggan
dikunjungi
satu
kali
oleh
∑∑
2
Setelah mengunjungi pelanggan j, kendaraan k harus meninggalkan pelanggan tersebut. ∑
∑
̅
6 3
Paling banyak ̅ kendaraan yang digunakan untuk melakukan pengiriman barang ̅
∑
4 Jarak yang ditempuh oleh setiap kendaraan tidak melebihi jarak maksimum yang boleh ditempuh oleh kendaraan tersebut ̅
∑∑
5 Banyaknya barang yang diambil dari lokasi j harus memenuhi permintaan pick-up di lokasi j ∑
∑
6 Banyaknya barang yang dikirim ke lokasi j harus memenuhi permintaan delivery di lokasi j ∑
∑
7 Total barang yang diambil dan dikirim tidak boleh melebihi kapasitas maksimum kendaraan. ∑
8 Variabel *
̅
bernilai 0 atau 1 +
̅
9 Banyaknya barang yang diminta diambil yang diangkut pada sisi ( negatif
) tidak
10 Banyaknya barang yang diminta dikirim yang diangkut pada sisi ( negatif
) tidak
Algoritme Tabu Search untuk VRPSPD Dalam karya ilmiah ini, VRPSPD diselesaikan dengan menggunakan algoritme tabu search. Algoritme tabu search merupakan salah satu metode optimisasi matematik yang melakukan pencarian solusi ke arah penentuan solusi lokal atau pencarian solusi neighborhood secara iteratif yang dimulai dari satu titik (solusi) kemudian melakukan pencarian ke arah solusi lain dengan memberikan status tabu pada solusi yang telah ditemukan pada pencarian sebelumnya. Algoritme tabu search pertama kali ditemukan pada tahun 1986 oleh Fred Glover. Tabu search mempunyai dua struktur memori berupa short-term memory dan long term memory yang mempunyai fungsi untuk mengevaluasi solusi yang pernah ditemukan. Short-term memory terdiri dari tabu list, tabu tenure dan kriteria aspirasi. Short-term memory digunakan untuk menghilangkan cycle terhadap solusi yang pernah ditemukan pada iterasi-iterasi sebelumnya. Long-term memory pada dasarnya digunakan untuk menyimpan informasi secara
7
lebih detail dari solusi yang telah tersimpan selama proses pencarian solusi. Longterm memory digunakan untuk fase intensifikasi dan diversifikasi. Algoritme tabu search memiliki beberapa tahapan penting yang mendasari setiap langkah dalam algoritme. Tahapan-tahapan tersebut yaitu: 1 penentuan solusi awal, 2 pencarian solusi neighborhood, 3 penggunaan memori yaitu short-term memory dan long-term memory, 4 penghentian algoritme. Penentuan solusi awal Pada karya ilmiah ini, penentuan solusi awal tabu search menggunakan kombinasi dari strategi pengelompokan pelanggan (smallest maximum load atau largest maximum load) dan prosedur penentuan rute (independent grouping and routing (IGR) atau simultaneous grouping and routing (SGR)). Misalkan net demand (permintaan bersih) dari pelanggan adalah () yang merupakan selisih banyaknya barang yang diminta diambil dan banyaknya barang yang diminta dikirim oleh pelanggan i, yaitu () . () Jika maka beban kendaraan akan berkurang sebesar ( ) setelah mengunjungi pelanggan . Jika ( ) maka beban kendaraan akan bertambah sebesar ( ) setelah mengunjungi pelanggan . Smallest maximum load terjadi ketika kendaraan mengunjungi semua () pelanggan yang mempunyai terlebih dahulu kemudian mengunjungi () pelanggan yang mempunyai . Largest maximum load terjadi ketika () kendaraan mengunjungi semua pelanggan dengan terlebih dahulu () kemudian mengunjungi pelanggan dengan . Penyisipan pelanggan baru ke dalam suatu grup dapat dilakukan jika tidak melanggar batas daya angkut kendaraan. Penentuan rute berdasarkan independent grouping and routing (IGR) dilakukan dengan cara menentukan grup untuk setiap pelanggan terlebih dahulu, kemudian menentukan rute kendaraannya. Prosedur ini digunakan pada masalah tanpa kendala jarak maksimum. Penentuan rute berdasarkan simultaneous grouping and routing (SGR) digunakan untuk masalah dengan kendala jarak maksimum. Pada prosedur ini, penyisipan pelanggan baru pada suatu grup harus memenuhi dua hal, yaitu pelanggan dapat dimasukkan ke dalam suatu grup jika tambahan pick-up dan delivery pelanggan tidak melanggar kapasitas maksimum kendaraan serta jarak yang ditempuh untuk mengantarkan barang tidak melebihi jarak tempuh maksimum yang diperbolehkan pada kendaraan tersebut. Empat prosedur heuristik yang dapat digunakan untuk menentukan solusi awal tabu search ialah: a IGR1: pengelompokan pelanggan dibuat berdasarkan smallest maximum load, kemudian metode heuristik 2-opt digunakan untuk memperbaiki rute awal yang diperoleh dengan mengurutkan kunjungan pelanggan, b IGR2: pengelompokan pelanggan dibuat berdasarkan largest maximum load, kemudian metode heuristik 2-opt digunakan untuk memperbaiki rute awal yang diperoleh dengan mengurutkan kunjungan pelanggan,
8
SGR1: pengelompokan pelanggan dibuat berdasarkan smallest maximum load, kemudian pelanggan lainnya ditambahkan dengan tidak melanggar batas daya angkut dan jarak tempuh maksimum kendaraan. Metode heuristik 2-opt digunakan untuk memperbaiki rute awal yang diperoleh dengan mengurutkan kunjungan pelanggan, d SGR2: pengelompokan pelanggan dibuat berdasarkan largest maximum load, kemudian pelanggan lainnya ditambahkan dengan tidak melanggar batas daya angkut dan jarak tempuh maksimum kendaraan. Metode heuristik 2-opt digunakan untuk memperbaiki rute awal yang diperoleh dengan mengurutkan kunjungan pelanggan.
c
Pencarian solusi neighborhood Neighborhood pada algoritme tabu search didefinisikan sebagai solusi yang diperoleh dengan melakukan satu „move‟. Dalam karya ilmiah ini, move merupakan proses penghilangan sisi yang ada dalam solusi kemudian menambahkan sisi yang baru ke dalam solusi. Setiap move akan menghasilkan satu solusi neighborhood. Terdapat empat tipe move untuk menentukan neighborhood dalam tabu search, yaitu tiga tipe move antar-rute (relokasi, interchange, dan crossover) dan satu tipe move di dalam rute (2-opt). Setiap tipe dari move antar-rute dapat membuat neighborhood-nya masingmasing. Pencarian neighborhood dilakukan secara iteratif hingga kriteria penghentian dalam pencarian neighborhood terpenuhi. Solusi neighborhood dapat dicari dengan dua kriteria : a first admissible solution, yaitu solusi fisibel pertama yang diperoleh dengan melakukan move, atau b best admissible solution, yaitu solusi fisibel terbaik yang diperoleh dengan melakukan move. First admissible solution sebaiknya digunakan ketika pencarian solusi neighborhood tidak dapat dilakukan secara keseluruhan. Best admissible solution selalu menghasilkan hasil yang lebih baik sehingga best admissible solution sering digunakan dalam semua tes neighborhood. Pemilihan move berdasarkan best admissible solution dapat menggunakan move_value yaitu selisih jarak total sisi yang dihilangkan dengan jarak total sisi yang ditambahkan. Misalkan untuk contoh relokasi pada Gambar 1, sisi ( ), ( ) dan ( ) dihilangkan dari rute dan akan diganti berturut-turut oleh sisi ( ), ). Nilai move_value dari relokasi didefinisikan oleh ( ) dan ( ( ) ( ) ( ) ( ) ( ) ( ) ) merupakan jarak antara pelanggan dengan ( dengan . Nilai move_value untuk interchange, crossover, dan 2-opt dapat dilihat pada Lampiran 1. Move dengan nilai move_value terbesar dipilih untuk menentukan solusi neighborhood. Penggunaan short-term memory Short-term memory merupakan salah satu struktur memori berbasis jangka pendek yang digunakan pada algoritme tabu search. Short-term memory menggunakan tabu list, tabu tenure dan kriteria aspirasi. Short-term memory
9
memiliki fungsi untuk menyimpan semua move yang telah dilakukan dalam pencarian solusi. Tabu list adalah list yang digunakan untuk menyimpan sisi yang bersifat tabu. Sebuah sisi bersifat tabu ketika sisi tersebut telah digunakan dalam sebuah move (penambahan dan penghapusan sisi) pada iterasi sebelumnya. Sisi yang disimpan dalam tabu list bersifat tabu-aktif untuk beberapa iterasi. Penetapan sisi sebagai tabu-aktif berguna untuk menghindari ditemukan kembali solusi yang sama pada iterasi selanjutnya. Status tabu-aktif berbeda untuk sisi yang dihilangkan atau ditambahkan. Status tabu-aktif untuk sisi yang ditambahkan bermakna sisi tersebut tidak diperbolehkan untuk dihapus untuk beberapa iterasi. Status tabu-aktif untuk sisi yang dihapus bermakna sisi tersebut tidak diperbolehkan untuk ditambahkan pada beberapa iterasi selanjutnya. Sebuah move dianggap tabu ketika sisi yang ditambahkan atau yang dihilangkan bersifat tabuaktif. Tabu list befungsi untuk menghindari ditemukan kembali solusi yang sama serta untuk mengarahkan pencarian solusi ke solusi lain yang belum pernah ditemukan sebelumnya. Tabu list bersifat FIFO (First In First Out) dalam menyimpan sisi. Tabu tenure merupakan suatu nilai untuk menentukan lamanya suatu sisi bersifat tabu aktif (berada pada tabu list). Nilai tabu tenure juga digunakan untuk membedakan sisi yang dihilangkan dari solusi dan sisi yang ditambahkan di dalam tabu list. Sisi yang ditambahkan mempunyai nilai tenure yang lebih rendah dari sisi yang dihilangkan. Tidak terdapat ukuran yang pasti untuk menentukan panjang tabu list dan nilai tabu tenure untuk suatu kasus. Status tabu-aktif pada sebuah sisi tidak digunakan untuk membatasi pencarian solusi neighborhood. Status tabu pada sebuah move dapat dilanggar apabila memenuhi kriteria aspirasi yaitu move yang bersifat tabu aktif menghasilkan solusi neighborhood yang memiliki nilai fungsi objektif yang lebih baik dari solusi terbaik yang pernah ditemukan sebelumnya. Misalkan solusi sekarang s* dan solusi neighborhood yang dihasilkan dari move yang berstatus tabu ialah s’. Untuk masalah minimisasi, status tabu dari move dapat dilanggar (memenuhi kriteria aspirasi) apabila f(s’) < f(s*) dengan f(s) adalah nilai fungsi objektif dari solusi s, maka solusi yang diperoleh dengan dengan melanggar status tabu lebih baik dari solusi sekarang (Schneider 2011). Penggunaan long-term memory Long-term memory pada karya ilmiah ini adalah struktur memori yang berbasis frekuensi. Long-term memory menyimpan frekuensi penggunaan sisi yang digunakan pada solusi yang telah ditemukan. Long-term memory digunakan pada fase intensifikasi dan fase diversifikasi. Fase intensifikasi memiliki tujuan melakukan pencarian neighborhood untuk menyelidiki solusi terbaik yang telah ditemukan secara lebih mendetail serta untuk meyakinkan bahwa solusi terbaik yang telah ditemukan pada fase sebelumnya telah ditemukan. Pencarian solusi neighborhood ditambahkan dengan insentif (incentive) berupa frekuensi penggunaan sisi yang ditambahkan dan yang dihilangkan. Pemilihan move menggunakan nilai economy of the movement (eco_mov). Untuk contoh relokasi pada Gambar 1, sisi ( ), ( ) dan ( ) dihilangkan dari rute dan akan diganti berturut-turut oleh sisi ( ), ( ) dan ( ). Nilai didefinisikan oleh
10
( ) , ( )( ) , ( )( ) , ( )( ) ( ) ( ) ( ) ( ) ( ) Pada fase intensifikasi, move yang mempunyai nilai eco_movi terbesar yang dipilih sebagai solusi neighborhood. Nilai untuk interchange, crossover dan 2-opt dapat dilihat pada Lampiran 1. Fase diversifikasi dimaksudkan untuk mengarahkan algoritme tabu search untuk melakukan pencarian solusi ke daerah solusi yang belum dikunjungi pada iterasi-iterasi sebelumnya. Pencarian solusi neighborhood ditambahkan dengan suatu insentif berupa frekuensi penggunaan sisi yang telah digunakan pada iterasiiterasi sebelumnya. Untuk contoh relokasi pada Gambar 1, nilai eco_movd didefinisikan oleh ( ) ( ) ( ) ( ) ( ) ( ) ( ) , ( )( ) [ ( )] ( ) , ( )dengan ( ) adalah jarak/panjang sisi berarah( ), ( ) adalah residence frequency dari sisi berarah( ), incentive didefinisikan sebagai ratarata semua jarak pada matriks jarak antarpelanggan. Residence frequency yaitu frekuensi penggunaan sisi berarah yang terdapat pada solusi yang telah ditemukan. Pada fase diversifikasi, move dengan eco_movd yang terbesar yang dipilih sebagai solusi neighborhood. Nilai untuk interchange, crossover dan 2-opt dapat dilihat pada Lampiran 1. Kriteria penghentian algoritme Aturan penghentian algoritme tabu search dalam karya ilmiah ini yaitu : a. tidak terdapat lagi move yang fisibel, b. banyaknya iterasi maksimum telah dilakukan. Setelah diketahui tahapan-tahapan dalam tabu search, berikut ditampilkan bagan algoritme tabu search seperti pada Lampiran 2. Berdasarkan penggunaan memori pada algoritme tabu search yaitu short-term memory dan long-term memory, algoritme tabu search dapat dikelompokkan dalam beberapa fase, antara lain: Fase 0. Penentuan solusi awal: menggunakan salah satu dari prosedur heuristik yaitu IGR1, IGR2, SGR1, atau SGR2. Fase 1. Fase awal: fase ini dimulai dari solusi awal yang didapatkan dari fase 0 dan solusi awal didefinisikan sebagai solusi sekarang. Pada fase ini, iterasi dimulai pencarian solusi neighborhood dari solusi sebelumnya (solusi awal untuk iterasi pertama), kemudian dilakukan pengecekan status move apakah bersifat tabu aktif atau tidak (jika tabu aktif dilakukan pengecekan kriteria aspirasi), update tabu list, dan update solusi sekarang (jika solusi yang
11
ditemukan setelah melakukan move memiliki nilai fungsi objektif lebih baik dari solusi sekarang). Iterasi dilakukan sebanyak initer iterasi. Fase 2. Fase intensifikasi: fase ini dimulai dari solusi terbaik yang diperoleh pada fase 1. Pada fase ini, langkah pencarian solusi neighborhood pada fase 1 diganti dengan pencarian solusi neighborhood menggunakan prosedur intensifikasi. Nilai tabu tenure dipecah menjadi dua pada saat fase ini. Fase ini dilakukan sebanyak iiter iterasi. Fase 3. Fase diversifikasi: fase ini dimulai dari solusi yang diperoleh pada fase 2. Pada fase ini, langkah pencarian solusi neighborhood pada fase 2 diganti dengan pencarian solusi neighborhood menggunakan prosedur diversifikasi. Pada fase ini nilai tabu tenure pada fase sebelumnya diperbaiki. Fase ini dilakukan sebanyak diter iterasi. Fase 4. Fase standar: fase ini dimulai dari solusi yang didapat dari fase 3. Pencarian solusi neighborhood algoritme tabu search dilakukan seperti pada fase 1. Nilai tabu tenure dari penghilangan dan penambahan sisi ditetapkan kembali. Fase ini dilakukan sebanyak interiter iterasi. Fase 5. Fase interaktif: ulangi fase 2-4 hingga salah satu dari kriteria penghentian dicapai. Fase 6. Pemberian nilai awal kembali: solusi awal yang baru dicari dengan prosedur heuristik (IGR1, IGR2, SGR1, dan SGR2) yang belum digunakan pada Fase 0. Fase 1-5 diulangi hingga empat prosedur heuristik telah digunakan untuk memproduksi solusi awal.
APLIKASI MASALAH Perusahaan air minum Fresh memiliki kendala dalam pendistribusian produk air minumnya. Perusahaan tersebut menerima permintaan pick-up dan delivery botol galon dari pelanggan yang dilayaninya. Perusahaan menginginkan rute yang optimal untuk meminimumkan total jarak yang ditempuh untuk melakukan kegiatan pick-up dan delivery dan perusahaan harus memenuhi seluruh permintaan yang diberikan pelanggannya. Misalkan perusahaan mempunyai 3 kendaraan untuk melakukan kegiatan pick-up dan delivery. Kendaraan tersebut dapat mengangkut barang sebanyak 90 galon dalam satu kali angkut sehingga total barang yang diambil dari pelanggan dan yang dikirim ke pelanggan tidak boleh melebihi kapasitas kendaraan. Satu pelanggan hanya boleh dikunjungi oleh satu kendaraan dan setelah pelanggan tersebut dikunjungi, maka kendaraan harus meninggalkan pelanggan tersebut. Perusahaan tersebut membatasi jarak maksimal yang boleh ditempuh setiap kendaraan yang beroperasi sejauh 150 km. Jarak antarpelanggan serta banyaknya permintaan pick-up dan delivery setiap pelanggan diberikan pada Tabel 1.
12
Tabel 1 Data jarak, permintaan pick-up dan delivery pelanggan Pelanggan ke0 1 2 3 4 5 6 7 8 9 10 Pick-up Delivery
0
1
2
3
4
5
6
7
8
9
10
0
5 0
7 3 0
12 8 5 0
35 31 28 27 0
7 2 5 10 33 0
19 14 17 22 45 12 0
3 8 10 15 38 10 22 0
8 13 15 20 43 15 27 5 0
30 35 37 42 65 37 49 27 22 0
0 0
18 20
36 35
20 21
16 15
41 40
23 25
25 27
21 19
12 11
48 53 55 60 83 55 67 45 40 18 0 12 10
Penyelesaian Masalah dengan Algoritme Tabu Search Penentuan solusi awal Dalam karya ilmiah ini, penetuan solusi awal dilakukan dengan metode IGR1 (kendala jarak tempuh maksimum kendaraan diabaikan) yaitu menentukan grup untuk setiap pelanggan kemudian menentukan rute kendaraan yang mengunjungi setiap pelanggan untuk setiap grup. Penentuan grup untuk setiap pelanggan Pilih pelanggan untuk grup pertama dengan pelanggan yang mempunyai ( ) 0 terlebih dahulu kemudian pelanggan dengan () dengan syarat tidak melebihi daya angkut maksimum kendaraan. Bentuk grup baru jika masih ada pelanggan yang belum mempunyai grup. () ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) Tabel 2 Grup dan rute kendaraan berdasarkan smallest maximum load Grup Pelanggan Rute awal Pick-up Delivery Jarak 1 1, 3, 6, 4 0, 1, 3, 6, 4, 0 77 81 115 km 2 7, 2, 8 0, 7, 2, 8, 0 82 81 36 km 3 5, 9, 10 0, 5, 9, 10, 0 65 61 110 km Total jarak tempuh kendaraan 261 km Penentuan rute untuk setiap grup pelanggan Gunakan metode heuristik 2-opt untuk meminimumkan jarak yang ditempuh pada setiap rute yang telah dibuat.
13
Tabel 3 Jalur dan jarak solusi awal berdasarkan IGR1 Grup Rute 1 0, 1, 6, 4, 3, 0 2 0, 7, 8, 2, 0 3 0, 5, 10, 9, 0 Total jarak tempuh kendaraan
Pick-up 77 82 65
Delivery 81 81 61
Jarak 103 km 30 km 110 km 243 km
Gambar 5 Rute solusi awal menggunakan IGR1 Ketika penentuan solusi awal, tabu list merupakan himpunan kosong. Tabu list : {}
Fase awal Pada fase ini, misalkan ditentukan nilai tabu tenure untuk sisi yang dihilangkan adalah 3 dan sisi yang ditambahkan adalah 2. Banyaknya sisi yang boleh berada pada tabu list adalah 20 sisi. Pencarian solusi neighborhood menggunakan best admissible solution. Iterasi 1 Pencarian solusi neighborhood Move terbaik yang dipilih yaitu relokasi yang memiliki nilai move_value sebesar 10 yaitu dengan menghilangkan sisi (9,0), (7,8), dan (8,2) kemudian menambahkan sisi (7,2), (9,8), dan (8,0) (lihat Lampiran 3). Sisi (9,0), (7,8), (8,2) (7,2), (9,8), dan (8,0) tidak bersifat tabu aktif karena sisi tersebut tidak ada pada tabu list. Gambar solusi awal dan solusi neighborhood-nya ialah sebagai berikut :
Gambar 6 Solusi awal dan solusi neighborhood-nya Path di antara dua pelanggan Sisi yang dihilangkan Sisi yang ditambahkan
14
Banyaknya barang dan jarak yang diangkut pada setiap rute diberikan pada Tabel 4. Tabel 4 Jalur dan jarak solusi neighborhood pada iterasi ke-1 Grup Rute 1 0, 1, 6, 4, 3, 0 2 0, 7, 2, 0 3 0, 5, 10, 9, 8, 0 Total jarak tempuh kendaraan
Pick-up 77 61 86
Delivery 81 62 80
Jarak 103 km 20 km 110 km 233 km
Update tabu list menjadi : {{(7,2),(9,8),(8,0)},{(7,8),(8,2),(9,0)}}. Sisi yang dihilangkan yaitu sisi (7,8),(8,2),(9,0) mempunyai nilai tabu tenure 3 dan sisi yang ditambahkan yaitu sisi (7,2),(9,8),(8,0) mempunyai nilai tabu tenure 2. Sisi yang memiliki nilai tabu tenure 3 dilarang (bersifat tabu-aktif) ditambahkan atau dihilangkan pada tiga iterasi selanjutnya. Solusi pada iterasi 1 lebih baik dari solusi sekarang sehingga solusi sekarang diganti dengan solusi yang terdapat pada iterasi 1. Kriteria penghentian belum terpenuhi, lanjutkan ke iterasi berikutnya.
Iterasi 2 Pilih move yaitu crossover dengan menghilangkan sisi (7,2) dan (5,10) kemudian menambahkan sisi (5,2) dan (7,10). Sisi (7,2) bersifat tabu aktif. Cek apakah solusi neighborhood yang dihasilkan dari move memenuhi kriteria aspirasi. Banyaknya barang yang diangkut dan jarak pada setiap rute dari solusi neighborhood diberikan pada Tabel 5. Tabel 5 Jalur dan jarak solusi neighborhood pada iterasi ke-2 Rute Jalur Pick-up Delivery Jarak 1 0, 1, 6, 4, 3, 0 77 81 103 km 2 0, 5, 2, 0 77 75 19 km 3 0, 7, 10, 9, 8, 0 70 67 96 km Total jarak tempuh kendaraan 218 km Nilai fungsi objektif solusi neighborhood yang didapat jika melanggar status tabu move yaitu 218 km, lebih baik dari solusi sekarang (233 km). Kriteria aspirasi terpenuhi. Status tabu pada move dapat dilanggar. Gambar solusi neighborhood :
Gambar 7 Solusi yang diperoleh dari iterasi 1 dan solusi neighborhood-nya
15
Update tabu list menjadi : {{(7,2),(9,8),(8,0)}, {(7,8),(8,2),(9,0),(7,10),(5,2)}, {(7,2),(5,10)}}. Sisi (7,2),(9,8),(8,0) mempunyai nilai tabu tenure 1 (pada iterasi 1 mempunyai nilai tabu tenure 2) dan sisi (7,8),(8,2),(9,0) mempunyai nilai tabu tenure 2 (pada iterasi 1 mempunyai nilai tabu tenure 3). Sisi yang ditambahkan yaitu sisi (7,10),(5,2) mempunyai nilai tabu tenure 2 serta sisi yang dihilangkan yaitu sisi (7,2),(5,10) mempunyai nilai tabu tenure 3. Sisi yang ada pada tabu list bersifat tabu untuk digunakan sebagai move pada iterasi selanjutnya. Solusi pada iterasi 2 lebih baik dari solusi sekarang sehingga solusi sekarang diganti dengan solusi yang didapat pada iterasi 2. Kriteria penghentian belum terpenuhi, lanjutkan ke iterasi berikutnya.
Iterasi 3 Pilih move yaitu crossover dengan menghilangkan sisi (5,2) dan (6,4) kemudian menambahkan sisi (5,4) dan (6,2). Sisi (5,2) bersifat tabu. Cek apakah solusi neighborhood yang dihasilkan dari move memenuhi kriteria aspirasi. Banyaknya barang yang diangkut dan jarak yang ditempuh pada setiap rute diberikan pada Tabel 6. Tabel 6 Jalur dan jarak solusi neighborhood yang bersifat tabu pada iterasi ke-3 Grup Rute 1 0, 5, 4, 3, 0 2 0, 1, 6, 2, 0 3 0, 7, 10, 9, 8, 0 Total jarak tempuh kendaraan
Pick-up 77 77 70
Delivery 76 80 67
Jarak 79 km 43 km 96 km 218 km
Solusi yang didapat jika melanggar status tabu tidak lebih baik dari solusi sekarang yaitu 218 km. Kriteria aspirasi tidak terpenuhi. Pilih move yaitu dengan melakukan 2-opt dengan menghilangkan sisi (0,1) dan (6,4) kemudian menambahkan sisi (0,6) dan (1,4). Sisi (0,1), (6,4), (0,6) dan (1,4) tidak ada pada tabu list. Gambar solusi neighborhood :
Gambar 8 Solusi yang diperoleh dari iterasi 2 dan solusi neighborhood-nya
Update tabu list : {{(7,8),(8,2),(9,0),(7,10),(5,2)},{(7,2),(5,10),(0,6),(1,4)}, {(0,1),(6,4)}}. Pada iterasi 3, sisi (7,2),(9,8),(8,0) mempunyai nilai tabu tenure 0 sehingga sisi tersebut tidak bersifat tabu-aktif pada iterasi selanjutnya. Sisi (7,8),(8,2),(9,0),(7,10),(5,2) mempunyai nilai tabu tenure 1, sisi
16
(7,2),(5,10),(0,6),(1,4) mempunyai nilai tabu tenure 2, dan sisi (0,1),(6,4) mempunyai nilai tabu tenure 3. Banyaknya barang dan jarak pada setiap rute diberikan pada Tabel 7. Tabel 7 Jalur dan jarak solusi neighborhood pada iterasi ke-3 Grup Rute 1 0, 6, 1, 4, 3, 0 2 0, 5, 2, 0 3 0, 7, 10, 9, 8, 0 Total jarak tempuh kendaraan
Pick-up 77 77 70
Delivery 81 75 67
Jarak 103 km 19 km 96 km 218
Solusi pada iterasi 3 tidak lebih baik dari solusi sekarang sehingga solusi sekarang tidak berubah. Kriteria penghentian belum terpenuhi, lanjutkan ke iterasi berikutnya.
Langkah-langkah pada iterasi selanjutnya sama dengan langkah pada iterasi sebelumnya yaitu pencarian solusi neighborhood, cek tabu list, kriteria aspirasi (jika move bersifat tabu), update tabu list, bandingkan solusi neighborhood dengan solusi terbaik sekarang. Lanjutkan iterasi sampai memenuhi kriteria pemberhentian atau batas banyaknya iterasi pada fase awal. Pada fase awal ini, iterasi dilakukan sebanyak 5 iterasi. Pada 5 iterasi pertama didapatkan solusi terbaik pada iterasi ke-2 dengan total jarak 218 km (lihat Lampiran 4). Fase intensifikasi Pada fase ini, nilai tabu tenure pada fase awal dibagi dua sehingga untuk sisi yang ditambahkan mempunyai nilai tabu tenure 1 dan sisi yang dihilangkan mempunyai nilai tabu tenure 2. Berdasarkan Tabel 1, dapat diketahui jarak antarpelanggan sehingga dapat diketahui besarnya incentive (rata-rata jarak antarpelanggan) yaitu sebesar 29.34. Frekuensi penggunaan sisi dapat dilihat pada Lampiran 5. Fase ini dimulai dari solusi terbaik yang telah ditemukan pada fase awal yaitu solusi pada iterasi ke-2. Pada fase ini, pencarian solusi neighborhood dilakukan dengan memilih move yang mempunyai eco_movi terbesar. Jika move bersifat tabu, cek apakah move memenuhi kriteria aspirasi. Iterasi 6 (fase intensifikasi) Pilih move yang mempunyai eco_movi sebesar 176.04 (lihat Lampiran 6), yaitu dengan melakukan 2-opt dengan menghilangkan sisi (7,10) dan (8,0), kemudian menambahkan sisi (7,8), dan (10,0). Sisi (7,10), (8,0), (7,8), dan (10,0) tidak bersifat tabu aktif Banyaknya barang dan jarak yang diangkut pada setiap rute diberikan pada Tabel 8.
17
Tabel 8 Jalur dan jarak solusi neighborhood pada fase intensifikasi Grup Rute 1 0, 1, 6, 4, 3, 0 2 0, 5, 2, 0 3 0, 7, 8, 9, 10, 0 Total jarak tempuh kendaraan
Pick-up 77 77 70
Delivery 81 75 67
Jarak 103 km 19 km 96 km 218 km
Update tabu list menjadi : {{(4,3),(3,0),(0,7),(5,1),(6,2),(7,8),(10,0)},{(6,1), (5,2),(7,10),(8,0)}}. Sisi (4,3),(3,0),(0,7),(5,1),(6,2),(7,8),(10,0) mempunyai nilai tabu tenure 1, sisi (6,1),(5,2),(7,10),(8,0) mempunyai nilai tabu tenure 2, dan sisi (6,1),(5,2) mempunyai nilai tabu tenure 3. Kriteria pemberhentian belum terpenuhi, lanjutkan ke iterasi berikutnya.
Fase diversifikasi Pada fase ini, iterasi dimulai dari solusi terakhir yang ditemukan pada fase intensifikasi. Nilai tabu tenure pada fase intensifikasi diperbaiki sehingga untuk sisi yang ditambahkan mempunyai nilai tabu tenure 2 dan sisi yang dihilangkan mempunyai nilai tabu tenure 3. Pencarian solusi neighborhood dengan memilih move yang mempunyai eco_movd terbesar. Jika move tersebut bersifat tabu, cek apakah memenuhi kriteria aspirasi. Iterasi 7 (fase diversifikasi) Pilih move yang mempunyai eco_movd sebesar 268.4, yaitu dengan melakukan crossover dengan menghilangkan sisi (6,4) dan (8,9) dan menambahkan sisi (6,9) dan (8,4). Sisi (6,4), (8,9), (6,9) dan (8,4) tidak bersifat tabu aktif Banyaknya barang dan jarak yang diangkut pada setiap rute diberikan pada Tabel 9 Tabel 9 Jalur dan jarak solusi neighborhood pada fase diversifikasi Grup Rute 1 0, 1, 6, 9, 10, 0 2 0, 5, 2, 0 3 0, 7, 8, 4, 3, 0 Total jarak tempuh kendaraan
Pick-up 65 77 82
Delivery 66 75 82
Jarak 134 km 19 km 190 km 243 km
Update tabu list menjadi : {{(6,1),(5,2),(7,10),(8,0)},{(6,9),(8,4)},{(6,4), (8,9)}}. Sisi (6,1),(5,2),(7,10),(8,0) mempunyai nilai tabu tenure 1, sisi (6,9),(8,4) mempunyai nilai tabu tenure 2, dan sisi (6,4),(8,9) mempunyai nilai tabu tenure 3. Kriteria pemberhentian belum terpenuhi, lanjutkan ke iterasi berikutnya.
Fase Standar Pada fase ini kembali dilakukan algoritme tabu search serta nilai tabu tenure untuk sisi yang ditambahkan dan sisi yang dihilangkan diperbaiki. Fase ini dilakukan seperti pada fase awal dalam pencarian solusi neighborhood. Fase ini akan dilakukan sebanyak 2 iterasi (lihat Lampiran 4).
18
Fase Interaktif Pada fase ini, iterasi diulangi dari fase awal, fase intensifikasi, fase diversifikasi dan fase standar. Fase-fase tersebut dapat dilakukan hingga kriteria pemberhentian telah tercapai pada salah satu fase. Pada karya ilmiah ini, banyaknya iterasi dibatasi hingga 15 iterasi. Didapatkan solusi seperti pada Lampiran 4. Hingga iterasi 15, didapatkan solusi terbaik yaitu pada iterasi 14 dengan nilai fungsi objektif sebesar 208 km. Pemberian Nilai Awal Kembali Penentuan solusi awal yang telah digunakan adalah metode IGR1. Selanjutnya algoritme tabu search akan diulangi dengan penentuan nilai awal menggunakan metode SGR2 yaitu dengan melakukan pengelompokan pelanggan () dengan kemudian menambahkan pelanggan ke dalam grup dengan tidak melanggar batas daya angkut kendaraan dan jarak tempuh kendaraan. Penentuan grup dan rute pelanggan Tabel 10 Grup dan rute kendaraan berdasarkan largest maximum load Grup Pelanggan Rute 1 2, 4, 8, 9 0, 2, 4, 8, 9, 0 2 5, 10 0, 5, 10, 0 Total jarak tempuh kendaraan
Pick-up 85 53
Delivery 80 50
Jarak 130 km 110 km 240 km
Pelanggan 1, 3, 6, dan 7 disisipkan kedalam grup dengan tidak melanggar batas daya angkut maksimum kendaraan dan jarak tempuh kendaraan. Tabel 11 Grup dan rute kendaraan berdasarkan SGR2 Grup 1 2 3
Pelanggan 2, 4, 8, 9 5, 10, 1 3, 6, 7
Rute Pick-up Delivery 0, 2, 4, 8, 9, 0 85 80 0, 5, 10, 1, 0 70 71 0, 3, 6, 7, 0 68 73 Total jarak tempuh kendaraan
Jarak 130 km 120 km 59 km 309 km
Penentuan rute untuk setiap grup pelanggan Gunakan metode heuristik 2-opt untuk mengurangi jarak yang ditempuh pada rute yang telah dibuat. Tabel 12 Jalur dan jarak solusi awal berdasarkan SGR2
Grup Rute Pick-up Delivery Jarak 1 0, 2, 4, 8, 9, 0 85 80 130 km 2 0, 10, 5, 1, 0 78 71 110 km 3 0, 3, 6, 7, 0 65 73 59 km Total jarak tempuh kendaraan 299 km Pada penentuan nilai awal dengan menggunakan metode SGR2 ini, banyaknya total iterasi dibatasi hingga 10 iterasi. Pencarian solusi neighborhood menggunakan first admissible solution. Hingga iterasi 10, didapatkan solusi terbaik dengan nilai fungsi objektif sebesar 208 km (lihat Lampiran 8).
SIMPULAN DAN SARAN Simpulan Penyelesaiaan masalah VRPSPD menggunakan algoritme tabu search memiliki tahapan-tahapan, yaitu penentuan solusi awal, pencarian solusi neighborhood, penggunaan short-term memory dan long-term memory, dan kriteria penghentian algoritme. Short-term memory dan long-term memory merupakan dua struktur memori yang digunakan dalam algoritme tabu search yang digunakan untuk menyimpan solusi yang telah ditemukan selama iterasi. Dua struktur memori ini memiliki fungsi yang berbeda. Berdasarkan struktur memori ini, algoritme tabu search dapat dikelompokkan dalam 6 fase yaitu fase penentuan nilai awal, fase awal, fase intensifikasi, fase diversifikasi, fase standar, dan fase interaktif. Dalam studi kasus masalah pendistribusian produk air minum, penentuan solusi awal menggunakan metode IGR1, fase awal dilakukan sebanyak 5 iterasi, fase intensifikasi dan fase diversifikasi masing-masing dilakukan sebanyak satu iterasi, dan fase standar dilakukan sebanyak dua iterasi. Setelah banyaknya iterasi pada fase standar dilakukan, iterasi dilanjutkan ke fase awal. Fase-fase ini diulangi hingga kriteria penghentian algoritme terpenuhi. Langkah-langkah ini menghasilkan solusi minimum pada iterasi 14 dari total 15 iterasi yang dilakukan. Dalam penentuan solusi awal menggunakan metode SGR2, fase awal dilakukan sebanyak 5 iterasi, fase intensifikasi dan fase diversifikasi masing-masing dilakukan sebanyak satu iterasi, dan fase standar dilakukan sebanyak dua iterasi. Setelah banyaknya iterasi pada fase standar dilakukan, iterasi dilanjutkan ke fase awal. Fase-fase ini diulangi hingga kriteria penghentian algoritme terpenuhi. Langkah-langkah ini menghasilkan solusi minimum pada iterasi 7 dari total 10 iterasi yang dilakukan.
Saran Jika ada yang ingin lebih mendalami karya ilmiah ini, disarankan untuk membangun software yang dapat menerapkan algoritme tabu search.
DAFTAR PUSTAKA Glover F, Laguna M. 1997. Tabu Search. Boston (US): Kluwer Academic. Montane FAT, Galvao RD. 2006. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computer & Operations Research. 33:595-619. Doi:10.1016/j.cor.2004.07.009. Pradhana FE, Sugiharti E, Kharis M. 2012. Penerapan algoritma tabu search untuk menyelesaikan vehicle routing problem. UJM. 1(1):1-6. Schneider U. 2011. A tabu search tutorial based on a real-world scheduling problem. CEJOR. 19:467-493. Doi:10.1007/s10100-010-0137-8.
20
Lampiran 1 Move_value, crossover, dan 2-opt
dan
untuk interchange,
Interchange Seperti contoh interchange pada Gambar 2, sisi ( ), ( ), ( ), dan ( ) dihilangkan dari rute dan akan diganti berturut-turut oleh sisi ( ), ( ), ( ), dan ( ). Nilai move_value didefinisikan oleh ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) Nilai
Nilai
didefinisikan oleh ( ) , ( ) , ( ) [ ( ) [ ( ) ( ( ) ( ( ) ( ( ) (
( ( ( ( ) ) ) )
didefinisikan oleh ( ) ( ( ) ( ( ) ( ( ) ( ( ) [ ( ) [ ( (
) )
[ ,
)))] )]
) ) ) ) ( ( ( (
)] )] )] )-
Crossover Seperti contoh crossover pada Gambar 3, sisi ( ) dan ( dihilangkan dari rute dan akan diganti berturut-turut oleh sisi ( ( ). Nilai move_value didefinisikan oleh ( ) ( ) ( ) ( ) Nilai
didefinisikan oleh ( ) , ( ( ) [ ( ( ) ( ) ( ) ( )
))]
) ) dan
21
Nilai
didefinisikan oleh ( ) ( ) ( ) ( ) ( ) [ ( )] ( ) [ (
)]
2-opt Seperti contoh 2-opt pada Gambar 3, sisi ( ) dan ( dihilangkan dari rute dan akan diganti berturut-turut oleh sisi ( ( ). Nilai move_value didefinisikan oleh ( ) ( ) ( ) ( ) Nilai
didefinisikan oleh ( ) , ( ( ) [ ( ( ) ( ( ) ( )
Nilai
didefinisikan oleh ( ) ( ( ) ( ( ) [ ( ) [ (
))] )
) ) ( )]
)]
) ) dan
22
Lampiran 2 Skema algoritme tabu search
23
Lampiran 3 Nilai move_value untuk move yang fisibel terhadap batas daya angkut kendaraan Sisi yang dihilangkan
Sisi yang ditambahkan
Panjang Panjang sisi sisi yang yang Move_value dihilangkan ditambahkan
2-opt (0,1),(6,4) (0,1),(4,3) (1,6),(4,3) (1,6),(3,0) (6,4),(3,0) (0,7),(8,2) (7,8),(2,0) (0,5),(10,9) (5,10),(9,0) Relokasi (0,1),(1,6),(0,5) (0,1),(1,6),(5,10) (0,1),(1,6),(10,9) (0,1),(1,6),(9,0) (1,6),(6,4),(0,5) (1,6),(6,4),(5,10) (1,6),(6,4),(10,9) (1,6),(6,4),(9,0) (6,4),(4,3),(0,5) (6,4),(4,3),(5,10) (6,4),(4,3),(10,9) (6,4),(4,3),(9,0) (4,3),(3,0),(0,5) (4,3),(3,0),(5,10) (4,3),(3,0),(10,9) (4,3),(3,0),(9,0) (0,7),(7,8),(0,5) (0,7),(7,8),(5,10) (0,7),(7,8),(10,9) (0,7),(7,8),(9,0) (7,8),(8,2),(0,5) (7,8),(8,2),(10,9) (7,8),(8,2),(9,0) (7,8),(8,2),(5,10) Interchange (0,1),(1,6),(0,7), (7,8) (0,1),(1,6),(7,8), (8,2) (0,1),(1,6),(5,10), (10,9) (0,1),(1,6),(10,9), (9,0) (1,6),(6,4),(0,7), (7,8)
(0,6),(1,4) (0,3),(1,3) (1,4),(6,4) (1,3),(6,0) (6,3),(4,0) (0,8),(7,2) (7,2),(8,0) (0,10),(5,9) (5,9),(10,0)
50 32 41 26 57 18 12 25 85
50 43 53 27 57 18 18 85 85
0 11 12 1 0 0 6 60 0
(0,6),(0,1),(1,5) (0,6),(5,1),(1,10) (0,6),(10,1),(1,9) (0,6),(9,1),(1,0) (1,4),(0,6),(6,5) (1,4),(5,6),(6,10) (1,4),(10,6),(6,9) (1,4),(9,6),(6,0) (6,3),(0,4),(4,5) (6,3),(5,4),(4,10) (6,3),(10,4),(4,9) (6,3),(9,4),(4,0) (4,0),(0,3),(3,5) (4,0),(5,3),(3,10) (4,0),(10,3),(3,9) (4,0),(9,3),(3,0) (0,8),(0,7),(7,5) (0,8),(5,7),(7,10) (0,8),(10,7),(7,9) (0,8),(9,7),(7,0) (7,2),(0,8),(8,5) (7,2),(10,8),(8,9) (7,2),(9,8),(8,0) (7,2),(5,8),(8,10)
26 74 37 49 66 144 77 89 79 127 90 102 46 94 57 69 15 63 26 38 27 38 50 75
26 74 107 59 62 110 147 99 90 138 170 122 57 105 137 89 21 63 80 38 33 72 40 65
0 0 70 10 4 4 70 10 11 11 80 20 11 11 80 20 6 0 54 0 6 34 10 10
27
43
16
39
46
7
92
152
60
67
137
70
67
92
25
(0,7),(7,6),(0,1), (1,8) (0,8),(8,6),(7,1), (1,2) (0,10),(10,6),(5,1), (1,9) (0,9),(9,6),(10,1), (1,0) (1,7),(7,4),(0,6), (6,8)
24 (1,6),(6,4),(7,8), (8,2) (1,6),(6,4),(5,10), (10,9) (1,6),(6,4),(10,9), (9,0) (6,4),(4,3),(7,8), (8,2) (6,4),(4,3),(5,10), (10,9) (6,4),(4,3),(10,9), (9,0) (4,3),(3,0),(0,7), (7,8) (4,3),(3,0),(7,8), (8,2) (4,3),(3,0),(5,10), (10,9) (4,3),(3,0),(10,9), (9,0) (0,7),(7,8),(5,10), (10,9) (0,7),(7,8),(10,9), (9,0) (7,8),(8,2),(5,10), (10,9) (7,8),(8,2)(10,9), (9,0) (8,2),(2,0),(0,5), (5,10) (8,2),(2,0),(5,10), (10,9) (8,2),(2,0)(10,9), (9,0) Crossover (1,6),(7,8) (1,6),(8,2) (1,6),(10,9) (6,4),(7,8) (6,4),(8,2) (6,4),(10,9) (4,3),(8,2) (4,3),(10,9) (7,8),(10,9) (8,2),(10,9) (8,2),(5,10)
(1,8),(8,4),(7,6), (6,2) (1,10),(10,4),(5,6), (6,9) (1,9),(9,4),(10,6), (6,0) (6,8),(8,3),(7,4), (4,2) (6,10),(10,3),(5,4), (4,9) (6,9),(9,3),(10,4), (4,0) (4,7),(7,0),(0,3), (3,8) (4,8),(8,0),(7,3), (3,2) (4,10),(10,0),(5,3), (3,9) (4,9),(9,0),(10,3), (3,0) (0,10),(10,8),(5,7), (7,9) (0,9),(9,8),(10,7), (7,0) (7,10),(10,2),(5,8), (8,9) (7,9),(9,2),(10,8), (8,0) (8,5),(5,0),(0,2), (2,10) (8,10),(10,0),(5,2), (2,9) (8,9),(9,0),(10,2), (2,0) (1,8),(7,6) (1,2),(8,6) (1,9),10,6) (6,8),(7,4) (6,2),(8,4) (6,9),(10,4) (4,2),(8,3) (4,9),(10,3) (7,9),(10,8) (8,9),(10,2) (8,10),(5,2)
79
95
16
132
197
65
107
186
79
80
113
33
145
225
80
120
209
89
47
73
26
59
71
12
112
183
71
87
167
80
81
125
44
56
100
44
93
137
44
68
112
44
84
84
0
95
130
35
70
114
44
19 29 32 50 60 63 42 45 23 33 60
35 30 102 65 60 132 48 125 67 77 60
16 1 70 15 0 69 6 80 44 44 0
25
Lampiran 4 Rangkuman solusi pada fase awal dengan nilai awal menggunakan IGR1 Iterasi ke0
1
2
3
4
5 6 (fase intensifika si) 7 (fase diversifika si) 8 (fase standar) 9 (fase standar) 10
11
12
13
14
15
Sisi yang digunakan (0,1),(1,6),(6,4),(4,3),(3,0), (0,7),(7,8),(8,2),(2,0), (0,5),(5,10),(10,9),(9,0) (0,1),(1,6),(6,4),(4,3),(3,0), (0,7),(7,2),(2,0), (0,5),(5,10),(10,9),(9,8),(8,0) (0,1),(1,6),(6,4),(4,3),(3,0), (0,5),(5,2),(2,0), (0,7),(7,10),(10,9),(9,8),(8,0) (0,6),(6,1),(1,4),(4,3),(3,0), (0,5),(5,2),(2,0), (0,7),(7,10),(10,9),(9,8),(8,0) (0,6),(6,1),(1,4),(4,0), (0,5),(5,2),(2,0), (0,3),(3,7),(7,10),(10,9),(9,8),(8,0) (0,5),(5,1),(1,4),(4,0), (0,6),(6,2),(2,0), (0,3),(3,7),(7,10),(10,9),(9,8),(8,0) (0,1),(1,6),(6,4),(4,3),(3,0), (0,5),(5,2),(2,0), (0,7),(7,8),(8,9),(9,10),(10,0) (0,1),(1,6),(6,9),(9,10),(10,0), (0,5),(5,2),(2,0), (0,7),(7,8),(8,4),(4,3),(3,0) (0,3),(3,1),(1,6),(6,9),(9,10),(10,0), (0,5),(5,2),(2,0), (0,7),(7,8),(8,4),(4,0) (0,5),(5,6),(6,9),(9,10),(10,0), (0,3),(3,1),(1,2),(2,0), (0,7),(7,8),(8,4),(4,0) (0,6),(6,5),(5,9),(9,10),(10,0), (0,3),(3,1),(1,2),(2,0), (0,7),(7,8),(8,4),(4,0) (0,6),(6,5),(5,9),(9,10),(10,0), (0,3),(3,1),(1,4),(4,0), (0,7),(7,8),(8,2),(2,0) (0,6),(6,5),(5,9),(9,10),(10,0), (0,3),(3,4),(4,1),(1,0), (0,7),(7,8),(8,2),(2,0) (0,6),(6,5),(5,9),(9,10),(10,0), (0,3),(3,4),(4,2),(2,0), (0,7),(7,8),(8,1),(1,0) (0,6),(6,5),(5,1),(1,0), (0,3),(3,4),(4,2),(2,0), (0,7),(7,8),(8,9),(9,10),(10,0) (0,6),(6,1),(1,5),(5,0), (0,3),(3,4),(4,2),(2,0), (0,7),(7,8),(8,9),(9,10),(10,0)
Jarak total 243 km
233 km
218 km
218 km
238 km
238 km 218 km
243 km
254 km
250 km
250 km
250 km
239 km
234 km
208 km
212 km
26
Lampiran 5 Frekuensi penggunaan sisi pada 5 iterasi pertama dengan nilai awal menggunakan IGR1 Pelanggan ke0 1 2 3 4 5 6 7 8 9 10
0 0 3 6 6 2 6 3 4 5 1 0
1 3 0 0 0 3 1 5 0 0 0 0
2 6 0 0 0 0 3 1 1 1 0 0
Lampiran 6 Nilai kendaraan Sisi yang dihilangkan 2-opt (0,1),(6,4) (0,1),(4,3) (1,6),(4,3) (1,6),(3,0) (6,4),(3,0) (0,7),(10,9) (0,7),(9,8) (7,10),(9,8) (7,10),(8,0) (10,9),(8,0) Relokasi (0,1),(1,6), (0,7) (0,1),(1,6), (7,10) (0,1),(1,6), (10,9) (0,1),(1,6), (9,8) (0,1),(1,6), (8,0) (6,4),(4,3), (0,7) (6,4),(4,3), (7,10) (6,4),(4,3), (10,9)
3 6 0 0 0 4 0 0 2 0 0 0
4 2 3 0 4 0 0 3 0 0 0 0
5 6 1 3 0 0 0 0 0 0 0 2
6 3 5 1 0 3 0 0 0 0 0 0
7 4 0 1 2 0 0 0 0 1 0 4
8 5 0 1 0 0 0 0 1 0 5 0
9 1 0 0 0 0 0 0 0 5 0 6
10 0 0 0 0 0 2 0 4 0 6 0
untuk move yang fisibel terhadap batas daya angkut (a - f(b) + f(c)) incentive
Sisi yang ditambahkan
Panjang sisi yang dihilangkan
Panjang sisi yang ditambahkan
(0,6),(1,4) (0,4),(1,3) (1,4),(6,3) (1,3),(6,0) (6,3),(4,0) (0,10),(7,9) (0,9),(7,8) (7,9),(10,8) (7,8),(10,0) (10,8),(9,0)
50 32 41 26 57 21 25 67 53 26
50 43 53 27 57 75 35 67 53 70
58.68 88.02 117.36 176.04 146.7 234.72 146.7 205.38 176.04 234.72
58.68 99.02 129.36 177.04 146.7 288.72 156.7 205.38 176.04 278.72
22
32
88.02
98.02
64
80
176.04
192.04
37
107
234.72
304.72
41
67
205.38
231.38
27
37
117.36
127.36
75
95
176.04
196.04
117
143
234.72
260.72
90
170
293.4
373.4
(0,6),(0,1), (1,0) (0,6),(7,1), (1,10) (0,6),(10,1), (1,9) (0,6),(9,1), (1,8) (0,6),(8,1), (1,0) (6,3),(0,4), (4,7) (6,3),(7,4), (4,10) (6,3),(10,4), (4,9)
27 (6,4),(4,3), (9,8) (6,4),(4,3), (8,0) (4,3),(3,0), (0,7) (4,3),(3,0), (7,10) (4,3),(3,0), (10,9) (4,3),(3,0), (9,8) (4,3),(3,0), (8,0) (7,10),(10,9), (0,5) (7,10),(10,9), (5,2) (7,10),(10,9), (2,0) (10,9),(9,8), (0,5) (10,9),(9,8), (5,2) (10,9),(9,8), (2,0) Interchange (0,1),(1,6), (0,7),(7,10) (0,1),(1,6), (7,10),(10,9) (0,1),(1,6), (10,9),(9,8) (0,1),(1,6), (9,8),(8,0) (1,6),(6,4), (0,7),(7,10) (1,6),(6,4), (7,10),(10,9) (1,6),(6,4), (10,9),(9,8) (1,6),(6,4), (9,8),(8,0) (6,4),(4,3), (7,10),(10,9) (6,4),(4,3), (10,9),(9,8) (6,4),(4,3), (9,8),(8,0) (4,3),(3,0), (0,7),(7,10) (4,3),(3,0),
(6,3),(9,4), (4,8) (6,3),(8,4), (4,0) (4,0),(0,3), (3,7) (4,0),(7,3), (3,10) (4,0),(10,3), (3,9) (4,0),(9,3), (3,8) (4,0),(8,3), (3,0) (7,9),(0,10), (10,5) (7,9),(5,10), (10,2) (7,9),(2,10), (10,0) (10,8),(0,9), (9,5) (10,8),(5,9), (9,2) (10,8),(2,9), (9,0) (0,7),(7,6), (0,1),(1,10) (0,10),(10,6) ,(7,1),(1,9) (0,9),(9,6), (10,1),(1,8) (0,8),(8,6), (9,1),(1,0) (1,7),(7,4), (0,6),(6,10) (1,10),(10,4), (7,6),(6,9) (1,9),(9,4), (10,6),(6,8) (1,8),(8,4), (9,6),(6,0) (6,10),(10,3), (7,4),(4,9) (6,9),(9,3), (10,4),(4,10) (6,8),(8,3), (9,4),(4,0) (4,7),(7,0), (0,3),(3,10) (4,10),(10,0),
94
130
264.06
300.06
80
100
205.38
225.38
42
62
29.34
49.34
84
110
205.38
231.38
57
137
322.74
402.74
61
97
293.4
329.4
47
67
117.36
137.36
70
130
322.74
382.74
68
137
234.72
303.72
70
130
381.42
441.42
47
107
381.42
441.42
45
114
322.74
391.74
47
107
381.42
441.42
67
83
146.7
162.7
82
158
410.76
486.76
59
145
410.76
496.76
49
75
176.04
202.04
107
132
261.06
289.06
122
207
410.76
495.76
99
194
440.1
535.1
89
124
322.74
357.74
135
230
381.42
476.42
112
217
410.76
515.76
102
147
322.74
367.74
87
113
117.36
143.36
102
188
410.76
496.76
28 (7,10),(10,9) (4,3),(3,0), (10,9),(9,8) (4,3),(3,0), (9,8),(8,0) (0,5),(5,2), (0,7),(7,10) (0,5),(5,2), (9,8),(8,0) (5,2),(2,0), (0,7),(7,10) (5,2),(2,0), (9,8),(8,0) Crossover (6,4),(5,2) (6,4),(7,10) (6,4),(10,9) (6,4),(9,8) (1,6),(7,10) (4,3),(10,9) (4,3),(9,8) (5,2),(7,10) (5,2),(10,9) (5,2),(9,8)
(7,3),(3,9) (4,9),(9,0), (10,3),(3,8) (4,8),(8,0), (9,3),(3,0) (0,7),(7,2), (0,5),(5,10) (0,8),(8,2), (9,5),(5,0) (5,7),(7,0), (0,2),(2,10) (5,8),(8,0), (9,2),(2,0) (6,2),(5,4) (6,10),(7,4) (6,10),(9,4) (6,8),(9,4) (1,10),(7,6) (4,9),(10,3) (4,8),(9,3) (5,10),(7,2) (5,9),(10,2) (5,8),(9,2)
79
193
469.44
565.44
69
105
146.7
182.7
60
75
42
85
88.02
113.02
60
75
88.02
103.02
42
67
117.36
142.36
50 90 63 67 59 45 49 50 23 27
50 105 132 92 75 125 85 65 92 52
88.02 146.7 205.38 176.04 205.38 234.72 205.38 58.68 205.38 176.04
88.02 161.7 274.38 201.04 221.38 314.72 241.38 73.68 274.38 201.04
0
15
Keterangan : a merupakan banyaknya sisi yang dihilangkan f(b) merupakan total penggunaan sisi yang dihilangkan f(c) merupakan total penggunaan sisi yang ditambahkan Nilai incentive sebesar 29.34 dan nilai frekuensi penggunaan sisi dapat dilihat pada Lampiran 4.
Lampiran 7 Tabu list dengan solusi awal menggunakan IGR1 Iterasi
1
Nilai tabu tenure 2
(7,8),(8,2), (9,0)
Inserted arc (7,2), (9,8), (8,0) (5,2), (7,10)
Removed arc (7,8), (8,2), (9,0) (7,2), (5,10)
(7,2), (5,10)
(0,6), (1,4)
(0,1), (6,4)
0
(0,1),(6,4)
(4,0), (0,3), (3,7)
(4,3), (3,0), (0,7)
20
(4,3),(3,0), (0,7)
(5,1), (6,2)
(6,1), (5,2)
0
(6,1),(5,2)
(7,8), (10,0)
(7,10), (8,0)
0
3
1
(7,8),(8,2), (9,0),(5,2), (7,10) (7,2), (5,10) (0,6),(1,4)
(7,2),(9,8), (8,0) (7,8),(8,2), (9,0),(5,2), (7,10) (7,2), (5,10), (0,6),(1,4) (0,1),(6,4), (4,0),(0,3), (3,7)
(0,1),(6,4), (4,0),(0,3), (3,7)
(4,3),(3,0), (0,7),(5,1), (6,2)
2 3
4
5
6
(7,2),(9,8), (8,0)
Nilai move 10 15
29 (4,3),(3,0), (0,7),(5,1), (6,2),(7,8), (10,0) (6,1),(5,2), (7,8), (10,0)
7
8
9
(6,9),(8,4)
10
11 12 13 14 15
(6,4),(8,9), (4,0),(0,3), (3,1) (4,3),(3,0), (0,1),(1,2), (5,6) (1,6),(5,2), (0,6),(5,9) (0,5),(6,9), (1,4),(8,2) (1,2),(8,4), (3,4),(1,0) (3,1),(4,0), (4,2),(8,1)
(6,1),(5,2) (7,10), (8,0) (6,9),(8,4) (6,4),(8,9), (4,0),(0,3), (3,1) (4,3),(3,0), (0,1),(1,2), (5,6) (1,6),(5,2), (0,6),(5,9) (0,5),(6,9), (1,4),(8,2) (1,2),(8,4), (3,4),(1,0) (3,1),(4,0), (4,2),(8,1) (4,1),(8,2), (5,1),(8,9)
(6,9), (8,4)
(6,4), (8,9)
25
(6,4),(8,9)
(4,0), (0,3), (3,1)
(4,3), (3,0), (0,1)
11
(4,3),(3,0),( 0,1)
(1,2), (5,6)
(1,6), (5,2)
4
(1,6),(5,2)
(0,6), (5,9)
(0,5), (6,9)
0
(0,5),(6,9)
(1,4), (8,2)
(1,2), (8,4)
0
(3,4), (1,0) (4,2), (8,1) (5,1), (8,9)
(3,1), (4,0) (4,1), (8,2) (5,9), (8,1)
(1,2),(8,4) (3,1),(4,0) (4,1),(8,2) (5,9),(8,1)
11 5 26 4
Lampiran 8 Rangkuman solusi dengan penentuan solusi awal menggunakan SGR2 Iterasi ke0
1
2
3
4
5 6 (fase intensifika si)
Sisi yang digunakan (0,2),(2,4),(4,8),(8,9),(9,0), (0,10),(10,5),(5,1),(1,0), (0,3),(3,6),(6,7),(7,0) (0,2),(2,4),(4,8),(8,0), (0,9),(9,10),(10,5),(5,1),(1,0), (0,3),(3,6),(6,7),(7,0) (0,2),(2,4),(4,3),(3,0), (0,9),(9,10),(10,5),(5,1),(1,0), (0,8),(8,6),(6,7),(7,0) (0,2),(2,4),(4,3),(3,0), (0,9),(9,10),(10,7),(7,1),(1,0), (0,8),(8,6),(6,5),(5,0) (0,2),(2,5),(5,0), (0,9),(9,10),(10,7),(7,1),(1,0), (0,8),(8,6),(6,4),(4,3),(3,0) (0,9),(9,2),(2,5),(5,0), (0,10),(10,7),(7,1),(1,0), (0,8),(8,6),(6,4),(4,3),(3,0) (0,2),(2,4),(4,3),(3,0), (0,9),(9,10),(10,8),(8,7),(7,1),(1,0), (0,6),(6,5),(5,0)
Jarak total 299 km
255 km
244 km
234 km
244 km
304 km 218 km
30 7 (fase diversifika si) 8 (fase standar) 9 (fase standar) 10
(0,2),(2,4),(4,3),(3,0), (0,9),(9,10),(10,8),(8,7),(7,0), (0,1),(1,6),(6,5),(5,0) (0,2),(2,3),(3,4),(4,0), (0,9),(9,10),(10,8),(8,7),(7,0), (0,1),(1,6),(6,5),(5,0) (0,2),(2,3),(3,4),(4,0), (0,10),(10,9),(9,8),(8,7),(7,0), (0,1),(1,6),(6,5),(5,0) (0,2),(2,3),(3,4),(4,0), (0,10),(10,9),(9,8),(8,6),(6,0), (0,1),(1,7),(7,5),(5,0)
208 km
208 km
208 km
238 km
Lampiran 9 Frekuensi penggunaan sisi pada 5 iterasi pertama dengan penentuan solusi awal menggunakan SGR2 Pelanggan ke0 1 2 3 4 5 6 7 8 9 10
0 0 6 5 6 0 3 0 3 5 6 2
1 6 0 0 0 0 3 0 3 0 0 0
2 5 0 0 0 4 2 0 0 0 1 0
3 6 0 0 0 4 0 2 0 0 0 0
4 0 0 4 4 0 0 2 0 2 0 0
5 3 3 2 0 0 0 1 0 0 0 3
6 0 0 0 2 2 1 0 3 4 0 0
7 3 3 0 0 0 0 3 0 0 0 3
8 5 0 0 0 2 0 4 0 0 1 0
9 6 0 1 0 0 0 0 0 1 0 4
10 2 0 0 0 0 3 0 3 0 4 0
Lampiran 10 Tabu list dengan penentuan solusi awal menggunakan SGR2 Iterasi
1
Nilai tabu tenure 2
3
1 (8,0),(0,9), (9,10)
(8,9),(9,0), (0,10)
2
3
4
Inserted Arc (8,0), (0,9), (9,10)
Removed Arc (8,9), (9,0), (0,10)
(4,3), (3,0), (0,8), (8,6)
(4,8), (8,0), (0,3), (3,6)
11
10
(8,0),(0,9), (9,10)
(8,9),(9,0), (0,10),(4,3), (3,0),(0,8), (8,6)
(4,8),(8,0), (0,3),(3,6)
(10,7), (7,1), (6,5), (5,0)
(10,5), (5,1), (6,7), (7,0)
(8,9),(9,0), (0,10),(4,3), (3,0),(0,8), (8,6)
(4,8),(8,0), (0,3),(3,6), (10,7),(7,1), (6,5),(5,0)
(10,5),(5,1), (6,7),(7,0)
(2,5), (6,4)
(2,4), (6,5)
Nilai move 44
10
31
5
6
7
8
9
10
(4,8),(8,0), (0,3),(3,6), (10,7),(7,1), (6,5),(5,0) (10,5),(5,1), (6,7),(7,0), (2,5),(6,4) (2,4),(6,5), (0,9),(9,2), (0,10) (0,9),(9,10), (0,2),(0,6), (10,8),(8,7) (0,8),(8,6), (10,7),(7,0), (0,1),(1,6) (7,1),(1,0), (0,6),(2,3), (4,0)
(10,5),(5,1), (6,7),(7,0), (2,5),(6,4) (2,4),(6,5), (0,9),(9,2), (0,10) (0,9),(9,10), (0,2),(0,6), (10,8),(8,7) (0,8),(8,6), (10,7),(7,0), (0,1),(1,6) (7,1),(1,0), (0,6),(2,3), (4,0) (2,4),(3,0), (0,10),(9,8)
(2,4),(6,5)
(0,9),(9,10), (0,2) (0,8),(8,6), (10,7) (7,1),(1,0), (0,6) (2,4),(3,0)
(0,9),(10,8)
(0,9), (9,2), (0,10)
(0,9), (9,10), (0,2)
(0,6), (10,8), (8,7) (7,0), (0,1), (1,6) (2,3), (4,0)
(0,8), (8,6), (10,7) (7,1), (1,0), (0,6) (2,4), (3,0)
(0,10), (9,8)
(0,9), (10,8)
(8,6), (6,0), (1,7), (7,5)
(8,7), (7,0), (1,6), (6,5)
60
16
10
0
0
30
RIWAYAT HIDUP Penulis menempuh pendidikan di Sekolah Menengah Pertama Negeri 7 Bukittinggi pada tahun 2003 hingga 2006 kemudian melanjutkan pendidikan di Sekolah Menengah Atas Negeri 1 Bukittinggi pada tahun 2006 yang diselesaikan pada tahun 2009. Penulis diterima di Institut Pertanian Bogor pada tahun 2009 melalui jalur Undangan Seleksi Masuk IPB (USMI) dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor pada tahun 2010. Penulis mendapatkan Beasiswa BBM dan PPA tahun 2009-2013. Penulis aktif menjadi asisten praktikum tahun ajaran 2011-2013 dengan mata kuliah Kalkulus 2 (semester ganjil tahun akademik 2011-2012), Kalkulus 3 (semester genap tahun akademik 2011-2012), Pengantar Teori Peluang (semester ganjil tahun akademik 2012-2013), Permodelan Matematika (semester genap tahun akademik 2012-2013), dan Permodelan Riset Operasi (Semester Pendek tahun akademik 2012-2013). Selama kuliah penulis aktif dalam organisasi kemahasiswaan Himpunan Profesi Gumatika sebagai Staf Divisi Keilmuan pada tahun 2010-2011 dan Kepala Divisi Keilmuan Gumatika pada tahun 2011-2012. Penulis pernah menjadi ketua acara ”Matematika Ria” pada tahun 2012. Penulis juga pernah menjadi panitia dan koordinator di berbagai acara kemahasiswaan serta pernah mengajar di bimbingan belajar GUMATIKA.
