物流服務供應鏈任務分配問題研究

王芝泉，劉晉浩

(1.東北林業大學工程技術學院，哈爾濱150040;2.北京林業大學工學院，北京100083)

目前，對供應鏈的定義有多種，其中比較權威的是我國在2001年發表的物流術語國家標準中的定義:“生產及流通過程中，涉及將產品和服務提供給最終用戶活動的上游與下游企業，所形成的網鏈結構”［1］。根據以上定義，供應鏈的內涵不僅包括提供產品 (產品供應鏈)，還包括提供服務 (服務供應鏈)。物流服務供應鏈是服務供應鏈中的一種，具有服務供應鏈的一般特征。田宇 (2003)認為其基本結構是:功能型物流服務提供商→物流服務集成商→制造、零售企業，其中功能型物流服務提供商是指傳統的功能型物流企業，如運輸企業、倉儲企業等，它們因提供的服務功能單一、標準，業務開展往往局限于某一地域，而被物流服務集成商在構建全國甚至全球服務網絡時吸納為供應商，它們利用自身物流能力，幫助物流服務集成商向客戶提供物流服務［2］。一般來說，物流服務集成商通常擁有眾多的功能型物流服務提供商。物流服務集成商在得到客戶需求后，根據客戶需求將物流服務訂單分配給各個服務提供商，由各個服務提供商提供相應的物流能力完成物流服務。這個過程就是物流服務供應鏈的任務分配過程。Suman和Patrick(2004)指出，任務分配決策是供應鏈戰略中最重要的決策之一［3］。面對多個物流服務提供商時，物流服務集成商如何進行需求訂單任務的合理分配是保證物流服務供應鏈長期穩定運作的關鍵。

1 物流服務供應鏈任務分配特點分析

物流服務供應鏈的任務分配就是由物流服務集成商將物流服務訂單分配給各個物流服務提供商，以使物流服務供應鏈的整體效益最優。物流服務供應鏈任務分配過程是一個不確定性環境下的序貫決策。具體來說，物流服務供應鏈任務分配具有以下特點:

(1)物流服務供應鏈任務分配是集中式運作。供應鏈中的成員相互合作，追求的物流供應鏈整體效益的最優。集中式運作意味著存在一個管理者或協調者，即物流服務集成商，該管理者擁有供應鏈中所有的決策信息，負責從物流服務供應鏈的整體效益最優角度制定決策，并將決策方案通知給供應鏈中的各個物流服務提供商。

(2)物流服務供應鏈任務分配環境具有不確定性。這種不確定性，一方面是由于外部環境的變化接到新訂單，另一方面是由于內部資源能力的限制，以前分配出去的任務執行失敗。面對每個新訂單的到來和分配完的訂單的執行失敗，物流服務集成商都需要不斷地進行任務分配和再分配。

(3)物流服務供應鏈的任務分配過程是一個序貫決策。序貫決策是指決策者 (物流服務集成商)在每個觀測點上 (出現新訂單或訂單執行失敗)都要進行決策 (任務分配或再分配)，決策時不知道下一個觀測點上的決策信息［4］。一般來講，序貫決策不僅需要當前決策的即時效應，還需要考慮當前決策對未來的影響，為將來決策創造機會。

(4)物流服務供應鏈任務分配具有馬爾可夫性。馬爾可夫性是指一個隨機過程未來發展的概率規律與觀察之前的歷史無關的性質，也就是說物流服務供應鏈任務分配決策只與物流服務提供商的最多可接受任務量以及目前已接受的任務量有關。

2 基于MDP的物流服務供應鏈任務分配模型

馬爾可夫決策過程MDP(Markov Decision Processes)是指決策者周期地或連續地觀察具有馬爾可夫性的隨機動態系統，序時地作決策。即根據每個時刻觀察到的狀態，從可用的行動集合中選用一個策略。系統下一步 (未來)的狀態是隨機的，決策者根據新觀察到的狀態，再作新的決策，依此反復地進行。馬爾可夫決策過程常用來解決動態規劃中的序貫決策，同時由于物流服務供應鏈任務分配過程的特點符合馬爾可夫決策過程的要求，因此物流服務供應鏈任務分配問題可用馬爾可夫決策過程建模求解。

2.1 前提假設

為了簡化這類問題的研究，做出如下假設:

假設1:任務空間的結構是明確的。各類任務都可以統一表達為分解任務，即用簡單任務及其相互依賴關系表示。被分配的任務都是已分解完成的任務，這些分解任務的類型有限。各類分解任務對應某一固定報酬。其中的簡單任務都只能由一個物流服務提供商單獨完成。

假設2:成批出現的任務服從相同的概率分布。由于物流服務供應鏈外部環境和內部成員資源能力的變化，隨時都可能出現需要分配的任務，且這些任務可以被分解，用簡單任務及其相互關系表達。這些分解后的簡單任務視為同批出現，它們具有相同的到達時間和到達概率。

假設3:物流服務提供商對它所分得任務的處理按先來先服務原則。由于物流服務提供商可能會在一批任務的分配時接受多個任務并且不等這批任務處理完畢，又可以接受新的任務。這樣就形成了各物流服務提供商的任務隊列，且各物流服務提供商按隊列中任務出現的先后序進行處理。

2.2 模型構建

基于前文對物流服務供應鏈任務分配特點的分析可知，物流服務供應鏈任務分配具有馬爾可夫性，即任務分配決策只與物流服務提供商的當前狀態有關。當前狀態包括被分配任務的特征和各物流提供商的任務執行能力兩項內容。每批出現的任務都可以表達為分解任務，即用簡單任務及其相互依賴關系表示。每個物流提供商具有不同的任務執行能力。任務執行能力由物流提供商的當前可接受的任務量和當前要執行的任務量來共同決定。狀態的轉移也包括被分配任務的特征轉移和各物流提供商的任務執行能力轉移。由于同批任務的具有相同概率分布，被分配任務特征的轉移概率與任務分配的策略無關，只取決于決策時刻該批任務的概率分布。由于各物流服務提供商的可接受的最大任務量在一定時間內是一定的，各物流提供商的任務執行能力轉移概率只與要執行的任務量和任務執行速度有關。每個物流服務提供商能接受的任務數受自身任務執行能力的限制。物流服務集成商在不同狀態下將出現的任務實時地分配給合適的物流服務提供商，以實現物流服務供應鏈績效最大化。完成每一項任務所獲得的收益，取決于完成任務所得的報酬與所消耗的費用。每一類型的任務都有固定的報酬。任何一項任務的完成都需要消耗一定的費用，包括執行費用和通信費用。執行費用是與物流服務提供商要執行的任務量有關的費用，它隨著需要執行的任務量的增加而增大;通信費用是因為簡單任務之間相互依賴物流服務提供商之間協商產生的費用，它取決于相互依賴任務的通信量和對應物流服務提供商之間的單位通信費用，而物流服務提供商之間的單位通信費用通常由物流服務供應鏈的結構決定，只有存在連接的兩個物流服務提供商能通信。

MDP馬爾可夫決策過程通常被表示為:{S，A(s)，p(s'/s，a)，r(s，a)，V}。其中:S 是狀態空間;A(s)是行動空間;p(s'/s，a)是狀態轉移概率函數;r(s，a)是報酬函數;V是準則函數［5］。物流服務供應鏈的運作具有長期性，考慮到資金的時間價值，因此應以在無限時段上完成任務獲得報酬的凈現值作為任務分配決策的準則。基于上述分析，物流服務供應鏈的任務分配模型構造如下:

(1)式的含義是最優任務分配策略是在完成任務所獲得收益的凈現值最大時取得。

(2)式的含義是任一簡單任務只由一個物流服務提供商完成。

(3)式的含義是物流服務提供商接受的任務量受其任務執行能力限制。

其中，β為折現因子;a*為最優任務分配策略;xikt=1表示t時刻第i項任務被分配給第k個物流服務提供商;xikt=0表示t時刻第i項任務沒有分配給第k個物流服務提供商;s表示狀態，s=b×w，b表示物流服務提供商的任務執行能力，w表示被分配任務的特點，記φk為第k個物流服務提供商的當前可接受任務量，lk為當前要執行的任務量，則t時刻第k個物流服務提供商的能力可表示為 bkt={＜ φk，lkt＞ /lkt=0，1，2，…，φk}，用 Vi表示簡單任務組成的集合，Ei為所有簡單任務構成的相互依賴關系集，則t時刻第i個物流服務提供商的任務執行能力可表示為Wit={Vit，Eit};r(s，a);為報酬函數，表示物流服務供應鏈采取任務分配策略a所獲得的收益，用R(Wt)表示完成任務Wt所獲得的報酬，C 1t表示執行費用，C2t表示通信費用，則rt(s，a)=R(Wt)-C1t-C2t，其中，qkt為t時刻第k個物流服務提供商要執行的作務量;j)fk，lxiktxilt，E(i，j)=1 表示第 i個任務和第 j個任務相互依賴，E(i，j)=0表示第i個任務和第j個任務相互不依賴，fk，l表示第k個物流服務提供商與第l個物流服務提供商之間的通信費用;pr(s'/s，a)為狀態轉移函數，可表示為pr(s'/s，a)，其中vk為各物流服務提供商在任意時段上的任務執行速度，h(vk):lk，t+1，表示下一決策時刻的要執行的任務量。

3 基于迭代算法的模型求解

從根本上講，基于MDP的物流服務供應鏈任務分配模型是一個動態規劃模型，可以利用求解動態規劃的迭代算法得到任務分配的最優策略。迭代算法的基本思想是:通過迭代逐步逼近最優準則值，隨著迭代次數的增加，所得的結果越來越接近最優準則值。從理論上講，迭代算法可進行無限次，但在現實應用中通常設定終止條件，選取有限步的計算結果，作為近似最優。具體步驟如下:

(1)選取初值:對?s∈S，令V0(s)=0，并給定一個充分小的正數ε。

(2)計算Vn+1(s)，Vn+1(s)∈ma{r(s，a)+β∑p(s'/s，a)Vn(s')}。

(4)對?s∈S，選取最優任務分配策略a*，并終止算法。最優任務分配策略a*就是使物流服務供應鏈完成任務所獲得報酬凈現值最大的任務分配策略，即滿足at(s)∈arg max{r(s，a)+β∑p(s'/s，a)Vn+1(s')}。

4 實驗仿真及結果分析

4.1 實驗設計

(1)實驗目的。比較三類任務分配策略對物流服務供應鏈績效的影響，檢驗基于MDP模型最優任務分配策略的有效性。三類策略是:隨機任務分配策略、即時最優任務分配策略和基于MDP模型的最優任務分配策略。隨機任務分配策略就是當任務出現時，從對應狀態下的任務分配行動空間中等可能地選取任務分配方案;即時最優策略是當前任務負載狀態下的最優任務分配策略，以指導系統按眼前最優策略行動;基于MDP的最優任務分配策略就是從系統存在的長遠意義出發，考慮一段時間上的總收益最優。

(2)實驗原理。一般認為，任務分配的較好策略是根據當時系統的狀態確定的，應當是即時最優策略;較差的策略是隨機任務分配策略，因為隨機策略不考慮系統完成任務的績效。因此，可以通過與即時最優策略和隨機策略的比較來判斷基于MDP模型的最優策略的有效性。

4.2 實驗結果

當狀態數較多，不便列舉出整個求解結果時，可采用仿真實驗方法證明任務分配MDP模型的有效性。仿真試驗進行1 000個時段，在相同的實驗條件下重復執行20次，每50個時段記錄一下從初始化狀態到當前為止系統執行任務的報酬凈現值。實驗結果如圖1所示，基于MDP的任務分配模型和即時最優策略明顯優于隨機策略;同時，還可發現基于MDP的任務分配策略也優于即時最優策略。

圖1 仿真時段Fig.1 Simulation Section

實驗結果表明，基于MDP的最優任務分配策略是有效的。這是因為基于MDP的最優任務分配策略不僅考慮了任務分配對即時所得報酬的影響，還考慮了任務分配對系統長遠報酬的影響。即時最優策略雖然在當前狀態下是最優的，但它可能會因為追求當前報酬的最優而導致下個時刻資源的不足，產生大的損失。

5 結論

物流服務集成商如何進行需求訂單任務的合理分配是保證物流服務供應鏈長期穩定運作的關鍵。由于新訂單不斷出現及舊訂單執行失敗，物流服務集成商要實時地進行任務分配和再分配。在實際操作中，物流服務供應鏈任務分配具有隨機性，任務分配過程是一個復雜的不確定環境下的動態決策過程。本文從分析物流服務供應鏈任務分配的特點出發，基于物流服務供應鏈任務分配具有集中運作性、決策過程的序時性及馬爾可夫性，提出用馬爾可夫決策過程構建物流服務供應鏈任務分配模型。最后給出了基于迭代算法的模型求解過程。由于求解過程中最優解的獲得可能要經過很多次的迭代，而物流服務供應鏈的任務分配應在任務出現時實時地進行分配，因此提出在模型實際求解中，可以在設定終止條件下，用迭代算法求出近似最優解。

［1］蔡云飛，鄒 飛.物流服務供應鏈及其構建［J］.企業改革與管理，2006，13(1):17-18.

［2］劉偉華，季建華，顧巧論.物流服務供應鏈兩級合作的質量監控與協調［J］.工業工程與管理，2007，11(3):47-52.

［3］劉偉華.物流服務供應鏈能力合作的協調研究［D］.上海:上海交通大學，2007.

［4］劉成鋼，寧宣熙.變動市場環境下的馬爾可夫決策［J］.南京航空航天大學學報，2002，34(5):505-508.

［5］李江洪，韓正之.馬爾可夫決策過程自適應決策的進展［J］.控制與決策，2001，16(1):7-11.

［6］楊 波，薛 偉.區域物流分流動力學仿真研究［J］.森林工程，2009，25(1):81-86.