基于成熟度的水蜜桃配送路徑優化研究*

□ 韋文鑫，劉新君,楊 洋,卞 貝,江億平

(南京農業大學 工學院，江蘇 南京 210000)

1 引言

伴隨著經濟的發展和人們生活水平的提高，冷鏈物流得到較快發展。由于我國生鮮冷鏈物流起步較晚，基礎薄弱，生鮮產品在運輸過程中損耗嚴重。據統計，我國現在每年約有4億噸生鮮農產品進入流通領域,其中，果蔬類冷鏈流通率達到10%,冷藏運輸率達到15%，其中的損耗率高達30%，損耗值每年在1000億元以上[1]。水蜜桃作為生鮮配送中最重要的農林作物，因其成熟階段正值高溫季節，加上自身保質期限短，易破損腐爛等特殊的生理屬性[2]，如何合理安排配送車輛行駛路徑將水蜜桃高效快捷地配送到客戶手中，并且同時可以滿足客戶的成熟度需求成為當下需要解決的問題。

針對帶時間窗的車輛路徑問題(VRPTW),國內外學者做了大量的研究。謝秉磊等將貨運量約束和時間窗約束轉化為目標約束,設計出了基于自然數編碼的可同時處理軟、硬時間窗約束的遺傳算法[3]。Sally Kassem等研究了閉環物流網絡優化中同時取貨和配送的車輛路徑問題，提出了一種混合整數規劃模型來表達所考慮的問題，并開發了一種啟發式求解方法用作模擬退火過程的初始解決方案[4]。何小鋒等針對蟻群算法在求解VRPTW問題時易陷入局部最優和收斂速度慢的問題，提出一種求解VRPTW的量子蟻群算法(QACA)，有效避免了算法陷入局部最優[5]。孫明明等充分考慮冷鏈物流配送過程中時間、溫度、貨損因素，通過節約成本法分析求解達到降低配送成本、滿足客戶需求時間的雙重要求[6]。Junlong Zhang等提出了一種新的隨機規劃模型，開發了一種結合了路由約簡機制的迭代禁忌搜索啟發式算法求解在旅行和服務時間不確定的情況下的具有軟時間窗的隨機車輛路徑問題模型[7]。

然而，現在對于水蜜桃采摘后的成熟度變化做出預測和評估的研究卻很少，把水蜜桃的采摘后自我成熟的過程和冷鏈運輸過程進行聯合優化的研究更是少有學者涉及。因此，本文的創新點體現在：以數學模型定量研究水蜜桃采摘后成熟度的動態變化，從而將客戶對水蜜桃成熟度的要求轉換為精確的配送時間窗的約束，再運用遺傳算法以總配送距離最短為目標求解建立的水蜜桃配送的聯合優化模型，不僅實現了對水蜜桃運輸過程中成熟度的預測和監控，減少浪費損失，還大大提高了客戶滿意度和冷鏈物流企業的競爭力，有效地驅動了我國生鮮配送市場未來的發展。

2 水蜜桃成熟度模型

2.1 實驗材料和各項指標分析

選取“湖景蜜露”水蜜桃品種作為試材，參照成熟度劃分標準，選擇無傷害、大小均勻的果實。在20℃恒溫儲藏的條件下測定果實的硬度(Y1)、出汁率(Y2)、可溶性固形物(Y3)和失重率(Y4)四項指標。得到各項指標隨時間增加的動態變化情況(圖1)，并通過SPSS軟件對各項指標進行曲線估計，擬合出四項指標的回歸方程(表1)，且四條回歸曲線的決定系數R2均大于0.8，擬合效果很好。

圖1 水蜜桃成熟度各項評價指標隨時間增加(成熟度增加)的變化情況

表1 水蜜桃成熟度各項評價指標隨時間增加(成熟度增加)的回歸方程

2.2 構建表征成熟度隨時間變化的數學模型

為了得到更加精確簡易的描述水蜜桃成熟度隨時間變化的模型，綜合了硬度(Y1)、出汁率(Y2)、可溶性固形物(Y3)和失重率(Y4)四項指標通過多元線性回歸建立了新的綜合回歸模型(1)，通過綜合指標Z關于時間t的數學模型更加全面地量化成熟度變化情況。

Z=7.443-0.027Y1+0.029Y2-0.030Y3+0.099Y4Z=6.872673+0.608970t-0.073632t2+0.006039t3

(1)

借助公式(1)，通過多元指標Z的變化規律，可為貯藏過程中的優化提供有價值的依據，用于水蜜桃采摘后貯藏過程中成熟度變化的預測和監控。 在20℃恒溫貯藏下，計算得到不同成熟度所需分配時間的范圍，如表2所示。

表2 各成熟度對應的分配時間

3 帶時間窗的車輛路徑問題的模型建立

3.1 問題描述

在生鮮農產品(水蜜桃)的配送中,需要經過生產加工，儲存運輸等環節才能交付到消費者手中。早期時候農產品運輸條件簡陋,路徑規劃不合理，導致運輸過程中大量農產品腐爛、變質,不能在客戶規定的時間段內把貨品送至客戶點。既給企業帶來了一定的經濟損失，又影響顧客體驗。

為了盡可能地提升客戶的服務質量和滿足配送的時效性，降低生鮮配送成本，則需要對配送車輛行駛路徑和時間進行合理規劃。從成熟度模型(1)中可以得到將不同成熟度的水蜜桃送到消費者手中所對應的時間窗約束，從而可以得到配送所需的時間。

本文以某地域的水蜜桃配送服務情況為研究對象。某個配送中心統一安排車輛對區域內的多個配送點提供配送服務，完成任務后返回配送中心，客戶信息已知，但是客戶對收到的水蜜桃有成熟度要求，配送車輛送達的水蜜桃必須滿足顧客所需的成熟度，又由于水蜜桃極易腐爛的特性，所以，客戶所需求的成熟度對應的時間窗為硬時間窗。在滿足一些假設的情況下，對配送路徑進行合理規劃，因為生鮮配送更強調時效性，所以，以車輛行駛總路程最小為目標函數。

3.2 基本假設

考慮到該地域的實際業務關系和生鮮配送行業的特點，為了完成規定的配送任務，將帶時間窗的生鮮配送問題轉換為數學模型，現在做出如下假設：

①單一配送中心，所有的配送車輛均由運輸中心發出，結束配送任務后都返回配送中心。

②每輛車只能服務一條路線，每個客戶有且只有一輛車提供配送服務，不可以一輛車服務多次或者由多輛車來服務同一個需求點。

③車輛提供的配送服務時間需要在規定的時間窗[ETi,LTi]范圍內。

④所有客戶的位置坐標，需求量，時間窗等都已知且相互獨立。

⑤配送中心到各客戶的距離已知，各客戶間的距離已知。

⑥每個車輛的限載量相同且已知，車輛配送過程中的載重量不可超過限載量。

⑦貨物恒溫運輸，其品質只與運輸時間相關。

3.3 參數定義

表3 參數定義

3.4 數學模型

(2)

(3)

(4)

Rk={rki|rki∈{1,2,…,w},i=1,2,…,nk}

(5)

Rk1∩Rk2=Φ,?k1≠?k2

(6)

Ski=Srk(i-1)+trk(i-1)rki+trk(i-1)

(7)

ti=Max{ETi-Si,0},i=1,2,…,W

(8)

Si≤LTi(i=1,2,…,W)

(9)

(10)

式(2)為目標函數，表示車輛配送的總路徑最小。

式(3)表示每輛車的載重要在車輛的限載范圍內。

式(4)表示k臺配送車輛所配送的客戶總數與需求的客戶數相等，即表示所有的客戶都獲得了配送服務。

式(5)表示每條線路的客戶組成。其中rki表示客戶rki由k號配送車輛的配送順序為i(rk0表示配送中心)。

式(6)表示每個客戶點只能由一臺配送車輛提供配送服務。

式(7)表示每條配送路徑上，車輛到達下一個客戶點rki的時刻等于當前到達K客戶rk(i-1)的時刻Srk(i-1)，在此客戶點的等待時間tk(i-1)和到達下一客戶點rki所花行駛時間三者之和。

式(8)表示等待時間非負。

式(9)表示配送車輛必須在客戶結束時間窗LTi之前完成配送任務。

式(10)表示如果第k輛車服務的客戶數≥1時，說明該輛車參與了配送。反之，則未參與配送。

4 基于遺傳算法的帶時間窗的車輛路徑問題的模型求解

4.1 染色體編碼與解碼

在遺傳算法中，人們經常使用的染色體編碼方式有自然數編碼和二進制編碼。結合處理問題的實際情況和本文中的帶時間窗的農產品配送路徑模型，明顯可得，采取自然數編碼的方式可以有效求解這一基于次序的組合優化模型，避免出現無效解的情況，具體采用自然數編碼的操作如下：

假設運輸網絡中有W個客戶，配送中心有K輛配送車輛，rki表示第k輛車服務第i個客戶，0表示配送中心。車輛從配送中心出發，完成對客戶點的配送任務后，最后回到配送中心，最終形成長度為W+K+1的染色體，染色體編碼串可表示為(0,r11,r12,…,r1t,0,r21,r22,…,r2n,0,…,0,r31,r32,…,r3s,0)，每條染色體反映的是車輛的配送路徑即代表一個候選解。其中相鄰的兩個0之間表示一個子路徑，子路徑的內部順序不可更改，子路徑與子路徑之間的順序可以更改。以染色體編碼串{0157024308690}為例：表示3輛車對9個客戶點進行服務，解碼后的3條子路徑為：子路徑(1)：0-1-5-7-0；子路徑(2)：0-2-4-3-0；子路徑(3)：0-8-6-9-0。

4.2 生成初始種群

遺傳算法的最優解對初始群體的要求并不是很高，且為了減少算法陷入局部最優的情況，本文采取隨機方式產生初始種群。隨機選取W個客戶點，根據服務的時間窗約束和車輛的最大載重約束，將K+1個0插入染色體中，形成(0,r11,r12,…,r1t,0,r21,r22,…,r2n,0,…,0,r31,r32,…,r3s,0)，如此反復至形成N條染色體，即生成種群規模為N的初始種群。

4.3 適應度函數

適應度函數是對目標函數的評價，其取值是選擇下一代的標準，適應度值的大小和被選擇的幾率成正比。本文構建的是以總距離最短為目標的組合優化模型，這就要求進行函數轉化。所以，將目標函數的倒數設置成適應度函數，設計的適應度函數為：fi=1/zi，zi表示第i個體的目標函數值。

4.4 選擇算子

本文的選擇操作采取混合選擇機制，使得上一種群中的優良個體大概率地被選擇成為優良父代進行繁衍。具體操作步驟如下：

步驟1：計算種群中個體的適應度，對適應度函數值進行從小到大排序，其中，前M個(設為種群規模的50%)個體直接進入下一代。

步驟2：剩下的個體通過輪盤賭法進行篩選。

④以[0,1]之間的隨機數α模擬輪盤指針，若α≤qi，則選擇個體1；否則，選擇個體i。

步驟3：重復步驟2，直到得到N-M個個體。

4.5 交叉操作

為了避免交叉操作破壞過多優良基因，在一定程度上保持種群的多樣性，同時，也為了能在最大范圍內進行搜索最優解，降低算法陷入局部最優的可能，本文采用部分匹配交叉法(PMX)。具體操作為：在染色體上隨機產生兩個位串交叉點，對兩個個體的位串交叉點之間的部分進行交叉操作。下面以兩個父代個體A(321654987)和B(147258369)舉例說明。

A：3 21 6 5 49 8 7 B：1 47 2 5 83 6 9

對方基因串位置前置自身染色體最前端

A’：7 2 5 83 2 1 6 5 4 9 8 7 B’：1 6 5 41 4 7 2 5 8 3 6 9

去掉與前端基因相同的基因片段，得到子代

A1：7 2 5 8 3 1 6 4 9 B1：1 6 5 4 7 2 8 3 9

4.6 變異操作

為了保持種群多樣性，將父代優秀的基因遺傳到下一代，本文采取對換變異的變異方式。具體操作：隨機選中一條染色體，在其上隨機產生兩個非0的自然數r1,r2,(r1,r2≠0)，然后交換r1,r2的基因。例如：r1=1，r2=4;A：3 216 549 8 7 ，變異后為，A’：3 246 519 8 7。

4.7 算法終止條件

當迭代次數達到預設次數時或者算法中的某一結果出現多次時，運算終止并輸出最優解。

5 案例分析

某配送中心rk0，坐標為(4.6，5.5)(單位：100km)。該配送中心擁有5輛配送車輛，每輛車的載重量為25t，平均速度為40km/h，運輸溫度是20°攝氏度。總共服務20位客戶，每個客戶所需的數量(單位：t)，所需的服務時間窗[ETi，LTi](H)和坐標位置見表4。通過設計的遺傳算法獲得適當的路線，以滿足客戶的時間需求和車輛的最短里程。

表4 客戶相關數據

初始參數定義如下：種群規模N=100,最大迭代次數C=500,交叉概率為0.8，變異概率為0.1，運用MATLAB軟件實現。得到最優配送路徑軌跡圖示意圖(圖2)和最優里程迭代圖(圖3)。

圖2 最優配送路徑軌跡圖示意圖

圖3 最優里程迭代圖

本文的遺傳算法的結果表明該算例中需要用到4輛配送車輛，對應最優的配送路線為：

路線1：3→16→8→13→4

路線2：18→17→15→20→7

路線3：14→9→6→19→5→10

路線4：11→1→12→2

6 結語

本文從現實生活中水蜜桃配送過程中面臨的問題出發，在建立蜜桃采摘后的成熟度變化的數學模型的基礎上，再構建硬時間窗的車輛路徑規劃的數學模型，最后，通過遺傳算法求解。通過將成熟度模型和配送路徑模型進行聯合優化，大大減少了水蜜桃配送過程中的浪費損耗，節約了運輸資源，最大程度地滿足了客戶的需求，對解決類似的采摘后成熟的生鮮配送問題有一定的參考意義。