Artikel Ilmiah oleh Siti Hasanah ini telah diperiksa dan disetujui oleh pembimbing.
Malang, 1 Agustus 2013 Pembimbing
Dra. Sapti Wahyuningsih,M.Si NIP 1962121 1198812 2 001
Penulis
Siti Hasanah NIP 309312426746
KINERJA ALGORITMA IMPROVED ANT COLONY SYSTEM (IACS) DALAM MENYELESAIKAN VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (VRPTW) Siti Hasanah1 , Sapti Wahyuningsih2 Jurusan Matematika FMIPA Universitas Negeri Malang E-mail:
[email protected]
ABSTRAK: Permasalahan pendistribusian suatu barang atau jasa dari suatu depot ke pelanggan dapat dipecahkan dengan menggunakan Vehicle Routing Problem With Time Windows (VRPTW). Salah satu algoritma yang digunakan dalam menyelesaikan VRPTW adalah algoritma Ant Colony System. Algoritma lain yang merupakan pengembangan dari Ant Colony System adalah algoritma Improved Ant Colony System. Algoritma Improved Ant Colony System (IACS) terdapat 3 tahap, yaitu: tahap penentuan parameter, tahap pembangkitan inisial solusi, dan tahap iterasi. Berdasarkan penyelesaian contoh 1 dan 2 diperoleh bahwa dalam algoritma Improved Ant Colony Sytem (IACS) terdapat state transition rule yang baru, pheromone updating rule yang baru, local search hanya dkenakan pada solusi terbaik saja, dan global pheromone update dikenakan pada pembentuk solusi terbaik iterasi sekarang dan sebelumnya. Kata Kunci: Vehicle Routing Problem With Time Window (VRPTW), Ant Colony System (ACS), Improved Ant Colony System (IACS)
Berbagai permasalahan dalam kehidupan sehari-hari dapat dipecahkan dengan menggunakan matematika. Misalnya permasalahan pendistribusian suatu barang atau jasa dari suatu depot ke pelanggan. Persoalan distribusi juga terdapat berbagai bidang pelayanan umum, misalnya persoalan pengiriman barang, penjemputan penumpang bus, penentuan jalur pembersihan jalan, dan penentuan trayek angkutan umum. Pada suatu kasus depot harus dapat melayani customer yang tersebar di seluruh wilayah, seringkali kendaraan harus menempuh perjalanan yang jauh dan tidak efisien. Pada saat mendistribusikan barang tersebut kendaraan yang digunakan harus menempuh jarak yang minimum dan memenuhi waktu yang telah ditentukan. Teori graph dapat memecahkan masalah meminimalisasi jarak dan jumlah kendaraan dalam suatu pendistribusian barang. Teori graph merupakan salah satu cabang matematika yang penting dan banyak manfaat karena teori-teorinya dapat diterapkan dalam kehidupan sehari-hari. Suatu permasalahan dapat dilihat dan diamati dengan jelas dengan menggunakan rumusan atau teori graph yang tepat, sehingga mudah untuk dianalisis. Salah satu model yang banyak dipakai dalam menyelesaikan masalah dalam kehidupan sehari-hari adalah Vehicle routing problem (VRP). Pendeskripsian VRP merupakan permasalahan dalam menentukan sejumlah rute untuk sekumpulan kendaraan identik yang harus melayani sejumlah costumer dari depot pusat. Tujuan dari permasalahan VRP adalah untuk melayani customer sesuai dengan permintaan dengan meminimalkan biaya angkut dan jumlah kendaraan yang dimulai dan berakhir di depot pusat. 1 2
Mahasiswi jurusan Matematika FMIPA Universitas Negeri Malang Dosen jurusan Matematika FMIPA Universitas Negeri Malang
1
2
Salah satu varian dari VRP adalah Vehicle Routing Problem With Time Windows (VRPTW) yang merupakan permasalahan bagaimana suatu depot dengan sejumlah kendaraan berkapasitas tertentu dalam melayani sejumlah customer pada titik-titik lokasi yang terpisah, dengan permintaan dan batasan time window tertentu dengan tujuan meminimalkan total biaya perjalanan tanpa mengabaikan batasan kapasitas kendaraan dan time window depot pusat. Terdapat beberapa algoritma dalam menyelesaikan masalah optimasi. Algoritma yang terinspirasi dari tingkah laku koloni semut ketika mencari jalan dari sarangnya menuju ke sumber makanan dikenal sebagai Improved Ant Colony System. Algoritma ini merupakan pengembangan dari Ant Colony System yang sudah mengalami perbaikan pada route contruction rule dan pheromone update rule. Selain itu, dalam algoritma ini local search yang digunakan untuk mengoptimalkan rute yang telah terbentuk dikenakan pada solusi terbaik saja. Batasan masalah yang diambil adalah 1) Bagaimana kinerja algoritma Improved Ant Colony System (IACS) dalam menyelesaikan Vehicle Routing Problem With Time Windows (VRPTW). 2) Bagaimana perbandingan penyelesaian Improved Ant Colony System (IACS) dengan Ant Colony System (ACS).
HASIL DAN PEMBAHASAN Menurut Robin J. Wilson, suatu graph terdiri dari himpunan-himpunan yang disebut titik dan himpunan-himpunan yang disebut sisi. Tiap sisi menghubungkan dua titik. Teori graph dapat memecahkan permasalahan dalam meminimalisasi jarak dan jumlah kendaraan dalam suatu pendistribusian barang. Vehicle Routing Problem With Time Windows (VRPTW) Vehicle Routing Problem With Time Window (VRPTW) merupakan varian dari VRP dengan kendala waktu. Pendeskripsian VRPTW merupakan permasalahan bagaimana suatu depot dengan sejumlah kendaraan berkapasitas tertentu untuk melayani sejumlah customer pada titik-titik lokasi yang terpisah, dengan permintaan dan batasan time window tertentu dengan tujuan meminimalkan total biaya perjalanan tanpa mengabaikan batasan kapasitas kendaraan dan time window depot pusat. Permasalahan VRPTW dapat dideskripsikan sebagai berikut: 1. Terdapat satu depot pusat distribusi barang dan sejumlah kendaraan pada depot dengan kapasitas tertentu yang akan melayani permintaan customer. 2. Setiap kendaraan harus memulai dan mengakhiri rutenya pada depot pusat. 3. Jumlah total permintaan yang akan dilayani setiap kendaraan tidak boleh melebihi kapasitas kendaraan (). 4. Tiap customer 1,2,3 … terdapat permintaan , waktu service , dan time window , . Time window didefinisikan sebagai interval waktu yang diberikan customer kepada depot pusat untuk menerima barang dengan waktu paling awal dan paling akhir untuk kendaraan datang. Data mengenai lokasi dari depot pusat dan customer serta jarak terpendek diketahui.
3
5. Pelayanan harus dipenuhi dalam sekali service saja dan sesuai dengan time window . 6. Kendaraan diperbolehkan datang sebelum waktu awal tetapi harus menunggu sampai waktu awal pelayanan customer tersebut untuk memenuhi permintaan customer. 7. Pelayanan semua customer harus sesuai dengan time window depot , artinya waktu paling awal untuk kendaraan berangkat dari depot adalah dan waktu paling akhir untuk kendaraan kembali ke depot pusat. Formulasi VRPTW sama halnya dengan VRP, fungsi tujuan VRPTW yaitu untuk meminimalkan total biaya travel semua kendaraan. Sedangkan semua batasannya juga sama dengan VRP persamaan (2.1-2.6) tetapi perlu ditambah beberapa batasan lagi yang berhubungan dengan time window. Batasan-batasan yang ditambahkan untuk VRPTW adalah sebagai berikut: Batasan 1: Setiap kendaraan memulai pelayanan pada titik dengan memenuhi
∑ ∑ k ∈V
i∈V
X ijk (bik + wi + f i + t i , j ) = b kj ∀ j ∈ N − {0}
(2.7)
Dengan w0 = f 0 = 0 Batasan 2 : Pelayanan harus dilakukan berdasarkan batasan waktu tiap tiap titik (2.8) ei ≤ bik + wi ≤ li ∀i ∈ N , k ∈ V Batasan 3 : Setiap kendaraan harus kembali sebelum waktu akhir depot pusat (2.9) ∀k ∈ V ∑ i∈N ∑ j∈N X ijk (ti, j + wi + fi ) ≤ l0 Keterangan: adalah waktu kendaraan k tiba pada waktu i bik
ei
adalah awal waktu untuk melayani titik i
li ti, j
adalah akhir waktu untuk melayani titik i adalah waktu perjalanan dari i ke j
wi
adalah waktu tunggu sebelum melayani di titik i
fi
adalah waktu pelayanan di titik i
Algoritma Improved Ant Colony System Algoritma Improved Ant Colony System (IACS) didasari oleh algoritma Ant Colony System (ACS). Ant Colony System (ACS) dikembangkan oleh Dorigo (1999) yang terinspirasi dari hasil percobaan mengenai tingkah laku dari koloni semut. Percobaan yang dilakukan adalah mendapatkan tingkah laku dari koloni semut ketika mencari jalan dari sarangnya ke sumber makanan. Dua cabang dari sarangnya ke sumber makanan yang diperlihatkan pada Gambar 1 dibedakan dari panjang jalannya. Pada periode tertentu setelah semut melalui kedua percabangan jalan itu, mereka berhasil menemukan jalan terpendek dari kedua jalan tersebut. Tingkah laku semut untuk mencari jalan terpendek merupakan hasil dari komunikasi secara tidak langsung yang disebut sebagai Stigmergy. Stigmergy didefinisikan sebagai suatu metode komunikasi pada sistem desentralisasi, dimana setiap individu memodifikasi lingkungan mereka dalam berkomunikasi. Pada kasus semut mencari makanan, semut merubah lingkungan
4
mereka dengan memberikan tanda-tanda kimiawi, yang dikenal sebagai pheromones, di sepanjang jalan dari jembatan yang mereka lalui. Menurut Dorigo, dengan merasakan jumlah dari pheromones yang diberikan sepanjang jalan tersebut, setiap semut dapat membuat keputusan berdasarkan kemungkinan, dipengaruhi oleh jumlah pheromone yang terdeteksi, cabang mana yang harus dipilih. Pada awalnya, semut membuat pilihan acak terhadap cabang yang dilalui karena keterbatasan dari pheromones. Ketika meninggalkan sumber makanan dan kembali ke sarangnya, mereka dapat mendeteksi pheromone sepanjang cabang yang lebih pendek, dan akan lebih memilih jalan tersebut untuk perjalanan balik, konsekuensinya, dengan bertambahnya jumlah dari pheromones sepanjang jalan yang lebih pendek, seperti pada Gambar 2.
Gambar 1 Rute Jalan Semut dari Sarang ke Makanan
Gambar 2 Pencarian jalan terpendek ke makanan
Dalam ACS, semut ditempatkan pada titik yang dipilih sesuai prosedur secara acak. Setiap semut membangun suatu perjalanan dengan berulang-ulang menerapkan suatu probabilitas nearest neighbor heuristic. Ketika mengkonstruksikan suatu perjalanan, semut memodifikasi level pheromone pada sisi yang dikunjungi dengan menerapkan local updating rule. Ketika semua semut menyelesaikan perjalanan mereka, level pheromone pada setiap sisi dimodifikasi lagi dengan menerapkan global updating rule yang mana mendahulukan sisi yang terhubung dengan best tour yang ditemukan dari awal. Algoritma IACS ini secara umum terdiri dari iterasi berikut: 1. Setiap semut membangun solusi secara bebas dan melakukan local pheromone update. 2. Menerapkan local search untuk memperbaiki solusi. 3. Meng-update global pheromone information. Secara rinci langkah-langkah Algoritma Improved Ant Colony System untuk VRPTW diuraikan sebagai berikut: Langkah 1: Menentukan parameter Langkah 2: Membangkitkan inisial solusi menggunakan algoritma Nearest Neighbor Heuristik
5
Langkah 3: Menerapkan local search ( algoritma insertion move) pada inisial solusi dan disimpan sebagai solusi pertama. Langkah 4: Membentuk solusi berdasarkan route onstruction rule dan melakukan local pheromone update. Banyak semut = banyaknya Semut+1 Langkah 5: Jika jumlah semut > jumlah max semut maka semut = 2 dan melakukan langkah 6. Jika jumlah semut jumlah max semut maka lakukan langkah 4. Langkah 6: Mengurutkan solusi ke-2 sampai dengan jumlah max semut dan menerapkan local search ( algoritma insertion move) pada solusi terbaik dan disimpan sebagai solusi ke-2. Langkah 7: Menerapkan Global Pheromone Update Langkah 8: Mencatat solusi terbaik sejauh ini dan disimpan sebagi solusi pertama pada generasi berikutnya. iterasi = iterasi +1 (Jika jumlah iterasi jumlah Max iterasi) maka berhenti (Jika jumlah iterasi jumlah Max iterasi) maka kembali ke langkah 4. Langkah 9: Berhenti Menentukan parameter Pemodelan sikap semut-semut biasanya mengenalkan beberapa parameter dimana nilai optimal harus dicapai. Parameter-parameter tersebut yang terpenting adalah ρ konstan ∈ [0,1] sebagai faktor pelupa, merupakan pemodelan dari penguapan per waktu penyimpanan pheromone dan jumlah semut yang digunakan. Terlalu banyak semut yang digunakan akan meningkatkan kompleksitas perhitungan. Pada sisi lain, terlalu sedikit semut akan membatasi hasil kerjasama secara sinergi. Parameter α dan β dipilih sedemikian sehingga didapat optimum terbaik. β merupakan parameter yang mempengaruhi kepentingan relatif nilai visibitity. Jika β = 0, hanya informasi pheromone yang digunakan, dimana dapat mengarahkan ke jalur sub-optimal. α = 0 merupakan parameter yang mempengaruhi kepentingan relatif pheromone. Jika α = 0, tidak ada pheromone yang digunakan dan ∈ [0,1] parameter yang mempengaruhi kepentingan relatif antara eksploitasi dan eksplorasi serta γ ∈ [0,1] adalah parameter yang mewakili penguapan pheromone (Lukas,2007). Inisialisasi Pheromone Inisialisasi jumlah pheromone pada setiap arc adalah: 1 τ $1% N. LNN dimana N adalah jumlah titik dan LNN total travel time hasil Nearest Neighbor. Algoritma Nearest Neighbor Heuristic Untuk membangkitkan inisial solusi dalam algoritma ini digunakan Algoritma Nearest Neighbor Heuristic. Langkah-langkah Algoritma Nearest Neighbor Heuristic sebagai berikut: 1. Perjalanan dimulai dari depot dengan muatan awal adalah 0. Waktu perjalanan adalah 0. 2. Cari jarak terpendek dari 0 sehingga & minimum dengan 0.
6
3. Hitung total permintaan dan total waktu tempuh dari & dengan 0 dan masing-masing dan ( 4. Tentukan sehingga titik yang sudah dikunjungi dijadikan . 5. Cari jarak terpendek dari 0 sehingga & minimum. 6. Hitung total permintaan dan total waktu tempuh dari & dengan 0 dan masing-masing ) dan ( ( ) ( . 7. Periksa apakah dan ( *+ , jika ya lanjutkan langkah 4-6. Jika tidak ulangi langkah 1. Route Construction dalam IACS Setiap semut yang berada pada titik akan memilih titik atau ,-.$, % berdasarkan state transition rule sebagai berikut: Jika (eksploitasi), maka $2% / arg max5∈U7 89: ;$< %= > Dimana = Bilangan random antara 0 dan 1 = Parameter yang menentukan kepentingan relatif antara eksploitasi dan eksplorasi. U@ = Himpunan titik yang belum dikunjungi ketika berada di titik : = Jumlah pheromone pada ,-.$, % < = Nilai visibility yang merupakan saving dari kombinasi dua titik dan pada satu perjalanan sebagai kebalikan pelayanan pada dua tur yang berbeda. < ) A B = Parameter yang menentukan pengaruh relatif pheromone C = Parameter yang menentukan pengaruh relatif nilai visibility Sedangkan jika D (eksplorasi), maka 9: ;$< %= / E $3% ∑5∈U7 9: ;$< %= Dimana E = Probabilitas semut dari titik munuju titik (Chen, 2006). Nilai paramater α dan β mempengaruhi nilai E, dimana E merupakan probabilitas dari kota ke kota . Semakin besar nilai keduanya, semakin besar pula probabilitas dari kota yang sekarang ke kota berikutnya. Ini berarti nilai paramater α dan β berbanding lurus dengan nilai E. Jika salah satu parameter yang digunakan mendekati nol berarti hanya mengandalkan pheromone saja atau informasi lokal saja. Nilai parameter ρ akan mempengaruhi nilai τ , dimana τ merupakan intensitas pheromone. Intensitas pheromone setiap kota berbeda-beda. Setiap iterasi yang dilakukan menyebabkan perubahan pada intensitas tersebut. Jadi setiap iterasi diadakan pembaharuan nilai intensitas tersebut. Semakin besar nilai ρ akan memperkecil nilai τ , sedangkan semakin kecil nilai ρ akan memperbesar nilai τ . Ini berarti nilai ρ berbanding terbalik dengan nilai τ . Semakin besar nilai ρ , maka intensitas pheromone menjadi lebih kecil sedangkan semakin kecil nilai ρ , maka intensitas pheromone menjadi lebih besar. Dalam kehidupan sehari-hari, semut memiliki perilaku yang cukup unik. Suatu koloni semut dapat menemukan sebuah jalur optimum pada saat pergi
7
mencari makanan dan kembali ke sarangnya. Semut-semut tersebut berjalan dengan meninggalkan jejaknya yaitu berupa pheromone. Pheromone yang ditinggalkan oleh semut di dalam perjalanan mencari makanan digunakan oleh semut lain untuk mengetahui jalan mana yang lebih optimum dibandingkan semua jalan yang ada. Semut akan lebih memilih jalan yang memiliki kadar pheromone yang kuat. Itu berarti bahwa jalan tersebut merupakan jalur optimum yang hampir kebanyakan semut melalui jalan tersebut, sedangkan jalan yang jarang dilalui kadar pheromonenya lama-kelamaan akan berkurang sehingga semut-semut tidak akan memilih jalan tersebut (Lukas,2007). Adapun tahap-tahap pada route construction pada IACS ini adalah sebagai berikut: Tahap 1: Setiap semut memilih customer awal secara acak Tahap 2: Semut memilih customer selanjutnya maunggunakan state transition rule berdasarkan persamaan (2) dan (3) Tahap 3: Semut melakukan update pheromone local dengan local updating rule berdasarkan persamaan (4). Tahap 4: Ulangi tahap 2 dan 3 hingga semut mengunjungi semua customer Tahap 5: Bagi solusi yang dihasilkan sehingga menghasilkan rute yang sesuai dengan batasan kapasitas kendaraan dan time window. Local Search dalam IACS Dalam ACS, setelah semut mengkonstruksikan solusinya tetapi sebelum pheromone melakukan local update, solusi setiap semut diperbaiki dengan menerapkan suatu local search. Sedangkan dalam IACS, local search dilakukan setelah membangkitkan inisial solusi dengan menggunakan algoritma Nearest Neighbor Heuristic dan dilakukan juga setelah semut mengkonstruksikan solusinya. Serta dalam 1 iterasi, local search dikenakan pada solusi terbaik saja. Local search dilakukan untuk pengoptimalan rute yang telah terbentuk, dalam algoritma ini diterapkan local search algoritma Insertion Move. Algoritma Insertion Move didefinisikan sama dengan algoritma 2-opt dan swap karena algoritma ini terdiri dari intra route dan inter route improvement. Algoritma Insertion Move bekerja dengan melakukan perpindahan titik dari suatu rute sehingga terbentuk rute yang baru. Intra route dan inter route improvement ditunjukkan seperti berikut: A. Intra-Route Intra-route merupakan perpindahan titik dalam satu rute tanpa mempengaruhi rute yang lain, misalnya terdapat 10 titik yang terbagi dalam dua rute maka perpindahan Intra-route dapat ditunjukkan sebagai berikut:
Rute 1 Rute 2
0 0
1 6
2 7
3 8
4 9
5 10
0 0
3 8
4 9
2 10
0 0
Menjadi
Rute 1 Rute 2
0 0
1 6
5 7
Titik 2 ditukar dengan titik 5
8
B. Inter- Route Inter-route merupakan perpindahan titik yang melibatkan dua buah rute, yaitu rute pertama sebagai asal titik rute dan rute kedua sebagai tujuan penempatan titik yang baru. Proses perpindahan inter-route dapat ditunjukkan sebagai berikut:
Rute 1 Rute 2
0 0
1 6
2 7
3 8
4 9
5 10
0 0
4 3
2 9
0 10
Titik 3 dalam rute 1 ditempatkan di rute 2
Menjadi
Rute 1 Rute 2
0 0
1 6
2 7
8
0
Diagram proses algoritma Insertion Move sebagai berikut: Rute semut k
Customer dan terhubung dalam jalur semut
$ A 1, % ) $, ) 1% ) $, ) 1% D $ A 1, ) 1% ) $, % ) $, ) 1% Tidak
Ya Tidak Muatan dan Time Window Ya Ubah arah rute
Ya
Ada customer yang dapat diubah Tidak Rute semut optimal Gambar 3 Diagram Insertion Move
9
Updating Pheromone Local dalam IACS Dalam algoritma semut, pheromone dari semua sisi termasuk rute diperoleh dari semut-semut yang akan dilocal update. Pheromone updating dalam ACS meliputi local dan global updating rule. Setiap kali melewati ,-.$, %, semut-semut akan meng-update jumlah pheromone pada ,-.$, % berdasarkan local update pheromone dari IACS sebagai berikut: : G :H ) I:0
$4%
Dimana 0 I 1 = parameter yang mewakili koefisien penguapan pheromone, dan :0 $K. LKK %A1 adalah inisial level pheromone dari sisi-sisi, dimana K adalah jumlah titik-titik dan LKK adalah panjang tour yang dihasilkan dengan menerapkan Nearest Neighbor Heuristic.
Updating Pheromone Global dalam IACS Dalam IACS, semut terbaik dari iterasi meliputi semut terbaik secara global dan terbaik secara iterasi dibiarkan untuk meletakkan pheromone pada arcs yang mereka lewati. Hal ini dilakukan untuk menyeimbangkan antara eksploitasi dan eksplorasi. Setelah semua semut telah membentuk solusinya masing-masing, maka sisi-sisi yang membentuk solusi pertama dan kedua pada setiap iterasi akan berubah jumlah pheromonenya berdasarkan persamaan Global pheromone update berikut: : G $1 A M%:H ) M∆:
$5%
Dimana 0 M 1 adalah parameter yang mewakili penguapan pheromone, dan 9L3 A LP ; ) $L3 A L1 % ∆:
L3 L3 = Panjang tur terbaik ke-3 pada setiap iterasi LP = Panjang tur terbaik secara keseluruhan L1 = Panjang tur terbaik pada setiap iterasi
Sisi-sisi yang tidak termasuk dalam terbaik secara global dan secara iterasi hanya menghilangkan pheromone sesuai dengan nilai M yang mana membentuk jalur penguapan. Contoh Algoritma Improved Ant Colony System untuk VRPTW Misalkan terdapat 6 customer yang terdiri dari customer 1,2,3,4,5,dan 6. Jarak antara depot dengan tiap-tiap customer dan jarak antar customer disajikan dalam tabel 1 berikut: Tabel 1 Jarak QRS 0 1 7 2 3 3 6 4 9 5 4 6 5
1 0 8 7 5 2 7
2
3
4
5
6
0 5 9 6 8
0 7 4 9
0 7 2
0 5
0
10
Misalkan time window kendaraan paling berangkat pada pukul 08.00 WIB dan kendaraan paling terakhir datang pada pukul 16.30 WIB. Kecepatan rata-rata kendaraan dan kapasitas kendaraan disajikan dalam tabel 2 berikut: Tabel 2 Data Depot Time Windows Customer TU C
08.00
Kecepatan Rata-Rata (Km/Jam)
VU 16.30
60
Kapasitas Kendaraan (dos) 27
Misalkan jumlah permintaan customer 1 adalah 4 dos. Kendaraan paling awal berangkat untuk melayani customer 1 pada pukul 08.30 WIB dan paling terakhir datang pada pukul 11.30 WIB. Sedangkan servise time untuk customer 1 adalah 15 menit. Selanjutnya untuk customer 2,3,4,5,dan 6 disajikan dalam tabel berikut: Tabel 3 Data Customer Jumlah Customer permintaan 4 &W 9 &X 6 &Y 10 &Z 5 &[ 8 &\
TR
VR
08.30 09.00 09.30 10.40 08.50 10.00
11.30 14.30 13.10 15.00 13.30 12.25
Servise Time 15 40 25 50 20 35
Parameter yang digunakan adalag ], ^, _, dan ` yang disajikan dalam tabel berikut: Tabel 4 Parameter yang digunakan ] ^ _ ` 1 1 0.1 0.1
aU 0.5
Jumlah Semut 2
Dari hasil penyelesaian menggunakan algoritma Improved Ant Colony System diperoleh 2 rute, yaitu: 1. & A&[ A&W A&ZA&\ A & Jumlah barang: 27 Jarak tempuh: 18 km 2. & A&Y A&X A & Jumlah barang: 15 Jarak tempuh: 11 km Jadi, jarak total yang ditempuh adalah 18 km+11 km= 29 km
11
PENUTUP Kesimpulan 1. Algoritma Improved Ant Colony System (IACS) terdapat 3 tahap, yaitu: tahap penentuan parameter, tahap inisialisasi awal jejak pheromone, dan tahap iterasi. Tahap penentuan parameter, Parameter yang ditentukan dalam algoritma ini adalah B, C, I dan M. Dalam tahap inisialisasi pheromone pada algoritma IACS ini menggunakan algoritma Nearest Neighbor Heuristic yaitu menempatkan setiap semut melalui perjalanan yang berawal dari depot dan mengunjungi customer. Setiap customer hanya dikunjungi satu kali. Dan pada tahap iterasi terdiri dari, setiap semut membangun solusi secara bebas dengan state transition rule dan melakukan local pheromone update, menerapkan local search untuk memperbaiki solusi dan meng-update global pheromone information. 2. Berdasarkan analisa hasil diperoleh bahwa parameter-parameter yang digunakan dalam algoritma Improved Ant Colony Sytem (IACS) sama dengan algoritma Ant Colony Sytem (ACS). Dalam tahap inisialisasi pheromone, IACS dan ACS sama-sama menggunakan algoritma Nearest Neighbor Heuristic, perbedaan pada kedua algoritma ini adalah pada tahap iterasi dimana pada IACS terdapat b-1 solusi (b=jumlah semut), sedangkan pada ACS solusinya sebanyak b (b=jumlah semut). Berdasarkan penyelesaian contoh 1 dan 2 diperoleh bahwa dalam algoritma Improved Ant Colony Sytem (IACS) terdapat state transition rule yang baru, pheromone updating rule yang baru, local search hanya dkenakan pada solusi terbaik saja, dan global pheromone update dikenakan pada pembentuk solusi terbaik iterasi sekarang dan sebelumnya. Saran Permasalahan disini membahas distribusi dengan kendala waktu dan kapasitas kendaraan dengan menggunakan algoritma Improved Ant Colony System, tetapi permasalahan tersebut hanya mengatasi permasalahan statis tidak bisa menggambarkan kondisi nyata yang dialami ketika melakukan proses distribusi seperti penambahan pelanggan, kondisi kepadatan jalan yang terlalu padat, sehingga sulit untuk dilewati oleh kendaraan atau berubahnya waktu tempuh disebabkan volume lalu lintas kendaraan yang lewat pada suatu jalan. Oleh karena itu, dengan menggunakan algoritma yang sama bisa dengan menambahkan permasalahan menjadi dinamis sehingga bisa menggambarkan kondisi nyata yang dialami ketika melakukan proses distribusi. DAFTAR PUSTAKA Agustin , Pratimoria Elly .2011. Penyelesaian Vehicle Routing Problem With Time Windows dengan algoritma Ant Colony System. Skipsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Negeri Malang.
12
Alam , Akhmad Fajar Nurul .2011. Algoritma Improved Ant Colony System (IACS) untuk menyelesaikan Dynamic Vehicle Routing Problem with Time Window dengan Variabel Travel Time. Skripsi tidak diterbitkan. Surabaya: Fakultas Teknologi Industri. Institut Teknologi Sepuluh November. Bin, Yu. .(2006), “ An Improved Ant Colony Optimization for Vehicle Routing Problem” European Journal of Operational Research http://web.itu.edu.tr/-keceli/optimizasyon/ant_colony.pdf (online) diakses pada tanggal 22 september 2012. Chen, C.H., Ting, C.J.(2006), “ An Improved Ant Colony Systems Algorithm for The Vehicle Routing Problem”, Working Paper 2004-2001, Department of Industrial Engineering and Management, Yuan Ze University, Taiwan. http://front.cc.nctu.edu.tw/16456.htm (online) diakses pada tanggal 5 september 2012. Dorigo, M. dan G. Di Caro. 1999. The Ant Colony Optimization Meta-Heuristic, McGraw-Hill. Harmerita.2007. Algoritma Ant Colony System untuk meyelesaikan Vehicle Routing Problem with Time Windows. Skripsi tidak diterbitkan. Surabaya: Fakultas Matematika dan Ilmu Pengetahuan Alam. Institut Teknologi Sepuluh November. Lukas, Samuel.2007. Penerapan Ant Colony System untuk Peyelesaikan Vehicle Routing Problem.Universitas Pelita Harapan. Purwanto. 1998. Matematika Diskrit. Institut keguruan dan ilmu pendidikan: Malang. Wilson ,Robin J.2004.Graph and applications an introductory approach. London. Springer.
