带权变量的交互式产品配置区间查找方法

冯涛

摘要：随着企业生产模式的转变，高效的交互式产品配置显得越来越重要。但传统的产品配置没有考虑变量的价值、成本、重要性等其他因素，因而我们给变量加上了权重，并且定义为带权变量的交互式产品配置。再通过二元决策图（BDD）储存交互式产品配置的解决方案，并针对BDD进行区间查找提出了三种区间查找算法：基本方法、变量节点剪枝方法和变量取值剪枝方法。最后采用了真实的汽车产品配置实验验证三种区间查找算法的效率，发现变量取值剪枝的区间查找方法最优。

关键词：交互式；产品配置；带权变量约束满足问题；区间查找

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2019）05-0220-03

随着计算机技术的飞速发展，企业在市场中的竞争也变得越来越激烈。为了加强企业之前的竞争力，企业的生产模式由大规模的生产转化为客户化生产[1]，从而更加满足客户的需求。但是在企业的产品生产中，产品的零件数量很多（比如自行车、汽车等），同时这些复杂的零件中还存在更复杂的关系，单纯地靠人工进行产品配置，需要花费大量的精力。

为了能高效快速地对产品进行配置，基于约束满足问题（Constraint Satisfaction Problem，简称CSP）的配置方法最早于1992年被Gusgen[2]提出。随后，Faltings[3]和Gelle[4]也提出了基于CSP的产品配置方法。产品配置方法通过将产品配置问题中的元素以及元素之间的关系转化为CSP中的变量、变量的值域和约束条件，从而得到了产品配置的约束满足模型。因为求解模型得到的解空间也就对应产品配置问题的解空间，所以对CSP的求解方法显得尤为重要。

1977年，Machworth[5]总结了基于弧相容技术的推理算法解决约束满足问题。该方法只是缩小变量的值域，实际对问题求解时，仍然需要通过搜索算法求解。1997年，Purdom[6]讨论了通过回溯算法对约束满足问题求解，指出了通过回溯算法求解所需的时间和变量数成指数的关系。而回溯算法求解时需要修改已赋值变量的值，在解决交互式过程中效率较低。2005年，Subbarayan[7]提出了通过二元决策图（Binary Decision Diagram 简称BDD）来解决约束满足问题，通过将CSP问题编译成BDD，既降低了储存解的空间大小，又减少了用户交互所消耗的时间。但是作者没有考虑到不同变量的权重值不同的情况，而在实际生产中，用户不仅仅只需要结果，也要考虑到价值、成本、重要性等其他因素。

在本文中，我们给产品配置中不同的变量加入了权重，并称之为带权变量的约束满足问题（Weighted Variables Constraint Satisfaction Problem，简称WV-CSP）。本文的主要创新点在于：a）定义带权变量的约束满足问题（WV-CSP）来表示产品配置，对变量的取值增加权重值这一属性；b） 提出了两种基于BDD的区间查找算法对WV-CSP进行求解。

1 带权变量的交互式产品配置问题描述

1.1 带权变量的交互式产品配置定义

产品配置[8]泛指对可配置产品的各个零件进行组合，并且根据用户的需求得到相应产品的过程。而带权变量是指可配置产品的各个零件都有自己的权重值，它可以表示零件的价值、成本、重要性等。交互式指在进行产品配置时，用户和系统之间存在交互作用的信息处理，即用户可以通过终端设备输入信息，系统对用户的输入信息进行处理之后将结果返回给用户，用户可以根据结果再进一步处理的过程。

1.2 带权变量的约束满足问题

在进行产品配置时通常需要使用一定的产品配置方法和配置系统来实现，使用最广泛的方法就是将产品配置转化为约束满足问题[9，10]。

定义带权变量的约束满足问题可以用一个四元组[（X，D，C，W）]表示：

[X]表示变量集合：[X={x1，x2，x3，...，xn}]

[D]表示变量[X]值域集合：

[D={ D（x1），D（x2），D（x3），...，D（xn）}]

[Dxi1≤i≤n]表示变量[xi1≤i≤n]的值域：

[Dxi=d1i，d2i，d3i，…，dni]

[C]表示约束集合：

[C={c1，c2，c3，...，cn}][W]表示变量[xi1≤i≤n]的值域各值得权重：[W=w1i，w2i，w3i，…，wni]

假设一个T恤的配置例子（如表1）：T恤的生产主要包括颜色（黑色-22、白色-18、红色-14、绿色-11），尺寸（大号-15、中号-12、小号-9）和图案（MIB-8、STW-6）三种变量，变量的不同取值成本也不同，所以每个变量后面的权重值代表着该变量的价格。在这三种变量之间存在一些约束关系：（1）當用户选择图案为MIB时，颜色只能是黑色；（2）当用户选择图案为STW时，尺寸不能是小号。

我们将该产品配置转化为WV-CSP：

变量：[X={x1，x2，x3}]

值域：

[D={ {黑色、白色、红色、绿色}，{大号、中号、小号}，{MIB、STW}}]

约束：

[C={（图案=MIB→颜色=黑色），（图案=STW→尺寸≠小号）}]

权重：[W=22，18，14，11， 15，12，9， {8，6}]

在不考虑约束的条件下，我们很清楚地知道配置的解决方案为[4×3×2=24]种，但是由于约束存在，解的空间大小减少，解决方案变成了11种（如表2）。因为每个变量都加入了权重信息，所以每个解决方案都有自己的权重信息。

1.3 二元决策图

二元决策图是只有两个终止节点0和1的有向无环图[11，12]，从根节点到终止节点之间有很多的变量节点，它们用来表示布尔变量。在BDD中，所有的变量节点都有两条边：“低”和“高”（“0”和“1”，分别用虚线和实线表示）。由根节点开始到终止节点，通过变量节点的两条边，可以对布尔变量进行赋值，得到的路径就是所有变量赋值后的结果，表示一种解决方案。如果某个变量节点没有出现，则表明该变量节点的取值有两种：“0”和“1”。对于所有的解决方案，如果路径到达终止节点0表示该解决方案无效，反之，到达终止节点1表示该解决方案有效。

对于表1的产品配置，我们先对T恤的产品配置进行二进制编码（表3），根据编码信息再生成图1所示的BDD。

表3 T恤的产品配置编码

我们对BDD进行遍历求解，得到所有的解决方案，即变量[x01x11x02x12x03]的取值有24种。根据BDD的定义，我们知道只有当路径到达终止节点1的时候，该路径才是有效配置，而路径到达终止节点0的均为无效配置。因而在24种解决方案中有效配置有11种，分别为：

[00000；00001；00010；00011；00100；01001；01011；10001；10011；11001；11011]将对应的二进制编码进行解码之后得到的结果也与表2对应。

2 对WVCSP进行区间查找

本文对变量引入权重的概念，不同的变量有着不同的权重值，这就导致最后得到的有效配置的总权重值也不同。在实际生产中，用户不仅仅只关注结果，同时也会考虑其他的一些比如成本、利润等因素，用户会考虑到自身的一些原因选择权重值在区间内的结果。例如在T恤的产品配置中，不同的变量代表着不同的价格。假设某用户只需要价格在[30，35]之间的T恤，这时我们需要根据用户的要求返回给用户需要的结果。

2.1 基本的区间查找方法

对产品配置进行编码生成BDD之后，所有的配置结果存储在BDD中，通过遍历BDD可以得到所有的有效配置。在遍历BDD的过程中，每得到一条有效配置，我们可以通过之前的编码信息求出该配置的总权重值，然后和用户输入的区间值进行比较，如果满足用户要求则保留该配置，直到遍历整个BDD。显然该方法所需要的时间和BDD结构正相关，当BDD节点多，遍历所需要的时间也增多，得到最终结果的时间同样增多。

2.2 变量节点剪枝的区间查找方法

因为基本的区间查找方法需要全遍历BDD得到最终结果，所需要的时间是很多的，因而我们考虑是否可以只遍历部分BDD便得到最终结果。基于此，我们提出了权重剪枝的区间查找方法：

1）首先对所有变量中不同取值的权重按照从大到小排序，再进行二进制编码生成BDD；

2）在BDD遍历过程中，根据已知变量节点的取值（“0”或者“1”），计算出该条路径最终可能得到的权重范围；

3）如果该路径可能的权重范围与用户输入的区间没有交集，那么后面的变量节点不需要再进行遍历。

比如在T恤的例子中，各个变量的不同取值已经按照权重的从大到小排好序，所以不需要重新排序编码，而生成的BDD也没有改变。当用户需要查找价格在[30，35]之间的结果时，我们则需要遍历BDD：

1）开始时，我们可以知道配置的权重范围为[26，45]（各变量的最小权重值相加和最大权重值相加）；

2）当[x01←0]，此时的[x01x11]取值只能是“00”或者“01”，对应颜色的权重值只能为22或18，该路径的权重下界变成了[26-11+18=33]，而上界没有改变，所以得到的权重范围为[33，45]；

3）接着当[x11←0]，此时的[x01x11]取值已经确定为“00”，对应颜色的权重值只能为22，该路径的权重下界变成了[33-18+22=37]，上界仍然没有改变，此时得到的权重范围为[37，45]，此时的权重范围与用户输入区间[30，35]沒有交集，所以没有必要再对该条路径遍历下去，从而跳过了变量节点[x02x12x03]；

4）接着遍历剩下的BDD并实时计算权重范围，最终得到所有的结果。

该方法根据变量节点的取值，实时计算当前路径的权重范围，并与用户的输入区间比较。一旦该路径的权重范围与用户输入区间没有交集，便放弃对该路径的继续赋值，实现了对BDD的剪枝操作，加速了求解过程。

2.3 变量取值剪枝的区间查找方法

在上一节中，我们提出了编码剪枝的方法，该方法根据变量节点的取值（“0”或者“1”），计算该条路径的权重范围，再与用户输入的范围比较，从而判断是否可以提前结束该路径。但是对权重范围的计算是有一定代价的，每经过一个变量节点就需要计算一次权重的上届或者下界，显然消耗的时间与变量节点的数量呈指数关系，所以在该节中，我们提出了取值剪枝的区间方法：在BDD遍历过程中，我们可以知道已经遍历过的变量节点的取值（“0”或者“1”），一旦某个变量取值可以确定，我们进行一次权重范围的计算。

比如在T恤的例子中：

1）当[x01←0]，此时的[x01x11]取值只能是“00”或者“01”，对应颜色的权重值还不能确定，此时我们不进行权重范围的计算；

2）当[x11←1]，我们可以确定颜色的权重取值只能是22，所以该路径的权重下界变成了[26-11+22=37]，而上界没有改变，所以得到的权重范围为[37，45]，从而可以判断出该路径可以提前结束；

3）接着遍历剩下的BDD并实时计算权重范围，最终得到所有的结果。

该方法根据变量的取值，计算当前路径的权重范围。

3 实验结果及分析

在我们的实验中，我们选用了某汽车公司的真实数据集，数据集的特征如表4所示：

数据集中变量取值的权重值随机赋值，根据权重值的初始范围，我们将权重值区间从小到大分成了240组。根据240组权重区间，我们得到240组区间内有效配置数量分布如图2所示：

从图中我们可以看出，第120组左右区间内有效配置的数量最多，在第0组到第65组和第145组到第240组区间内均没有有效配置，整个分布图呈正态分布。

根据这240组区间，我们分别采用三种区间查找方法进行计算求解，实验结果如图3所示：

图中通过观察三种区间查找方法，我们发现：

1）基本的区间查找方法因为对BDD进行全遍历，没有进行任何剪枝操作，所以消耗的时间基本一样；

2）变量节点剪枝的区间查找方法随着有效配置数量增多时，消耗的时间增长更快；

3）变量取值剪枝的区间查找方法在三种区间查找方法中表现最好，因为减少了权重范围计算所消耗的时间；

4）变量节点剪枝的区间查找方法和变量取值的区间查找方法消耗的时间与区间内有效配置的数量呈正相关，这也说明了解的数量越多，消耗的时间越多。

4 结论

本文通过引入变量权重，将变量取值的权重和产品配置联系起来，并定义了变量权重的约束满足问题，再通过BDD表示问题所有的解决方案。在对BDD遍历求解时，提出了三种区间查找算法，通过实验分析发现：1）三种剪枝方法中变量取值的剪枝方法效果最好；2）变量节点的剪枝方法和变量取值的剪枝方法随着区间内有效配置的数量变化，消耗时间也呈正相关。

参考文献：

[1] Sabin D ， Weigel R . Product Configuration Frameworks-A Survey[J]. IEEE Intelligent Systems & Their Applications， 1998， 13（4）：42-49.

[2] Güsgen， Hans Werner， Hertzberg J . A Perspective of Constraint-Based Reasoning - An Introductory Tutorial[M]// Perspective of Constraint-Based Reasoning： An Introductory Tutorial. Springer-Verlag New York， Inc. 1992.

[3] Faltings B ， Weigel R . Constraint-Based Knowledge Representation for Configuration Systems[J]. 1994.

[4] Gelle E ， Weigel R . Interactive Configuration using Constraint Satisfaction Techniques[C]// International Conference on Practical Application of Constraint Technology. 1996.

[5] Mackworth A K. Consistency in networks of relations[J]. Artificial intelligence， 1977， 8（1）： 99-118.

[6] Purdom P W . Backtracking and random constraint satisfaction[J]. Annals of Mathematics & Artificial Intelligence， 1997， 20（1-4）：393-410.

[7] Subbarayan S. Integrating CSP decomposition techniques and BDDs for compiling configuration problems[C]//International Conference on Integration of Artificial Intelligence （AI） and Operations Research （OR） Techniques in Constraint Programming. Springer， Berlin， Heidelberg， 2005： 351-365.

[8] Guo Yongji. Engineering Theory for Reliability [M].Beijing： Tinghua University Press， 2001.

[9] Tsang E. Foundations of constraint satisfaction. London： Academic Press， 1993.

[10] Liu Yu. Test and Evaluation for Reliability Model on Customer Satisfaction [M]. Beijing： Documentary Press for Social Sciences， 2003.

[11] 張涛， 张建军. 一种基于BDD的多阶段任务系统可靠度新算法[C]//国际可靠性、维修性、安全性会议. 2004.

[12] 吕关锋， 苏开乐， 林瀚， 等. 基于BDD的图表示及其算法[J].中山大学学报：自然科学版，2006，45（1）.

【通联编辑：唐一东】