基于多智能體博弈的供應鏈配送網(wǎng)絡協(xié)調(diào)優(yōu)化模型研究

［摘 要］ 供應鏈配送網(wǎng)絡的流通效率是影響供應鏈績效的關(guān)鍵因素。在運輸能力有限的條件下，加快企業(yè)間的資源流通，促使配送網(wǎng)絡最大限度地流通順暢，對提高供應鏈整體績效有著十分重要的意義。本文以多智能體技術(shù)為基礎，利用博弈論的相關(guān)知識提出了供應鏈配送網(wǎng)絡優(yōu)化的協(xié)調(diào)模型，以求網(wǎng)絡運輸系統(tǒng)最終達到Nash均衡，從而較好地解決有限運輸能力條件下的供應鏈配送網(wǎng)絡的整體優(yōu)化問題，達到整個配送網(wǎng)絡的整體績效最優(yōu)。

［關(guān)鍵詞］ Agent；供應鏈配送網(wǎng)絡；博弈協(xié)調(diào)；Nash均衡

［中圖分類號］F270.7［文獻標識碼］A［文章編號］1673-0194（2009）01-0048-04

一、問題的提出

長期以來，供應鏈配送網(wǎng)絡的設計與優(yōu)化都是物流研究領域的重要課題。研究的內(nèi)容主要包括單一配送中心（Dｉｓｔｒｉｂｕｔｉｏｎ Cｅｎｔｅｒ，ＤＣ）選址方法和多個配送中心選址及分配方法兩個方面［１］。人們也提出了很多著名的方法和模型來求解這些問題［２］。但是卻很少考慮運輸過程中，在運輸能力有限的條件下如何最大限度地發(fā)揮運輸效率的問題。配送網(wǎng)絡的流通效率是影響供應鏈績效的關(guān)鍵因素，發(fā)揮供應鏈配送網(wǎng)絡最大流通效率解決方案的文獻較少, 這些研究的主要方法是通過建立物流的數(shù)學模型，運用運籌學和最優(yōu)控制理論來控制和優(yōu)化整個供應鏈配送網(wǎng)絡。但由于供應鏈系統(tǒng)的復雜性、物流模型的局限性等因素，導致供應鏈優(yōu)化控制的效果不理想。

具有自主性、移動性、協(xié)作性等特點的智能體(Agent)為供應鏈配送網(wǎng)絡這個復雜的大系統(tǒng)開辟了新的解決途徑，基于多智能體的供應鏈系統(tǒng)已成為一個研究熱點。區(qū)域協(xié)調(diào)是基于多智能體的供應鏈配送網(wǎng)絡協(xié)調(diào)的一個主要問題，它是指在運輸能力有限的條件下, 根據(jù)不同的運輸策略，均衡某幾個節(jié)點企業(yè)所組成的小區(qū)域的運輸量，從而提高整個供應鏈配送網(wǎng)絡的流通能力。它要求各小區(qū)域間的良好協(xié)作，而現(xiàn)實中的供應鏈配送網(wǎng)絡是由利益相對獨立的多個企業(yè)通過聯(lián)盟或合作關(guān)系組成的，為實現(xiàn)整個供應鏈配送網(wǎng)絡的協(xié)調(diào)必然會引起各小區(qū)域之間一定程度的沖突。因此，如何解決這些沖突是急需解決的重要問題。博弈論是研究理性的主體之間沖突及合作的理論，它研究主體的行為是如何相互影響的，主體是如何在相互作用中做出自己的行為選擇和行為決策的［３－５］。用博弈論的方法來分析問題，使問題的研究不僅局限于站在某個決策方的立場上找出針對其他方的對策，更重要的是在分析這些決策過程時能夠發(fā)現(xiàn)各方相互制約、相互作用的規(guī)律，從而導出合理的結(jié)果并用以解決相應的實際問題［６］。將供應鏈配送網(wǎng)絡上的各個倉庫、配送中心、中轉(zhuǎn)倉庫、分銷商、零售商等都看成是一個個的中轉(zhuǎn)站，而將原材料、裝配件、半成品、成品等都看成是運輸?shù)馁Y源，使供應鏈上的全部資源在配送網(wǎng)絡中最大效率地流通順暢。

二、Agent代理供應鏈配送網(wǎng)絡系統(tǒng)的運作機理

配送網(wǎng)絡是由多個單元構(gòu)成的，基本的單元包括倉庫、配送中心、中轉(zhuǎn)倉庫、分銷商、零售商等，這些單元可以稱為子系統(tǒng)［７］，這些子系統(tǒng)當中任何一個或幾個結(jié)合起來都可以構(gòu)成一個配送網(wǎng)絡。這些不同的單元共同構(gòu)成了配送網(wǎng)絡不同的具體內(nèi)容和功能。所有這些單元互相區(qū)別又互相聯(lián)系，它們既是不同的單元，彼此又互相聯(lián)系著。由它們的互相區(qū)別性，可以各自發(fā)揮自己的特長，由它們的互相聯(lián)系性，又可以起到互相協(xié)作、互相補充的效果。根據(jù)單元在配送網(wǎng)絡上所處的位置，可以把整個的供應鏈配送網(wǎng)絡分成一個個的區(qū)域，而每個區(qū)域又分成一個個的單元，在每個區(qū)域內(nèi)的單元都是交互的。因此，多Agent供應鏈配送網(wǎng)絡協(xié)調(diào)系統(tǒng)主要包括兩類Agent：由單個單元組成的單元Agent和由幾個單元所組成的區(qū)域Agent。

每個Agent主要包括3個層次［８］：通信層、協(xié)作層和控制層。通信層由通信模塊構(gòu)成，主要完成與其他Agent的信息交互；協(xié)作層由學習機、推理機、規(guī)則庫和知識庫4個部分組成，主要完成和其他Agent進行協(xié)調(diào)并生成最終決策的功能；控制層由控制模塊構(gòu)成，主要完成指導控制任務，并將控制任務的信息通過通信層傳遞給其他Agent。

所有的單元Agent和區(qū)域Agent都有著共同的全局目標——使得整個配送網(wǎng)絡績效最優(yōu)。而又有自己的局部目標——盡量使本單元利潤最大（或是本區(qū)域利潤最大）。單元Agent之間，單元 Agent與區(qū)域Agent之間，區(qū)域Agent之間是相互影響、相互作用的，因此，每個Agent的決策必然要受到另一些Agent策略選擇的影響，Agent之間必然會發(fā)生一定程度的沖突。下面應用博弈論的相關(guān)知識，建立基于Agent的供應鏈配送網(wǎng)絡系統(tǒng)運輸模型，實現(xiàn)博弈均衡，實現(xiàn)配送網(wǎng)絡的整體運輸效率最大，以提高整個供應鏈系統(tǒng)的績效。

三、供應鏈配送網(wǎng)絡系統(tǒng)協(xié)調(diào)優(yōu)化模型

1. 基本符號和定義

為建立供應鏈配送網(wǎng)絡運輸系統(tǒng)的協(xié)調(diào)模型，引入以下符號和定義：

（1）將每個單元都看成是中轉(zhuǎn)站，在某一時段內(nèi)要運出的資源數(shù)量是一定的，運輸能力也是一定的。用東、西、南、北4個方向表示資源要運去的4個其他單元。Qi（t）表示t時段內(nèi)等候在第i個單元的產(chǎn)品數(shù)量的向量。Qi（t）=

{Qi，E（t），Qi，S（t），Qi，W（t），Qi，N（t）}，Qi，E（t），Qi，S（t），Qi，W（t），Qi，N（t）分別表示t時段內(nèi)等候在i單元的運往東、南、西、北4個單元的資源數(shù)。

（2）Qi表示第i單元的資源數(shù)值的向量，Qi ={Qi，E，Qi，S，Qi，W，Qi，N}，Qi，E，Qi，S，Qi，W，Qi，N分別表示運往不同單元的等候資源的數(shù)量值，可以根據(jù)具體情況進行修改。

（3）A表示博弈協(xié)調(diào)中的行為和決策Agent，它的目的是通過選擇行動策略以最大化自己的效用水平，是所有Agent的集合。A={Agent1，Agent2，…，Agent n}。

（4）I表示每個Agent擁有的信息，包括其他Agent的特征和行動策略的信息。

（5）S表示Agent的所有可能的策略或行動的集合，一個Agent的全部可行策略稱為它的策略空間。每個Agent有一個純策略的有限集，為了表示有限運輸能力和運輸?shù)挠行蛐裕\輸策略S只取4種策略，S={東西直運、南北直運、東西雙左運、南北雙左運}。例如：東西直運表示在東西方向等待的資源運往東西兩個單元，那么運往南北兩個單元的資源要繼續(xù)等待。東西雙左運表示在東西方向等待的資源分別運向南北兩個單元，而南北方向的單元要繼續(xù)等待。在每個方向上運輸能力也是有限制的，用閾值表示，閾值就是每個方向上可運輸資源的最大量。閾值可根據(jù)具體情況進行修改。

（6）U表示Agent獲得的利益，是指在既定策略組合條件下Agent的得失情況，即在一個特定的組合下得到的效用水平。U為Qi（t）的收益函數(shù)。收益即是排隊的資源數(shù)。排隊的資源數(shù)越少，效用水平越高。

（7）Nash均衡：設有n個Agent的博弈描述為Ｇ＝｛Ａ，Ｓ，Ｕ｝，若此問題中戰(zhàn)略組合S*＝｛S1*，S2*，…，Sn*｝是一個納什均衡，則必須滿足Ui（Si*，S- i*）≥Ui（Si，S- i*），?坌si∈Si，式中：Si*表示第i個Agent選擇的戰(zhàn)略；S- i*表示除i之外的所有Agent的策略組成的向量；Ui表示第i個Agent的效用水平；Si表示第i個Agent的策略空間。

2. 協(xié)調(diào)模型［９］

一個Agent的決策會影響其他Agent的決策，同時，也受其他Agent決策的影響，因此，一個Agent在做決策時，應考慮其他Agent可能采取的戰(zhàn)略來決定自己的戰(zhàn)略。通過Agent間的相互通信，每一個Agent對其他Agent的特征（策略空間、效用函數(shù)等）有完全的了解，這決定了Agent間的協(xié)調(diào)過程是基于完全信息的博弈過程。一次博弈協(xié)調(diào)，定義為Ｇ＝｛Ａ，Ｉ，Ｓ，Ｕ｝，式中：Ａ＝｛Ａｇｅｎｔ１，Ａｇｅｎｔ２，…，Ａｇｅｎｔ ｎ｝，Ｉ表示每個Ａｇｅnt擁有的信息，Ｓ＝｛東西直運、南北直運、東西雙左運、南北雙左運｝，Ｕ為Qi（t）的收益函數(shù)。每個Agent依據(jù)它所擁有的信息I，在S中選擇合適的策略，通過不斷的協(xié)調(diào)，使它們的盈利達到納什均衡，即：

Ui（Si*，S- i*）≥Ui（Si，S- i*），?坌si∈Si。（式１）

整個協(xié)調(diào)過程分為3個層次：下層是單元Agent與其相鄰的單元Agent之間的協(xié)調(diào)；中間層是區(qū)域Agent與單元Agent之間的協(xié)調(diào)；上層是區(qū)域Agent與其相鄰的區(qū)域Agent之間的協(xié)調(diào)。如圖1所示。

3. 協(xié)調(diào)算法：Q2（T | s1，s1）

第一步，單元Agent的資源排隊數(shù)超過閾值，則向相鄰的單元Agent發(fā)出請求。

第二步，相鄰的單元Agent響應請求，并構(gòu)建如圖2所示的博弈樹（博弈樹分枝上的字母代表Agent的策略），根據(jù)式1尋找Nash均衡。

第三步，如果Nash均衡存在，則Agent的行動策略就是達成Nash均衡時的策略，每個Agent按照該策略控制單元策略，本次協(xié)調(diào)結(jié)束。如果沒有Nash均衡，則向該單元Agent所在的區(qū)域Agent發(fā)出請求。

第四步，區(qū)域Agent響應請求，對其所管轄的單元Agent進行博弈協(xié)調(diào)，尋求Nash均衡，如果Nash均衡不存在，則該區(qū)域Agent向相鄰的區(qū)域Agent發(fā)出請求。

第五步，相鄰的區(qū)域Agent響應請求，進行博弈協(xié)調(diào)，尋求Nash均衡，如果Nash均衡不存在，協(xié)調(diào)失敗，則每個Agent保持原先的策略不變。

四、計算案例

用圖3所示的一個簡單供應鏈配送網(wǎng)絡來說明上面的協(xié)調(diào)算法。Agent 1、Agent 2、Agent 3分別是3個單元Agent，它們由區(qū)域Agent管轄。為分析方便，每個Agent的策略集為S={東西直運、南北直運、東西雙左運、南北雙左運}。圖中的數(shù)字為t0時段內(nèi)各個單元向各個方向等待運送的資源數(shù)。

由于運輸能力有限，當?shù)却馁Y源數(shù)超過閾值時，單元 Agent間就要進行協(xié)調(diào)。在t0時段西口的排隊產(chǎn)品數(shù)

Q2，W（t0）=19，大于閾值QW（設QW=15），則Agent 2向Agent 1發(fā)出請求，Agent 1響應請求并進行博弈協(xié)調(diào)，博弈協(xié)調(diào)的收益即是排隊資源數(shù)，它是Agent 1、Agent 2博弈協(xié)調(diào)的目標和得失情況的體現(xiàn)，收益的多少取決于它們的策略組合。假設每個運貨周期，到達單元的每個方向的資源數(shù)為λ，可運往到各單元的資源數(shù)為μ，并假設μ =1.5λ，那么單元1和單元2在t1時段的排隊資源數(shù)是由在t0時刻采取的策略決定的。通過構(gòu)建博弈樹可以知道有以下的4種情況：

（1）Agent 1，Agent 2都選擇s1，兩個單元的資源數(shù)分別是15+2λ，13+3.5λ。

（２）Agent 1選擇s1，Agent 2選擇s2，兩個單元的資源數(shù)分別為15+2λ，25+2.5λ。

（3）Agent 1選擇s2，Agent 2選擇s1，兩個單元的資源數(shù)分別為16＋２．５λ，１３＋２λ。

（4）Agent 1，Agent 2都選擇s2，兩個單元的資源數(shù)分別為16+λ，25+λ。

當λ<12時，Agent 1，Agent 2都選擇s1，達到Nash均衡；當λ>12時，Agent 1，Agent 2都選擇s2，達到Nash均衡。Agent 1，Agent 2根據(jù)其相應的策略控制單元。以上介紹的是下層協(xié)調(diào)，如果單元3南口的資源排隊數(shù)Q3，S（t0）等于18而不是圖中所示的9，那么Q3，S（t0）大于閾值QS（設QS=15），則Agent 3向Agent 2發(fā)出請求，而此時Agent 2也向Agent 1發(fā)出請求，這種情況下Agent 3和Agent 2，Agent 2和Agent 1之間的Nash均衡很難達到。于是它們向區(qū)域Agent發(fā)出請求，區(qū)域Agent響應請求并進行博弈協(xié)調(diào)，開始中間層協(xié)調(diào)。

通過搜索博弈樹可知，當Agent 1選擇策略s2，Agent 2選擇策略s2，Agent 3選擇策略s2，達到Nash均衡。上層協(xié)調(diào)與下層協(xié)調(diào)類似。

通過區(qū)域Agent與區(qū)域Agent間的協(xié)調(diào)，可以使在各個單元等候的資源數(shù)達到最少，從而可以最大限度地使資源在整個配送網(wǎng)絡上流通順暢。

五、結(jié)束語

供應鏈配送網(wǎng)絡是配送過程中相互聯(lián)系的組織與設施的集合。它的最終目的是為了使最終顧客滿意，從而實現(xiàn)整個供應鏈的價值，并增強供應鏈的競爭能力。但是因為配送網(wǎng)絡中的元素是屬于不同實體所有的，這些不同實體之間都有著自己的利潤和風險，因此它們會從自己的利益出發(fā)，采取相應的措施使自己利潤最大化。一方做出的看來合理的決策有可能會對整個系統(tǒng)帶來很大的影響。因此,在進行配送網(wǎng)絡協(xié)調(diào)時就要把供應鏈的協(xié)調(diào)和整合機制作為指導思想，從而把供應鏈中的不同實體作為一個整體來進行協(xié)調(diào)。

用Agent技術(shù)來協(xié)調(diào)供應鏈配送網(wǎng)絡，就可以發(fā)揮系統(tǒng)協(xié)調(diào)整合的優(yōu)勢。每一個配送網(wǎng)絡都是—種有機結(jié)合體，而不是一個組合體。系統(tǒng)各個單元之間變成一種互相聯(lián)系、不可分割的關(guān)系，只有這樣才能互相協(xié)調(diào)力量。使系統(tǒng)的整體功能大于各個單元功能之和。只有這樣，供應鏈配送網(wǎng)絡的協(xié)調(diào)才能從整個系統(tǒng)的角度進行較為全盤的優(yōu)化。

主要參考文獻

［１］ 李延暉，馬士華，劉黎明. 基于時間約束的供應鏈配送系統(tǒng)隨機模型［Ｊ］. 預測，２００４（４）.

［２］ 日通綜合研究所. 物流手冊［Ｍ］. 吳潤濤，等，譯. 北京：中國物資出版社，１９８６：２２６－２４５.

［３］ Ｍａｒｔｉｎ Ｊ Ｏｓｂｏｒｎｅ，Ａｒｉｅｌ Ｒｕｂｉｎｓｔｅｉｎ. 博弈論教程［Ｍ］. 魏玉根，譯. 北京：中國社會科學出版社，２０００.

［４］ 施錫銓. 博弈論［Ｍ］. 上海：上海財經(jīng)大學出版社，２０００.

［５］ Ｆｅｉ Ｙｕｅ Ｗａｎｇ. Ａ Ｃｏｏｒｄｉｎａｔｉｏｎ Ｔｈｅｏｒｙ ｆｏｒ Ｉｎｔｅｌｌｉｇｅｎｔ Ｍａｃｈｉｎｅｓ［Ｄ］. Ｒｅｎｓｓｅｌａｅｒ Ｐｏｌｙｔｅｃｈｎｉｃ Ｉｎｓｔｉｔｕｔｅ，１９９０.

［６］ 陳進. 論區(qū)域博弈分析的方法研究［Ｊ］. 管理科學，１９９９（４）：６６-６８.

［７］ 任春玉，王曉博，李子群. 基于供應鏈的物流配送網(wǎng)絡模型研究［Ｊ］. 哈爾濱商業(yè)大學學報：自然科學版，２００６，22（4）.

［８］ 陳森發(fā). 復雜系統(tǒng)建模理論與方法［Ｍ］. 南京：東南大學出版社，２００５：４２－４３.

［９］ 李振龍，陳德望. 交通信號區(qū)域協(xié)調(diào)優(yōu)化的多智能體博弈模型［Ｊ］. 公路交通科技，２００４，２１（１）.