HEURISTIC ALGORITHM FOR RING TOPOLOGY NETWORK OPTIMIZATION

• Main Author: Rokhayah
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/50576
• Institution: Institut Teknologi Bandung

The Travelling Salesman Problem (TSP) is to find a routing of a salesman who starts from a home location, visits a prescribed set of cities and returns to the original location such in such a way that the total distance travelled is minimum and each city visited exactly once. TSP has a widespread application value in real life. In telecommunication networks it is important to determine the shortest route (cost) in designing the ring topology. So an efficient solution to this problem can reduces deployment costs. TSP is a classic problem that is simple but difficult to solve conventionally. That have intrigued researchers to explore and develop algorithms for solving TSP problems. Some algorithms that have been found include brute force algorithm, ant colony optimization algorithm (ACO), greedy algorithm, Greedy Randomized Adaptive Search Procedure (GRASP). Brute force Algorithm is the easiest and most expensive solution for TSP. This algorithm try all possibilities, so it generates an absolute minimum value but takes a very long execution time for a big number of nodes. Other algorithms use the heuristic method, so it does not always provide an optimal solution although it can save execution time compared to the brute force algorithm. Research for the development of heuristic algorithms is still very open. This study focuses on getting the solution to the Traveling Salesman Problem with the heuristic method so it can produce algorithms with fast execution times and accurate results close to the absolute minimum value, so it can be implemented in network planning. This algorithm is a development of an existing algorithm. This algorithm successfully corrects the shortcomings of the previous algorithm, which is a long computational time. In this study python programming languages are used, Net2Plan network simulator is used for simulations. The results showed that this algorithm in some data could outperform some other algorithms both in terms of execution time and the resulting minimum value solution.