分支和价格求解 VRPTW 问题代码详情

// check first that we need to solve this node. Not the case if we have
// already found a solution within the gap precision
if ((upperbound - lowerbound) / upperbound < userParam.gap)
    return true;

// init
if (branching == null) { // root node - first call
    // first call - root node
    treeBB newNode = new treeBB();
    newNode.father = null;
    newNode.toplevel = true;
    newNode.branchFrom = -1;
    newNode.branchTo = -1;
    newNode.branchValue = -1;
    newNode.son0 = null;
    branching = newNode;
}

// display some local info
if (branching.branchValue < 1) {
    System.out.println("\nEdge from " + branching.branchFrom + " to "
            + branching.branchTo + ": forbid");
} else {
    System.out.println("\nEdge from " + branching.branchFrom + " to "
            + branching.branchTo + ": set");
}

// Compute a solution for this node using Column generation
columngen CG = new columngen();
CGobj = CG.computeColGen(userParam, routes);

// update the global lowerBound when required
    if ((branching.father != null) && (branching.father.son0 != null)
            && branching.father.toplevel) {
        // all nodes above and on the left have been processed=> we can compute
        // a new lowerBound
        lowerbound = Math.min(branching.lowestValue, branching.father.son0.lowestValue);
        branching.toplevel = true;
    } else if (branching.father == null) {
        // root node
        lowerbound = CGobj;
    }

if (branching.lowestValue > upperbound) {
    CG = null;
    System.out.println("CUT | Lower bound: " + lowerbound
            + " | Upper bound: " + upperbound + " | Gap: "
            + ((upperbound - lowerbound) / upperbound) + " | BB Depth: "
            + depth + " | Local CG cost: " + CGobj + " | " + routes.size()
            + " routes");
    return true; // cut this useless branch
}

// ///////////////////////////////////////////////////////////////////////////
// check the (integer) feasibility. Otherwise search for a branching
// variable
feasible = true;
bestEdge1 = -1;
bestEdge2 = -1;
bestObj = -1.0;
bestVal = 0;
// transform the path variable (of the CG model) into edges variables
for (i = 0; i < userParam.nbclients + 2; i++) {
    java.util.Arrays.fill(userParam.edges[i], 0.0);
}
for (route r : routes) {
    if (r.getQ() > 1e-6) {
        // we consider only the routes in the current local solution
        ArrayList<Integer> path = r.getpath(); // get back the sequence of
        // cities (path for this route)
        prevcity = 0;
        for (i = 1; i < path.size(); i++) {
            city = path.get(i);
            userParam.edges[prevcity][city] += r.getQ(); // convert into edges
            prevcity = city;
        }
    }
}
// find a fractional edge
for (i = 0; i < userParam.nbclients + 2; i++) {
    for (j = 0; j < userParam.nbclients + 2; j++) {
        coef = userParam.edges[i][j];
        if ((coef > 1e-6) && ((coef < 0.9999999999) || (coef > 1.0000000001))) {
            // this route has a fractional coefficient in the solution =>
            // should we branch on this one?
            feasible = false;
            // what if we impose this route in the solution? Q=1
            // keep the ref of the edge which should lead to the largest change
            change = Math.min(coef, Math.abs(1.0 - coef));
            change *= routes.get(i).getcost();
            if (change > bestObj) {
                bestEdge1 = i;
                bestEdge2 = j;
                bestObj = change;
                bestVal = (Math.abs(1.0 - coef) > coef) ? 0 : 1;
            }
        }
    }
}

if (branching.lowestValue < upperbound) { // new incumbant feasible solution!
    upperbound = branching.lowestValue;
    bestRoutes.clear();
    for (route r : routes) {
        if (r.getQ() > 1e-6) {
            route optim = new route();
            optim.setcost(r.getcost());
            optim.path = r.getpath();
            optim.setQ(r.getQ());
            bestRoutes.add(optim);
        }
    }
    System.out.println("OPT | Lower bound: " + lowerbound
            + " | Upper bound: " + upperbound + " | Gap: "
            + ((upperbound - lowerbound) / upperbound) + " | BB Depth: "
            + depth + " | Local CG cost: " + CGobj + " | " + routes.size()
            + " routes");
    System.out.flush();
} else {
    System.out.println("FEAS | Lower bound: " + lowerbound
            + " | Upper bound: " + upperbound + " | Gap: "
            + ((upperbound - lowerbound) / upperbound) + " | BB Depth: "
            + depth + " | Local CG cost: " + CGobj + " | " + routes.size()
            + " routes");
}
return true;

// ///////////////////////////////////////////////////////////
// branching (diving strategy)
// first branch -> set edges[bestEdge1][bestEdge2]=0
// record the branching information in a tree list
treeBB newNode1 = new treeBB();
newNode1.father = branching;
newNode1.branchFrom = bestEdge1;
newNode1.branchTo = bestEdge2;
newNode1.branchValue = bestVal; // first version was not with bestVal
// but with 0
newNode1.lowestValue = -1E10;
newNode1.son0 = null;
// branching on edges[bestEdge1][bestEdge2]=0
EdgesBasedOnBranching(userParam, newNode1, false);
// the initial lp for the CG contains all the routes of the previous
// solution less(去掉分支的边) the routes containing this arc
ArrayList<route> nodeRoutes = new ArrayList<route>();
for (route r : routes) {
    ArrayList<Integer> path = r.getpath();
    boolean accept = true;
    if (path.size() > 3) { // we must keep trivial routes
        // Depot-City-Depot in the set to ensure
        // feasibility of the CG
        prevcity = 0;
        for (j = 1; accept && (j < path.size()); j++) {
            city = path.get(j);
            if ((prevcity == bestEdge1) && (city == bestEdge2))
                accept = false;
            prevcity = city;
        }
    }
    if (accept) nodeRoutes.add(r);
}
boolean ok;
ok = BBNode(userParam, nodeRoutes, newNode1, bestRoutes, depth + 1);
nodeRoutes = null; // free memory
if (!ok) {
    return false;
}
branching.son0 = newNode1;