IRP問題多Agent模型調(diào)度策略研究*

孫斌鋒 呂雄偉 李 軍

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

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

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

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

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

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

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

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

配送中心Agent根據(jù)客戶Agent提供的需求信息和自身的能力約束,生成客戶初始補(bǔ)貨計(jì)劃,并以時(shí)間順序?qū)⒂?jì)劃細(xì)分,動(dòng)態(tài)生成補(bǔ)貨任務(wù)Agent.

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

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

車輛Agent與實(shí)際配送設(shè)備相對(duì)應(yīng),通過知識(shí)推理能力,與其他車輛Agent相互競(jìng)爭(zhēng)補(bǔ)貨任務(wù),主動(dòng)爭(zhēng)取任務(wù)安排.車輛Agent維持自己的下述屬性:(1)可用性運(yùn)輸能力以及車載能力約束;(2)使用成本;(3)補(bǔ)貨客戶集合等.

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

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

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

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

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

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

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

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

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

步驟4 車輛Agent評(píng)價(jià)配送該任務(wù)的可行性,為其在本車服務(wù)客戶集合中指定合適的順序,并將車輛能力預(yù)定給該補(bǔ)貨Agent,確保不被其他Agent使用;然后將增加的相關(guān)成本,以及當(dāng)前空閑的運(yùn)載能力作為標(biāo)書返回給招標(biāo)的補(bǔ)貨任務(wù)Agent.

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

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

步驟7 談判反復(fù)進(jìn)行,直至當(dāng)前補(bǔ)貨期內(nèi)補(bǔ)貨任務(wù)都被指定給車輛.車輛實(shí)體執(zhí)行配送計(jì)劃.

步驟8 重復(fù)上述活動(dòng),直至計(jì)劃期的結(jié)束.

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

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

2.2 補(bǔ)貨任務(wù)Agent優(yōu)先級(jí)

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

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

2.3 車輛Agent投標(biāo)書的制作

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

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

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

2.4 沖突消解機(jī)制分析

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

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

3 算例分析

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

表1 補(bǔ)貨任務(wù) Agent特征

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

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

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

4 結(jié) 束 語(yǔ)

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

[1]馬士華,林 勇,陳志祥.供應(yīng)鏈管理[M],北京:機(jī)械工業(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],科學(xué)技術(shù)與工程,2004,4(4):325-328.

[4]王紅衛(wèi).建模與仿真[M].北京:科學(xué)出版社,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].計(jì)算機(jī)應(yīng)用,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].北京:中國(guó)物資出版社,2001.

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