Kajian metode local search dengan perbaikan double-swap pada travelling salesman problem with time window / Alinda Kusumawardani

Kusumawardani, Alinda (2019) Kajian metode local search dengan perbaikan double-swap pada travelling salesman problem with time window / Alinda Kusumawardani. Diploma thesis, Universitas Negeri Malang.

Full text not available from this repository.

Abstract

RINGKASAN Kusumawardani, A. 2019. Kajian Metode Local Search dengan Perbaikan Double-swap pada Travelling Salesman Problem with Time Window. Skripsi, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Malang. Pembimbing: Dra. Sapti Wahyuningsih, M. Si. Kata kunci: Travelling Salesman Problem with Time Windows, Local Search, Double-swap Permasalahan dari Travelling Salesman Problem (TSP) merupakan pencarian rute optimal untuk mengunjungi semua costumer tepat satu kali dengan jarak minimum dan kembali lagi ke depot. Salah satu varian dari TSP adalah Travelling Salesman Problem with Time Window (TSPTW) dengan kendala time window. Permasalahan TSPTW dapat diselesaikan dengan menggunakan beberapa algoritma. Salah satunya menggunakan metode local search. Pencarian rute optimal pada TSPTW dengan menggunakan metode local search akan dilihat dengan perbaikan double-swap. Langkah metode local search dengan perbaikan double-swap yaitu pencarian solusi awal dengan menggunakan algoritma nearest neighbor, insertion, 2-Opt, 3-Opt, Or-Opt, exchange, perbaikan double-swap, dan penentuan kondisi optimal. Diberikan 3 contoh penerapan TSPTW menggunakan metode local search dengan perbaikan double-swap. Hasil dari 2 contoh menunjukan bahwa dengan menggunakan perbaikan double-swap diperoleh solusi yang lebih baik. Sedangkan hasil dari 1 contoh menunjukan solusi yang tidak lebih baik dengan menggunakan perbaikan double-swap. Dengan menerapkan metode local search dengan perbaikan double-swap pada TSPTW dari hasil contoh tersebut, menghasilkan solusi yang sama atau lebih baik dibandingkan dengan local search. SUMMARY Kusumawardani, A. 2019. Local Search Method Study with Double-swap repairs on Travelling Salesman Problem with Time Window. Skripsi, Departnebt of Mathematics, Faculty of Mathematics and Natural Science, State University of Malang. Supervisor: Dra. Sapti Wahyuningsih, M. Si. Kata kunci: Travelling Salesman Problem with Time Windows, Local Search, Double-swap The problem of the Traveling Salesman Problem (TSP) is to find the optimal route for all customers exactly once with the minimum distance and return to the depot. One variant of TSP is Traveling Salesman Problem with Time Window (TSPTW) with time window constraints. TSPTW problems can be solved using several algorithms. One of them uses the local search method. Searching for the optimal route on TSPTW using the local search method will be seen with a double-swap. The step of the local search method is by repairing double-swap, that is search for the initial solution using the nearest neighbor algorithm, insertion, 2-Opt, 3-Opt, Or-Opt, exchange, double-swap repairs, and optimal conditions. There are 3 examples of the application of TSPTW using the local search method with double-swap repairs. The results of the 2 examples show that using a double-swap repair has a better solution. While the results from 1 example show a solution that is no better by using double-swap repairs. By applying the local search method by repairing the double-swap on TSPTW from the results of the example, it produces a solution that is the same or better than local search.

Item Type: Thesis (Diploma)
Subjects: ?? ??
Divisions: Fakultas Matematika dan IPA (FMIPA) > Jurusan Matematika (MAT) > S1 Matematika
Depositing User: Users 2 not found.
Date Deposited: 21 Aug 2019 04:29
Last Modified: 09 Sep 2019 03:00
URI: http://repository.um.ac.id/id/eprint/92657

Actions (login required)

View Item View Item