帶權變量的交互式產品配置區間查找方法

馮濤

摘要：隨著企業生產模式的轉變，高效的交互式產品配置顯得越來越重要。但傳統的產品配置沒有考慮變量的價值、成本、重要性等其他因素，因而我們給變量加上了權重，并且定義為帶權變量的交互式產品配置。再通過二元決策圖（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）.

【通聯編輯：唐一東】