COMPARATION AND IMPLEMENTATION OF PARTIALLY MATCHED CROSSOVER ALGORITHM AND DIJKSTRA GRAPH THEORY FOR TRAVELLING SALESMAN PROBLEMS

• Main Author: Banas Lubis, Faras
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/69315
• Institution: Institut Teknologi Bandung

One of the problems in logistics is the Capacitated Vehicle Routing Problem (CVRP) which is a sub-problem of the Traveling Salesman Problem. This problem takes the form of determining the minimum route and minimal 'cost' of delivering goods by vehicle and can be solved by algorithmic analysis. The methodology used in the analysis of the algorithm in this study is the Engineering Design Process (EDP). In the implementation of EDP, two algorithms will be compared, namely the genetic algorithm and the algorithm of the rule-based algorithm. Genetic algorithm is an algorithm that looks for the best solution based on the theory of biological evolution which is applied to computer algorithms. The genetic algorithms to be analyzed are Partially Matched Crossover and One Order Crossover. While the algorithm of rule-based algorithm is an algorithm that applies rules or rules to computer algorithms. There are two algorithms of the rule-based algorithm that will be analyzed, namely: Graph Theory Dijkstra and Integer Linear. The algorithm will be tested by measuring the complexity of time, space, effectiveness, and completeness. These criteria are important in algorithm comparison. Based on the result score, the Partially Matched Crossover algorithm gets a score of 50.91% and Dijkstra's algorithm gets a score of 83.27%. Of the algorithms tested, the Graph Theory Dijkstra algorithm got the higher score. This is used as the foundation for route selection applications that can be used by demand chain logistics companies. The site uses Heroku as a platform.