vendredi 29 janvier 2021

how to solve the runtime problem without getting a result while solving the vehicle routing problem using java

I wanto to resolve the vehicle routing problem while respecting the constraint of times window. I have the following class

  public class VrpProblem {

private static int maxLocomotives=3;
private int numRames;
private int[] serviceTimes;
private int[] windowStartTimes;
private int[] windowEndTimes;
public double[][] rameTimes;
public double[] timesFromMultimodal;

private double maxTime;

public VrpProblem(int numRames,double[][] rameTimes,double[] timesFromMultimodal,int[] serviceTimes,int[] windowStartTimes, int[] windowEndTimes) {

    this.numRames = numRames;
    this.serviceTimes = serviceTimes;
    this.windowStartTimes = windowStartTimes;
    this.windowEndTimes = windowEndTimes;
    this.timesFromMultimodal = timesFromMultimodal;
    double[][] mat=new double[numRames][];
    for (int i=0 ; i<mat.length; i++)
        mat[i]=new double[numRames];
    for (int i = 0; i < numRames; i++) {
          
          for (int j = 0; j < numRames; j++) {
            mat [i][j] = rameTimes[i][j];
            if (rameTimes[i][j] > maxTime) {
              maxTime= rameTimes[i][j];
            }
          }
        }
    
    this.rameTimes = mat;


      }

public int[] getServiceTimes() {
    return serviceTimes;
}

public int[] getWindowStartTimes() {
    return windowStartTimes;
}

public double getMaxTime() {
    return maxTime;
}

//si Id est negatif, Il refere au multimodal
  public double getTime(int custId1, int custId2) {
    if (custId1 >= 0 && custId2 >= 0) {
      return rameTimes[custId1][custId2];
    } else if (custId1 >= 0) {
      return timesFromMultimodal[custId1];
    } else if (custId2 >= 0){
      return timesFromMultimodal[custId2];
    } else {
      return 0; //les 2 multimodal
    }
  }

public int[] getWindowEndTimes() {
    return windowEndTimes;
}

public double[][] getRameTimes() {
    return rameTimes;
}
public double[] getTimesFromMultimodal() {
    return timesFromMultimodal;
}

public int getNumRames() {
        return this.numRames;
      }}

And the class VrpReader

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

  public class VrpReader {

private static File f;

public static  VrpProblem readSolomon(String FilePath, int numRames) throws IOException{

        
    f = new File(FilePath);
    BufferedReader br = new BufferedReader(new FileReader(f));
    String line = br.readLine();
     String[] tokens = line.trim().split("\\s+");
        int depotX = (int)(Double.parseDouble(tokens[1]));
        int depotY = (int)(Double.parseDouble(tokens[2]));
        List<String> lines = new ArrayList<String>();
        for (int i = 0; i < numRames && (line = br.readLine()) != null; i++) {
          lines.add(line);
        }
        numRames = lines.size();
        int[] xCoors = new int[numRames];
        int[] yCoors = new int[numRames];
        int[] demands = new int[numRames];
        int[] windowStarts = new int[numRames];
        int[] windowEnds = new int[numRames];
        int[] serviceTimes = new int[numRames];
        double[][] rameTimes = new double[numRames][numRames];
        double[] timesFromMultimodal = new double[numRames];
        
        for (int i = 0; i < numRames; i++) {
            tokens = lines.get(i).trim().split("\\s+");
            //CUST NO.   XCOORD.   YCOORD.    DEMAND   READY TIME   DUE DATE   SERVICE TIME
            int x = (int)(Double.parseDouble(tokens[1]));
            xCoors[i] = (x);
            int y = (int)(Double.parseDouble(tokens[2]));
            yCoors[i] = (y);
            int windowStart = (int)(Double.parseDouble(tokens[4]));
            windowStarts[i] = (windowStart);
            int windowEnd = (int)(Double.parseDouble(tokens[5]));
            windowEnds[i] = (windowEnd);
            int serviceTime = (int)(Double.parseDouble(tokens[6]));
            serviceTimes[i] = (serviceTime);
          }
        
        for (int i = 0; i < numRames; i++) {
            for (int j = 0; j < numRames; j++) {
            int xDiff = xCoors[i] - xCoors[j];
            int yDiff = yCoors[i] - yCoors[j];
            rameTimes[i][j] = Math.sqrt(xDiff * xDiff + yDiff * yDiff);
            
          }
        }
    
        for (int i = 0; i < numRames; i++) {
              int xDiffFromDepot = xCoors[i] - depotX;
              int yDiffFromDepot = yCoors[i] - depotY;
              timesFromMultimodal[i] = Math.sqrt(xDiffFromDepot * xDiffFromDepot + yDiffFromDepot * yDiffFromDepot);
        }
        
        VrpProblem problem = new VrpProblem(numRames, rameTimes, timesFromMultimodal, serviceTimes, windowStarts, windowEnds);
        return problem;
        } }

And the class Solution

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

 public class Solution{

private List<List<Integer>> routes;
private List<Integer> unrouted;
private int numLocomotives;
private VrpProblem problem;
private double toursCost = -1;

public Solution(VrpProblem problem) {
    this.problem = problem;
    this.routes = new ArrayList<List<Integer>>();
    this.unrouted = new ArrayList<Integer>();
}

public Solution(VrpProblem problem, List<List<Integer>> routes) {
    this.problem = problem;
    this.routes = routes;
    this.unrouted = new ArrayList<Integer>();

}

public Solution(VrpProblem problem, List<List<Integer>> routes, List<Integer> unrouted) {
    this.problem = problem;
    this.routes = routes;
    this.unrouted = unrouted;

}

public void setNumLocomotives(int numLocomotives) {
    this.numLocomotives = numLocomotives;
}

public void setRoutes(List<List<Integer>> routes) {

    this.routes = routes;
}

public void setUnrouted(List<Integer> unrouted) {
    this.unrouted = unrouted;
}

private double calcToursCost(List<List<Integer>> routes, VrpProblem problem) {
    double[][] times = problem.getRameTimes();
    double[] timesFromMultimodal = problem.getTimesFromMultimodal();

    double toursCost = 0;
    for (List<Integer> route : routes) {
        Iterator<Integer> iter = route.iterator();
        if (!iter.hasNext()) {
            continue;
        }
        int prev = iter.next();
        toursCost += timesFromMultimodal[prev];
        while (iter.hasNext()) {
            int cur = iter.next();
            toursCost += times[prev][cur];
            prev = cur;
        }
        toursCost += timesFromMultimodal[prev];
    }
    return toursCost;
}

public VrpProblem getProblem() {
    return problem;
}

public List<List<Integer>> getRoutes() {
    return routes;
}

public List<Integer> getUninsertedNodes() {
    return unrouted;
}

public int getNumLocomotives() {
    return numLocomotives;
}

public double getToursCost() {
    if (toursCost >= 0) {
        return toursCost;
    } else {
        return toursCost = calcToursCost(this.getRoutes(), this.getProblem());
    }
}

public void SolutionInitiale()

{
    VrpProblem problem=this.getProblem(); 
     int[] windowEndTimes = problem.getWindowEndTimes();
     int[] windowStartTimes = problem.getWindowEndTimes();
     double[] timesFromMultimodal = problem.getTimesFromMultimodal();
     int[] serviceTimes = problem.getServiceTimes();
     double[][] times = problem.getRameTimes();
    List<List<Integer>> routes =  new ArrayList<List<Integer>>();
     double[] timesFromDepot = problem.getTimesFromMultimodal();
    routes = this.getRoutes(); 
    HashSet<Integer> remainingNodes = new HashSet<Integer>();
    for (int i = 0; i < problem.getNumRames(); i++) {
        remainingNodes.add(i);
        }
        for (List<Integer> route : routes) {
          for (Integer node : route) {
            remainingNodes.remove(node);
          }
        }
        List<Integer> curRoute = new ArrayList<Integer>();
        routes.add(curRoute);
        int curNodeId = -1;
        double curVisitTime = 0;
        while (remainingNodes.size() > 0) {
            Iterator<Integer> iter = remainingNodes.iterator();
            while (iter.hasNext()) {
              int nextnodeId = iter.next();
              double distance = (curNodeId == -1) ? timesFromDepot[nextnodeId] : times[curNodeId][nextnodeId];
              int curLastServiceTime = (curNodeId == -1) ? 0 : serviceTimes[curNodeId];
              double minVisitTime = curVisitTime + curLastServiceTime + distance;
              
              if (minVisitTime < windowStartTimes[nextnodeId]) {
                  nextnodeId = curNodeId;
              }
              if (nextnodeId != -1) {
                    remainingNodes.remove(nextnodeId);
                    curRoute.add(nextnodeId);
                    curNodeId = nextnodeId;
                    curVisitTime = minVisitTime;
                  } else {
                    curRoute = new ArrayList<Integer>();
                    routes.add(curRoute);
                    curVisitTime = 0;
                    curNodeId = -1;
                  }
        }
     }
    
        this.setRoutes(routes);
        this.setNumLocomotives(routes.size());
    }}

And the main class

import java.io.IOException;
import java.util.ArrayList;
 import java.lang.management.ThreadMXBean;

       public class Test {

public static void main(String[] args) {
           VrpReader vr = new VrpReader();
          VrpProblem problem;
       try {
        problem =vr.readSolomon("D:\\c102.txt", 100);
          Solution initial = new Solution(problem);
    
        initial.SolutionInitiale();
        toString(initial);
        System.out.println("Pour test :"+initial.getToursCost());
        System.out.println("Pour test :"+initial.getNumLocomotives());
        System.out.println("-----------------------");




      } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    
  public static void toString(Solution sol) {
           System.out.println("La solution : " + sol.getRoutes()); 
  }
     }
         }

Example of data :
0 40 50 0 0 1236 0
1 45 68 10 0 1127 90
2 45 70 30 0 1125 90
3 42 66 10 0 1129 90
4 42 68 10 727 782 90

When I run my code it takes a long time without getting a result , I don't know what to do and where is the problem.




Aucun commentaire:

Enregistrer un commentaire