×
INTELLIGENT WORK FORUMS
FOR ENGINEERING PROFESSIONALS

Log In

Come Join Us!

Are you an
Engineering professional?
Join Eng-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!
  • Students Click Here

*Eng-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

Jobs

Shortest Distance Problem

Shortest Distance Problem

Shortest Distance Problem

(OP)
Has anyone come across a program/algorithm/technology that will optimize the shortest distance between two points? Say for example, the shortest distance between Toronto and Montreal, given certain constraints: maximum gradient.

RE: Shortest Distance Problem

Remember to use the great circle not a "map" point.

RE: Shortest Distance Problem

One could do this with a GIS package such as ArcView.  A topology query would find the shortest route.  One can weight the potential routes for grade as well as other things.  It may take a bit of time to set it up for your particular query.

For your example, one may need spatial analyst module to analyze grades based on given data, then assign the grades to road segments, decide what weight to give grades, then build the query....

RE: Shortest Distance Problem

You could use Simplex method, either the table or more easily the graphical method. You would approximate a function for the line between the 2 points and then put a constraint that you want to minimize. You may find more detail in Linear programming texts. I like the REA problem solvers in linear algebra for that method-it has solved problems for more guidance.

RE: Shortest Distance Problem

The partiular problem is also one of about 30 classical optimization or optimal constraint problems.  Some people will write a masters or doctoral thesis on even one such problem and solution.  

In multivariate mathematics, check out the Society of Industrial and Applied Mathematics (SIAM) for some good white papers on this area of study,  (out of Rice Univ, I believe, down in Houston).

ArcView uses a very simplified method of cost weighting.  It simply assigns a gridded cell map over the topology, then assigns a weighted cost function ranging from 1-5 into each cell, then runs a linear programming approach to optimizing the shortest path problem.

Although highly oversimplified, there's quite a bit to be said for accessing that type of tool if available.

Next priority is really an identification problem issue.  Identify all possible variables that might have a cost associated with them.

Next is a normalization factor.  Some people will assess an area a 1-5 scale from 5 possible values, but compare issues that are different in actual cost by orders of magnitude or by exponential impact.

There's quite a bit to be said for humanly estimating these values into a simple range of 5 discrete values and then mapping some potential solutions.

This method also varies by the resolution of cells and the number of iterations the path sums before deciding which set of possible solutions will next be considered.

Some topologies might indeed have some hard problems associated with them.  I.e. there might be some golf greens that might be impossible to sink the ball on one stroke or even three.

I used to solve some of these problems in the gas industry in the early 80s.  Today I'm developing some mountainous road paths by the same methods.  50 years ago there was a decent number of foremen and operational folk who had some inuition on these problems.  Hard to find them today.

Some solutions come from even the least wealthy sources.  In southern Asia, one method to solve the problem is to take a goat to the destination and let it go,..he then finds the shortest path back to the water source.  Many mountain roads in that area were first explored by that method.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Eng-Tips Forums free from inappropriate posts.
The Eng-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Eng-Tips forums is a member-only feature.

Click Here to join Eng-Tips and talk with other members!


Resources