Random Savings Algorithm for Solving Russian TSP Instances - Sanggala, Ekra; Bisma, Muhammad Ardhya (Universitas Insan Cendekia Mandiri, 2024)
Travelling Salesman Problem (TSP) is the problem for finding the shortest route starting from start node then visiting number of node exactly once and finally go back to start node. Savings Algorithm (SA) is a heuristic for solving TSP. In the Savings Algorithm, the first step that must be taken is to calculate the Savings for each pair of nodes. Then the Savings values that have been obtained are sorted from the largest Savings to the smallest Savings. Route is made by first inserting into the route the pair of nodes who has the highest Savings value. Sometimes there are many pairs of node who have the same Savings value, so it will become problem for SA to choose one of them. Random Algorithm can be a solution for solving this problem. Using Random on SA, makes SA become Random Savings Algorithm (RSA). Performance RSA on solving TSP must be tested on TSP Instance. Two important criterias on the test are solution route and CPU Time. Russian TSP Instances contain ten TSP Instances, on which RSA can be tested. The test result shows that RSA can improve the length of existing route rapidly.