基于配送地點變化的物流干擾管理研究

卜心怡，劉超，錢軍

（杭州電子科技大學管理學院，浙江杭州310018）

基于配送地點變化的物流干擾管理研究

卜心怡，劉超，錢軍

（杭州電子科技大學管理學院，浙江杭州310018）

在物流配送過程中，通常會出現各種干擾事件影響配送車輛的正常運行，這時原配送計劃往往變得不可使用，文章針對客戶配送點變化這一干擾事件，運用干擾管理思想，從三個主體對干擾事件進行分析和度量，并以客戶不滿意度最小，成本最低，路徑偏離最少為目標，建立擾動恢復模型。設計了改進的遺傳算法對模型進行求解，并結合算例進行仿真實驗，與重調度法進行對比分析，驗證了干擾恢復模型的有效性。

干擾管理；車輛路徑問題；配送點變化；遺傳算法

一、引言

隨著電子商務及物流行業的迅速發展，物流運輸速度已經成為了影響物流總成本和服務質量的最重要環節。然而在實際的物流運輸過程中，往往會出現各種干擾事件，如出現新的客戶需求，客戶時間窗或者配送地點發生變化，車輛出現故障或者天氣原因等原因影響了正常配送。因此當在物流配送過程中，出現這些干擾事件時，如何有效地形成新的配送方案，使得配送成本及線路擾動最低成為了車輛路徑問題的熱點及難點問題。

目前關于車輛路徑問題的研究，國內外已經進行了比較全面的研究，Roberto Baldacci等[1]采用精確算法求解了兩級帶載重約束的車輛路徑問題。S.A.MirHassani等人[2]通過建立綠色車輛路徑問題模型，用引力算法作為求解搜索方式。得出最短的路徑并不一定是綠色車輛路徑模型的最優解。Ando N等人[3]建立以運輸成本最低，運輸時間和碳化物和氮化物排量小作為目標的車輛路徑模型，采用改進遺傳算法進行求解。Andreas Bortfeldt[4]等人通過變鄰域搜索算法求解了具有三維裝載約束、有時間窗約束、帶回程取貨車輛路徑問題。

張旭鳳[5]等人通過動態規劃方法求解了單配送中心、用戶信息已知、取貨送貨混合的車輛路徑問題。崔珊珊[6]等在分析井噴需求下，針對時間相應型顧客選取配送時間最短作為目標函數，對時間延遲型客戶選取成本最低作為目標函數，來設計不同求解模型，實現客戶滿意度與運輸成本的平衡。這些研究往往問題及限定條件是事先已知，而沒有考慮配送過程中可能會發生的干擾事件對配送計劃的影響。

一些學者基于配送過程中經常出現干擾事件這樣問題出發，提出基于干擾管理思想的車輛擾動恢復模型來解決此類問題。最初Hane等[7]將干擾管理模型用于解決航空機組調度問題。Yu[8]等人率先提出了一個關于干擾管理的數學模型。王征[9]等針對顧客時間窗變化這一干擾因素，以系統整體擾動最小化建立數學模型，采用變鄰域搜索算法求解顧客時間窗變化的多車場物流配送干擾管理問題。楊文超[10]等將行駛延遲和顧客更改配送時間這兩類時間干擾，采用了統一的方法進行處理，使得擾動恢復模型適用范圍變得更加廣泛。王旭坪[11]等研究了在配送過程中車輛故障這一干擾問題，采用增派、臨近及取消策略進行救援，并根據成本最小及系統擾動最小目標設計了擾動恢復方案。蔣麗等[12]同樣針對某一配送車輛發生故障這一問題，研究在配送中心無備車的情況下，通過其他在途車輛救援策略的干擾管理問題。胡祥培[13]基于客戶需求量變化引發的物流配送干擾問題，從客戶不滿意度、配送成本以及路徑偏離程度三個方面度量物流配送系統中的擾動，建立模型并采用融合多種鄰域函數的禁忌搜索算法實現模型的求解。蔣麗等[14]研究了針對帶回程取貨的運輸過程

中，因客戶需求變化引發的干擾管理問題。

以上研究主要針對時間因素擾動、車輛動力擾動和客戶需求擾動三類干擾事件進行分析的，同時有考慮了集貨與送貨相結合情況，但是基于客戶配送地點變化干擾事件進行研究的比較少。客戶配送點發生變化，可以看做是已有的某個配送點取消配送，同時又出現一個新的需求點，因此出現新客戶需要點和某客戶需求點取消可以和某客戶配送點發生變化進行結合研究。

為此，本文針對車輛在配送過程中出現客戶更改配送地點這一問題，基于干擾管理的思想，首先將新客戶進行分類，根據不同的客戶類型設置了不同的擾動恢復模型；并采用了遺傳算法進行求解，最后通過算例對算法在其問題上的處理能力及效率進行驗證。

二、問題描述及模型建立

本文將問題設定為有一個配送中心，多個客戶需求點，車輛對各個需求點進行配送，最終返回配送中心。車輛在運行過程中，車輛載重不超過其最大載重量，滿足顧客時間窗限制，配送中心根據限制條件生成車輛運輸成本最小的初始方案。

然而在現實的配送過程中，如果某客戶配送地點發生變化，會對初始方案產生了擾動，使的原計劃變得不可行，因此需要在初始方案的基礎上，快速生成新的費用最低及原計劃擾動最小的調整方案。

（一）初始配送方案數學模型

1.問題假設

通過對上述問題的設定，可以問題進行以下描述：

（1）車輛從配送中心出發，按照初始行駛計劃，分別對顧客進行配送，最后回到配送中心。配送中心有多輛車輛。

（2）每個客戶只允許訪問一次，且只能由一輛車輛進行服務。

（3）車輛有載重限制，不需要考慮體積限制，車輛載重不超過其最大載重量。

（4）每個客戶都有其服務的時間窗，車輛需盡量滿足顧客時間窗要求。

（5）客戶配送點發生變化，需求量不發生變化。

（6）貨物是同質商品，配送過程不會對商品質量產生影響。

2.參數及變量說明

n：客戶數量；

Dij：顧客節點i到j的距離；

ij=0，1，2，3，…，n，其中0代表配送中心；

Q：表示車輛的裝載容量；

qi：顧客i的貨物重量；

K：車輛數目；

Cij：從顧客節點i到顧客節點j的成本；

[Ei，Li]：表示客戶i的服務時間窗，Ei-δ是客戶要的取貨開始點，Li-δ是客戶要的取貨結束點；

Tik:車輛k到達顧客i的時間；

δ：超過顧客時間窗的最大容忍時間；

3.初始方案模型

根據上述描述，可以建立初始配送方案模型：

在這里初始模型沒有加入違反客戶時間窗懲罰，只考慮車輛的運輸成本，模型中式（1）為目標函數，表示運輸成本最低；式（2）為車輛k裝載的貨物總量不大于車輛的裝載能力；式（3）為每車輛都從配送中心出發；式（4）車輛服務顧客后返回配送中心；式（5）每個顧客只由一輛車輛進行服務；式（6）和式（7）表示變量之間關系；式（8）表示滿足顧客時間窗最大容忍要求，超過則客戶會拒絕接受。

（二）客戶配送點變化的物流干擾管理模型

1.問題描述

當某個客戶配送點發生變化后，配送中心沒有其他配送車輛，剩余未完成的任務依靠原配送車輛進行配送完成。同時假設發生干擾事件時，以各個配送車輛的位置為起始位置，原配送中心為終點。由于本文是以客戶點發生變化為干擾事件，因此當發生干擾時，未配送客戶點集合將會隨之發生變化，這時需要兩個客戶點集合加以區分。

2.參數設置與說明

m：發生干擾時，未配送客戶數量，未配送客戶點集合V（v1，…vm）。

C0：發生干擾時，初始配送計劃中，客戶點集合。

C：發生干擾時，調整計劃中，客戶點集合。C={c0，c1，…，cm，cm+1，…，cm+k}，其中c0是初始配送點，c1，…cm是未配送客戶點，cm+1…cm+k是發送干擾時的虛擬配送點出發點。

3.擾動度量

在配送過程中，當干擾事件發生后，基于干擾管理思想，需要在滿足新約束條件下重新設計一個系統擾動最小的配送方案。如何度量客戶配送點變化對系統造成的擾動

大小事建立干擾管理模型的關鍵。在配送過程中，主要存在三個主體，即客戶、物流運營商、配送員，因此當某個客戶配送地點發生變化后，主要影響的是客戶、物流運營商、配送員這三個主體。

（1）客戶：客戶在商品質量一定的，最先考慮的是能否按時收貨。當某個客戶的配送地點發生變化后，需要調整部分剩余客湖的配送順序，車輛的到達時間就勢必發生變化，使得某些客戶無法按時收到貨物，因此這部分受影響的客戶的滿意度就會受到影響。因此客戶干擾度量就首先要分析配送車輛偏離客戶時間窗的程度，目前物流配送方面的研究，主要有兩類時間窗：一種是硬時間窗，配送車輛必須按照客戶規定時間配送，否則客戶將放棄本次服務；另一種是軟時間窗，配送車輛如果無法按照客戶規定時間配送，則給予配送車輛一定懲罰。

圖1 客戶時間窗懲罰圖

在現實配送過程中，通常不會只是一種時間窗要求，往往需要滿足兩種時間窗要求，因此本文基于顧客混合時間窗要求進行研究。圖中當Ei≤Tik≤Li時，表示車輛k在客戶規定時間內到達，懲罰為0。當Ei－δ＜Tik＜Ei或者Li≤Tik≤Li+δ時表示違反了客戶時間要求，進而進行一定懲罰，同時值得注意的是，配送車輛如果提前到達客戶配送地點，可以選擇提前交貨，或者選擇等待客戶時間窗開啟，僅需要承擔等待成本即可，因此往往受到的懲罰會比較少。

因此每個客戶的不滿意度可以表示為：

其中Max是一個較大的正數；u1和a1代表早到的懲罰系數，u2和a2代表遲到的懲罰系數；當i客戶由k車輛服務時yik=1，當i客戶不是由k車輛服務時yik=1。

整個物流系統中客戶不滿意度的度量方法如下：

其中n為客戶數量，F1表示平均客戶不滿意度。

（2）物流運營商。物流運營商首先關心的是物流配送成本，在配送過程中，當某一客戶配送點發生變化時，剩余未配送地點集合將發生變化，因此配送路線隨之跟隨變化，這將直接影響配送成本。因此客戶配送地點變化對物流運營商運輸成本的影響程度可以表示為：

（3）配送員。配送員是物流配送任務的執行者，在配送過程中會對原配送路線相對熟悉，當發生擾動時間后，配送路線也將相應發生變化，勢必會影響配送員的工作情緒，同時也影響配送效率。

因此在設計配送路線時不僅要考慮配送成本，同時也要考慮路線的變化程度。設a為屬于調整后路線，而不在原路線的路段個數。b為屬于原路線，而不屬于調整后路線的路段個數。β+為原路線中增加一條路段的成本，β－的為原路徑中減少一條路段的成本。

因此客戶配送地點變化對物流配送員的影響程度可以表示為：

4.干擾管理模型

根據上節中干擾度量函數為依據，采用字典序的多目標規劃的方法，構建物流配送干擾管理模型：

干擾管理模型需要滿足初始配送模型的限制，其中式（12）為目標函數，表示調整方案與初始方案的偏離最小，即系統的擾動程度最小。W1，W2，W3為目標函數的權重系數。式（14）確保每輛車輛載重量不超過最大限度。式（15）每輛車輛從虛擬出發點出發。式（16）每輛車輛最終回到配送中心點。式（17）表示滿足客戶時間窗要求。

三、干擾管理模型的求解方法研究

本文所研究的是基于帶時間窗的車輛路徑問題（VRPTW），該問題已被證明為NP-hard。本文所構建的干擾模型必須考慮優化多個目標，求解過程復雜，加之實際物流調整計劃的實時性要求，精確算法難以勝任，因此選擇采用啟發式算法來求解物流干擾管理問題。遺傳算法具有很好的魯棒性、泛化能力、信息處理潛在的并行性、可擴展性等特點，使得廣泛應用于許多領域。由于遺傳算法的局部搜索能力差，導致單純的遺傳算法比較費時，并且在求解一些實際問題時，容易產生早熟收斂的問題，結合以上分析本文采用改進的遺傳算法來求解配送地點發生變化的物流干擾管理問題。

1.染色體的編碼方式。遺傳算法有多種編碼方式，對于車輛路徑問題主要有自然編碼方式和基于顧客的編碼

方式。本文采用自然編碼方式，對客戶集合C={c0，c1，…，cm，cm+1，…，cm+k}中的客戶進行自然編號，c0配送中心對應自然數0，cm+1到cm+k對應自然數1到m+k。

2.初始化種群。在完成染色體編碼后，首先要產生一個初始種群作為初始解，生成的初始解應該具有多樣性，防止出現局部最優。由于干擾管理目標函數中有一個目標是路徑偏離最低，因此將初始化種群中加入一定比例的初始最優路徑，使得求解結果更傾向于最初派送路線，并利于加快收斂速度。

3.適應度函數。度量個體適應度的函數稱為適應度函數，它是以數值的方式來描述個體優劣程度的指標，是遺傳算法中評價個體好壞的依據，個體染色體的適應度越高表示個體越優秀，反之越劣質。

適應度函數依據目標函數確定的用于區分群體中個體好壞的標準，本文中目標函數是最小問題，因此需要將目標函數進行相應轉換，本文的適應度函數：

其中Z為目標函數，c為目標函數函數界限的保守估計值。

4.選擇。遺傳算法中使用選擇算子對種群中的個體進行優勝劣汰操作，根據每個個體的適應的大小進行選擇，適應的較高的個體被遺傳到下一代群體中的概率比較大；反之亦然。為防止隨機操作造成誤差，本文采用選擇算子采用輪盤賭選擇與精英保留策略相互結合的方式，即防止隨機誤差，又加快收斂速度。

5.交叉。在遺傳算法中，通過交叉運算將兩個染色體交換部分基因，形成新的染色體，從而產生新的個體。交叉算子在遺傳算法中起著關鍵作用，是產生新個體的主要方法，很大程度決定了遺傳算法的搜索速度。本文采用兩點交叉（Two-point Crossover）方式進行交叉運算。主要分為兩步：（1）在相互配對的兩個個體編碼串中隨機設置兩個交叉點；（2）交換兩個個體在所設定的兩個交叉點之間的部分染色體。由于本文采用十進制編碼，兩點交叉會出現重復，因此需要加入去除重復這一步。

6.變異。變異是指將染色體編碼串的部分基因改換成其他基因，進而形成新個體的現象。在遺傳運算中，通過變異算子可以維持種群的多樣性，防止早熟，有效提高局部搜索能力。本文采用均勻變異方法來進行變異操作，均勻變異是指用符合某一范圍均勻分布的隨機數，以某一較小的概率替換某一個體染色體中各個基因上原有的基因值，具體操作過程如下：首先依次設定編碼體中的每個基因座的變異點，然后對每個變異點，以變異概率從基因取值范圍取隨機數來替代原有基因值，最后進行去重工作。

均勻變異操作可以在整個搜索空間內自由尋找，可以很好地確保種群的多樣性，防止過早陷入局部最優。

四、模型仿真及分析

（一）初始設置及初始配送路線

本文仿真實驗在matlab2014a版本上進行運行。為了驗證模型的有效性，本文借鑒文獻[12]中的方法，在100*100平面采用全隨機方式選取29個點，具體信息如表1所示。初始配送點為點1（50，50），配送點之間的距離為直線距離，假設配送車輛的載重量為10，車輛速度為每個單位時間行駛1單元距離，車輛在配送點的服務時間為0，從0時開始對這29個點進行配送。

表1 客戶點信息表

根據初始配送要求，求出初始配送路線如圖2所示。

車輛1配送路線：1-4-12-24-10-2-5-25-1（滿載率：92.0%）

車輛2配送路線：1-8-21-30-15-19-1（滿載率：99.0%）

車輛3配送路線：1-17-28-3-11-16-22-6-7-1（滿載率：82.0%）

車輛4配送路線：1-27-9-20-18-23-29-1（滿載率：97.0%）

車輛5配送路線：1-26-13-14-1（滿載率：73.0%）

圖2 初始配送路線圖

（二）干擾分析

假設在配送途中車輛3在行駛到配送點28時，客戶11的配送位置由原來的（15，44）變為（30，50），本文在不考慮其他車輛援助情況下，為完成配送任務，分別采用重調度法和本文方法重新設計配送路線，調整后配送路線如圖3所示。

通過兩種方法求解結果進行對比如表2所示。我們通過這兩種方法與初始配送路線進行對比得出結論：重調度法僅以最小配送成本為目標進行路線設計，雖然使得配送距離比本文方法少，但是具有較高的客戶不滿意度，拉低物流運營商整體服務水平；而本文方法在增加了少量配送成本的基礎上，大大降低了客戶不滿意度。從物流運營商長遠角度考慮，采用本文方法運輸成本可能會部分增加，但是可以很好地降低客戶不滿意度，增強客戶粘性，進而與客戶建立長期的穩定關系，有利于物流運營商長遠發展，現實持久盈利。

F252

A

1004-2768（2016）11-0019-04

2016-09-20

浙江省哲學社會科學規劃課題“面向協同網絡組織的新服務開發激勵模型與策略研究”（13NDJC038YB）；“管理科學與工程”省高校人文社科重點研究基地優秀碩士學位論文培育“基于配送地點變化的物流路線優化研究”（GK150203204004/016）

卜心怡（1961-），女，上海人，杭州電子科技大學管理學院教授，研究方向：系統分析和決策優化、服務管理、供應鏈管理；劉超（1990-），男，山東濰坊人，杭州電子科技大學管理學院碩士研究生，研究方向：物流系統分析與仿真、供應鏈管理；錢軍（1991-），男，安徽宣城人，杭州電子科技大學管理學院碩士研究生，研究方向：物流系統分析與仿真、供應鏈管理。