基于自適應(yīng)分布式搜索的供應(yīng)鏈協(xié)調(diào)優(yōu)化算法

付立坤++喬佩利

摘 要：主要研究生產(chǎn)計(jì)劃下的多級(jí)供應(yīng)鏈伙伴之間的協(xié)調(diào)優(yōu)化問(wèn)題.在多階段多項(xiàng)目約束生產(chǎn)批量問(wèn)題模型的基礎(chǔ)上，考慮關(guān)聯(lián)約束及相關(guān)需求約束，對(duì)整個(gè)供應(yīng)鏈的生產(chǎn)計(jì)劃問(wèn)題利用拉格朗日松弛算法將其分解為多個(gè)子問(wèn)題，并應(yīng)用自適應(yīng)分布式算法更新內(nèi)部?jī)r(jià)格來(lái)協(xié)調(diào)各成員之間的決策，實(shí)現(xiàn)了多級(jí)供應(yīng)鏈批量生產(chǎn)問(wèn)題的協(xié)調(diào)優(yōu)化，以及較好的保證各成員隱私，實(shí)驗(yàn)分析證明了該策略在協(xié)調(diào)多級(jí)供應(yīng)鏈生產(chǎn)計(jì)劃問(wèn)題具有優(yōu)越性，

關(guān)鍵詞：供應(yīng)鏈協(xié)調(diào)：樹搜索；自適應(yīng)分布式

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

中圖分類號(hào)：TP399

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1007-2683（2015）02-0080-05

0 引 言

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

在供應(yīng)鏈中合作伙伴尋求競(jìng)爭(zhēng)優(yōu)勢(shì)，如在短時(shí)問(wèn)內(nèi)不斷滿足成員多樣化需求的能力，本研究著重從宏觀角度看，是一個(gè)典型的規(guī)劃和調(diào)度問(wèn)題.在本研究中，將拉格朗日松弛算法和自適應(yīng)分布式算法結(jié)合起來(lái)，以協(xié)調(diào)各成員子問(wèn)題間的決策，

本研究中，先利用拉格朗日松弛算法簡(jiǎn)化多廠供應(yīng)鏈問(wèn)題，并用自適應(yīng)分布式搜索算法對(duì)其進(jìn)行協(xié)調(diào)優(yōu)化.首先，將多級(jí)供應(yīng)鏈生產(chǎn)計(jì)劃問(wèn)題模型用拉格朗日松弛算法分解為多個(gè)相對(duì)獨(dú)立成員的子問(wèn)題，降低問(wèn)題本身的復(fù)雜度，其次，提出該模型可行解的構(gòu)造方法，將問(wèn)題模型用樹形結(jié)構(gòu)表示，并用自適應(yīng)分布式搜索算法子問(wèn)題進(jìn)行協(xié)調(diào)優(yōu)化，最后，對(duì)供應(yīng)鏈整體進(jìn)行協(xié)調(diào)優(yōu)化.

1 多級(jí)供應(yīng)鏈問(wèn)題

1. 1 優(yōu)化模型

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

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

1.2 模型的拉格朗日分解

拉格朗日松弛算法通過(guò)拉格朗日乘子，將模型中復(fù)雜約束作為懲罰項(xiàng)整合到目標(biāo)函數(shù)中，以降低問(wèn)題的復(fù)雜度，拉格朗日松弛式（8），將拉朗格朗日乘子整合到目標(biāo)函數(shù)中，可將原問(wèn)題分解為一組成員獨(dú)立的子問(wèn)題，能較好的保證成員信息的隱私.拉格朗日算子A表示對(duì)不符合產(chǎn)品上下游供應(yīng)平衡約束的懲罰.本文稱其為產(chǎn)品的內(nèi)部?jī)r(jià)格，其中示工廠的原料成本.在確定產(chǎn)品的內(nèi)部?jī)r(jià)格后，式（9）中所有變量為工廠的本地變量，無(wú)需其它工廠信息.拉格朗日分解后模型MLCLSP為：

2 自適應(yīng)分布式搜索算法

2.1 建立樹形結(jié)構(gòu)

次梯度算法常用于求解拉格朗日松弛算法分解后的子問(wèn)題.在本模型中，分解后的子問(wèn)題為線性目標(biāo)函數(shù)，如果采用次梯度對(duì)其求解，將產(chǎn)生振蕩，難于收斂.拉格朗日松弛技術(shù)對(duì)于成員企業(yè)之間的信息必須保證全部共享，對(duì)于本模型來(lái)說(shuō)，并不適用.因此本文建立的協(xié)調(diào)結(jié)構(gòu)和協(xié)調(diào)過(guò)程內(nèi)嵌了一個(gè)基于自適應(yīng)分布式可行化方法，該方法不需要集成模型和成員的全部信息，在可行化過(guò)程中，自適應(yīng)算法淘汰可能會(huì)失敗的拉格朗日乘子，保證能求得問(wèn)題的可行解.雖然增加了淘汰步驟，但在汁算過(guò)程中，子問(wèn)題是并行計(jì)算，所耗費(fèi)時(shí)間很短.為此，本文在拉格朗日松弛算法的基礎(chǔ)上，運(yùn)用自適應(yīng)分布式搜索算法，進(jìn)行可行化求解.

圖l為多級(jí)供應(yīng)鏈生產(chǎn)計(jì)劃問(wèn)題的用樹形表示的結(jié)構(gòu)圖.樹的根節(jié)點(diǎn)是協(xié)調(diào)中心，根節(jié)點(diǎn)制定產(chǎn)品的內(nèi)部?jī)r(jià)格，以及協(xié)調(diào)各個(gè)工廠.A、B、C為3個(gè)工廠，作為根節(jié)點(diǎn)的子節(jié)點(diǎn)，3個(gè)工廠根據(jù)自己的本地信息，在獲得內(nèi)部?jī)r(jià)格后，可得到各自工廠的生產(chǎn)計(jì)劃，并將確定各自向上游工廠提出的原料需求量，和向下游工廠提供的產(chǎn)品供給量，以及所得優(yōu)化結(jié)果傳給根節(jié)點(diǎn).10種產(chǎn)品作為工廠節(jié)點(diǎn)的子節(jié)點(diǎn)，生產(chǎn)計(jì)劃結(jié)果和其它信息通過(guò)枝進(jìn)行傳遞，協(xié)調(diào)中心根據(jù)接收到的消息，更新內(nèi)部?jī)r(jià)格，然后將其傳送給各個(gè)工廠.一直執(zhí)行該步驟，直到得出最優(yōu)決策，才停止運(yùn)行.

2.2優(yōu)化算法

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

對(duì)應(yīng)本模型的具體步驟如下：

步驟1：初始化參數(shù).如制定初始的產(chǎn)品內(nèi)部?jī)r(jià)格、各個(gè)節(jié)點(diǎn)值、節(jié)點(diǎn)之間的關(guān)系變量、初始化掩格朗日乘子、最大迭代次數(shù)等，

步驟2：各獨(dú)立成員接收由協(xié)調(diào)中心所推送的拉格朗日乘子，在協(xié)調(diào)中心局部求解過(guò)程中，采用模糊次梯度算法進(jìn)行更新.在協(xié)調(diào)過(guò)程中，協(xié)調(diào)中心采用自適應(yīng)方法對(duì)優(yōu)化結(jié)果進(jìn)行判斷.為第一種，其他為.其中J為最優(yōu)解的估計(jì)值.這里選擇步長(zhǎng)α5滿足：

步驟3：每個(gè)獨(dú)立成員在拉格朗日乘子的基礎(chǔ)上，并行計(jì)算f值，并將所得結(jié)果傳送給協(xié)調(diào)中心.

步驟4：上游成員把下游成員的X品作為子問(wèn)題模型中參數(shù)xkit的輸入值，然后更新值，，并向根節(jié)點(diǎn)（即協(xié)調(diào)中心）發(fā)送可行性和值fe，同時(shí)迭代次數(shù)n減1.

步驟5：如果迭代次數(shù)達(dá)到最大值，則轉(zhuǎn)向步驟6，否則，根據(jù)白適應(yīng)方法，直到得到最優(yōu)結(jié)果，才停止運(yùn)行.

步驟6：輸出最優(yōu)解后，停止運(yùn)行.

3 實(shí)例與分析

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

平均每個(gè)時(shí)期的需求為最終產(chǎn)品的組裝結(jié)構(gòu)中被設(shè)置為100.實(shí)例中，大的正數(shù)M=1000，物料k的庫(kù)存保存成本和生產(chǎn)準(zhǔn)備成本參數(shù)如表2所示，

可利用Visual Studio 2005實(shí)現(xiàn)供應(yīng)鏈運(yùn)作汁劃協(xié)調(diào)算法（拉格朗日松弛技術(shù)與自適應(yīng)分布式算法），對(duì)成員獨(dú)立的子問(wèn)題的求解可用Liogo11軟件.拉格朗日乘子取值范圍介于-100到100之間，最大代數(shù)值為100.首先，將通過(guò)Lingol1軟件求解所得到最優(yōu)解作為評(píng)價(jià)其它算法性能的一個(gè)基準(zhǔn)，在拉格朗日松弛的基礎(chǔ)上，對(duì)比白適應(yīng)分布式算法和文中的LRCASCP算法求解問(wèn)題的結(jié)果，如表3所示.表中的偏差由兩種算法的解與基準(zhǔn)對(duì)比可得，如圖3所示.

偏差為通過(guò)計(jì)算所得的最優(yōu)結(jié)果和基準(zhǔn)的之間的差：其中：t，為初始最優(yōu)解；J*為整個(gè)問(wèn)題計(jì)算所得的最優(yōu)解.

如表2結(jié)果顯示，自適應(yīng)分布式搜索算法和LRGASCP算法的優(yōu)化性能基本不依賴于問(wèn)題的結(jié)構(gòu)，相對(duì)比自適應(yīng)分布式算法的平均偏差更低些.

由表3和圖3可得，在75個(gè)問(wèn)題中，應(yīng)用LR—CASCP算法所得偏差為1.47%；自適應(yīng)分布式搜索算法的情況，偏差在l%以內(nèi)占問(wèn)題總數(shù)的61%，問(wèn)題偏差在5%以內(nèi)占問(wèn)題總數(shù)的97%.對(duì)比可知，自適應(yīng)分布式搜索算法具有優(yōu)越性和魯棒性.將自適應(yīng)分布式搜索算法、LRGASCP算法同文中所提到的中心強(qiáng)制、一般協(xié)調(diào)和最大公平協(xié)調(diào)，以及文中的內(nèi)部?jī)r(jià)格協(xié)調(diào)與基準(zhǔn)比較后的偏差進(jìn)行對(duì)比，結(jié)果如表4所示.顯而易見(jiàn)，在相同問(wèn)題集的情況下，白適應(yīng)分布式搜索算法的優(yōu)化性能在這幾種協(xié)調(diào)機(jī)制中是最高的.

在求解問(wèn)題的計(jì)算過(guò)程中，各成員獨(dú)立子問(wèn)題的求解占據(jù)了大部分的運(yùn)行時(shí)間，自適應(yīng)分布式搜索算法具有分布式的特性，即成員子問(wèn)題的決策計(jì)算過(guò)程都是并行進(jìn)行計(jì)算，可減少子問(wèn)題串行計(jì)算所消耗的時(shí)間，因此，該算法具有較高的運(yùn)算效率.

4 結(jié) 論

本文針對(duì)多階段多項(xiàng)目批量供應(yīng)鏈協(xié)調(diào)優(yōu)化問(wèn)題，在拉格朗日松弛算法的基礎(chǔ)上，運(yùn)用白適應(yīng)分布式搜索算法協(xié)調(diào)產(chǎn)品的內(nèi)部?jī)r(jià)格協(xié)調(diào)策略，應(yīng)用拉格朗日松弛技術(shù)分解簡(jiǎn)化本文中的數(shù)學(xué)模型，可得到多個(gè)成員獨(dú)立的子問(wèn)題，子問(wèn)題的運(yùn)算復(fù)雜性較低，其中，協(xié)調(diào)中心主要是對(duì)拉格朗日乘子進(jìn)行更新，來(lái)達(dá)到對(duì)各個(gè)成員決策的協(xié)調(diào)優(yōu)化目的，利用自適應(yīng)分布式搜索算法來(lái)求解成員的子問(wèn)題，可降低了求解問(wèn)題的復(fù)雜度，并具有高效性.實(shí)驗(yàn)結(jié)果表明，與其它多種協(xié)調(diào)機(jī)制對(duì)比，自適應(yīng)分布式搜索算法具有優(yōu)越性以及魯棒性.