基于自適應分布式搜索的供應鏈協調優化算法

付立坤++喬佩利

摘 要：主要研究生產計劃下的多級供應鏈伙伴之間的協調優化問題.在多階段多項目約束生產批量問題模型的基礎上，考慮關聯約束及相關需求約束，對整個供應鏈的生產計劃問題利用拉格朗日松弛算法將其分解為多個子問題，并應用自適應分布式算法更新內部價格來協調各成員之間的決策，實現了多級供應鏈批量生產問題的協調優化，以及較好的保證各成員隱私，實驗分析證明了該策略在協調多級供應鏈生產計劃問題具有優越性，

關鍵詞：供應鏈協調：樹搜索；自適應分布式

DOI：1O.15938/j.jhust.2015.02.015

中圖分類號：TP399

文獻標志碼：A

文章編號：1007-2683（2015）02-0080-05

0 引 言

供應鏈管理（SCM）是在充分利用資源條件下，通過協調供應鏈中各成員間相互關系，以實現供應鏈整體的協調優化，供應鏈運作計劃在SCM主要在滿足客戶服務約束的前提下，負責協調供應鏈上資源的調配，物料的供需關系，以及優化供應鏈總成本.在以往關于供應鏈協調問題的研究中，較為常用的方法是層次式模式，假定由一個決策者掌握了全部的信息，并集中對協調問題進行決策，供應鏈中的信息具有私有性、實時性、非對稱性等特性，雖然層次式模式通常情況下，可高效獲得全局最優策略，但如果供應鏈有多個決策者，則無法使用層次式模式.文提出一種在不干涉自主決策實體的決策權和私有信息等條件下，又能夠有效的協調和優化整個供應鏈運作的模式，并用拉格朗日松弛技術和遺傳算法對多級多成員批量生產供應鏈問題進行協調優化，但其效率并不是最優的.文根據協調理論分析了供應鏈在物流、資源共享和時序間的依懶關系，并用拉格朗日松弛算法對模型進行協調優化.文運用拉格朗日松弛技術和啟發式算法協調優化的多廠生產計劃內部價格問題，有相對較好的優化性能，文基于協調企業和代理商之間供需關系，采用基于自適應分布式搜索算法來縮短整個供應鏈協調過程巾的所耗費的時間，每次提出的協調策略都是最優的.

在供應鏈中合作伙伴尋求競爭優勢，如在短時問內不斷滿足成員多樣化需求的能力，本研究著重從宏觀角度看，是一個典型的規劃和調度問題.在本研究中，將拉格朗日松弛算法和自適應分布式算法結合起來，以協調各成員子問題間的決策，

本研究中，先利用拉格朗日松弛算法簡化多廠供應鏈問題，并用自適應分布式搜索算法對其進行協調優化.首先，將多級供應鏈生產計劃問題模型用拉格朗日松弛算法分解為多個相對獨立成員的子問題，降低問題本身的復雜度，其次，提出該模型可行解的構造方法，將問題模型用樹形結構表示，并用自適應分布式搜索算法子問題進行協調優化，最后，對供應鏈整體進行協調優化.

1 多級供應鏈問題

1. 1 優化模型

如多級供應鏈生產計劃問題是指在某一計劃時問內，最終產品需求以及對應其產品結構的物料清單，并為最終產品加工或裝配部件的成員企業制定生產計劃，以達到最小化總成本的目的，其本質是為多級多產品受約束的批量問題（multi-level，multi-i-tem Capacitaled Lot-Sizing Problern，MLCLSP）.在本模型的計算過程中，假定產品所需提前周期為0.MLCLSP的主要約束包括：1）成員企業提供資源的數量約束和物料之問的順序約束；2）最大庫存能力約束；3）企業n的加工能力約束.符號定義如下： Prn為工廠n乍產的產品集合；Ok為生產產品k所需要的原料集合；D（n，k）為企業中所有下游工廠以工廠n的產品k為原料的集合；U（n，1）為企業中所有L游工廠為工廠n提供原料f的集合；為周期為t寸，下游工廠m向上游丁廠，n請求的產品k的產品數量；為周期為t時，上游工廠n向下游工廠m提供的產品k的產品數量；T為整個生命周期；hnk為工廠n對于產品k的單位庫存a費用；Snk為工廠n對于產品k的setup費用；Cn，k為工廠，n對于產品k的單位生產費用；dn，k為外部市場生產周期t時，對工廠n的產品k的需求量；trn，k為工廠n生產產品k的setup時問；tbn，k為工廠n生產單位產品k耗時；capn，1為工廠n在生產周期t的加工能力；/i：'ak為工廠n對于產品k的最大庫存能力；k.1β為產品k和產品2之間的物料清單關系；M為大的正數；Xn.k.為工廠n中產品k在生產周期t時的生乍產量為工廠n中產品k在生產周期t結束時對應的庫存數量；為為0-1變量，如果生產取值為1，則表示工廠n在生產周期f時，是生產產品k，反之亦然.

在模型中，式（1）為最小化供應鏈總成本；式（2）為庫存平衡約束；式（3）為產品的物料消單關系和T廠，z相對于其全部的上游工廠的原料需求；式（4）為工廠n的產品生產加工能力；式（5）為工廠在產品生產時，所需固定值的生產準備費用；式（6）為企業的產品庫存最大值；式（7）表示物料在上下游工廠的平衡約束條件，保證上下游工廠的供需平衡.

1.2 模型的拉格朗日分解

拉格朗日松弛算法通過拉格朗日乘子，將模型中復雜約束作為懲罰項整合到目標函數中，以降低問題的復雜度，拉格朗日松弛式（8），將拉朗格朗日乘子整合到目標函數中，可將原問題分解為一組成員獨立的子問題，能較好的保證成員信息的隱私.拉格朗日算子A表示對不符合產品上下游供應平衡約束的懲罰.本文稱其為產品的內部價格，其中示工廠的原料成本.在確定產品的內部價格后，式（9）中所有變量為工廠的本地變量，無需其它工廠信息.拉格朗日分解后模型MLCLSP為：

2 自適應分布式搜索算法

2.1 建立樹形結構

次梯度算法常用于求解拉格朗日松弛算法分解后的子問題.在本模型中，分解后的子問題為線性目標函數，如果采用次梯度對其求解，將產生振蕩，難于收斂.拉格朗日松弛技術對于成員企業之間的信息必須保證全部共享，對于本模型來說，并不適用.因此本文建立的協調結構和協調過程內嵌了一個基于自適應分布式可行化方法，該方法不需要集成模型和成員的全部信息，在可行化過程中，自適應算法淘汰可能會失敗的拉格朗日乘子，保證能求得問題的可行解.雖然增加了淘汰步驟，但在汁算過程中，子問題是并行計算，所耗費時間很短.為此，本文在拉格朗日松弛算法的基礎上，運用自適應分布式搜索算法，進行可行化求解.

圖l為多級供應鏈生產計劃問題的用樹形表示的結構圖.樹的根節點是協調中心，根節點制定產品的內部價格，以及協調各個工廠.A、B、C為3個工廠，作為根節點的子節點，3個工廠根據自己的本地信息，在獲得內部價格后，可得到各自工廠的生產計劃，并將確定各自向上游工廠提出的原料需求量，和向下游工廠提供的產品供給量，以及所得優化結果傳給根節點.10種產品作為工廠節點的子節點，生產計劃結果和其它信息通過枝進行傳遞，協調中心根據接收到的消息，更新內部價格，然后將其傳送給各個工廠.一直執行該步驟，直到得出最優決策，才停止運行.

2.2優化算法

自適應分布式搜索算法是一種全局性的搜索算法.許多研究者采用失敗學的方法處理樹在遍歷過程中違反約束導致失敗的情況，并分析樹在整個搜索中的其余部分，它具有對函數的形態無要求、搜索效率高、較好的全局搜索能力等優勢，并且可以處理混合參數的約束優化問題.自適應方法涉及系統的動態響應和調整特定實例的求解過程，能充分利用問題的約束條件.自適應算法的實現通常為：1）更新數據.每次遍歷一個新的節點，可能會引起相關節點的數據變化，及時更新數據，自適應判斷是否更新當前節點的數據，即對全局決策無影響，不更新除父節點和本身節點以外的節點.2）選擇節點，最優決策通過系統地遍歷樹的所有節點，根據節點的屬性值判斷獲得最優策略的可能性，可動態搜索概率最高的節點.每次通過比較該次得到的策略與上次最優策略，保存對比后較優策略對應的數據和路徑.當搜索到最優決策之后，便停止搜索.本步驟的所有操作在多節點上都是并行進行處理.3）網溯節點.根據約束條件或者搜索到葉子后，采用回溯方法，常用的回溯方法是SyncLDS（ synchronous limited dis-crepancy search）

對應本模型的具體步驟如下：

步驟1：初始化參數.如制定初始的產品內部價格、各個節點值、節點之間的關系變量、初始化掩格朗日乘子、最大迭代次數等，

步驟2：各獨立成員接收由協調中心所推送的拉格朗日乘子，在協調中心局部求解過程中，采用模糊次梯度算法進行更新.在協調過程中，協調中心采用自適應方法對優化結果進行判斷.為第一種，其他為.其中J為最優解的估計值.這里選擇步長α5滿足：

步驟3：每個獨立成員在拉格朗日乘子的基礎上，并行計算f值，并將所得結果傳送給協調中心.

步驟4：上游成員把下游成員的X品作為子問題模型中參數xkit的輸入值，然后更新值，，并向根節點（即協調中心）發送可行性和值fe，同時迭代次數n減1.

步驟5：如果迭代次數達到最大值，則轉向步驟6，否則，根據白適應方法，直到得到最優結果，才停止運行.

步驟6：輸出最優解后，停止運行.

3 實例與分析

采用文中標準MLCLSP問題中的ClassB集的非循環產品結構，最終產出4個最終產品，用該實例驗證白適應分布式搜索算法的如何求解多級供應鏈生產計劃問題.每級對應有一個成員（成員各有一種資源）的三級供應鏈中，擁有10種物料，成員之問的物流結構關系如圖2所示.利用文[3]中的方法，生產準備成本可分為：1）生產規模均衡、準備成本相對低；2）生產規模均衡、準備成本適中；3），生產規模均衡、生產準備成本高；4）下游準備成本較低和上游準備成本較高時；5）下游準備成本較高和上游準備成本較低時，其中p為變化的資源利用率，取值情況如表l所示.3種需求模式，通過不同的變異系數改變需求，變異系數（coefficients ofvariation）分別為0.1，0.4，0.7.共計75個問題，

平均每個時期的需求為最終產品的組裝結構中被設置為100.實例中，大的正數M=1000，物料k的庫存保存成本和生產準備成本參數如表2所示，

可利用Visual Studio 2005實現供應鏈運作汁劃協調算法（拉格朗日松弛技術與自適應分布式算法），對成員獨立的子問題的求解可用Liogo11軟件.拉格朗日乘子取值范圍介于-100到100之間，最大代數值為100.首先，將通過Lingol1軟件求解所得到最優解作為評價其它算法性能的一個基準，在拉格朗日松弛的基礎上，對比白適應分布式算法和文中的LRCASCP算法求解問題的結果，如表3所示.表中的偏差由兩種算法的解與基準對比可得，如圖3所示.

偏差為通過計算所得的最優結果和基準的之間的差：其中：t，為初始最優解；J*為整個問題計算所得的最優解.

如表2結果顯示，自適應分布式搜索算法和LRGASCP算法的優化性能基本不依賴于問題的結構，相對比自適應分布式算法的平均偏差更低些.

由表3和圖3可得，在75個問題中，應用LR—CASCP算法所得偏差為1.47%；自適應分布式搜索算法的情況，偏差在l%以內占問題總數的61%，問題偏差在5%以內占問題總數的97%.對比可知，自適應分布式搜索算法具有優越性和魯棒性.將自適應分布式搜索算法、LRGASCP算法同文中所提到的中心強制、一般協調和最大公平協調，以及文中的內部價格協調與基準比較后的偏差進行對比，結果如表4所示.顯而易見，在相同問題集的情況下，白適應分布式搜索算法的優化性能在這幾種協調機制中是最高的.

在求解問題的計算過程中，各成員獨立子問題的求解占據了大部分的運行時間，自適應分布式搜索算法具有分布式的特性，即成員子問題的決策計算過程都是并行進行計算，可減少子問題串行計算所消耗的時間，因此，該算法具有較高的運算效率.

4 結 論

本文針對多階段多項目批量供應鏈協調優化問題，在拉格朗日松弛算法的基礎上，運用白適應分布式搜索算法協調產品的內部價格協調策略，應用拉格朗日松弛技術分解簡化本文中的數學模型，可得到多個成員獨立的子問題，子問題的運算復雜性較低，其中，協調中心主要是對拉格朗日乘子進行更新，來達到對各個成員決策的協調優化目的，利用自適應分布式搜索算法來求解成員的子問題，可降低了求解問題的復雜度，并具有高效性.實驗結果表明，與其它多種協調機制對比，自適應分布式搜索算法具有優越性以及魯棒性.