模拟退火算法解决带时间窗的车辆路径规划问题

 public static double CreateNew() {//relocation插入算子
  InitAndPrint read=new InitAndPrint();
  int position= 0,rand=0,path=0;
  int bestRoute = 0;// best route 所属路径
  int bestPosition = 0; // best position所在位置
  double Ans = INF,temp1,temp2;// best vehicle 所属车辆
  double score = 0;
  while(rand<=1||rand>CustomerNumber+1)
   rand= (int)(Math.random()*CustomerNumber)+1;
  for(int i=1;i< VehicleNumber;i++) 
   for(int j=0;j<routes[i].seq.size();j++) 
    if(routes[i].seq.get(j).Number==rand) {
     path=i;
     position = j;// 标记位置
     break;
    }
  read.Output(routes);
  System.out.print("a:"+path+" "+customers[rand].Path_Number+" "+position+" "+rand+"  ");
  removenode(path, position, rand);// 将客户i从原路径的第P个位置中移除
  
  for (int j = 1; j <= VehicleNumber;j++)
   for (int l = 1; l < routes[j].seq.size(); l++)// 分别枚举每一个节点所在位置
    if (customers[rand].Path_Number != j) {
     addnode(j, l, rand);// 将客户l插入路径j的第i个位置
     temp1 = routes[customers[rand].Path_Number].SubT; // 记录原先所在路径的时间窗违反总和
     temp2 = routes[j].SubT; // 记录插入的路径时间窗违反总和，这样就不用再update一次了
     // 更新i节点移出的路径：
     routes[customers[rand].Path_Number].SubT = 0;
     UpdateSubT(routes[customers[rand].Path_Number]);
     // 更新i节点移入的路径j：
     routes[j].SubT = 0;
     UpdateSubT(routes[j]);
     score = Calculation(routes);// 计算目标函数值
     if(score<Ans) {
      Ans =score; // best vehicle 所属车辆
      System.out.print(j);
      bestRoute = j; // best route 所属路径
      bestPosition = l; // best position所在位置
     }
     routes[customers[rand].Path_Number].SubT = temp1;
     routes[j].SubT = temp2;
     removenode(j, l, rand);
    }
  addnode(customers[rand].Path_Number, position, rand);//与前面的第一次remove呼应，复原
  //正式插入
  for (int i = 1; i < routes[customers[rand].Path_Number].seq.size(); i++)
   if (routes[customers[rand].Path_Number].seq.get(i).Number == rand) {
    position= i;
    break;
   }
  removenode(customers[rand].Path_Number, position,rand);
  addnode(bestRoute, bestPosition, rand);
  routes[bestRoute].SubT = 0;
  UpdateSubT(routes[bestRoute]);
  routes[customers[rand].Path_Number].SubT = 0;
  UpdateSubT(routes[customers[rand].Path_Number]);
  customers[rand].Path_Number= bestRoute;
  return Ans;
 }
  
   public static void addnode(int r, int position, int cus) {// 节点加入的路径routes[r],节点customer[Cus],节点加入路径的位置pos
  // 更新在路径r中加上节点Cus的需求
  routes[r].Load += customers[cus].Demand;
  // 更新在路径r中插入节点Cus后所组成的路径距离
  routes[r].Dis = routes[r].Dis
    - Graph[routes[r].seq.get(position - 1).Number][routes[r].seq.get(position).Number]
    + Graph[routes[r].seq.get(position - 1).Number][customers[cus].Number]
    + Graph[routes[r].seq.get(position).Number][customers[cus].Number];
  // 在路径r中插入节点Cus
  routes[r].seq.add(position, new CustomerType(customers[cus]));
 }
  
   public static void removenode(int r, int position, int Cus) {// 节点去除的路径routes[r],节点customer[cus],节点所在路径的位置pos
  // 更新在路径r中去除节点Cus的需求
  routes[r].Load -= customers[Cus].Demand;
  // 更新在路径r中去除节点Cus后所组成的路径的距离
  routes[r].Dis = routes[r].Dis
    - Graph[routes[r].seq.get(position - 1).Number][routes[r].seq.get(position).Number]
    - Graph[routes[r].seq.get(position).Number][routes[r].seq.get(position + 1).Number]
    + Graph[routes[r].seq.get(position - 1).Number][routes[r].seq.get(position + 1).Number];
  // 从路径r中去除节点Cus
  routes[r].seq.remove(position);
 }

 public static void Search() {
  while (temperature > 1) {
   double currentScore = Calculation(currentroutes);
   double bestScore = Calculation(bestroutes);
   double score = CreateNew();
   if (score < currentScore) {// 接受
    currentScore = score;
    for (int i = 1; i <= VehicleNumber; i++)
     deepcopy(currentroutes[i], routes[i]);
    if (Check(routes) == true && bestScore > currentScore) {
     bestScore = currentScore;
     for (int i = 1; i <= VehicleNumber; i++)
      deepcopy(bestroutes[i], currentroutes[i]);
    }
   } else {
    if (Math.random() < Math.exp(-(score - currentScore) / temperature)) {// 接受
     currentScore = score;
     for (int i = 1; i <= VehicleNumber; i++)
      deepcopy(currentroutes[i], routes[i]);
    } else
     for (int i = 1; i <= VehicleNumber; i++)
      deepcopy(routes[i], currentroutes[i]);// 还原
    if (Check(routes) == true && bestScore > currentScore) {
     bestScore = currentScore;
     for (int i = 1; i <= VehicleNumber; i++)
      deepcopy(bestroutes[i], currentroutes[i]);
    }
   }
   temperature = speed * temperature;
  }
 }