There seem to exist TSP solutions (https://en.wikipedia.org/wiki/Held–Karp_algorithm) that are better than O(n!), provided we have enough memory.

However, after fiddling with it for a while, I'm not sure what happens is related to solving it. In my particular case, we start with 12 islands and keep those 12 islands until the end, but at the beginning those islands are really close to each other, so the order doesn't matter much and any semi-reasonable walk order will be OK, it changes, however, when we start printing columns. Issue is, Cura doesn't seem to re-evaluate island visiting order when conditions change. Whatever order it came up with when putting the first layer it continues using till the very end.

## Recommended Posts

## gr5 2,224

There are 2 modes for the setting "print sequence": "one at a time" and "all at once". Cura recently added a feature that lets you choose the print order but only in "one at a time" mode so this doesn't help you at all. Your model can't be printed in one at a time mode as it's too tall and even if it were shorter you'd have to space the parts much farther apart.

There is an optimization algorithm but as you've discovered it could be better. I believe the way it works is that once it's done with one tower (aka "island" in the source code) it picks the nearest island from where the head ended on the current island. This helps so much more than printing in random order. So there is an optimization algorithm but it's pathetically simple.

Your optimization goal is called "the traveling salesman problem" and is one of the most famous optimization problems in software and something that computer science students study. You only have 12 towers but even in this example there are 12! or 479 million possible orders to print the islands on layers with towers. 479 million is small enough that a computer could certainly calculate every possible route in a few seconds but if you go to 15 towers it's now too large a number to do in a reasonable time. And that's just "island order". There are other optimizations within each island and from one layer to the next. So it's usually not possible to find the best solution but the optimization algorithm could certainly be improved! A lot! For example it should at least try 1000 different random possibilities and pick the fastest! But there are 100s of known algorithms that can improve over what it does now.

I'm sure someone on the Cura team did some analysis and realized that doing a better optimization sequence would only improve printing time of most models by say 10% but I don't know.

## Link to post

## Share on other sites