Hasanah, Nur (2017) Kajian solusi travelling salesman problem with time window dengan algoritma nearest neighbor dan algoritma Clarke Wright dengan perbaikan metode local search / Nur Hasanah. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
ABSTRAK Hasanah Nur. 2017. Kajian Solusi Travelling Salesman Problem With Time Window dengan Algoritma Nearest Neighbor dan Algoritma Clarke Wright dengan Perbaikan Metode Local Search. Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing Dra. Sapti Wahyuningsih M.Si Kata Kunci Graph Travelling Salesman Problem (TSP) Travelling Salesman Problem with Time Window (TSPTW) Algoritma Clarke Wright Algoritma Nearest Neighbor Local Search Distribusi merupakan suatu kegiatan yang dilakukan untuk menyalurkan suatu produk dari produsen ke konsumen. Penentuan rute yang optimum pada proses distribusi sangatlah penting. Suatu kajian dalam matematika yang membahas tentang penentuan rute optimum dikenal dengan Travelling Salesman Problem With Time Window (TSPTW). Travelling Salesman Problem with Time Window adalah permasalahan seorang salesman untuk mencari total jarak tour minimum dimana semua kota dikunjungi tepat satu kali dengan batasan time window. Travelling Salesman Problem With Time Window dapat diselesaikan dengan menggunakan algortima clarke wright dan algoritma nearest neighbor dengan perbaikan local search. Penentuan solusi awal menggunakan algortima clarke wright dilakukan dengan cara memilih titik awal dan titik tujuan. Kemudian dihitung matrik jarak antar titik awal dengan titik tujuan dan antar titik tujuan. Dihitung nilai savings untuk setiap pasang titik. Kemudian diurutkan nilai savings dari yang terbesar ke yang terkecil dan nilai savings terbesar merupakan rute awal. Selain itu solusi awal dapat dicari menggunakan algoritma nearest neighbor yang dilakukan dengan cara memilih sebarang titik awal lalu titik tersebut dipasangkan dengan titik baru yang memiliki bobot sisi minimum. Dari titik baru dipilih titik yang belum termuat pada lintasan dengan bobot sisi minimum. Kedua solusi awal tersebut diperbaiki menggunakan perbaikan metode local search dengan lima metode perbaikan yaitu insertion 2-opt 3-opt Or-opt dan exchange. Perbaikan yang menghasilkan solusi yang optimum akan menggantikan solusi awal.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 12 Sep 2017 04:29 |
| Last Modified: | 09 Sep 2017 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17504 |
Actions (login required)
 |
View Item |