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

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

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

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

[中圖分類號(hào)]C93； TP18[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]1673 - 0194（2012）22- 0059- 03

0引言

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

干擾管理（disruption management）[1]正是一種致力于實(shí)時(shí)處理這類問題的方法論，是近年來國際上管理科學(xué)、運(yùn)籌學(xué)和系統(tǒng)工程等領(lǐng)域備受關(guān)注的新的研究方向。干擾管理需要針對(duì)各種實(shí)際問題和擾動(dòng)的性質(zhì)，建立相應(yīng)的優(yōu)化模型和有效的求解算法，通過對(duì)初始方案進(jìn)行局部優(yōu)化調(diào)整，實(shí)時(shí)生成使系統(tǒng)擾動(dòng)最小的調(diào)整方案。這個(gè)調(diào)整方案不是針對(duì)擾動(dòng)發(fā)生后的狀態(tài)完全徹底地重新進(jìn)行建模和優(yōu)化，而是以此狀態(tài)為基礎(chǔ)，通過對(duì)初始方案進(jìn)行局部優(yōu)化調(diào)整，快速生成使系統(tǒng)擾動(dòng)最小的調(diào)整方案。

干擾管理自提出以來，已成功應(yīng)用到航空[2]、機(jī)器調(diào)度[3]、供應(yīng)鏈[4]等多個(gè)領(lǐng)域。在物流配送受擾延遲上也取得了一定的進(jìn)展[5-8]。以上學(xué)者為解決受擾延遲問題開辟了一條新的途徑，但是關(guān)于干擾事件的影響分析以及物流配送系統(tǒng)擾動(dòng)程度的評(píng)價(jià)方法，仍然沒有得到很好的解決。

因此，為解決干擾管理在物流配送領(lǐng)域存在的上述問題，本文首先確定了需要對(duì)原計(jì)劃進(jìn)行調(diào)整的條件并提出了物流配送系統(tǒng)擾動(dòng)程度的評(píng)價(jià)方法，然后建立了物流配送受擾延遲問題的干擾管理數(shù)學(xué)模型并給出了求解該模型的蟻群算法，最后通過實(shí)例驗(yàn)證了上述方法的有效性。

1系統(tǒng)擾動(dòng)的判定

延遲發(fā)生后，首先應(yīng)該判定系統(tǒng)是否發(fā)生了擾動(dòng)，即是否需要對(duì)初始方案進(jìn)行調(diào)整。如圖1所示，當(dāng)配送車輛完成客戶B的配送任務(wù)后發(fā)生了干擾事件，延遲時(shí)間為Δt，此時(shí)如果依然按照初始方案執(zhí)行配送任務(wù)，那么到達(dá)未完成的任意客戶I的時(shí)間為ti + Δt（ti是在沒有發(fā)生延遲的條件下，按初始方案到達(dá)客戶I的時(shí)間）。因此判定系統(tǒng)是否發(fā)生了擾動(dòng)，與ti + Δt是否在客戶I的時(shí)間窗內(nèi)有關(guān)，即

ti + Δt > LT系統(tǒng)發(fā)生了擾動(dòng)，需要對(duì)初始方案進(jìn)行調(diào)整otherwise系統(tǒng)沒有發(fā)生擾動(dòng)，不需要對(duì)初始方案進(jìn)行調(diào)整 （1）

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

干擾事件發(fā)生后，如果需要對(duì)原計(jì)劃進(jìn)行調(diào)整，那么如何評(píng)價(jià)物流配送系統(tǒng)的擾動(dòng)程度，使系統(tǒng)的擾動(dòng)最小，是干擾管理的核心問題。本節(jié)首先建立物流配送原計(jì)劃的數(shù)學(xué)模型，進(jìn)而在該模型的基礎(chǔ)上，研究物流配送受擾延遲問題的干擾管理數(shù)學(xué)模型。

2.1物流配送原計(jì)劃數(shù)學(xué)模型的構(gòu)建

對(duì)于本文所要解決的物流配送問題，具體界定如下：從某一物流配送中心用單臺(tái)配送車輛向多個(gè)客戶送貨，車輛為非滿載（裝載貨運(yùn)量小于車輛容量，一臺(tái)車可服務(wù)多個(gè)客戶），每個(gè)客戶的位置和需求量一定，客戶對(duì)送貨時(shí)間的要求滿足硬時(shí)間窗，要求合理安排車輛配送路徑和行車時(shí)間，使目標(biāo)函數(shù)得到最優(yōu)，即準(zhǔn)時(shí)到達(dá)和成本最低。

根據(jù)以上描述，建立物流配送原計(jì)劃的數(shù)學(xué)模型如下：

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

模型中各參數(shù)及變量的含義為：

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

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

cij： 車輛從vi到vj的運(yùn)輸成本；

qi： vi的需求量；

Q：車輛裝載能力；

[ETi，LTi]：vi的時(shí)間窗。其中，ETi是vi要求到貨時(shí)間段的始點(diǎn)，LTi是vi要求到貨時(shí)間段的終點(diǎn)；

ti：到達(dá)vi的時(shí)刻（即vi開始接受服務(wù)的時(shí)刻）；

si：車輛在vi的服務(wù)時(shí)間。

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

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

2.2.1基本假設(shè)

假設(shè)1：發(fā)生延遲的地點(diǎn)作為虛擬的配送中心，是處理干擾事件的起點(diǎn)，且剩余的任務(wù)只能由原配送車輛完成。

假設(shè)2：延遲后，客戶的時(shí)間敏感度已知。

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

假設(shè)3：物流配送系統(tǒng)擾動(dòng)程度的評(píng)價(jià)主要與交貨完成率、配送成本、客戶消費(fèi)總值以及貨物價(jià)值有關(guān)。

物流配送系統(tǒng)主要包括物流供應(yīng)商、客戶和配送貨物等組成部分，延遲發(fā)生后，對(duì)各部分的影響如下：

對(duì)物流供應(yīng)商來說，主要體現(xiàn)在兩方面：①企業(yè)信譽(yù)，這方面主要與交貨完成率有關(guān)，交貨完成率越低，則抱怨企業(yè)的用戶越多，對(duì)企業(yè)信譽(yù)造成的影響越大；②配送成本，這也是物流配送原計(jì)劃的主要目標(biāo)，干擾事件發(fā)生后，供應(yīng)商還是希望用盡量低的成本，完成配送任務(wù)。

對(duì)客戶來說，客戶的重要程度越高，干擾事件對(duì)客戶的影響越大。這主要體現(xiàn)在客戶與供應(yīng)商的業(yè)務(wù)往來上，客戶累計(jì)的消費(fèi)總值越大，該客戶的重要程度就越大。

對(duì)配送貨物來說，貨物的價(jià)值越大，對(duì)買賣雙方的影響越大。如果貨物不能按時(shí)送到，整個(gè)配送系統(tǒng)的擾動(dòng)也就越大。

2.2.2干擾管理模型的構(gòu)建

進(jìn)行上述假設(shè)后，由于決策者的偏好以及客觀情況不同，因此在評(píng)價(jià)物流配送系統(tǒng)擾動(dòng)程度時(shí)，對(duì)于各指標(biāo)的側(cè)重也就不同，即各指標(biāo)之間具有不同的優(yōu)先級(jí)，本文依據(jù)字典序多目標(biāo)規(guī)劃方法，建立物流配送受擾延遲問題的干擾管理數(shù)學(xué)模型如下：

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

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

模型中各參數(shù)及變量的含義為：

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

P1，P2，P3，P4：不同指標(biāo)的優(yōu)先級(jí)；

yi = 1，vi任務(wù)被完成；0，otherwise

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

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

ni：vi累計(jì)的消費(fèi)總值；

gi：vi此次配送的貨物價(jià)值；

其余參數(shù)及變量與前文相同。

上述模型中：（5）為目標(biāo)函數(shù)，表示系統(tǒng)的擾動(dòng)程度最小。其中f1為交貨完成率， f2為新計(jì)劃配送成本與原計(jì)劃配送成本的比值， f3為已完成客戶的消費(fèi)總值之和與所有客戶的消費(fèi)總值之和的比值， f4為已完成客戶的貨物價(jià)值之和與所有客戶的貨物價(jià)值之和的比值；（6）為對(duì)于可完成配送任務(wù)的客戶，必須滿足客戶要求的時(shí)間窗。

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

由于上述干擾管理的數(shù)學(xué)模型是NP-hard問題，求解起來非常困難，因此如何快速實(shí)時(shí)地處理干擾事件，獲得擾動(dòng)小、恢復(fù)快的抗干擾策略，是干擾管理的關(guān)鍵環(huán)節(jié)。由于蟻群算法具有正反饋、分布式計(jì)算以及貪婪的啟發(fā)式搜索等主要特點(diǎn)，為有效地求解復(fù)雜的優(yōu)化問題提供了可能，因此采用蟻群算法對(duì)上述模型進(jìn)行求解。主要實(shí)現(xiàn)步驟如下：

Step 1：初始化各控制參數(shù)；

Step 2：每一只螞蟻選擇下一個(gè)未走過節(jié)點(diǎn)；

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

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

3實(shí)驗(yàn)結(jié)果及分析

本節(jié)采用具體算例，驗(yàn)證上述方法的有效性。為計(jì)算方便，對(duì)客戶的信息進(jìn)行無量綱數(shù)據(jù)處理。

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

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

根據(jù)第1節(jié)系統(tǒng)擾動(dòng)的判定方法，當(dāng)Δt > 20時(shí)，即發(fā)生了干擾事件。因此對(duì)于情況①，即Δt = 10時(shí)，此時(shí)沒有發(fā)生干擾事件，按原計(jì)劃繼續(xù)配送即可。對(duì)于情況②，即Δt = 30時(shí)，此時(shí)發(fā)生了干擾事件，需要重新安排剩余客戶的配送計(jì)劃。

干擾事件發(fā)生后，采用以下兩種方法進(jìn)行處理：① re-scheduling的方法，目標(biāo)函數(shù)為準(zhǔn)時(shí)到達(dá)且成本最低，此時(shí)上述問題無可行解；② 本文的方法，以坐標(biāo)點(diǎn)（79，65）作為虛擬的配送中心，各指標(biāo)的優(yōu)先級(jí)從高到低的順序?yàn)椋航回浲瓿陕省⑴渌统杀?、客戶消費(fèi)總值以及貨物價(jià)值，客戶的配送路線相應(yīng)為3、10、9、8、12、11、7，此時(shí)客戶2、5無法配送，如圖3所示。該策略主要適用于以下情況：優(yōu)先完成客戶數(shù)量，其次配送成本最低。此外，可針對(duì)不同的條件，設(shè)定各評(píng)價(jià)指標(biāo)優(yōu)先級(jí)的順序，得出相應(yīng)的抗干擾策略，本文由于篇幅所限，不逐一進(jìn)行列舉。

4結(jié)論

（1） 本文以交貨完成率、配送成本、客戶消費(fèi)總值以及貨物價(jià)值等4個(gè)指標(biāo)來評(píng)價(jià)系統(tǒng)的擾動(dòng)程度，并進(jìn)一步提出系統(tǒng)擾動(dòng)程度的評(píng)價(jià)方法，可針對(duì)不同的條件，獲得擾動(dòng)小的抗干擾策略，使干擾帶來的副作用最小化，為求解物流配送受擾延遲這一難題提供新的手段。

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

主要參考文獻(xiàn)

[1] 胡祥培，丁秋雷，張漪，等. 干擾管理研究評(píng)述[J]. 管理科學(xué)，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ī)干擾管理研究[J]. 運(yùn)籌與管理，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] 胡祥培， 孫麗君， 王雅楠. 物流配送系統(tǒng)干擾管理模型研究[J]. 管理科學(xué)學(xué)報(bào)，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.