// --------------------------------------------------------- 3OPT
      // Precondizione: sol ha n+1 elementi, l'ultimo e' uguale al primo
      public  int Loc3optSIMM(int[] sol, int zold, int[,] d)
      {      
         int[] solnew = new int[sol.Length], soltemp = new int[sol.Length];
         int[] zorario = new int[sol.Length];   // costi incrementali tour in senso orario
         int[] zantior = new int[sol.Length];   // costi incrementali tour in senso antiorario
         int end1a,end2a,end3a,end1b,end2b,end3b;
         int znew=int.MaxValue, l_old, zorg, z2opt, zprev;
         int i,j,k,n,n1,n2,z,ind1;
      
         int nsol = n = sol.Length;  // con l'ultimo uguale al primo
         
         if(nsol <= 5) 
            return(-1);

         n2=nsol-2;
         n1=nsol-1;
      
         // Inizio di una nuova ricerca
         zorg = zold;
lab900:  zold = 0;
         zorario[0] = 0;
         zantior[nsol-1] = 0;
         for(int js=0;js<nsol-1;js++)
         {  zold += d[sol[js],sol[js+1]];
            zorario[js+1] = zold;
            zantior[nsol-js-2] = zantior[nsol-js-1] + d[sol[nsol-js-1],sol[nsol-js-2]];
         }
            
         sol.CopyTo(soltemp,0);
         z2opt = Loc2optASIM(soltemp, d);
         if(z2opt < znew)   // nel caso un 2opt migliori un 3opt precedente
         {  znew = z2opt;
            soltemp.CopyTo(sol,0);
         }
         zold = ( zold < z2opt ? zold : z2opt);

         for(ind1=1;ind1<n2;ind1++)                   // 0 ... ind1-1
         {  end1a=sol[ind1-1];
            end1b=sol[ind1];

            int ind1meno1=ind1-1;

            for(int ind2=ind1+1;ind2<n1;ind2++)       // ind1 ... ind2-1
            {  end2a=sol[ind2-1];
               end2b=sol[ind2];

               for(int ind3=ind2+1;ind3<nsol;ind3++)  // ind2 ... nsol
               {  end3a=sol[ind3-1];
                  end3b=sol[ind3];

                  l_old=zold-d[end1a,end1b]-d[end2a,end2b]-d[end3a,end3b];

                  // ------------------------------- primo riattacco
                  if(end1b==end2a) goto lab600;
                  if(end2b==end3a) goto lab600;

                  // provo a riattaccare 1a-2a, 1b-3a, 2b-3b
                  zprev = l_old+d[end1a,end2a]+d[end1b,end3a]+d[end2b,end3b];
                  if (zprev >= zold) goto lab600;

                  // Qui ho migliorato
                  for(k=0;k<=ind1meno1;k++)
                     solnew[k]=sol[k];

                  k=ind1meno1;
                  for(int lk=ind2-1;lk>=ind1;lk--)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(int lk=ind3-1;lk>=ind2;lk--)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(k=ind3;k<nsol;k++)
                     solnew[k]=sol[k];
         
                  znew = 0;
                  flog = new StreamWriter("log.txt",true);
                  for(int js=0;js<nsol;js++)
                  {  sol[js]=solnew[js];
                     if(js<nsol-1)
                     {  znew += d[solnew[js],solnew[js+1]];
                        flog.WriteLine(String.Format("i {0} sol {1} d {2} znew {3}",js,sol[js],d[solnew[js],solnew[js+1]],znew));
                     }
                  }
                  flog.Close();            
                  if(znew != zprev)
                     MessageBox.Show("3opt (1): qualcosa tragia");
                  zold=znew;
                  goto lab900;
                  
                  // ------------------------------- secondo riattacco
lab600:           if(end1b == end2a) goto lab700;
                  if(end3b == end1a) goto lab700;

                  // provo a riattaccare 1a-3a, 2b-1b, 2a-3b
                  zprev = l_old+d[end1a,end3a]+d[end2b,end1b]+d[end2a,end3b];
                  if(zprev >= zold) goto lab700;

                  // Qui ho migliorato
                  for(k=0;k<=ind1meno1;k++)
                     solnew[k]=sol[k];

                  k=ind1meno1;
                  for(int lk=ind3-1;lk>=ind2;lk--)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(int lk=ind1;lk<=ind2-1;lk++)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(k=ind3;k<nsol;k++)
                     solnew[k]=sol[k];

                  znew = 0;
                  flog = new StreamWriter("log.txt",true);
                  for(int js=0;js<nsol;js++)
                  {  sol[js]=solnew[js];
                     if(js<nsol-1)
                     {  znew += d[solnew[js],solnew[js+1]];
                        flog.WriteLine(String.Format("i {0} sol {1} d {2} znew {3}",js,sol[js],d[solnew[js],solnew[js+1]],znew));
                     }
                  }
                  flog.Close();            
                  if(znew != zprev)
                     MessageBox.Show("3opt (2): qualcosa tragia");
                  zold=znew;
                  goto lab900;

                  // ------------------------------- terzo riattacco
lab700:           if(end2b == end3a) goto lab800;
                  if(end1a == end3b) goto lab800;

                  // provo a riattaccare 1a-2b, 3a-2a, 1b-3b
                  zprev = l_old+d[end1a,end2b]+d[end3a,end2a]+d[end1b,end3b];
                  if(zprev >= zold) goto lab800;

                  // Qui ho migliorato
                  for(k=0;k<=ind1meno1;k++)
                     solnew[k]=sol[k];

                  k=ind1meno1;
                  for(int lk=ind2;lk<=ind3-1;lk++)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(int lk=ind2-1;lk>=ind1;lk--)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(k=ind3;k<nsol;k++)
                     solnew[k]=sol[k];
         
                  znew = 0;
                  for(int js=0;js<nsol;js++)
                  {  sol[js]=solnew[js];
                     if(js<nsol-1)
                        znew += d[solnew[js],solnew[js+1]];
                  }            
                  if(znew != zprev)
                     MessageBox.Show("3opt (3): qualcosa tragia");
                  zold=znew;
                  goto lab900;

                  // ------------------------------- quarto riattacco
lab800:           if(end1a == end3b) continue;
                  if(end1b == end2a) continue;
                  if(end2b == end3a) continue;

                  // provo a riattaccare 1a-2b, 3a-1b, 2a-3b
                  zprev = l_old+d[end1a,end2b]+d[end3a,end1b]+d[end2a,end3b];
                  if(zprev >= zold) continue;
        
                  // Qui ho migliorato
                  for(k=0;k<=ind1meno1;k++)
                     solnew[k]=sol[k];

                  k=ind1meno1;
                  for(int lk=ind2;lk<=ind3-1;lk++)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(int lk=ind1;lk<=ind2-1;lk++)
                  {  k=k+1;
                     solnew[k]=sol[lk];
                  }
                  for(k=ind3;k<nsol;k++)
                     solnew[k]=sol[k];
         
                  znew = 0;
                  for(int js=0;js<nsol;js++)
                  {  sol[js]=solnew[js];
                     if(js<nsol-1)
                        znew += d[solnew[js],solnew[js+1]];
                  }            
                  if(znew != zprev)
                     MessageBox.Show("3opt (4): qualcosa tragia");
                  zold=znew;
                  goto lab900;
         
               }  // for l3 (inizio)
            }  // for l2 (inizio)
         }  // for l1 (inizio) 
         // write(*,*) ' fine opt3: ldold',ldold

         if(zorg>znew)
         {  //MessageBox.Show("Zorg = "+zorg+" znew = "+znew);
            zorg = znew;
            goto lab900;
         }

         z=0;
         sol[n-1]=sol[0];
         for(i=0;i<n-1;i++)
            z+=d[sol[i],sol[i+1]];

         // Trace.WriteLine("Fine 3 opt! z= "+z.ToString());

         return(znew);
      }