A greedy randomized adaptive search procedure application to solve the travelling salesman problem

Abstract

The main objective of this article is to show an algorithm capable to find a minimal total length evaluation function roundtrip in symmetric Travelling Salesman Problem (TSP). Application of concepts related to Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristics, with a 2D Euclidean distance between nodes and return to start point. It was implemented through two instances defined in the TSPLIB. As results, it was observed that in all iterations the value of the initial solution, such as constructive heuristic, minimized over the course of local search optimization process, developed by the assumptions of the 2-Opt heuristics, where the best results found (836909 km) was established for simulation considering a total of 5000 iterations. The traditional TSP solution has a strong implication in determining product delivery routes for customers established in different locations, inspired by the vendors' need to deliver products in different locations (the cities) using a shorter route, reducing the time required for the trip and the possible costs. Furthermore, the use of efficient TSP resolution methods can be adapted to applications found in industrial process practices, such as determining the delivery routes of materials to traverse a range of sectors from a common distribution center.

Keywords

• greedy randomized adaptive search procedure (grasp)
• metaheuristics
• operational research
• travelling salesman problem (tsp)