+ Reply to Thread
Results 1 to 8 of 8

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

  1. #1
    Registered User
    Join Date
    02-06-2009
    Location
    Dallas, Texas
    MS-Off Ver
    Excel 2007
    Posts
    3

    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.
    Attached Files Attached Files
    Last edited by VBA Noob; 02-08-2009 at 06:06 PM.

  2. #2
    Forum Contributor
    Join Date
    01-18-2005
    Location
    Auckland New Zealand
    MS-Off Ver
    Office Professional 2007
    Posts
    295

    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

  3. #3
    Forum Guru shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,673

    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.
    Last edited by shg; 02-08-2009 at 09:19 PM.
    Entia non sunt multiplicanda sine necessitate

  4. #4
    Registered User
    Join Date
    02-06-2009
    Location
    Dallas, Texas
    MS-Off Ver
    Excel 2007
    Posts
    3

    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?

  5. #5
    Forum Guru shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,673

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

    Just follow the instructions at the link.

    I'd be pleasantly surprised if it worked.

  6. #6
    Registered User
    Join Date
    02-06-2009
    Location
    Dallas, Texas
    MS-Off Ver
    Excel 2007
    Posts
    3

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

    I will give it a shot and let you know.

  7. #7
    Forum Guru shg's Avatar
    Join Date
    06-20-2007
    Location
    The Great State of Texas
    MS-Off Ver
    2003, 2010
    Posts
    40,673

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

    Please do -- I'd be interested in your results.

  8. #8
    Forum Contributor
    Join Date
    01-18-2005
    Location
    Auckland New Zealand
    MS-Off Ver
    Office Professional 2007
    Posts
    295

    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.

+ Reply to Thread

Thread Information

Users Browsing this Thread

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

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1