Skripsi

Kinerja algoritma Improved Ant Colony System (IACS) dalam menyelesaikan Vehicle Routing Problem with Time Windows (VRPTW) / Siti Hasanah

Abstrak
Hasanah Siti. 2013. Kinerja Algoritma Improved Ant Colony System (IACS) dalam menyelesaikan Vehicle Routing Problem With Time Windows (VRPTW). Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing Dra.Sapti Wahyuningsih M.Si. Kata kunci Vehicle Routing Problem With Time Windows(VRPTW) Improved Ant Colony System(IACS). Permasalahan pendistribusian suatu barang atau jasa dari suatu depot ke pelanggan dapat dipecahkan dengan menggunakan teori graph khususnya VRPTW. Vehicle Routing Problem With Time Windows (VRPTW) merupakan permasalahan optimasi penentuan rute dengan kendala kapasitas dan waktu tempuh kendaraan. Salah satu algoritma yang digunakan dalam menyelesaikan VRPTW adalah algoritma Ant Colony System. Algoritma ini terinspirasi dari tingkah laku koloni semut ketika mencari jalan dari sarangnya menuju ke sumber makanan. 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. Dalam tahap penentuan parameter parameter yang digunakan adalah 945 946 961 dan 947 . Tahap pembangkitan inisial solusi 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. Pada tahap iterasi terdiri atas 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. Berdasarkan analisa hasil parameter-parameter yang digunakan dalam algoritma Improved Ant Colony Sytem (IACS) sama dengan algoritma Ant Colony Sytem (ACS). 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.

Informasi Detail

DDC

Rs 511.8 HAS k

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2013.

Deskripsi Fisik

ix, 159 lembar : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

04237/KI/13

Edisi

Skripsi (Sarjana). Universitas Negeri Malang, 2013

Subjek

1. ALGORITMA

Pembimbing

1. Sapti Wahyuningsih

Lampiran Berkas