Penyelesaian Vehicle Routing Problem with Time Windows (VRPTW) dengan menggunakan algoritma Ant Colony System (ACS) / Pratimoria Elly Agustin

Agustin, Pratimoria Elly (2011) Penyelesaian Vehicle Routing Problem with Time Windows (VRPTW) dengan menggunakan algoritma Ant Colony System (ACS) / Pratimoria Elly Agustin. Diploma thesis, Universitas Negeri Malang.

Full text not available from this repository.

Abstract

Kata Kunci: Graph, Vehicle Routing Problem (VRP), VRP With Time Window (VRPTW), Algoritma Ant Colony System (ACS). Vehicle Routing Problem With Time Window (VRPTW) merupakan masalah kombinatorial yang kompleks dalam masalah optimalisasi. Pendeskripsian VRPTW adalah bagaimana suatu depot pusat distribusi barang, dengan sejumlah kendaraan berkapasitas tertentu melayani sejumlah customer pada titik-titik lokasi terpisah, dengan permintaan dan batasan time window tertentu, dengan tujuan meminimalkan total biaya perjalanan, tanpa mengabaikan batasan kapasitas kendaraan dan time window depot. Penyelesaian VRPTW dapat dilakukan menggunakan metode eksak atau heuristik. Dalam tugas akhir ini, VRPTW diselesaikan dengan menggunakan algoritma Ant Colony System (ACS) yang merupakan permasalahan optimasi berbasis artificial intelligence yang berdasarkan pada observasi tingkah laku koloni semut nyata. Dari segi pandangan optimasi, satu hal yang terpenting dalam perilaku koloni semut nyata adalah perilaku mereka dalam mencari makanan. Lebih tepatnya, semut dapat menemukan jalur terpendek dalam mencari makanan dari sarang mereka ke sumber makanan dan sebaliknya. Penyelesaian contoh permasalahan pada bab 3 yang dikerjakan dengan menggunakan algoritma ACS. Pada contoh pertama menghasilkan 2 rute dengan total jarak tempuh 32 km, contoh kedua menghasilkan 2 rute dengan total jarak tempuh 122,63 km, dan untuk contoh ketiga menghasilkan 2 rute dengan total jarak tempuh 130,8 km. Sedangkan penyelesaian contoh permasalahan yang diselesaikan dengan algoritma Clark and Wright pada contoh pertama menghasilkan 2 rute dengan total jarak tempuh 37 km, contoh kedua 2 rute dengan total jarak tempuh 140,35 km, dan pada contoh ketiga menghasilkan 2 rute dengan total jarak tempuh 144,88 km. Dari hasil ketiga penyelesaian contoh permasalahan terlihat bahwa algoritma ACS menghasilkan rute dengan total jarak tempuh yang lebih minimum dibandingkan dengan algoritma Clark and Wright. Kelebihan dari algoritma ACS yaitu pada saat perluasan rute yang dilakukan dengan cara penyisipan customer pada dua rute yang berbeda. Yaitu, apabila pada rute pertama kendala kapasitas belum mencapai batas maksimum dari kapasitas kendaraan, maka customer pada rute kedua dapat disisipkan pada rute pertama dengan menggunakan Local Search Insertion Move tanpa mengabaikan batasan time window dan kapasitas kendaraan.

Item Type: Thesis (Diploma)
Subjects: Q Science > QA Mathematics
Divisions: Fakultas Matematika dan IPA (FMIPA) > Jurusan Matematika (MAT) > S1 Matematika
Depositing User: Users 2 not found.
Date Deposited: 15 Sep 2011 04:29
Last Modified: 09 Sep 2011 03:00
URI: http://repository.um.ac.id/id/eprint/17063

Actions (login required)

View Item View Item