Shortest Distance Problem

[kbreede]

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.

 

[BigH]

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

 

[TerryScan]

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....

 

[fndn]

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.

 

[cvengr]

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.