Genetic Algorithm for Optimizing Traveling Salesman Problems with Time Windows (TSP-TW)

Juwairiah Juwairiah, Dicky Pratama, Heru Cahya Rustamaji, Herry Sofyan, Dessyanto Boedi Prasetyo

Abstract


The concept of Traveling Salesman Problem (TSP) used in the discussion of this paper is the Traveling Salesman Problem with Time Windows (TSP-TW), where the time variable considered is the time of availability of attractions for tourists to visit. The algorithm used for optimizing the solution of Traveling Salesman Problem with Time Windows (TSP-TW) is a genetic algorithm. The search for a solution for determining the best route begins with the formation of an initial population that contains a collection of individuals. Each individual has a combination of different tourist sequence. Then it is processed by genetic operators, namely crossover with Partially Mapped Crossover (PMX) method, mutation using reciprocal exchange method, and selection using ranked-based fitness method. The research method used is GRAPPLE. Based on tests conducted, the optimal generation size results obtained in solving the TSP-TW problem on the tourist route in the Province of DIY using genetic algorithms is 700, population size is 40, and the combination of crossover rate and mutation rate is 0.70 and 0.30 There is a tolerance time of 5 seconds between the process of requesting distance and travel time and the process of forming a tourist route for the genetic algorithm process.


Keywords


TSP-TW; Time Window; Genetic Algorithm; Route Optimization; Adult Tourism Object

Full Text:

PDF

References


Arkeman, Y., Seminar, K. B., & Gunawan, H. (2012). Algoritma Genetika. Teori Dan Aplikasinya Untuk Bisnis Dan Industri. https://doi.org/10.1007/s13398-014-0173-7.2

Cahya, D., Nugraha, A., Mahmudy, W. F., Ilmu, M., Informatika, K., Komputer, F. I., … No, J. V. (2015). Optimasi Vehicle Routing Problem With Time Windows Pada Distribusi Katering Menggunakan Algoritma, (November), 2–3.

Dinas Pariwisata. (2017). Statistik Kepariwisataan 2017.

Pelka, N. A. (2017). Sistem Informasi Geografis Lokasi Pool Bus Di Kota Medan Menggunakan Metode Grapple Berbasis Android.

Pressman, R. S. (2012). Rekayasa Perangkat Lunak: Pendekatan Praktisi. Andi.

Priandani, N. D., & Mahmudy, W. F. (2015). Optimasi Travelling Salesman Problem With Time Windows ( TSP-TW ) pada Penjadwalan Paket Rute Wisata Di Pulau Bali Menggunakan Algoritma Genetika, (November), 2–3.

Sugiyono. (2012). Metode Penelitian Kuantitatif Kualitatif dan R&D. Bandung: Alfabeta.




DOI: http://dx.doi.org/10.25139/ijair.v1i1.2024

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Juwairiah Juwairiah, Dicky Pratama, Heru Cahya Rustamaji, Herry Sofyan, Dessyanto Boedi Prasetyo

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

____________________________________________________________
International Journal of Artificial Intelligence & Robotics (IJAIR)
ISSN 2686-6269 (Online)
Published By Universitas Dr. Soetomo
Managed By Informatics Department, Universitas Dr Soetomo
Address Jl. Semolowaru no 84, Surabaya, 60118, (031) 5944744
Website https://ejournal.unitomo.ac.id/index.php/ijair/index
Email [email protected]

Inform is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.