Pemilihan Rute Optimal Penjemputan Penumpang Travel menggunakan Ant Colony Optimization pada Multiple travelling Salesman Problem (M-TSP)

Sitanggang, Yosua Christopher (2017) Pemilihan Rute Optimal Penjemputan Penumpang Travel menggunakan Ant Colony Optimization pada Multiple travelling Salesman Problem (M-TSP). Sarjana thesis, Universitas Brawijaya.

Abstract

Multiple salesman problem (M-TSP) adalah suatu permasalahan lanjutan dari TSP yaitu mencari biaya minimal dalam suatu perjalanan pada beberapa lokasi, dengan syarat setiap lokasi hanya dapat dikunjungi sebanyak satu kali. Ada banyak permasalahan yang termasuk kedalam permasalahan M-TSP, salah satunya yaitu rute penjemputan penumpang travel. Pemilihan jalur yang tepat dalam proses penjemputan penumpang tentunya akan mempengaruhi efektivitas dan biaya yang diperoleh dalam kegiatan tersebut. Ant colony optimization (ACO) adalah algoritme yang mengadopsi kecerdasan dari sekelompok semut dalam pencarian makanan yang mampu meyelesaikan permasalahan M-TSP. Pada penelitian ini ada dua parameter yang digunakan dalam mencari solusi terbaik yaitu jarak dan waktu. Dalam proses penyetaraan nilai parameter jarak dan waktu, diterapkan normalisasi min-max pada bagian data. Hasil terbaik yang diperoleh berada pada saat parameter NcMax atau iterasi sebanyak 300, nilai α sebesar 0,5, nilai β sebesar 0,5, nilai τ0 sebesar 0,5, nilai ρ sebesar 0,5 dan jumlah penumpang dalam satu mobil sebanyak 5 dengan cost sebesar 148,829.

English Abstract

Multiple salesman problem (M-TSP) is an advanced problem from TSP that is looking for minimal cost from tour in some location which can only be visited once. There are many problems that are included in the case of M-TSP, one of them is the passenger pickup route. Choosing the right path in the process of picking up passengers will certainly affect the effectiveness and cost in those activities. Ant colony optimization (ACO) is an algorithm that adopts the intelligence of a group of ants in a food search and able to solving the M-TSP problem. In this study there are two parameters used in finding the best solution that is distance and time. In equalize the value of distance and time parameters, applied min-max normalization in data. The best results are obtained when the parameter NcMax or iteration is 300, the value of α is 0.5, the value of β is 0.5, the value of τ0 is 0.5, the value of ρ is 0.5 and the number of passengers in one car as much as 5 with cost 148.829.

Item Type:	Thesis (Sarjana)
Identification Number:	SKR/FTIK/2017/819/051800657
Uncontrolled Keywords:	multiple travelling salesman problem, rute penjemputan, ant colony optimization, normalisasi min-max
Subjects:	000 Computer science, information and general works > 003 Systems > 003.8 Systems distinguished in relation to time
Divisions:	Fakultas Ilmu Komputer > Teknik Informatika
Depositing User:	Budi Wahyono Wahyono
Date Deposited:	26 Jan 2018 08:54
Last Modified:	21 Jun 2022 01:34
URI:	http://repository.ub.ac.id/id/eprint/8481

Text Yosua Christopher Sitanggang.pdf Download (10MB)

Actions (login required)

View Item