I am solving the capacitated vehicle routing probelm cvrp
with the approached methods (metaheuristics).
To do this I have to build a random feasible solution
.
I'm using the following code :
public void RandomInitializer() {
VrpProblem problem = this.getProblem();
List<List<Integer>> routes = new ArrayList<List<Integer>>();
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;
int remCapacity = problem.getVehicleCapacity();
while (remainingNodes.size() > 0) {
int ret = findNode(curNodeId, remCapacity, remainingNodes, problem);
int nextNodeId = ret;
if (nextNodeId != -1) {
remainingNodes.remove(nextNodeId);
curRoute.add(nextNodeId);
curNodeId = nextNodeId;
remCapacity -= problem.getDemands()[nextNodeId];
} else {
curRoute = new ArrayList<Integer>();
routes.add(curRoute);
curNodeId = -1;
remCapacity = problem.getVehicleCapacity();
}
}
this.setRoutes(routes);
this.setNumLocomotives(routes.size());
}
private <E> int findNode(int curLastId, int remCapacity, HashSet<Integer> remainingNodes, VrpProblem problem) {
int[] demands = problem.getDemands();
double[][] times = problem.getRameTimes();
double[] timesFromDepot = problem.getTimesFromMultimodal();
int bestNodeId = -1;
E randomElement = null;
int currentIndex = 0;
Random random = new Random();
//this will generate a random number between 0 and HashSet.size - 1
int randomNumber = random.nextInt(remainingNodes.size());
Iterator<Integer> iter = remainingNodes.iterator();
int node = 0;
while (iter.hasNext()) {
randomElement = (E) iter.next();
if(currentIndex == randomNumber) {
node = (int) randomElement;
}
currentIndex++;
if (demands[(int) node] > remCapacity) {
continue;
}
bestNodeId = node;
}
return bestNodeId = (int) node;
}
I'm trying to randomly take an element from the hashset and just after test if this element does not violate the capacity constraint.
But I always get an unfeasible solution with the violation of the capacity constraint.
Is that it does not take into consideration this condition :
if (demands[(int) node] > remCapacity) {
continue;
}
Aucun commentaire:
Enregistrer un commentaire