Skripsi

Kajian solusi travelling salesman problem with time window dengan algoritma nearest neighbor dan algoritma Clarke Wright dengan perbaikan metode local search / Nur Hasanah

Abstrak
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.

Informasi Detail

DDC

Rs 518.1 HAS k

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2017.

Deskripsi Fisik

xi, 107 lembar : il. , tab. ; 30 cm

Bahasa

Indonesia

No Reg

05425/KI/17

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2017

Subjek

1. ALGORITMA

Pembimbing

1. Sapti Wahyuningsih

Lampiran Berkas