物流配送受擾延遲問題的干擾管理模型研究

[摘要] 物流配送過程中配送車輛遭遇干擾事件產生延遲后，如何快速形成使系統擾動最小的調整方案，是目前學術界和企業界面臨的難點。針對這一問題，基于干擾管理思想，首先對系統擾動進行判定，明晰對初始方案進行調整的條件；然后分析物流配送系統的組成要素，提出了物流配送系統擾動程度的評價方法；進而構建了物流配送受擾延遲問題的干擾管理數學模型，并給出了求解該模型的蟻群算法；最后通過一個具體實例，驗證了上述方法的有效性。

[關鍵詞] 管理工程； 物流配送； 干擾管理； 蟻群算法

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 22. 034

[中圖分類號]C93； TP18[文獻標識碼]A[文章編號]1673 - 0194（2012）22- 0059- 03

0引言

物流配送是現代物流管理的重要組成部分之一，直接涉及到企業的生存與發展。因此，如何為客戶提供滿意的配送服務是物流企業必須解決的關鍵問題。物流配送過程中，配送車輛經常會碰到大量的干擾事件，如車輛拋錨、道路堵塞、天氣變化等，從而導致延遲的發生，導致事先制訂好的計劃受到影響，甚至變得不可行。這就需要快速實時地生成新的調整方案，使得整個系統受到的擾動最小。因此，如何有效地處理干擾事件，已成為物流配送系統亟待解決的問題。

干擾管理（disruption management）[1]正是一種致力于實時處理這類問題的方法論，是近年來國際上管理科學、運籌學和系統工程等領域備受關注的新的研究方向。干擾管理需要針對各種實際問題和擾動的性質，建立相應的優化模型和有效的求解算法，通過對初始方案進行局部優化調整，實時生成使系統擾動最小的調整方案。這個調整方案不是針對擾動發生后的狀態完全徹底地重新進行建模和優化，而是以此狀態為基礎，通過對初始方案進行局部優化調整，快速生成使系統擾動最小的調整方案。

干擾管理自提出以來，已成功應用到航空[2]、機器調度[3]、供應鏈[4]等多個領域。在物流配送受擾延遲上也取得了一定的進展[5-8]。以上學者為解決受擾延遲問題開辟了一條新的途徑，但是關于干擾事件的影響分析以及物流配送系統擾動程度的評價方法，仍然沒有得到很好的解決。

因此，為解決干擾管理在物流配送領域存在的上述問題，本文首先確定了需要對原計劃進行調整的條件并提出了物流配送系統擾動程度的評價方法，然后建立了物流配送受擾延遲問題的干擾管理數學模型并給出了求解該模型的蟻群算法，最后通過實例驗證了上述方法的有效性。

1系統擾動的判定

延遲發生后，首先應該判定系統是否發生了擾動，即是否需要對初始方案進行調整。如圖1所示，當配送車輛完成客戶B的配送任務后發生了干擾事件，延遲時間為Δt，此時如果依然按照初始方案執行配送任務，那么到達未完成的任意客戶I的時間為ti + Δt（ti是在沒有發生延遲的條件下，按初始方案到達客戶I的時間）。因此判定系統是否發生了擾動，與ti + Δt是否在客戶I的時間窗內有關，即

ti + Δt > LT系統發生了擾動，需要對初始方案進行調整otherwise系統沒有發生擾動，不需要對初始方案進行調整 （1）

2物流配送受擾延遲問題的干擾管理模型與算法研究

干擾事件發生后，如果需要對原計劃進行調整，那么如何評價物流配送系統的擾動程度，使系統的擾動最小，是干擾管理的核心問題。本節首先建立物流配送原計劃的數學模型，進而在該模型的基礎上，研究物流配送受擾延遲問題的干擾管理數學模型。

2.1物流配送原計劃數學模型的構建

對于本文所要解決的物流配送問題，具體界定如下：從某一物流配送中心用單臺配送車輛向多個客戶送貨，車輛為非滿載（裝載貨運量小于車輛容量，一臺車可服務多個客戶），每個客戶的位置和需求量一定，客戶對送貨時間的要求滿足硬時間窗，要求合理安排車輛配送路徑和行車時間，使目標函數得到最優，即準時到達和成本最低。

根據以上描述，建立物流配送原計劃的數學模型如下：

ETi ≤ ti ≤ si ≤ LTi i = 1，2，…，n （4）

模型中各參數及變量的含義為：

G = （V，E）：無向圖，V表示頂點集，E表示邊集，頂點v1，v2，…，vn為客戶，v0為配送中心；

xij = 1，車輛由vi出發后開向vj0，otherwise；

cij： 車輛從vi到vj的運輸成本；

qi： vi的需求量；

Q：車輛裝載能力；

[ETi，LTi]：vi的時間窗。其中，ETi是vi要求到貨時間段的始點，LTi是vi要求到貨時間段的終點；

ti：到達vi的時刻（即vi開始接受服務的時刻）；

si：車輛在vi的服務時間。

上述模型中：（2）為目標函數，表示成本最低；（3）為車輛裝載的貨物總量小于車輛的限定容量；（4）為滿足客戶要求的時間窗。

2.2物流配送受擾延遲問題的干擾管理模型研究

2.2.1基本假設

假設1：發生延遲的地點作為虛擬的配送中心，是處理干擾事件的起點，且剩余的任務只能由原配送車輛完成。

假設2：延遲后，客戶的時間敏感度已知。

客戶的時間敏感度，即客戶對時間延遲的容忍程度，如非工作群體通常對時間較不敏感，可以容忍一定程度的延遲，即在時間窗以外到達對這類客戶沒有影響。由于客戶的時間敏感度與多種因素有關，因此本文不對客戶的時間敏感度進行研究，即在延遲發生后，客戶的時間敏感度已知。

假設3：物流配送系統擾動程度的評價主要與交貨完成率、配送成本、客戶消費總值以及貨物價值有關。

物流配送系統主要包括物流供應商、客戶和配送貨物等組成部分，延遲發生后，對各部分的影響如下：

對物流供應商來說，主要體現在兩方面：①企業信譽，這方面主要與交貨完成率有關，交貨完成率越低，則抱怨企業的用戶越多，對企業信譽造成的影響越大；②配送成本，這也是物流配送原計劃的主要目標，干擾事件發生后，供應商還是希望用盡量低的成本，完成配送任務。

對客戶來說，客戶的重要程度越高，干擾事件對客戶的影響越大。這主要體現在客戶與供應商的業務往來上，客戶累計的消費總值越大，該客戶的重要程度就越大。

對配送貨物來說，貨物的價值越大，對買賣雙方的影響越大。如果貨物不能按時送到，整個配送系統的擾動也就越大。

2.2.2干擾管理模型的構建

進行上述假設后，由于決策者的偏好以及客觀情況不同，因此在評價物流配送系統擾動程度時，對于各指標的側重也就不同，即各指標之間具有不同的優先級，本文依據字典序多目標規劃方法，建立物流配送受擾延遲問題的干擾管理數學模型如下：

min Lex = P1 ∶ （-f1）P2 ∶ f2P3 ∶ （-f3） P4 ∶ （-f4）（5）

ETi ≤ （ti+ si）yi ≤LTi （6）

模型中各參數及變量的含義為：

G = （V，E）：無向圖，V表示頂點集，E表示邊集，頂點v1，v2，…，vm為未完成的客戶，v0為虛擬的配送中心；

P1，P2，P3，P4：不同指標的優先級；

yi = 1，vi任務被完成；0，otherwise

xij = 1，車輛由vi出發后開向vj；0，otherwise

d0：按原路線行駛的配送成本；

ni：vi累計的消費總值；

gi：vi此次配送的貨物價值；

其余參數及變量與前文相同。

上述模型中：（5）為目標函數，表示系統的擾動程度最小。其中f1為交貨完成率， f2為新計劃配送成本與原計劃配送成本的比值， f3為已完成客戶的消費總值之和與所有客戶的消費總值之和的比值， f4為已完成客戶的貨物價值之和與所有客戶的貨物價值之和的比值；（6）為對于可完成配送任務的客戶，必須滿足客戶要求的時間窗。

2.3干擾管理模型的求解算法研究

由于上述干擾管理的數學模型是NP-hard問題，求解起來非常困難，因此如何快速實時地處理干擾事件，獲得擾動小、恢復快的抗干擾策略，是干擾管理的關鍵環節。由于蟻群算法具有正反饋、分布式計算以及貪婪的啟發式搜索等主要特點，為有效地求解復雜的優化問題提供了可能，因此采用蟻群算法對上述模型進行求解。主要實現步驟如下：

Step 1：初始化各控制參數；

Step 2：每一只螞蟻選擇下一個未走過節點；

Step 3：所以螞蟻搜索完成后，更新信息素；

Step 4：判斷是否滿足迭代終止條件，若是，則算法結束，輸出結果；否則，跳回Step 2，重復進行上述步驟。

3實驗結果及分析

本節采用具體算例，驗證上述方法的有效性。為計算方便，對客戶的信息進行無量綱數據處理。

隨機產生一組物流配送的數據，客戶信息如表1所示，配送中心的坐標為（40，50），開始配送的時間為0，返回配送中心的時間為240。配送車輛的載重量為5，行駛速度為1，客戶的服務時間忽略不計。根據上述條件，可以得出物流配送原計劃的配送路線，如圖2所示，其中客戶的配送路線為2、4、5、3、6、10、9、1、8、12、7、11，相應到達各客戶的時間ti為21、35、40、60、70、76、85、97、114、136、145、156，此時配送成本最低，為162。

假設配送車輛在由客戶5向客戶3行駛的途中，即在時間53、坐標（79，65）處發生延遲Δt，對延遲時間分以下兩種情況進行討論：即①Δt = 10；②Δt = 30。

根據第1節系統擾動的判定方法，當Δt > 20時，即發生了干擾事件。因此對于情況①，即Δt = 10時，此時沒有發生干擾事件，按原計劃繼續配送即可。對于情況②，即Δt = 30時，此時發生了干擾事件，需要重新安排剩余客戶的配送計劃。

干擾事件發生后，采用以下兩種方法進行處理：① re-scheduling的方法，目標函數為準時到達且成本最低，此時上述問題無可行解；② 本文的方法，以坐標點（79，65）作為虛擬的配送中心，各指標的優先級從高到低的順序為：交貨完成率、配送成本、客戶消費總值以及貨物價值，客戶的配送路線相應為3、10、9、8、12、11、7，此時客戶2、5無法配送，如圖3所示。該策略主要適用于以下情況：優先完成客戶數量，其次配送成本最低。此外，可針對不同的條件，設定各評價指標優先級的順序，得出相應的抗干擾策略，本文由于篇幅所限，不逐一進行列舉。

4結論

（1） 本文以交貨完成率、配送成本、客戶消費總值以及貨物價值等4個指標來評價系統的擾動程度，并進一步提出系統擾動程度的評價方法，可針對不同的條件，獲得擾動小的抗干擾策略，使干擾帶來的副作用最小化，為求解物流配送受擾延遲這一難題提供新的手段。

（2） 提出物流配送受擾延遲問題的干擾管理模型及其求解算法，可實時地獲得處理干擾事件的抗干擾策略，提高了物流配送系統的快速應變能力，為物流調度提供了科學化的新工具。

主要參考文獻

[1] 胡祥培，丁秋雷，張漪，等. 干擾管理研究評述[J]. 管理科學，2007， 20（2）：2-8.

[2] J Clausen，A Larsen，J Larsen，etc. Disruption Management in the Airline Industry-concepts，Models and Methods[J]. Computers & Operations Research，2010，37（5）：809-821.

[3] 王建軍，劉鋒，何平. 帶折扣因子的單機干擾管理研究[J]. 運籌與管理，2011，20（5）：39-45.

[4] X Qi，J F Bard，G Yu. Supply Chain Coordination with Demand Disruptions[J]. Omega，2004，32（4）：301-312.

[5] J Y Potvin，Y Xu，I Benyahia. Vehicle Routing and Scheduling with Dynamic Travel Times[J]. Computers & Operations Research，2006，33（4）：1129-1137.

[6] D Huisman，R Freling，A P M Wagelmans. A Robust Solution Approach to the Dynamic Vehicle Scheduling Problem[J]. Transportation Science，2004，38（4）：447-458.

[7] 胡祥培， 孫麗君， 王雅楠. 物流配送系統干擾管理模型研究[J]. 管理科學學報，2011，14（1）：50-60.

[8] Q Ding，X Hu，Y Wang. A model of Disruption Management for Solving Delivery Delay[C]. Advances in Intelligent Decision Technologies： Proceedings of the Second KES International Symposium IDT，Baltimore， USA，2010.