Two Phase Heuristic Algorithm (TPHA) untuk Multiple Traveling Salesman Problem (MTSP) dan implementasinya / Rahma Try Iriani

Iriani, Rahma Try (2018) Two Phase Heuristic Algorithm (TPHA) untuk Multiple Traveling Salesman Problem (MTSP) dan implementasinya / Rahma Try Iriani. Diploma thesis, Universitas Negeri Malang.

Full text not available from this repository.

Abstract

v ABSTRAK Iriani, Rahma Try. 2018. Two Phase Heuristic Algorithm (TPHA) untuk Multiple Travelling Salesman Problem (MTSP) dan Implementasinya, Skripsi, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Malang. Pembimbing: (I) Dra. Sapti Wahyuningsih, M.Si. (II) Darmawan Satyananda, S.T, M.T. Kata Kunci: graph, travelling salesman problem (TSP), multiple travelling salesman problem (MTSP), two phase heuristic algorithm (TPHA). Pemilihan rute merupakan salah satu aspek penting dalam bidang pendistribusian. Travelling Salesman Problem (TSP) merupakan suatu permasalahan penentuan rute salesman untuk mengunjungi semua customer dengan jarak tempuh minimum. Rute berawal pada suatu depot dan melayani semua customer yang dikunjungi tepat satu kali lalu kembali ke depot. Multiple Travelling Salesman Problem (MTSP) merupakan salah satu varian TSP yang melibatkan beberapa salesman dalam melakukan sebuah perjalanan mengunjungi beberapa customer. Permasalahan MTSP dapat diselesaikan dengan menggunakan Two Phase Heuristic Algorithm (TPHA). Prinsip kerja dari TPHA untuk MTSP ini adalah mengelompokan customer-customer ke dalam beberapa wilayah dengan menggunakan algoritma K-Means, yang kemudian akan dicari solusi rute pada masing-masing wilayah dengan menggunakan algoritma genetika. Pengelompokan customer pada algoritma K-Means dilakukan berdasarkan perolehan jarak minimum setiap titik terhadap centroid (pusat kelompok) menggunakan nilai fitness Euclidean. Proses pencarian solusi rute dengan menggunakan algoritma genetika dilakukan melalui beberapa tahapan yaitu pembangkitan populasi awal, evaluasi kromosom, seleksi kromosom, proses crossover, dan proses mutasi. Terdapat 3 operator genetika penting yang akan digunakan dan bertujuan untuk meningkatkan keragaman solusi. Operator genetika tersebut adalah proses seleksi kromosom menggunakan metode roullete wheel, proses crossover menggunakan teknik order crossover, dan mutasi menggunakan teknik swapping mutation. Proses genetika ini dilakukan secara berulang sampai diperoleh kondisi optimum. Kondisi optimum tercapai saat semua generasi yang telah ditentukan sudah terlewati dan menghasilkan solusi terbaik berdasarkan nilai fitness yang diperoleh. vi Pada skripsi ini dibahas mengenai TPHA yang digunakan dalam menyelesaikan permasalahan MTSP. Implementasi dari TPHA untuk MTSP dalam bahasa pemrograman Borland Delphi 7.0 telah dirancang secara terstruktur. Program telah diuji coba pada kasus 21 titik, 32 titik, dan 46 titik. Solusi yang baik adalah solusi yang mendekati optimum, yang nilai parameternya dirancang dengan baik. Berdasarkan uji coba pengaruh perubahan nilai parameter pada kasus 21 titik, diperoleh solusi optimum dengan 80 individu, 100 generasi, probabilitas crossover yaitu 0,95 dan probabilitas mutasi yaitu 0,1. Dewan Penguji Anggota, Anggota, Dra. Sapti Wahyuningsih, M.Si Darmawan Satyananda, S.T, M.T NIP. 19621211 198812 2 001 NIP. 19730724 199903 1 001 Ketua, Prof. Drs. Purwanto, Ph.D NIP. 19591222 198502 1 006

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: 02 Nov 2018 04:29
Last Modified: 09 Sep 2018 03:00
URI: http://repository.um.ac.id/id/eprint/17259

Actions (login required)

View Item View Item