Penyelesaian Traveling Salesman Problem dengan Kendala Time Windows Menggunakan Algoritme Genetika

Abstract

TSPTW (Traveling Salesman Problem with Time Windows) merupakan salah satu perluasan dari TSP (Traveling Salesman Problem). TSPTW merupakan masalah penentuan rute yang menggambarkan perjalanan seorang salesman dari node awal kemudian mengunjungi beberapa node lain tepat sekali dan akhirnya kembali ke node awal dengan syarat node yang dikunjungi terlayani dalam selang waktu yang telah ditentukan. Karya ilmiah ini membahas implementasi algoritme genetika pada TSPTW dengan bantuan software Python 3.6.8. Operator genetika yang diterapkan yakni, metode rank based selection untuk proses seleksi, metode 1-point crossover untuk proses kawin silang, dan metode swap mutation untuk proses mutasi. Pencarian solusi dilakukan dengan memberikan parameter genetika hingga didapatkan solusi terbaik yang bisa ditemukan oleh algoritme genetika. Solusi TSPTW dengan 1 depot dan 15 node diperoleh total waktu perjalanan paling minimum saat kombinasi peluang kawin silang dan peluang mutasi berturut-turut 0.8 dan 0.3, serta ukuran generasi 200 dan ukuran populasi 10.

TSPTW (Traveling Salesman Problem with Time Windows) is such an extension of TSP (Traveling Salesman Problem). TSPTW is a finding route-problem that represents a trip of salesman from starting node then visits each node exactly once and ending the trip by returns to starting node with constraint would be the nodes must be served within predefined time constraints. This paper discussed about the implementation of genetic algorithm in TSPTW that is solved by Python version 3.7.8. Genetic operators that will be used are rank based selection for selection, 1-point crossover for crossover, and swap mutation for mutation. Solution-seeking has been done by giving genetic parameters until the best solution can be found by this algorithm. The solution of TSPTW with 1 depot and 15 nodes have the minimum total travel time when the combination of crossover probability and mutation probability 0.8 and 0.3 in a row, with generation size of 200 and population size of 10.