IRP問題多Agent模型調度策略研究*

孫斌鋒 呂雄偉 李 軍

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

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

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

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

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

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

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

圖1 IRP問題多Agent模型調度框架

配送中心Agent根據客戶Agent提供的需求信息和自身的能力約束,生成客戶初始補貨計劃,并以時間順序將計劃細分,動態生成補貨任務Agent.

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

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

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

2 基于多Agent協商談判的調度研究

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

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

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

2.1 多Agent調度流程

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

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

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

步驟3 觸發集合中優先級最高的、且與其他正在招標的補貨任務Agent沒有資源沖突的補貨任務Agent,向系統內車輛Agent發出招標信息.

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

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

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

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

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

圖2 基于Agent協商談判的IRP問題調度流程

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

2.2 補貨任務Agent優先級

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

描述缺貨概率越高的補貨任務優先完成.

2.3 車輛Agent投標書的制作

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

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

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

2.4 沖突消解機制分析

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

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

3 算例分析

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

表1 補貨任務 Agent特征

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

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

表2 調度結果

4 結 束 語

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

[1]馬士華,林 勇,陳志祥.供應鏈管理[M],北京:機械工業出版社,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]王紅衛.建模與仿真[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]李 軍,郭耀煌.物流配送車輛優化調度理論與方法[M].北京:中國物資出版社,2001.

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