Pro-G

Spaghetti Bridges help students to understand materials and structures resistance with fun and at low cost. Richard Williams from Las Vegas, Nevada designed the “Barilla Fettucini Bridge ” with SolidWorks, and we calculated its strenght with CosmosWorks.

Dry pasta material data can be found in [1] :

• density : 1.5 kg/dm³
• Young modulus 3600 N/mm²
• elasticity and yield limit : 16.778 N/mm²

Using CosmosWorks, we made a statics study of the bridge under a load of 10N (~1Kg) on 0.1m x 0.1m square placed on the center of the deck, and obtained the safety factor which gives the maximal load of the bridge as well as the location of maximal stresses, which indicates the points to reinforce

Référence:

1. Luis Alberto Segovia González, Inácio Benvegnu Morsch, João Ricardo Masuero, “Didactic Games in Engineering Teaching – Case : Spaghetti Bridges and Building Contest “, 2005, Proceedings of COBEM 2005 18th International Congress of Mechanical Engineering

[english]This page shows how to solve a common problem in geometry, with applications in CAD/CAM : How to find the shortest path going through a set of points ?

History

It all started form a “challenge” posted by Cliff Huprich on alt.machines.cnc newsgroup: find the shortest path going through 400 random X/Y points. Some people tried to solve the problem with existing (expensive) tools or simple heuristics.

We took the challenge by considering the problem as a general operations research problem, made some web searches and proposed to use a “Travelling Salesman” approach in some posts summarized below:

This is known as the “travelling salesman” problem.
see http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html for a complete reference.
What you need is a program that would “sort” your list of points along the shortest path.
—
Made some more research on the “travelling salesman” problem (TSP) that
reminded me good old times at university…

Basically, TSP is a “NP-complete” (even “NP_hard”) problem, which means the absolute optimum path can only be found by trying all possible paths, which results in exponential complexity :  if it takes a time T to solve for N points, it will take N*T to solve for N+1 points. On a powerful PC, if you have more than about 100 points, forget it!

Luckily, there are several approximate methods and algorithms around. See http://w1.859.telia.com/~u85905224/tsp/TSP.htm for very nice, animated web-based solvers that illustrate the most common methods.

The efficiency of the various approximate methods depends on how the points are distributed : they work faster on points that are grouped in clusters or spread along a curve compared to random points.

http://www.math.princeton.edu/tsp/concorde.html is apparently the most efficient code available (check their “benchmarks” link ) but it still takes 7 mins for 1000 points, one hour for 1300, and days for 2000…
So to solve your problem, the first question is : do you accept sub-optimal solutions ?
The second is : how many points do you have ?
And the third : how are they spread in space ? (please send me a sample by e-mail)
—
I could compile concorde on Windows and it works pretty well in 2D now, about 5 secs for 1000 points on my dual AMD 1800.
Will modify it for 3D and ask Princeton if they allow me to release the executable
for free, because their license restricts use to academic research.
—

The “travelling salesman problem” (TSP) in general considers a “cost” for each pair of points (cities).
all you have to provide to the algorithm is simply this cost function.
If the function gives the (euclidian) distance between the points, it will solve the problem discussed here.
In the case where you have highway or routes, you assign them for example the travel time as cost (and even give different costs to the A->B and B->A route), and infinite (or very large) cost to pairs that have no direct route between them, which actually speeds the algorithm considerably up by limiting the search width. This is why TSP algorithms are tested/benchmarked precisely on “symmetric euclidian” problems like the one we have here.

As you see, the TSP approach is very powerful, but I still have a difficulty with the problem posed here as TSP solvers give the shortest *closed* path through all points. For an open path with a given start point, there should be a simple thing to do but I’m not sure which…

Links:

1. http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html everything on Travelling Salesman Problem (TSP)
2. http://w1.859.telia.com/~u85905224/tsp/TSP.htm very nice, animated web-based solvers that illustrate the most common methods.
3. http://www.math.princeton.edu/tsp/concorde.html concorde solver
4. Kenneth Castelino Roshan D’Souza and Paul K. Wright “Tool-path Optimization for Minimizing Airtime during Machining” http://kingkong.me.berkeley.edu/~kenneth/research/pubs/airtime_minimization_joms.pdf

[/english]