# How do I find the shortest distance between x,y coordinates in excel

1. ## How do I find the shortest distance between x,y coordinates in excel

Ok so I have a project in a linear programming class of mine here it is:
I must pick up 40 tennis balls (x,y points) These balls must all be picked up and put in a basket. Please determine the shortest tour that allows you to pick up every ball and return to (0,0). You must begin at (0,0) and you must walk around the net. The net poles are located at (12,39) and (48,39). Show your path on a figure and give the total distance travelled.

So I need to find the shortest distance to pick up the "balls", the grid is essentially a tennis court with a net in the middle. I am sure there is a formula for this but I do not know it, any and all help is greatly appreciated. I have attached the data containing the 40 points, on the left side of the data sheet is the original 40 points sorted x,y descending, on the right hand side is how I have sorted them in the path which I think may be the shortest route.  Register To Reply

2. ## Re: How do I find the shortest distance between x,y coordinates in excel

Sounds like a job for Miscrosoft Solver (Excel add-in). There's a good (more complex) worked example at http://blogs.msdn.com/excel/archive/...k-problem.aspx concerning network optimisation which could probably be adapted to your situation.

Regards
Mike  Register To Reply

3. ## Re: How do I find the shortest distance between x,y coordinates in excel

I think your instructor is pulling your leg. This is called the Traveling Salesman problem, one of a class of problems called hard; see, for example, http://en.wikipedia.org/wiki/Traveling_salesman_problem.

There is no closed-form solution other than trying all possible combinations (which for your 40 balls, leaves about 10^48 possibilities). Using the approach described at the link by Mikeopolo, there are 780 possible legs for Solver to evaluate as in or out.

That said, your path looks pretty good.  Register To Reply

4. ## Re: How do I find the shortest distance between x,y coordinates in excel

Thanks for the help, I downloaded solver and I will give it a try..Im just not really sure on how to use it/which cell values to put in, specifically the constraints (being the net) and the function to minimize (clearly distance but what cell should I use). Any suggestions on that?  Register To Reply

5. ## Re: How do I find the shortest distance between x,y coordinates in excel

I'd be pleasantly surprised if it worked.  Register To Reply

6. ## Re: How do I find the shortest distance between x,y coordinates in excel

I will give it a shot and let you know.  Register To Reply

7. ## Re: How do I find the shortest distance between x,y coordinates in excel  Register To Reply

8. ## Re: How do I find the shortest distance between x,y coordinates in excel

As far as the net is concerned, your input will consist mainly of co-ordinates between two points, so would you not just omit the pairs where the net gets in the way? So the solver won't have those paths as options.  Register To Reply

There are currently 1 users browsing this thread. (0 members and 1 guests) 