Skripsi

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

Abstrak
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

Informasi Detail

DDC

Rs 518.1 IRI t

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2018.

Deskripsi Fisik

xvi, 113 lembar : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

06243/KI/18

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2018

Subjek

1. ALGORITMA
2. ALGORITHMS

Pembimbing

1. Sapti wahyuningsih ; 2. Darmawan Satyananda

Lampiran Berkas