CPLEX开发PVRP遇子回路约束死循环问题求助

Hey there, let’s break down why your PVRP model is getting stuck in an infinite loop after adding sub-tour elimination constraints—especially since you referenced CPLEX’s TSP example. PVRP has unique twists (pickup/dropoff pairs, node dependencies) that TSP doesn’t, so let’s go through the most likely culprits and fixes:

1. You’re Using TSP-Focused Constraints That Don’t Account for PVRP Logic #

The Miller-Tucker-Zemlin (MTZ) constraints or basic subset-based sub-tour rules work great for TSP, but they don’t account for PVRP’s core requirement: you must pick up a load before delivering it. If you’re using vanilla MTZ constraints without modifying them for pickup/dropoff pairs, you’re either missing critical constraints (allowing invalid sub-tours like delivering without picking up) or adding redundant ones that confuse the solver.

For example, if you have a pickup node i and its corresponding dropoff node i', you need to add an extra constraint like:

u[i'] >= u[i] + 1

This ensures the dropoff happens after the pickup, and prevents sub-tours that isolate either node. Without this, the solver might waste time exploring invalid paths that violate pickup/dropoff order.

2. You’re Pre-Generating All Sub-Tour Constraints (Instead of Using Lazy Constraints) #

If you’re adding every possible subset-based sub-tour constraint upfront (e.g., sum(x_ij for i,j in S) <= |S| -1 for every non-empty subset S of nodes), you’re creating an exponential number of constraints. CPLEX can’t process that efficiently, leading to endless loop behavior as it tries to handle millions of redundant or unnecessary constraints.

The fix here is to use lazy constraints (via CPLEX callbacks). Instead of adding all constraints at once, you only add a sub-tour elimination constraint when the solver finds a feasible solution that contains a sub-tour. This keeps the constraint set lean and focused.

Here’s a simplified example of how to implement a lazy constraint callback in CPLEX for PVRP:

class PVRLazyCallback : public IloCplex::LazyConstraintCallback {
protected:
    IloBoolVarArray x; // Decision variable x[i][j] = 1 if we go from node i to j
    int nodeCount;
    int depotIdx; // Index of your depot node
    std::unordered_map<int, int> pickupToDropoff; // Maps pickup node to its dropoff node

public:
    PVRLazyCallback(IloEnv env, IloBoolVarArray x, int nodes, int depot, std::unordered_map<int, int> p2d)
        : IloCplex::LazyConstraintCallback(env), x(x), nodeCount(nodes), depotIdx(depot), pickupToDropoff(p2d) {}

    void main() {
        // Grab the current feasible solution's x values
        IloNumArray solutionVals(getEnv(), x.getSize());
        getValues(solutionVals, x);

        // Build adjacency list to detect sub-tours
        std::vector<std::vector<int>> adj(nodeCount);
        for (int i = 0; i < nodeCount; i++) {
            for (int j = 0; j < nodeCount; j++) {
                if (solutionVals[i * nodeCount + j] > 0.5) { // Treat values >0.5 as 1
                    adj[i].push_back(j);
                }
            }
        }

        // Detect and eliminate sub-tours
        std::vector<bool> visited(nodeCount, false);
        for (int start = 0; start < nodeCount; start++) {
            if (!visited[start] && start != depotIdx) {
                std::vector<int> cycle;
                int current = start;
                // Traverse to find the full cycle
                while (!visited[current]) {
                    visited[current] = true;
                    cycle.push_back(current);
                    // Find next node in the path (assuming single outgoing edge for valid paths)
                    for (int nextNode : adj[current]) {
                        if (!visited[nextNode]) {
                            current = nextNode;
                            break;
                        }
                    }
                }
                // Check if the cycle is a valid sub-tour (doesn't include depot, and isn't a pickup/dropoff pair alone)
                bool hasDepot = std::find(cycle.begin(), cycle.end(), depotIdx) != cycle.end();
                if (!hasDepot && cycle.size() >= 2) {
                    // Add constraint: sum of x_ij within the cycle <= size of cycle -1
                    IloExpr subTourConstraint(getEnv());
                    for (int u : cycle) {
                        for (int v : cycle) {
                            subTourConstraint += x[u * nodeCount + v];
                        }
                    }
                    add(subTourConstraint <= cycle.size() - 1);
                    subTourConstraint.end();
                }
            }
        }
        solutionVals.end();
    }
};

To use this callback, register it with your CPLEX solver instance:

PVRLazyCallback cb(env, xVars, totalNodes, depotIndex, pickupDropoffMap);
cplex.use(&cb);

3. Your Decision Variables or Constraint Bounds Are Misconfigured #

Double-check your variable definitions and bounds:

• Are your x_ij variables correctly restricted (e.g., no direct edges from a dropoff node back to a pickup node that hasn’t been visited yet)?
• For MTZ’s u variables (node order indicators), did you set appropriate bounds? The depot should have u[depot] = 0 or 1, and other nodes should have bounds that align with pickup/dropoff order (e.g., u[dropoff] >= u[pickup] +1).
• Are there any redundant constraints that are forcing the solver to waste time checking impossible paths?

4. Solver Parameters Are Tuned for TSP, Not PVRP #

CPLEX’s default parameters might not be optimized for PVRP’s complexity. Try adjusting these:

• Increase CPX_PARAM_HEURFREQ to run heuristic solutions more often, which can help find feasible paths faster and avoid deep dives into invalid search spaces.
• Adjust CPX_PARAM_EPINT (integer feasibility tolerance) to a reasonable value (e.g., 1e-6) to avoid the solver getting stuck on near-integer solutions.
• Disable unnecessary preprocessing steps if they’re causing the solver to overcomplicate the model (though this is a last resort).

Final Quick Checks #

• Verify that your model doesn’t have any logical errors (e.g., allowing a vehicle to carry more weight than its capacity, or missing constraints that enforce pickup before delivery).
• Test with a small instance first (e.g., 5 pickup/dropoff pairs) to see if the loop occurs there too—this can help isolate whether the issue is with constraint logic or scale.

内容的提问来源于stack exchange，提问作者Obmn