lundi 15 février 2021

Java : Implementation of a feasible solution for cvrp

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