孫斌鋒 呂雄偉 李 軍

(湖南大學應用經(jīng)濟博士后流動站1) 長沙 410079) (西南交通大學經(jīng)濟管理學院2) 成都 610031)

在實施供應商管理庫存(vendorm anaged inventory,VM I)[1]策略下,零售商企業(yè)根據(jù)合同協(xié)議,將庫存業(yè)務外包給供應商完成,進而專注于核心業(yè)務的開發(fā),快速響應客戶的需求,提高企業(yè)競爭優(yōu)勢;同時供應商整合多家企業(yè)的庫存業(yè)務,綜合考慮庫存與運輸相互影響,合理安排車輛進行商品配送從而獲取規(guī)模效應,降低運作成本,實現(xiàn)供應鏈系統(tǒng)整體優(yōu)化.

VMI的實施是個復雜的系統(tǒng)工程,具體運作需要多方面的考慮.存貯路徑問題(inventory routing p rob lem,IRP)是VM I管理策略下的核心問題之一[2],在單個供應商對多個分散零售商庫存進行統(tǒng)一管理的模式下,系統(tǒng)考慮庫存控制與運輸計劃之間的協(xié)調(diào),制定使得供應商運輸成本與零售商庫存成本總和極小的補貨策略(包括車輛運輸計劃和零售商庫存策略).

最終的補貨策略可以認為是計劃期內(nèi)一組車輛路線的集合,它規(guī)定了不同補貨期內(nèi)車輛怎樣和以什么順序完成零售商補貨任務;同時它也被認為是系統(tǒng)內(nèi)各零售商庫存策略的集合,規(guī)定了各客戶補貨的時間和補貨的數(shù)量.因而,IRP問題需要解決的是補貨任務(包括時間與數(shù)量)的生成和分配,即為補貨任務在時間維度上安排合理的數(shù)量,以及空間維度上指定配送的順序.

在單個供應商和多個零售商構(gòu)成系統(tǒng)中,無論是作為客戶的零售商,還是起著配送中心作用的供應商,它們在地理位置上分散,組織結(jié)構(gòu)上分屬于不同的自治成員企業(yè),同時各個成員都具有自己核心的能力,因此為實現(xiàn)系統(tǒng)的總體目標,必須相互協(xié)作與協(xié)調(diào).盡管IRP問題也已被諸多學者從不同角度提出了求解方案[3],有鑒于各方案大多采用集中式模型為主的優(yōu)化技術[4],忽視系統(tǒng)成員決策的自治性和環(huán)境的動態(tài)性,本文設計了IRP問題的多Agent模型[5]整體框架,利用多Agent協(xié)商談判實現(xiàn)補貨策略的求解.該方法較之傳統(tǒng)集中式、非自主數(shù)學模型更強調(diào)功能實體間的交互作用.

1 IRP問題多Agent模型整體框架

IRP問題系統(tǒng)中包含多種配送資源和多樣的零售商需求,邏輯和控制關系十分復雜.基于多Agent的協(xié)商求解方法提供了一種動態(tài)靈活、快速響應市場的配送調(diào)度機制,通過對配送中心與零售商的聯(lián)合,實現(xiàn)系統(tǒng)的集成.本文建立了IRP問題的多Agent模型[6],通過Agent之間的合作以及多Agent系統(tǒng)協(xié)調(diào)來完成補貨策略的求解,并達到預先規(guī)定的系統(tǒng)目標.在多Agent模型中,包括四類Agent:配送中心 Agent、客戶 Agent、補貨任 務Agent和車輛Agent,如圖 1所示.

圖1 IRP問題多Agent模型調(diào)度框架

配送中心Agent根據(jù)客戶Agent提供的需求信息和自身的能力約束,生成客戶初始補貨計劃,并以時間順序?qū)⒂媱澕毞?動態(tài)生成補貨任務Agent.

客戶Agent負責預測客戶需求、實時監(jiān)控自身庫存水平;與車輛Agent交互,接收車輛補貨數(shù)據(jù),更新庫存信息;記錄周期內(nèi)客戶消耗情況,生成實際需求歷史數(shù)據(jù)庫,以及提交客戶需求信息.

補貨任務Agent作為客戶每天補貨任務的代理,在每個配送周期開始前由配送中心Agent根據(jù)需要動態(tài)生成;與車輛Agent通信,實現(xiàn)補貨任務的分配;監(jiān)控車輛Agent的運行情況,對任務的執(zhí)行狀況和車輛負載情況進行監(jiān)控.

車輛Agent與實際配送設備相對應,通過知識推理能力,與其他車輛Agent相互競爭補貨任務,主動爭取任務安排.車輛Agent維持自己的下述屬性:(1)可用性運輸能力以及車載能力約束;(2)使用成本;(3)補貨客戶集合等.

2 基于多Agent協(xié)商談判的調(diào)度研究

計算機技術的迅速發(fā)展為設計功能足夠強大的Agent提供了重要的技術支持,運用多Agent系統(tǒng)理論研究IRP問題,可以運用多個Agent通過協(xié)商談判共同完成補貨策略的制定,將IRP問題分解為許多個子過程分散處理,大大簡化了IRP問題的復雜性,提供系統(tǒng)的可維護性,降低生成客戶庫存策略和車輛調(diào)度計劃成本.

基于多A gent的IRP模型是個典型的合作性多Agent系統(tǒng),Agent協(xié)商談判的目的是動態(tài)生成補貨任務,并為補貨任務制定補貨順序、分配給適合的車輛完成配送,實現(xiàn)系統(tǒng)性能指標的最大化.在多Agent系統(tǒng)中,談判是任務分配的一種有效機制,參與談判的每一方都根據(jù)自身的利益做出決策,最終的補貨策略是多方共同的意向.本文采用合同網(wǎng)[7]進行管理與協(xié)調(diào)Agent,并在此基礎上實現(xiàn)Agent間的協(xié)商談判.

在IRP問題調(diào)度模型中,客戶Agent與配送中心Agent負責補貨計劃的生成與分解,并動態(tài)生成補貨任務Agent;車輛Agent負責補貨任務的調(diào)度.在這個過程Agent是相互協(xié)作的,他們必須要具有相應的調(diào)度流程及沖突消解策略.

2.1 多Agent調(diào)度流程

在基于多Agent的IRP問題模型中,其基本流程見圖2.從需求信息的發(fā)送,到補貨任務的生成,以及車輛競標分配,各Agent協(xié)同工作,實現(xiàn)補貨策略決策.對于補貨策略的規(guī)劃,基本流程描述如下.

步驟1 配送中心Agent根據(jù)客戶提供客戶的需求信息,以及配送中心倉儲能力等約束,為系統(tǒng)內(nèi)各客戶生成補貨計劃.補貨計劃是客戶在計劃期內(nèi)接受配送中心配送的數(shù)量與時間集.

步驟2 配送中心A gent與客戶Agent進行協(xié)商談判,根據(jù)配送中心能力約束及客戶需求限制,將補貨計劃分解成當前補貨期內(nèi)的補貨任務,動態(tài)生成補貨任務Agent,組成待調(diào)度的任務集合.

步驟3 觸發(fā)集合中優(yōu)先級最高的、且與其他正在招標的補貨任務Agent沒有資源沖突的補貨任務Agent,向系統(tǒng)內(nèi)車輛Agent發(fā)出招標信息.

步驟4 車輛Agent評價配送該任務的可行性,為其在本車服務客戶集合中指定合適的順序,并將車輛能力預定給該補貨Agent,確保不被其他Agent使用;然后將增加的相關成本,以及當前空閑的運載能力作為標書返回給招標的補貨任務Agent.

步驟5 在收到所有可行車輛Agent投標信息后,補貨任務給予啟發(fā)式原則(如總成本最低等)從競標對象中選擇合適的車輛Agent,發(fā)送確認信息;同時發(fā)送失敗信息給其余車輛Agent.

步驟6 收到確認信息的車輛Agent將預定能力和順序標記為占用;其他則將該預定信息消除位.所有的Agent繼續(xù)為下一次競標做準備.

步驟7 談判反復進行,直至當前補貨期內(nèi)補貨任務都被指定給車輛.車輛實體執(zhí)行配送計劃.

步驟8 重復上述活動,直至計劃期的結(jié)束.

圖2 基于Agent協(xié)商談判的IRP問題調(diào)度流程

從整體上看,圖2所表達的是Agent相互關系和調(diào)度工作的先后順序,但在實際的運作過程中,各相關A gent又是相互獨立并行工作的.

2.2 補貨任務Agent優(yōu)先級

在前文闡述的補貨策略決策流程中,配送中心Agent和客戶Agent負責補貨任務Agent的生成,并為之設定優(yōu)先級.A gent的自治、自主等特性,使得Agent具備的信息具有不完全性,難以從整體上把握問題的目標,因而其局部目標和系統(tǒng)整體目標存在著差異.IRP問題是以整體成本極小為主要目標的,可以通過在補貨任務優(yōu)先級的確定上體現(xiàn)出全局的目標約束.本文以表達式(1)的數(shù)值降序標識補貨任務的優(yōu)先級,數(shù)值越大優(yōu)先級越高.

描述缺貨概率越高的補貨任務優(yōu)先完成.

2.3 車輛Agent投標書的制作

在IRP問題的多Agent模型中,補貨任務是由車輛Agent自主競標決定起執(zhí)行的方式,因此投標書的制作是車輛獲取補貨任務的關鍵.如果考慮每個任務由單車負責配送,顯然會造成成本的極大浪費,也會限制車輛競爭任務的能力.這里車輛Agent決策能力采用節(jié)約/插入算法[8],為招標的補貨任務在已有的車輛服務客戶集合中選擇最適合的配送順序.

設R={1,2,…,n}為車輛Agent的服務客戶集,0表示配送中心,cij表示車輛從點i行使到點j的費用,則在進行投標之前,車輛Agent配送路線為 .由節(jié)約/插入算法,得到招標補貨任務k插入到配送路線中點i和點j的之間的費用節(jié)約值

在R∪{0}集合中選擇s(i,j)極小值,將該位置預留給補貨任務k,并做好標識.同時將將s(i,j)作為車輛Agent投標值和車輛空閑能力提交給招標Agent.

2.4 沖突消解機制分析

由單個供應商和多個零售商構(gòu)成系統(tǒng)中,由于知識不完備、不同的局部目標及有限的資源約束,成員企業(yè)間的沖突發(fā)生往往不可避免,如補貨任務的生成、車輛配送相同優(yōu)先級的補貨任務等.這時需要構(gòu)建相應的策略規(guī)避與消解沖突,提高IRP問題決策的求解效率.

沖突一般可以采用數(shù)學的方法和人工智能的方法進行消解[9].在構(gòu)建的IRP問題多Agent模型中,各Agent本身具有推理機,因此采用知識推理和協(xié)商的方法進行模型沖突的消解.

3 算例分析

設有8個客戶接受單個配送中心的補貨,某作業(yè)期內(nèi)生成的補貨任務A gent特征及通過表達式(1)得到各任務Agent的優(yōu)先級見表1.這些補貨或人物Agent由配送中心發(fā)出的容量為8 t的車輛Agent競爭完成,配送中心與各客戶的距離(單位:km)見文獻[8].

表1 補貨任務 Agent特征

算例的多Agent調(diào)度流程見表2.需要注意的是,第3輪中車輛1在競爭任務7時載重約束受限,只能給出最大投標值M(M表示極大整數(shù)值);在第4輪中補貨任務Agent1,Agent5處于相同優(yōu)先級,則此兩任務同時觸發(fā)招投標過程.

若不考慮庫存成本影響,僅就客戶任務進行補貨,問題簡化成為車輛路徑問題(VRP),此時對應的運輸方案為[8]:0-8-5-7-0,0-6-4-0,0-3-1-2-0.二者比較,后者對應的運輸成本更低,而前者為平衡庫存成本的影響,選擇了運輸成本略高的配送方案,進而實現(xiàn)系統(tǒng)總成本的優(yōu)化目標.

表2 調(diào)度結(jié)果

4 結(jié) 束 語

本文在分析VM I管理模式下的IRP問題研究內(nèi)容及特點的基礎上,運用分布式人工智能中的多 Agent方法構(gòu)建問題求解框架,通過多Agent之間的協(xié)商談判實現(xiàn)IRP問題補貨策略的制定,并對調(diào)度流程中的優(yōu)先級確定、標書的制作及沖突的消解作了簡要的闡述;與IRP問題其他集中式模型求解策略相比,本文側(cè)重于通過功能實體間交互作用研究問題求解,這也是集中式方法忽略的內(nèi)容.然而模型中的A gent間的通信、沖突消解的具體實現(xiàn)等的深入分析,將有助于IRP問題的進一步研究.

[1]馬士華,林 勇,陳志祥.供應鏈管理[M],北京:機械工業(yè)出版社,2000.

[2]K leyw egt A J,Nori V S.The stochastic inventory routing problem with direct deliveries[J].Transportation Science,2002,36(1):94-118.

[3]李 軍,劉建新.第三方存貯-路徑問題研究綜述[J],科學技術與工程,2004,4(4):325-328.

[4]王紅衛(wèi).建模與仿真[M].北京:科學出版社,2002.

[5]W ooldridge M J,Jennings N R.Agent theories,architectures and languages[C]//First International Conference on M u lti-Agent Systems.San Francisco,June 12-14,1995.

[6]孫斌鋒,呂雄偉,李 軍.基于MAS方法的存貯路徑問題研究[J].計算機應用,2006,26(2):276-278.

[7]Sm ith R G,Davis R.Frameworks for cooperation in distributed p rob lem solving[J].IEEE Transactions Engineering Management,1981,11(1):61-69.

[8]李 軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社,2001.

[9]黃必清.虛擬企業(yè)系統(tǒng)的理論與技術[M].北京:機械工業(yè)出版社,2004.