Newspaper Route Determination System in Palu City Using Genetic Algorithm

Abstract

Newspaper distribution route is a common problem faced by a deliveryman alongside the high demand of Radar Sulteng newspaper that must be satisfied. A deliveryman must delivernewspapers in a timely fashion to the customers. The Travelling Salesman Problem (TSP) is a method that may be used to solve deliverymen’s problem, the tedious nature of visiting each customer exactly once until they come back to the starting point. This study aims to implement Genetic Algorithm (AG) to TSP model to develop a route determination system of Radar Sulteng newspaper distribution using Hypertext Preprocessor (PHP) programming language. With this system, it is expected that an optimal newspaper distribution route can be created, which would result in reduction in travel time and cost and, ultimately, maximum profit for the company. Genetic Algorithm (AG) is an algorithm that mimics how genetic process works in living creatures, where selection, recombination and mutation processes take place to obtain the best chromosome in a generation. One aspect that plays an important role in AG method is the determination of recombination involving crossover and mutation. In this study, AG parameters used to solve the TSP are a crossover probability of 0.05, mutation probability of 0.5, total chromosome of 800 and total generation of 200, by inputting data from 66 customers. The best fitness obtained at 194^th generation with 24,569 KM with computation time of 8197,48182371652 seconds or 2 Hours 16 Minutes