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