CPLEX中CLuVRP的δ+(Z)、δ-(Z)与Z集合生成语法问询

核心集合的OPL语法定义 #

先明确基础集合的前置定义：假设你已定义顶点集V（包含仓库和所有集群节点）、车辆集合K（1..m，m为车辆总数），以及集群集合Clusters（每个元素是V的子集，对应一个客户集群）。

1. 生成V的所有非空真子集Z #

利用OPL的powerset函数结合过滤条件，直接生成符合要求的子集：

{int} V = ...; // 替换为你的顶点集定义（如包含仓库的节点列表）
{setof(int)} AllProperSubsets = { Z | Z in powerset(V) : Z != {} && Z != V };

2. 定义出边集合δ+(Z) #

δ+(Z)是起点属于Z、终点不属于Z的所有边，基于预定义的全边集合E生成：

// 先定义所有可行边集合（排除自环）
{tuple} E = { <i,j> | i in V, j in V : i != j };

// 对每个非空真子集Z，生成对应的出边集合
{tuple} deltaPlus(Z in AllProperSubsets) = { <i,j> in E : i in Z && j not in Z };

3. 定义入边集合δ-(Z) #

δ-(Z)是起点不属于Z、终点属于Z的所有边，写法类似：

{tuple} deltaMinus(Z in AllProperSubsets) = { <i,j> in E : i not in Z && j in Z };

约束(7)的具体实现 #

约束要求每个集群被恰好一辆车访问，分两种场景实现：

场景1：基于集群访问变量的直接约束 #

如果定义了y[c][k]（二进制变量，1表示车辆k访问集群c），约束可直接写为：

{setof(setof(int))} Clusters = ...; // 替换为你的集群集合定义

forall(c in Clusters) {
  sum(k in K) y[c][k] == 1;
}

场景2：基于边流量变量的约束 #

如果使用边变量x[i][j][k]（二进制变量，1表示车辆k行驶边<i,j>），结合δ集合确保每个集群的访问唯一性：

// 确保每个集群的入边仅来自一辆车的路径
forall(c in Clusters) {
  sum(k in K) sum(<i,j> in E : j in c) x[i][j][k] == 1;
}

// 结合δ集合的子回路消除辅助约束（可选，确保路径连通性）
forall(Z in AllProperSubsets, k in K) {
  sum(<i,j> in deltaPlus(Z)) x[i][j][k] >= sum(c in Clusters : intersect(c,Z) != {}) y[c][k];
}

性能优化提示 #

若顶点集V规模较大，枚举所有非空真子集会导致模型规模急剧膨胀，建议改用懒约束（Lazy Constraints）或有效不等式，在求解过程中动态生成必要的子集约束，避免预先生成所有子集。

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