Close
0%
0%

G-code Optimization

Traveling salesman problem

Similar projects worth following
I have made a little program for optimizing G-code that can be downloaded free on my Github. It started with that I was using my CNC machine to make pcbs. The generated G-code wasn't very efficient, and was making a lots of unnecessary long move between cuts.
Then I found out that this is a known problem called Traveling salesman problem (TSP), which is to find the shortest tour to a number of cities the salesman have to visit. In my problem the cities is the cuts and the tour is the moves between the cuts.

There is a lot of information on the internet about this problem, and the first way I was trying to solve the problem with was Ant Colony Optimization (ACO). But after implementing it I realized that is was not very fast, and the resulting route wasn'toptimized very good.This could the due to I haven't used the most optimal parameter settings for the problem I was solving at the time.But because this algorithm have parameter, that they should be changed after a given problem is a major drawback. So I changed to a 2-opt kernighan–Lin algorithm.

The algorithm used:

The 2-opt algorithm is very simple and works by switching two paths to make the tour shorter. As shown here:

The algorithm is going through all possible swaps, and by replacing only the shorter swaps with to the tour. Resulting in a shorter and shorter tour, and when the tour can't get any shorter it stops and your have found the optimum tour with this algorithm.

The code I made to this algorithm was surprisingly simple, faster and give more optimum tour than the Ant Colony Optimization. So here it is:

int[] opt2(int[] path, double[][] dis)
{
  int cities = dis.GetLength(0), i, j;
  START:
  for (i = 0; i < cities - 2; i++)
  {
    for (j = i + 2; j < cities; j++)
    {
      double swap_length = dis[path[i]][path[j]] +
                           dis[path[i + 1]][path[j + 1]];
      double old_length = dis[path[i]][path[i + 1]] + 
                          dis[path[j]][path[j + 1]];
      if (swap_length < old_length)
      {
         // Make the new and shorter path.
         for (int x = 0; x < (j - i) / 2; x++)
         {
            int temp = path[i + 1 + x];
            path[i + 1 + x] = path[j - x];
            path[j - x] = temp;
         }
         goto START;
      }
    }
  }
  return path;
}

This function has 2 input parameters :

int[] path : An array that represent the current path(tour).

Ex. path = {0,2,1,0} is a tour that goes form city 0 to - 2 - 1 - 0.

double[][] dis : Is an array of arrays where the row index represent the city your are coming from and the column index represent the city you are going to.

Ex. dis[0][2] = gives the distance from city 0 to city 2.

The return parameter is the optimized tour.

  • New version: 0.4.4

    Rune11/29/2015 at 16:36 1 comment

    A new version is available which support X and Y coordinates in different lines and fixed some small optimization bugs.
    If you have problems with the program, and if you find bugs just contact me.

View project log

Enjoy this project?

Share

Discussions

agp.cooper wrote 07/24/2016 at 05:18 point

Hi one more time,

I finished coding my version of the g-Code optimiser and a surprising result.

Some Background

I use Vectric Cut2D v1.5 as my CAM software and I noticed that the output order was rather "random" in that it was neither left to right nor top to bottom nor in order of creation, etc.

In fact it would do half a group of letters, then go away and then come back to finish the text.

So okay I thought I could clean this up using the Travelling Salesman Algorithm (TSA).

The Result

I have some working code (checks out mathematically against test data and graphically as valid) but it is 20% worse than the Cut2D gCode!?

Well the answer is that the Cut2D gCode has already been optimised using a better  TSA than mine. The reason for the apparent random lettering is that the Cut2D gCode is a good solution but not an optimal solution (which is expected as optimal solutions are very hard to solve) and we are both using approximate solution algorithms.

So an interesting exercise but a fatally flawed premise.

I would appear to me that practically all CAM software probably outputs a TSA solution for its gCode (obviously I have not checked). It just looks "random" the naive eye. 

My code also filters out redundant points based on a tolerance parameter so not everything was wasted (Cut2D v1.5 does not do that).

Regards Alan

  Are you sure? yes | no

agp.cooper wrote 07/23/2016 at 15:06 point

Hi Again,

One last comment.

Your algorithm will work but it is not actually 2-Opt.

The 2-Opt algorithm swaps the best improvement swap found for each pass, your algorithm swaps the first improvement found.

So it may be slower and it may not find as good a solution as 2-Opt.

2-Opt is famous because it was the best of its type!

Regards Alan

  Are you sure? yes | no

agp.cooper wrote 07/23/2016 at 14:40 point

Hi,

I realize that the post is old but having written some similar code I can see some bugs (perhaps you have already found them) :

1- You are using zero based arrays but your code "path[j + 1]" will reference "path[cities]" (as j will equal "cities-1". You need to catch this and substitute "path[0]".

2- The route reversing code (I think) does not swap the middle two cities. I think "x < (j - i) / 2" should be "x<(j-i+1)/2". At least when I do it with pencil and paper!

In my code I blocked the swap when either path candidate was a "G1" paths.

I don't see anything that protects "G1" paths in your code - It is important?

It is possible to do this outside the function (in the distance array) by transforming an asymmetrical distance array into a symmetrical array but I suspect this was not your plan. Note: The 2-Opt algorithm only works with symmetrical arrays.

In the end I abandoned the 2-Opt algorithm for an asymmetrical TSP algorithm (i.e. Farthest Insertion).

In that way I could lock the "G1" paths in both position or route and direction, using the distance array only.

Here is an example where I locked path 2 -> 3:

<code>

int w[6][6]={
    {999,  3, 93, 13, 33,  9},
    {999,999, 77,999,999,999}, // 2 can only go to 3
    { 45, 17,999, 36, 16, 28}, // No need to block 3 going to 2
    { 39, 90, 80,999, 56,  7},
    { 28, 46, 88, 33,999, 25},
    {  3, 88, 18, 46, 92,999}
  };

</code>

I hope this was not too confusing.

Regards Alan 

  Are you sure? yes | no

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates