tspslover.java

this tar includes my code which employ the Lin-Kernighan algorithm to address the tsp problem. this

import java.util.Vector;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;
import java.io.FileReader;
import java.io.FileNotFoundException;
import java.io.BufferedReader;
/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class TSPslover {
  public static Vector KL(Vector vec) throws IOException {
    final Vector City_list = vec;
    final double city_number = City_list.size();
    double best_cost = Double.MAX_VALUE;// the bestcost 
    double best_cost1 = Double.MAX_VALUE;// the cost of new Tour1 (created by clock P_path) 
    double best_cost2 = Double.MAX_VALUE;// the cost of new Tour2 (created by counter clock P_path)
    double best_cost3 = Double.MAX_VALUE;// the cost which store the  smallest cost of tour to update the bestcost
    Vector NewTour1 = new Vector();//new Tour1 (created by clock P_path) 
    Vector NewTour2 = new Vector();//new Tour1 (created by counter -clock P_path)  

    Vector Tour = TSP.Change_point(City_list, 1);// first tour 
    for (int i = 1; i < city_number+1; i++) {
      Tour = TSP.Change_point(Tour, i); // outer loop to change points which in the tour
  System.out.println("bestcost="+best_cost);
      Vector P_path = (Vector) Tour.clone();
int n=6;
     // inner loop of KL alogrithm. because the unmber of the inner loop is independent with 
	 //city number and approximate  3.5 (see reference in Readme). So, modified the LK alogrithm to improve the
	 //performance.  i set this loop = 10.
	  while (n>0) {
    
        for (int a = 1; a < city_number - 2; a++) {
          P_path = (Vector) Tour.clone();// great the p _path
        //  TSP.display_city(Tour);
        //  TSP.display_city(P_path);
          if (TSP.Cost_point(P_path, (City) P_path.get(a)) < best_cost) { 
            P_path.add(P_path.get(a)); // creat p_path// if cost of p_path < tour
            Vector clock = TSP.P_path_to_Tour(P_path);// make this p_path into a tour
            //System.out.println("clock="+TSP.Best_cost(clock) );
            if (TSP.Best_cost(clock) < best_cost1) { 
              NewTour1 = clock; //creat_tour
              best_cost1 = TSP.Best_cost(NewTour1);
             // System.out.println("best_cost="+best_cost1);
            }
          }
          if (NewTour1.size()==0){ // if no path is legal then store the original tour 
             NewTour1=P_path;
           //  TSP.display_city(P_path);
            best_cost1= TSP.Best_cost(NewTour1);

          }
        }
        for (int b = 1; b < city_number - 2; b++) {

          Vector Un_path = (Vector) Tour.clone();// because one tour can generate 2(n-3) P_path
		     // in two direction( clock and counter-clock)  unpath is counter-clock p_path
         // best_cost2 = Double.MAX_VALUE;
         // TSP.display_city(Tour);
         // TSP.display_city(Un_path);
         Vector Un_path1 = TSP.unclock_path(Un_path);
         // TSP.display_city(Un_path1);
          if (TSP.Cost_point(Un_path1, (City) Un_path1.get(b)) < best_cost) {// if cost of p_path< cost of tour
            Un_path.add(Un_path1.get(b)); // creat p_path
            Vector unclock = TSP.P_path_to_Tour(Un_path1);
            //System.out.println("unclock="+TSP.Best_cost(unclock));
            if (TSP.Best_cost(unclock) < best_cost2) {
              NewTour2 = unclock; //creat_tour
              best_cost2 = TSP.Best_cost(NewTour2);
              //System.out.println("best_cost2="+best_cost2);
            }
          }
          if (NewTour2.size()==0){// if no legal P_path store the original tour.
          NewTour2=Un_path;
          best_cost2=TSP.Best_cost(NewTour2);

          }
        }
        if (best_cost1<best_cost2){// find the best tour created by p_path
           best_cost=best_cost1;
            Tour=(Vector)NewTour1.clone();// update the tour 
            NewTour1.removeAllElements();// update the bestcost
           //System.out.println("dsfsdfsd");
           // TSP.display_city(Tour);
          //  flag=true;
        }
      if (best_cost1>best_cost2){// update the tour 
      best_cost=best_cost2; // update the bestcost
      Tour=(Vector)NewTour2.clone();
      NewTour2.removeAllElements();
      // System.out.println("***********");
      //TSP.display_city(Tour);
     // flag=true;
      }
if (best_cost1==best_cost2){// after a inner loop , the edge (i,k) doesn't change, so it 
 // means the inner loop is over , and need to change point.

   Tour= TSP.Change_edge(Tour);
}
    n--;

      }
    }

 return Tour;
  }

  public static void main(String args[]) throws IOException {
    if (args.length != 2) {
      System.out.println("input worng");
      System.out.println("Please input 2 args ");
      System.out.println("Arg[0]is  the path inputfile.txt" + " " +
                         "Arg[1]is the path of config.txt");
      System.exit(0);
    }
  Vector Bese_Tour=new Vector();
  double Bestcost=Double.MAX_VALUE;

   FileReader Reader = new FileReader(args[1]);// how many iterations
    BufferedReader in = new BufferedReader(Reader);
   int  b= Integer.parseInt(in.readLine());
  for (int i=0;i<b;i++){
  Vector aa = KL(TSP.Tour(args[0]));
   if(TSP.Best_cost(aa)<Bestcost){

     Bese_Tour=aa;
     Bestcost=TSP.Best_cost(aa);
	 
	 
   }
System.out.println("the "+i+"th"+"iteration");
 TSP.display_city(Bese_Tour);
  }
  System.out.println("final_result");
  System.out.println(Bestcost);
   System.out.println();
  TSP.display_city(Bese_Tour);
  System.out.println("final_result");
  }

}