# Solving Travelling Salesman Problem

Which means we are looking at a Euclidean Travelling Salesman Problem.

The 2-opt algorithm is highly dependent on the initialization that we pick for our data.

I started with using Nearest neighbour based initial path (ie Choose the nearest point as the next point in path), since theoretically, it gives the best result.

A very simple example where there are just 4 points, but it takes 2 attempts for a user to get it right.

Expectation of how the software should work " data-medium-file="https://i1com/crondev.blog/wp-content/uploads/2018/08/Wrong.gif?

Alas, it doesn’t work in the cases below (which I must mention are very much real farms and not a figment of my imagination 🙂 ) Trying to re-analyze our problem, we are trying to find a best bounding polygon for a set of points, i.e. Any intersecting edges would produce an invalid polygon (with respect to physical land entities) since it would lead us to having a negative area.

(Theoretically, there can be negative areas, eg: a farm around a house, but realistically, we don’t handle any such cases) Using Triangle inequality, the shortest path when walking along all of these points is guaranteed to have no intersecting lines.The weights between the points (sites) involved are taken to be the Euclidean distance between the points.If in an optimal tour some pair of edges AC and BD cross as shown below (Figure 4, top), then this can not be an optimal tour. Consider the tour where the edges A’B’ and D’C’ replace the edges AC and BD in our tour.In this post, we will be exploring an extremely interesting implementation of the Travelling Salesman Problem. We at Lean Agri, work towards digitising farmlands by tagging coordinates of a farm.This is helpful for various purposes: Getting an exact area of the farm, Remote monitoring farm area using satellites, Obtaining weather predictions for the specific region etc.It isn’t needed to walk along, but we can simply mark these corners.From our data, we have realized that the users are unable to mark these points in order and they need to do it over and over again.We know that AQ QB is larger than A’B’ (because in the triangle AQB, the sum of any two sides has Euclidean length greater than the third side). Intuitively for a user, the travelling salesman problem solution is going to make the most sense. TSP is solvable in time which for 15 points is going to be ~10^15 iterations!Please note that humans are extremely good at solving the Travelling Salesman Problem. Fortunately, a lot of research is done on this problem to generate approximate heuristic solutions much faster than the brute force solution.fit=173,300&ssl=1" data-large-file="https://i1com/crondev.blog/wp-content/uploads/2018/08/Wrong.gif? fit=320,556&ssl=1" class="size-medium wp-image-2199" src="https://i1com/crondev.blog/wp-content/uploads/2018/08/Wrong.gif? resize=173,300&ssl=1" alt="" width="173" height="300" data-recalc-dims="1" /How to make it work " data-medium-file="https://i2com/crondev.blog/wp-content/uploads/2018/08/Right.gif?fit=173,300&ssl=1" data-large-file="https://i2com/crondev.blog/wp-content/uploads/2018/08/Right.gif? fit=320,554&ssl=1" class="size-medium wp-image-2198" src="https://i2com/crondev.blog/wp-content/uploads/2018/08/Right.gif? resize=173,300&ssl=1" alt="" width="173" height="300" data-recalc-dims="1" / So, isn’t the solution to train users to mark them in order always?

## Comments Solving Travelling Salesman Problem

• ###### Traveling Salesman Problem OR-Tools Google Developers

The Traveling Salesman Problem TSP is one of the most famous problems. You can solve TSPs using the OR-Tools vehicle routing library.…

• ###### GeoMapping and the Travelling Salesman Problem Cron-Dev

Solving the Travelling Salesman Problem to make mapping Farms using Geotagging easier and intuitive for application uses the.…

• ###### Solving a Traveling Salesman Problem in Python for fun.

For the Nerdland Science Podcast with ao Lieven Scheire, we posed a Traveling Salesman Problem for the song “Ambiance, Ambiance” by.…

• ###### Collaboratively Solving the Traveling Salesman Problem with.

Collaboratively Solving the Traveling Salesman Problem with Limited Disclosure. Authors; Authors and affiliations. Yuan Hong; Jaideep Vaidya; Haibing Lu.…

• ###### Elephants Herding Optimization for Solving the Travelling.

This paper proposes a novel metaheuristic called Elephant Herding Optimization EHO to solve the Travelling Salesman Problem TSP, which.…

• ###### Usage of the extermal algebra in solving the travelling.

Usage of the extremal algebra in solving the travelling salesman problem. Alena Pozdílková. 1. Richard Cimler. 2. Abstract. This article compares many ways of.…

• ###### A Survey on Approaches to Solve Travelling Salesman Problem

Abstract Travelling Salesman Problem TSP is widely used in traffic. dynamic and meta-heuristic algorithms to solve the Travelling Salesman Problem. Our.…