The Travelling Salesman Problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

In order to solve TSP and find an Optimal Route we used a Neighbordhood Search Strategy. We implemented a Basic VNS algorithm with Local Serch to get a local optima solution. To leave the local optimal solution we implemented a swap skaker operator and to create new neighborhoods given an S' solution we implemented a 2-opt operator.

The Architecture is Based on Microservices in order to do Route Optimizations for a set of Stops. Each service solves one problem, Optimizer is the entry point to start an optimization and exposes an API REST to the client (POST /api/v1/tsp). The table is a gRPC Server to compute a Distance Matrix using OSRM Project and VNS service exposes a gRPC Server to perform a Metaheuristic algorithm.