帶權(quán)變量的交互式產(chǎn)品配置區(qū)間查找方法

馮濤

摘要：隨著企業(yè)生產(chǎn)模式的轉(zhuǎn)變，高效的交互式產(chǎn)品配置顯得越來越重要。但傳統(tǒng)的產(chǎn)品配置沒有考慮變量的價值、成本、重要性等其他因素，因而我們給變量加上了權(quán)重，并且定義為帶權(quán)變量的交互式產(chǎn)品配置。再通過二元決策圖（BDD）儲存交互式產(chǎn)品配置的解決方案，并針對BDD進行區(qū)間查找提出了三種區(qū)間查找算法：基本方法、變量節(jié)點剪枝方法和變量取值剪枝方法。最后采用了真實的汽車產(chǎn)品配置實驗驗證三種區(qū)間查找算法的效率，發(fā)現(xiàn)變量取值剪枝的區(qū)間查找方法最優(yōu)。

關(guān)鍵詞：交互式；產(chǎn)品配置；帶權(quán)變量約束滿足問題；區(qū)間查找

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2019）05-0220-03

隨著計算機技術(shù)的飛速發(fā)展，企業(yè)在市場中的競爭也變得越來越激烈。為了加強企業(yè)之前的競爭力，企業(yè)的生產(chǎn)模式由大規(guī)模的生產(chǎn)轉(zhuǎn)化為客戶化生產(chǎn)[1]，從而更加滿足客戶的需求。但是在企業(yè)的產(chǎn)品生產(chǎn)中，產(chǎn)品的零件數(shù)量很多（比如自行車、汽車等），同時這些復(fù)雜的零件中還存在更復(fù)雜的關(guān)系，單純地靠人工進行產(chǎn)品配置，需要花費大量的精力。

為了能高效快速地對產(chǎn)品進行配置，基于約束滿足問題（Constraint Satisfaction Problem，簡稱CSP）的配置方法最早于1992年被Gusgen[2]提出。隨后，F(xiàn)altings[3]和Gelle[4]也提出了基于CSP的產(chǎn)品配置方法。產(chǎn)品配置方法通過將產(chǎn)品配置問題中的元素以及元素之間的關(guān)系轉(zhuǎn)化為CSP中的變量、變量的值域和約束條件，從而得到了產(chǎn)品配置的約束滿足模型。因為求解模型得到的解空間也就對應(yīng)產(chǎn)品配置問題的解空間，所以對CSP的求解方法顯得尤為重要。

1977年，Machworth[5]總結(jié)了基于弧相容技術(shù)的推理算法解決約束滿足問題。該方法只是縮小變量的值域，實際對問題求解時，仍然需要通過搜索算法求解。1997年，Purdom[6]討論了通過回溯算法對約束滿足問題求解，指出了通過回溯算法求解所需的時間和變量數(shù)成指數(shù)的關(guān)系。而回溯算法求解時需要修改已賦值變量的值，在解決交互式過程中效率較低。2005年，Subbarayan[7]提出了通過二元決策圖（Binary Decision Diagram 簡稱BDD）來解決約束滿足問題，通過將CSP問題編譯成BDD，既降低了儲存解的空間大小，又減少了用戶交互所消耗的時間。但是作者沒有考慮到不同變量的權(quán)重值不同的情況，而在實際生產(chǎn)中，用戶不僅僅只需要結(jié)果，也要考慮到價值、成本、重要性等其他因素。

在本文中，我們給產(chǎn)品配置中不同的變量加入了權(quán)重，并稱之為帶權(quán)變量的約束滿足問題（Weighted Variables Constraint Satisfaction Problem，簡稱WV-CSP）。本文的主要創(chuàng)新點在于：a）定義帶權(quán)變量的約束滿足問題（WV-CSP）來表示產(chǎn)品配置，對變量的取值增加權(quán)重值這一屬性；b） 提出了兩種基于BDD的區(qū)間查找算法對WV-CSP進行求解。

1 帶權(quán)變量的交互式產(chǎn)品配置問題描述

1.1 帶權(quán)變量的交互式產(chǎn)品配置定義

產(chǎn)品配置[8]泛指對可配置產(chǎn)品的各個零件進行組合，并且根據(jù)用戶的需求得到相應(yīng)產(chǎn)品的過程。而帶權(quán)變量是指可配置產(chǎn)品的各個零件都有自己的權(quán)重值，它可以表示零件的價值、成本、重要性等。交互式指在進行產(chǎn)品配置時，用戶和系統(tǒng)之間存在交互作用的信息處理，即用戶可以通過終端設(shè)備輸入信息，系統(tǒng)對用戶的輸入信息進行處理之后將結(jié)果返回給用戶，用戶可以根據(jù)結(jié)果再進一步處理的過程。

1.2 帶權(quán)變量的約束滿足問題

在進行產(chǎn)品配置時通常需要使用一定的產(chǎn)品配置方法和配置系統(tǒng)來實現(xiàn)，使用最廣泛的方法就是將產(chǎn)品配置轉(zhuǎn)化為約束滿足問題[9，10]。

定義帶權(quán)變量的約束滿足問題可以用一個四元組[（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]的值域各值得權(quán)重：[W=w1i，w2i，w3i，…，wni]

假設(shè)一個T恤的配置例子（如表1）：T恤的生產(chǎn)主要包括顏色（黑色-22、白色-18、紅色-14、綠色-11），尺寸（大號-15、中號-12、小號-9）和圖案（MIB-8、STW-6）三種變量，變量的不同取值成本也不同，所以每個變量后面的權(quán)重值代表著該變量的價格。在這三種變量之間存在一些約束關(guān)系：（1）當(dāng)用戶選擇圖案為MIB時，顏色只能是黑色；（2）當(dāng)用戶選擇圖案為STW時，尺寸不能是小號。

我們將該產(chǎn)品配置轉(zhuǎn)化為WV-CSP：

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

值域：

[D={ {黑色、白色、紅色、綠色}，{大號、中號、小號}，{MIB、STW}}]

約束：

[C={（圖案=MIB→顏色=黑色），（圖案=STW→尺寸≠小號）}]

權(quán)重：[W=22，18，14，11， 15，12，9， {8，6}]

在不考慮約束的條件下，我們很清楚地知道配置的解決方案為[4×3×2=24]種，但是由于約束存在，解的空間大小減少，解決方案變成了11種（如表2）。因為每個變量都加入了權(quán)重信息，所以每個解決方案都有自己的權(quán)重信息。

1.3 二元決策圖

二元決策圖是只有兩個終止節(jié)點0和1的有向無環(huán)圖[11，12]，從根節(jié)點到終止節(jié)點之間有很多的變量節(jié)點，它們用來表示布爾變量。在BDD中，所有的變量節(jié)點都有兩條邊：“低”和“高”（“0”和“1”，分別用虛線和實線表示）。由根節(jié)點開始到終止節(jié)點，通過變量節(jié)點的兩條邊，可以對布爾變量進行賦值，得到的路徑就是所有變量賦值后的結(jié)果，表示一種解決方案。如果某個變量節(jié)點沒有出現(xiàn)，則表明該變量節(jié)點的取值有兩種：“0”和“1”。對于所有的解決方案，如果路徑到達終止節(jié)點0表示該解決方案無效，反之，到達終止節(jié)點1表示該解決方案有效。

對于表1的產(chǎn)品配置，我們先對T恤的產(chǎn)品配置進行二進制編碼（表3），根據(jù)編碼信息再生成圖1所示的BDD。

表3 T恤的產(chǎn)品配置編碼

我們對BDD進行遍歷求解，得到所有的解決方案，即變量[x01x11x02x12x03]的取值有24種。根據(jù)BDD的定義，我們知道只有當(dāng)路徑到達終止節(jié)點1的時候，該路徑才是有效配置，而路徑到達終止節(jié)點0的均為無效配置。因而在24種解決方案中有效配置有11種，分別為：

[00000；00001；00010；00011；00100；01001；01011；10001；10011；11001；11011]將對應(yīng)的二進制編碼進行解碼之后得到的結(jié)果也與表2對應(yīng)。

2 對WVCSP進行區(qū)間查找

本文對變量引入權(quán)重的概念，不同的變量有著不同的權(quán)重值，這就導(dǎo)致最后得到的有效配置的總權(quán)重值也不同。在實際生產(chǎn)中，用戶不僅僅只關(guān)注結(jié)果，同時也會考慮其他的一些比如成本、利潤等因素，用戶會考慮到自身的一些原因選擇權(quán)重值在區(qū)間內(nèi)的結(jié)果。例如在T恤的產(chǎn)品配置中，不同的變量代表著不同的價格。假設(shè)某用戶只需要價格在[30，35]之間的T恤，這時我們需要根據(jù)用戶的要求返回給用戶需要的結(jié)果。

2.1 基本的區(qū)間查找方法

對產(chǎn)品配置進行編碼生成BDD之后，所有的配置結(jié)果存儲在BDD中，通過遍歷BDD可以得到所有的有效配置。在遍歷BDD的過程中，每得到一條有效配置，我們可以通過之前的編碼信息求出該配置的總權(quán)重值，然后和用戶輸入的區(qū)間值進行比較，如果滿足用戶要求則保留該配置，直到遍歷整個BDD。顯然該方法所需要的時間和BDD結(jié)構(gòu)正相關(guān)，當(dāng)BDD節(jié)點多，遍歷所需要的時間也增多，得到最終結(jié)果的時間同樣增多。

2.2 變量節(jié)點剪枝的區(qū)間查找方法

因為基本的區(qū)間查找方法需要全遍歷BDD得到最終結(jié)果，所需要的時間是很多的，因而我們考慮是否可以只遍歷部分BDD便得到最終結(jié)果。基于此，我們提出了權(quán)重剪枝的區(qū)間查找方法：

1）首先對所有變量中不同取值的權(quán)重按照從大到小排序，再進行二進制編碼生成BDD；

2）在BDD遍歷過程中，根據(jù)已知變量節(jié)點的取值（“0”或者“1”），計算出該條路徑最終可能得到的權(quán)重范圍；

3）如果該路徑可能的權(quán)重范圍與用戶輸入的區(qū)間沒有交集，那么后面的變量節(jié)點不需要再進行遍歷。

比如在T恤的例子中，各個變量的不同取值已經(jīng)按照權(quán)重的從大到小排好序，所以不需要重新排序編碼，而生成的BDD也沒有改變。當(dāng)用戶需要查找價格在[30，35]之間的結(jié)果時，我們則需要遍歷BDD：

1）開始時，我們可以知道配置的權(quán)重范圍為[26，45]（各變量的最小權(quán)重值相加和最大權(quán)重值相加）；

2）當(dāng)[x01←0]，此時的[x01x11]取值只能是“00”或者“01”，對應(yīng)顏色的權(quán)重值只能為22或18，該路徑的權(quán)重下界變成了[26-11+18=33]，而上界沒有改變，所以得到的權(quán)重范圍為[33，45]；

3）接著當(dāng)[x11←0]，此時的[x01x11]取值已經(jīng)確定為“00”，對應(yīng)顏色的權(quán)重值只能為22，該路徑的權(quán)重下界變成了[33-18+22=37]，上界仍然沒有改變，此時得到的權(quán)重范圍為[37，45]，此時的權(quán)重范圍與用戶輸入?yún)^(qū)間[30，35]沒有交集，所以沒有必要再對該條路徑遍歷下去，從而跳過了變量節(jié)點[x02x12x03]；

4）接著遍歷剩下的BDD并實時計算權(quán)重范圍，最終得到所有的結(jié)果。

該方法根據(jù)變量節(jié)點的取值，實時計算當(dāng)前路徑的權(quán)重范圍，并與用戶的輸入?yún)^(qū)間比較。一旦該路徑的權(quán)重范圍與用戶輸入?yún)^(qū)間沒有交集，便放棄對該路徑的繼續(xù)賦值，實現(xiàn)了對BDD的剪枝操作，加速了求解過程。

2.3 變量取值剪枝的區(qū)間查找方法

在上一節(jié)中，我們提出了編碼剪枝的方法，該方法根據(jù)變量節(jié)點的取值（“0”或者“1”），計算該條路徑的權(quán)重范圍，再與用戶輸入的范圍比較，從而判斷是否可以提前結(jié)束該路徑。但是對權(quán)重范圍的計算是有一定代價的，每經(jīng)過一個變量節(jié)點就需要計算一次權(quán)重的上屆或者下界，顯然消耗的時間與變量節(jié)點的數(shù)量呈指數(shù)關(guān)系，所以在該節(jié)中，我們提出了取值剪枝的區(qū)間方法：在BDD遍歷過程中，我們可以知道已經(jīng)遍歷過的變量節(jié)點的取值（“0”或者“1”），一旦某個變量取值可以確定，我們進行一次權(quán)重范圍的計算。

比如在T恤的例子中：

1）當(dāng)[x01←0]，此時的[x01x11]取值只能是“00”或者“01”，對應(yīng)顏色的權(quán)重值還不能確定，此時我們不進行權(quán)重范圍的計算；

2）當(dāng)[x11←1]，我們可以確定顏色的權(quán)重取值只能是22，所以該路徑的權(quán)重下界變成了[26-11+22=37]，而上界沒有改變，所以得到的權(quán)重范圍為[37，45]，從而可以判斷出該路徑可以提前結(jié)束；

3）接著遍歷剩下的BDD并實時計算權(quán)重范圍，最終得到所有的結(jié)果。

該方法根據(jù)變量的取值，計算當(dāng)前路徑的權(quán)重范圍。

3 實驗結(jié)果及分析

在我們的實驗中，我們選用了某汽車公司的真實數(shù)據(jù)集，數(shù)據(jù)集的特征如表4所示：

數(shù)據(jù)集中變量取值的權(quán)重值隨機賦值，根據(jù)權(quán)重值的初始范圍，我們將權(quán)重值區(qū)間從小到大分成了240組。根據(jù)240組權(quán)重區(qū)間，我們得到240組區(qū)間內(nèi)有效配置數(shù)量分布如圖2所示：

從圖中我們可以看出，第120組左右區(qū)間內(nèi)有效配置的數(shù)量最多，在第0組到第65組和第145組到第240組區(qū)間內(nèi)均沒有有效配置，整個分布圖呈正態(tài)分布。

根據(jù)這240組區(qū)間，我們分別采用三種區(qū)間查找方法進行計算求解，實驗結(jié)果如圖3所示：

圖中通過觀察三種區(qū)間查找方法，我們發(fā)現(xiàn)：

1）基本的區(qū)間查找方法因為對BDD進行全遍歷，沒有進行任何剪枝操作，所以消耗的時間基本一樣；

2）變量節(jié)點剪枝的區(qū)間查找方法隨著有效配置數(shù)量增多時，消耗的時間增長更快；

3）變量取值剪枝的區(qū)間查找方法在三種區(qū)間查找方法中表現(xiàn)最好，因為減少了權(quán)重范圍計算所消耗的時間；

4）變量節(jié)點剪枝的區(qū)間查找方法和變量取值的區(qū)間查找方法消耗的時間與區(qū)間內(nèi)有效配置的數(shù)量呈正相關(guān)，這也說明了解的數(shù)量越多，消耗的時間越多。

4 結(jié)論

本文通過引入變量權(quán)重，將變量取值的權(quán)重和產(chǎn)品配置聯(lián)系起來，并定義了變量權(quán)重的約束滿足問題，再通過BDD表示問題所有的解決方案。在對BDD遍歷求解時，提出了三種區(qū)間查找算法，通過實驗分析發(fā)現(xiàn)：1）三種剪枝方法中變量取值的剪枝方法效果最好；2）變量節(jié)點的剪枝方法和變量取值的剪枝方法隨著區(qū)間內(nèi)有效配置的數(shù)量變化，消耗時間也呈正相關(guān)。

參考文獻：

[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的多階段任務(wù)系統(tǒng)可靠度新算法[C]//國際可靠性、維修性、安全性會議. 2004.

[12] 呂關(guān)鋒， 蘇開樂， 林瀚， 等. 基于BDD的圖表示及其算法[J].中山大學(xué)學(xué)報：自然科學(xué)版，2006，45（1）.

【通聯(lián)編輯：唐一東】