Solving the Traveling Salesman Problem Using Genetic Algorithm: An Applied Study on Almadina Misurata Paints

Abstract

Operations research is considered one of the most important quantitative approaches that help organizations address complex problems through accurate solutions based on mathematical models and computational analysis. One of the most prominent and widely encountered problems in this field is the Traveling Salesman Problem (TSP), which aims to determine the shortest possible route that visits a set of locations exactly once before returning to the starting point. The complexity of this problem arises from the exponential growth in the number of possible routes as the number of locations increases, making it extremely difficult to obtain an optimal solution manually. In this context, this study aims to apply the Genetic Algorithm (GA), as one of the heuristic approaches, to address the Traveling Salesman Problem through a practical case study of Almadina Paints Company in Misrata. Location data were collected using Google Maps, and a distance matrix between the locations was constructed. Subsequently, the Solver tool in Microsoft Excel, using the Evolutionary solving method, was employed to identify a near-optimal route. The results revealed a reduction in the total route distance from 66.3 km under the current route to 48.6 km under the optimized route, representing a decrease of 17.7 km and an improvement rate of approximately 26.7%. This improvement demonstrates the role of the Genetic Algorithm in reducing travel distances, thereby contributing to lower operating costs, reduced fuel consumption, time savings, improved operational efficiency, and enhanced customer service. The study highlights the importance of employing heuristic algorithms within the framework of operations research to address routing problems in organizations. It also emphasizes the need to update location and distance data periodically to ensure the continued relevance of the proposed solutions. Furthermore, the proposed approach can be extended to address other operational problems, such as raw material distribution and transportation scheduling.