2
$\begingroup$

I'm currently solving the capacitated vehicle routing problem (cvrp) with the approached methods (metaheuristics).

In order to do this I have to build a random initial solution.

My question is when we say a random solution it means that we have to solve it without respecting the capacity constraint or what?

EDIT

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) {
        Number[] ret = findNode(curNodeId, remCapacity, remainingNodes, problem);

        int nextNodeId = (Integer) ret[0];
        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 Number[] 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;
    Iterator<Integer> iter = remainingNodes.iterator();

         while (iter.hasNext()) {
          int nodeId = iter.next();
          
          if (demands[nodeId] > remCapacity) {
                continue;
            }
        
            bestNodeId = nodeId;
           
        }

    return new Number[] { new Integer(bestNodeId) };
}}

But when I run my program several times I get the same solution is this normal since I proceed randomly?

$\endgroup$
7
$\begingroup$

"Random solution" means the decision variables are chosen randomly. It does not usually mean ignoring feasibility constraints. So, in the case of CVRP, it would mean choosing the cities for a given route, as well as their sequence on the route, randomly. There are various ways to deal with the capacity constraint -- for example, if the next randomly chosen city would violate the capacity of the current route, start a new route. Or, if the next randomly chosen city would violate the capacity, then keep checking all the cities (in random order) until you find one that is capacity-feasible, or until you've checked all remaining cities.

$\endgroup$
2
  • 1
    $\begingroup$ I did not see your answer before I posted mine and I see we agree on the interpretation. $\endgroup$
    – Sune
    Feb 15 at 10:53
  • $\begingroup$ please check my EDIT $\endgroup$ Feb 15 at 11:05
7
$\begingroup$

Usually such statements mean that you should device a construction heuristic, which relies on some level of randomness. That is, if you run your construction procedure twice you should not (necessarily) get the same solution. I would in most cases, if not stated explicitly, expect the solution to be feasible to the problem (in your case it should probably respect the capacity constraints).

A simple, and probably not very good, randomized construction heuristic for cvrps could be something along the lines of

  1. Start a new route by placing a vehicle at the depot. Let the depot be the current node
  2. Make a list of $k\geq 1$ promising nodes that does not belong to any other routes (nodes with demand less than the residual capacity of the vehicle).
  3. Generate a random number, $l$, between 1 and $k$ and extend the route with the $l$'th node from the list. Let the $l$' th node become the current node.
  4. If all nodes belong to a route, return the solution.
  5. If the route cannot be extended further, return to the depot and go to 1. Else go to 2.
$\endgroup$
1
  • $\begingroup$ please ckeck My EDIT $\endgroup$ Feb 15 at 11:05
5
$\begingroup$

Altough I agree with the other answers, I think its worth mentioning that a random initial solution does not have to be feasible.

When using (meta)heuristics, it is often the case that infeasible solutions are used in the search space, while the number of conflicts (the number of times a constraint is violated) is minimized in the cost function.

For example, this is the case in this paper, where the authors develop a tabu search heuristic for the CVRP called TABUROUTE, where infeasible routes (with respect to length or capacity) are used throughout the procedure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.