生鮮品多中心區域協作半開放式配送路徑研究

■ 何滿輝 曹騰 馬長城

遼寧工程技術大學工商管理學院 葫蘆島市 125000

0 引言

隨著第“四次工業革命”的開展，推動了消費轉型與”互聯網+“時代的到來，生鮮物流業進一步蓬勃發展，但生鮮配送仍有諸多問題亟待解決。生鮮品由于時效性和高品質要求，需要一套合理的配送方案。然而各配送部門各區域內獨自配送方案割裂了整體聯系，難以實現資源整合，造成資源浪費。同時，由于各配送部門信息技術水平的差異，難以實現信息共享，部門間很難建立合作關系。因此，要樹立一種基于信息技術應用，進行區域協同發展，滿足顧客要求、整合區域資源，以實現配送高效低成本的新物流發展理念[1-2]。

自車輛路徑問題(VRP)提出以來，諸多學者就將智能算法的發展成果應用于物流配送上，以尋求最優的配送路徑[3-6]。由于客戶需求量的逐年提升，單中心已不能滿足實際需求，對多中心車輛路徑問題（MDVRP）研究成為熱點。葛顯龍[7]等在城市供應鏈多方協同運作背景下，利用改進遺傳算法解決設計的模型并驗證了帶越貨配送方案的優越性。魯建廈[8]等將不同配送中心存在配送費用差異問題考慮在內，通過改進變鄰域搜索算法解決相應模型并得出合理的配送調度方案。Petr Stodola[9]等利用蟻群優化算法對MDVRP模型提出一種新的解決辦法，具有一定的參考價值。此外,在MDVRP基礎上,把時間窗（Time Windows）限制考慮在內,使模型更加實際化，建立了帶時間窗的多中心車輛路徑問題（MD‐VRTW）。劉璽[10]在物流協同網絡下，利用遺傳算法解決多車輛配送路徑最小成本方案選擇問題。

通過進一步研究，考慮車輛與車場關系，提出新的路徑模型，即開放式車輛路徑問題（OVRP）,該路徑區別于封閉式路徑，車輛完成任務后可直接駛離，不需要返回車場，若要返回，則需原路徑返回。龐燕[12]等在家具制造業將配送環節外包給第三方配送企業趨勢下，利用改進的禁忌搜索算法解決OVRP 模型，通過對比實驗得出第三方物流配送相對于自營物流能更加節約支出。針對OVRP，Z. Fu 等[13]設計禁忌搜索算法解決該難題，并取得理想的結果。為了解決OVRP，D.Sariklis等[14]提出了一種基于帶懲罰程序的最小生成樹的啟發式算法。

綜合上述研究，一方面，以往學者多數對封閉式和開放式路徑進行研究，而這兩種模式難以符合實際配送要求。MDVRP模型是封閉式的，難以資源融合。OVRP模型多是利用外包資源，難以形成配送標準化。另一方面，解決模型的算法都是僅針對自身改進，存在一定局限性。因此，結合MDVRP與OVRP特點，建立區域協作下帶時間窗的半開放式車輛路徑模型（HOMDVRPTW）,該模型的車輛路徑在完成任務后，不必返回原配送中心，而是依據情況選擇合適的車場返回，既改進VRP 模型，車輛不必一定返回原配送中心，減少資源不必要的浪費弊端。又改善OVRP 模型配送難以實現標準化和長期發展的不足。此外，在設計解決此模型算法時，對遺傳算法自身改進的同時，與變鄰域搜索算法相結合，取長補短，提高算法的性能。

HOMDVRTWP 模型一方面能夠反映新物流下區域協作的理念，另一方面在關注配送系統價值同時也關注各配送部門間的資源、信息的共享。隨著新物流理念的加深，對于生鮮配送業而言這種模式將是未來發展的趨勢。通過對該模式的研究進而可以為未來生鮮企業區域配送發展提出具有借鑒性的意見。

1 問題描述與前提假設

1.1 問題描述

區域協作下的生鮮配送模式，設定在企業配送部門之間接受新物流理念的背景下。問題描述為：A 生鮮企業服務多個區域，每區域內都有一個配送部門，根據歷史數據，多區域內建立N 個客戶需求點。每個配送部門有D 輛配送冷藏車；冷藏車從配送中心出發，向需求點配送生鮮產品，完成配送任務后，根據情況可以返回任意的配送中心。為提高企業服務水平，配送中心為顧客預先處理生鮮產品；利用信息設備，實時監控車輛位置和冷庫溫度并在生鮮產品上貼條形碼，便于信息及時反饋和數據在部門間實時共享；配送有時間窗限制，超過范圍不但會影響生鮮品質量還將受到一定懲罰同時滿意度會受到影響；基于上述描述，建立一個生鮮配送成本最小化的模型，同時將時間懲罰、滿意度指標考慮在內，盡量減少路徑距離，提高設備利用率，從而減少成本，提高滿意度。

1.2 前提假設

問題滿足以下條件假設：（1）各配送部門的設備規格參數一致，并且有足夠的設備能夠完成任務；（2）需求點以及配送中心地理位置已知，且坐標固定不變。（3）需求點的需求量不會超過冷藏車車載上限。（4）冷庫內外溫度穩定不變。（5）每個需求點由一車負責并且只接受一次服務。（6）冷藏車完成任務后離開需求點。（7）冷藏車從任意配送部門開始任務，完成顧客需求生鮮品配送后，考慮較優方案，選擇合理的路徑返回配送中心。（8）不考慮道路狀況，駕駛員以同一速度行駛車輛。

2 模型構建

2.1 符號解釋

建立模型的需要，設置了如下符號并予以解釋見表1：

表1 符號解釋

2.2 滿意度函數構建

顧客滿意度可以充分體現企業的服務質量，高滿意度能提高企業市場占有率。顧客滿意度與送達時間成一定的關系，在期望時間內顧客的滿意度極高，在可接受的時間范圍內隨時間的變化會產生改變，超過可接受范圍，顧客滿意度極低。顧客滿意度的函數可以用模糊隸屬函數如下所示：

2.3 成本分析

2.3.1 行駛成本

各種行駛損耗，與行駛里程成正相關，表示為（a）：

2.3.2 派遣成本

車輛管理費、駕駛員薪資以及信息設備啟動等，與車量成正相關，表示為（b）：

2.3.3 非對稱軟時間窗懲罰成本

鑒于生鮮產品特性，建立一種非對稱性軟時間窗。如果在指定時間到達，不會受到懲罰。若提前或者延遲送達會產生懲罰成本，延遲比提前的懲罰更高，如下所示：

時間懲罰成本，表示為（c）：

2.3.4 配送過程中的生鮮貨損成本

生鮮產品在配送過程中會發生一定程度的變質，變質的程度受商品本身的特性、時間影響造，生鮮貨損系數[14]如下所示：

生鮮貨損成本，表示為（d）：

2.3.5 配送過程中的能耗成本

配送過程中由于外部溫度對內部的熱傳遞和打開車門作業時熱空氣侵入導致制冷劑消耗能耗成本表示為：

（1）路途中能耗成本，如下所示：

（2）作業過程中的能耗成本，如下所示：

總能耗成本，表示為（e）：

2.3.6 信息和生鮮處理成本

數據錄入、分析和共享及對生鮮品進行預處理，與需求數量正相關：

（1）信息處理成本：

（2）生鮮產品處理成本：

處理總成本,表示為（f）：

2.4 模型建立

基于上述成本分析，模型建立如下：

2.5 模型約束條件

模型建立需加入一約束些條件，以符合論文提出模型特點和要求：

其中（g）生鮮配送最小成本模型；（h）不超過冷藏車裝載上限；（i）配送中心對需求點只配送一次；（j）禁止從配送中心出發不經過需求點而直接去配送中心；（k）服務完需求點后不能停留在原地；（l）從配送中心出發，滿足需求點后，可返回任一中心；（m）按照順序執行配送；（n）冷藏車d 將產品送到需求點j 時間;（o）平均滿意度必須大于等于百分之七十五：（p）(q)表示（0,1）變量。

3 研究方法設計

3.1 變鄰域自適應遺傳算法

遺傳算法（GA）的優越性在于對大型的復雜問題具有全局搜索最優解的能力,是求解復雜問題的優秀方法。然而，遺傳算法不可回避的問題是局部搜索能力和收斂性較差、易“早熟”。變鄰域搜索算法（VNS）是對鄰域結構進行改變來實現拓展搜索能力以求得較優解的算法。不可忽略的是，初始解的質量直接影響VNS求得最優解的質量。因此，基于遺傳算法與變鄰域搜索算法的優劣性，將二者進行結合，基于此基礎上，設計一種混合算法AGAVNS。該算法擁有全局搜索能力的同時，又避免計算陷入局部最優的困境。AGA 為VNS 奠定了高質量的初始解，而VNS 引導AGA 跳出局部最優，使所求目標解的質量得到一定的提高。

AGAVNS在解決HOMDVRP模型時設計如下：

3.1.1 編碼與解碼

（1）編碼：

算法采用多層編碼方式，保證配送問題解的全面性。

第一層編碼表示需求點的順序，編碼長度為節點數量N，

第二層編碼表示需求點由哪個配送中心發出的車輛進行服務，編碼長度為節點數量N，編碼為1～K，K 為配送中心數量

如，10需求點，2個配送中心

第一層

第二層

（2）解碼：

對應配送中心k，根據第二層編碼確定，配送中心k服務的需求點的編號，然后根據第一層編碼確定需求點的服務順序.

如，上例中：

中心1對應需求點和配送次序

中心2對應需求點及配送次序

根據需求點需求及車載上線在上述路徑中插入配送中心0

中心1對應需求點及配送次序

0為中心，根據上一個點到所有中心的距離就近選擇中心

上述路徑可解碼為

從中心1出發就近回中心1

從中心1出發就近回中心2

從中心1出發就近回中心2

根據該路徑，計算各目標函數值.

3.1 2 初始化種群

基本遺傳算法初始群的產生一般是隨機的，這樣會對算法的運算效率和解的質量產生一定的影響。本文利用掃描法生成初始種群。一、建立一個坐標系，以配送中心為原點，將配送中心與任一需求點相連，定義角度，設立需求點坐標。二、從小角度開始，建立一個群組，按逆時針方向把剩余需求量添加到種群中，添加的需求量不能超過冷藏車最大載重量。以此類推，建立新群組，直到所有需求點全部被覆蓋。三、這樣會得出一個較合理的線路。進行掃描后的初始種群對提高運算的效率和質量有一定的幫助。

3.1 3 適應度評價

通過將帶時間窗的多中心半開放式路徑問題進行數學模型化，其最終要求是求得配送的最優成本，即求目標函數的最小值。總配送成本為C，適應度值表示為f=1/c，由于配送成本與適應度值成反比，總成本越大適應度越低，個體適用度值越大，越能表明該個體越接近問題的可行解。

3.1 4 選擇

輪盤賭是基本遺傳算法選擇方法，適應度較大的個體被選中的概率也大，反之則小。輪盤賭方法，雖然保證了種群的多樣性，但是其隨機性可能導致大概率事件依舊可能不發生。因此本文采用輪盤賭與最佳個體保留法相結合方法。一方面保證適應度較高的個體不被破壞能遺傳到下一代。另一方面，又克服最佳個體充滿空間，陷入局部最優解的弊端。

3.1 5 交叉、變異

基本遺傳算法的交叉、變異概率是固定不變。這會對種群的多樣性和算法效率造成一定的影響。對于優良個體，應減少交叉變異概率使其能保留；對于不良個體，則加大交叉變異概率使其進化。同時，迭代初期種群需要較高交叉變異概率，快速尋求最優解；后期需要減少交叉變異概率，使找到最優解后快速收斂。因此固定取值不合理，需采用自適應交叉變異概率，按照上述思想進行動態調節。采用自適應交叉、變異概率如下所示：

其中pa交叉概率、pb變異概率、Pcmax交叉概率最大值、Pcmin交叉概率最小值、Pmmax變異概率最大值、Pmmin變異概率最小值、G迭代數最大值、g遺傳代數。

算法采用多層編碼方式，每一層編碼獨立進行交叉變異。

①交叉

第一層采用部分匹配。

選擇

交換

沖突檢測，以4-2-8映射關系為例。

第二層采用單點交叉。

為隨機生成交叉點產生新個體

②變異

第一層采用翻轉變異

對片段

翻轉為

變異后染色體為

第二層采用差值變異

對片段

操作，變異為2（這個2是配送中心數量）加1 減去

等于

3.1.6 變鄰域搜索

將遺傳算法求得的最優解作為變鄰域算法初始解。搜索方法為首先對每代個體的最優解進行變鄰域搜索，若在該鄰域不能找到一個比當前結果更優的解的時候，則跳入下一個鄰域繼續尋找。當在本鄰域搜尋到一個比現在解更優的解的同時，就跳回第一個鄰域重新開始搜索。直到所有鄰域都被搜索完畢。鄰域結構則采用交換操作，例如

操作前

操作后

3.2 算法流程

根據上述設計，算法流程如圖1所示：首先設置基本參數，利用掃描法生成初始化種群，計算適應度，接著運用輪盤賭和最佳個體保留相結合方法進行選擇，進行自適應交叉、變異，然后對每代最優解進行變鄰域搜索。當程序循環次數達到設定數量時，算法停止。

圖1 算法流程圖

4 實例分析

4.1 數據來源

以A 生鮮配送企業為例，它服務于三個區域，每個區域都各有一個配送部門，各部門有一個配送中心，為各自區域進行生鮮配送。根據報表，隨機選取一天的顧客日需求量，依照歷史數據，調查出顧客可接受和期望服務時間，并將需求點位置以1∶5000 縮小在坐標系中。配送中心用A、B、C表示，需求點用數字表示，如表2：

表2 配送中心和需求點數據

4.2 參數設置

采用載重量0.3 噸的冷藏車，冷藏車派遣成本500元，平均速度35 千米/小時，單位行駛成本5 元。采用軟時間窗，提前到達懲罰成本為60 元/小時，延遲到達懲罰成本為100 元/小時。冷藏車制冷劑單價0.4 元/千克，車廂內外溫差為10 攝氏度。車廂傳熱面積為12 平方米，常數取值為0.6，傳熱系數為0.3 千米/（千克*小時）。生鮮產品的價格5000元/噸，產品保質期為14小時，時間敏感調節因子為0.6，作業時間0.25 小時。生鮮和信息處理成本為0.2元/千克和0.4元/千克。

4.3 實驗結果分析

利用MATLAB 進行仿真實驗,算法參數設置為：NP=100,maxgen=1000,Pamax=0.8，Pamin=0.2，Pbmax=0.5，Pbmin=0.1，Kmax=20,Lmax=50.多次進行實驗，并隨機抽取8 次實驗數據，并選取最值，求均值，如表3-4：

由表3-4，可以得出，隨機選取8次計算結果中，平均成本11860.609 元，平均滿意度平均值87.7%.平均行駛里程653.574 千米。最優解為成本11652.346 元，平均滿意度為96.0%，行駛距離為636.420 千米.最劣解成本為11960.128，平均滿意度87.7%，行駛里程678.490 千米。最優解、最劣解與平均值的相對偏差分別為0.89%、0.42%，所需冷藏車均為7 輛，運行時間均在22 秒內。因此，混合算法的解能穩定收斂于較優解，且運行時間較快。

表3 區域協作下混合算法隨機選取8次計算結果

表4 區域協作下運算結果最優劣解與均值

為證明區域協作下半開放式路徑合理性，與A 生鮮企業目前方案對比，該方案利用遺傳算法求解最有路徑且已用于各區域各部門獨立配送，數據為：成本15957.372 元、里程877.73 千米、平均滿意度15.4%、冷藏輛8輛，配送方案如表5：

表5 各區域獨立配送方案

經過兩種模式的對比可知，區域協作下的半開放式配送成本平均值比各區域獨立封閉式配送成本下降了25.67%，現配送模式比原來的平均滿意度增長了72.30%。同時原里程數較現平均里程數降低了34.30%，車數從8 輛減少到7 輛。整體客戶平均滿意度超過80%。由此可以得出，區域協作下的半開放式配送路徑較各區域獨立配送，降低了成本，使企業盈利能力提高；行駛里程降低，提高了配送效率；保證了客戶滿意度同時使車輛的利用率提升，也考慮了信息共享和客戶服務，能促進整體生鮮配送的合作發展。因此，此模型是合理的、有效的。

根據以上數據，可知第三次實驗效果最佳，其方案如表6。同時利用基本遺傳算法對區域協作下的半開放式模型求解，得出數據：成本12301.338 元、里程740.96千米、平均滿意度81.9%、冷藏車7 輛?；旌纤惴ㄝ^遺傳算法成本下降了5.3%、里程下降了14.1%，平均滿意度提升14.1%。根據以上所有數據和算法對比迭代圖（圖2）可知，AGAVNS較基GA能夠跳出局部最優解，提高解的質量并且收斂性更穩定。因此AGAVNS 較GA 在解決該模型上具有一定的改進。

表6 區域協作下配送最優方案

圖2 算法迭代圖對比

5 結語和對策建議

本文以區域生鮮企業配送過程為研究對象，提出各配送部門各區域獨立配送造成嚴重資源浪費、高成本、低滿意度的弊端。在新物流理念下，設計了區域協作下的多中心半開放式配送模式，并建立考慮時間窗和保持一定客戶滿意度約束下的成本優化模型，應用AGAVNS多次求解。結合A 生鮮配送企業數據，模型通過與各區域獨立配送方案比對，以及AGAVNS 與GA 對比，驗證了模型合理性和算法改進性。研究成果可以有效降低生鮮企業配送的成本，降低客戶投訴率，加快運作效率，為促進區域生鮮物流的協作發展提供一定參考。

同時，基于研究成果，對未來生鮮配送企業進一步發展提出對策建議：

5.1 打破傳統思維，引入“新物流”發展理念

一方面，與傳統物流配送標準化和自動化相結合，提高生鮮品智慧配送的水平。另一方面，在滿足客戶對生鮮品定制化服務的同時，最大限度利用企業潛力，從而打造一個高柔性，高敏捷性的綜合生鮮配送企業。

5.2 將科技發展成果融入生鮮品配送整個環節

對生鮮品配送企業進行智慧升級，逐步提升企業信息化水平。將智能算法、大數據、物聯網、人工智能等先進技術融入到企業生鮮配送的各個環節，以建立一套智能化的物流管理系統。

5.3 建立區域生鮮企業物流戰略聯盟，促成物流企業間協同發展

加強區域范圍內整個物流商務系統的融合，以供應鏈系統為核心，要求各個部門或企業間的商流、物流、信息流有效結合，形成相互信任、共享資源的物流聯盟。做到生鮮品配送全過程的科研、開發、運作、分析等高度協作，在獲得互利互惠的同時，促進區域生鮮配送的整體發展。