基于改進遺傳算法的生鮮產品配送路徑優化

陳 寧，陳翔宇

（武漢理工大學 交通學院，湖北 武漢 430063）

1 引言

隨著經濟基礎的提高，人們對于更新鮮更健康食品的要求也日益增高，這一需求促進了更快、更高效、更好保存產品的生鮮物流的出現。但當前城市生鮮產品配送仍受限于傳統配送模式的影響，有待進一步優化。針對生鮮物流的特點制定合理的配送計劃，不僅關系到企業提供有效服務的能力，而且關系到企業能否以安全可靠的服務給企業帶來更大的發展空間。

配送路徑問題一直是交通運輸領域一個重要的研究方向，對于新興的生鮮產品配送，也有不少專家進行了研究。如：Tas D等[1]研究了帶軟時間窗的配送路線問題，并分析了從硬時間窗到軟時間窗變化過程中配送總成本的變化。Hsu C I等[2]考慮了運輸時間和溫度變化對冷藏成本的影響，建立了綜合考慮固定成本、損失成本、運輸成本和冷藏成本的分布優化模型，并利用該模型對路徑選擇、車輛分配和配送時間問題進行了優化。Agustina Dwi等[3]以最低交貨成本為目標，研究了存在交叉對接操作情況下小規模食品配送的車輛調度和路徑選擇問題。Le Tung等[4]研究了易腐產品的配送問題，以庫存成本及運輸成本為優化目標構建優化模型，并通過實驗驗證了庫存和路徑的整合對于成本的影響。Derigs Ulrich等[5]以葡萄牙一家食品分銷公司每日配送情況為基礎，研究多站點多車隊的車輛路徑問題，使用大鄰域搜索的方法進行求解并驗證了該方法面對市場變化時的靈活性。李娜[6]構建了具有硬時間窗約束條件下的生鮮食品配送模型，并且在求解該問題時使用蟻群算法，其計算結果表明集成決策能夠有助于降低配送成本，同時使用車輛的固定成本較高時對決策影響較大。王咪、楊孔雨[7]考慮車輛行駛過程中不同的顛簸程度對生鮮產品質量的影響，構建了生鮮產品配送優化模型，并采用免疫遺傳算法求解最優的配送路徑，驗證了模型的有效性。屠丹等[8]構建了只考慮一種產品的一對多的多階段生鮮產品供應鏈優化模型，模型中考慮生鮮產品劣化及不確定需求的影響，研究了配送中心的選址問題及車輛等設備的配置問題。曹美容[9]以今年來快速發展的電商模式下的農產品配送為研究對象，采用蟻群算法求解最優的配送路徑并與matlab仿真結果進行對比，驗證了其模型的有效性。湯齊、張亞麗[10]采用Dijkstra算法對帶有時間窗約束的生鮮產品配送問題進行優化，并對實際案例優化前后的各項成本進行對比，分析了其經濟性。然而在這些研究中，大多只是考慮單純的線性的配送成本，沒有考慮不同的車輛實際配載會有單位里程運輸成本。本文針對這一點進行了改進，綜合考慮生鮮產品配送的各類成本，構建模型對車輛配載及其路徑進行優化。

2 模型構建

本文研究的對象是單配送中心為周邊多個需求點配送一種生鮮產品的配送網絡，分析配送過程中的各類成本，以綜合成本最低為目標，對生鮮產品配送的車輛配載和路徑進行優化。

2.1 模型假設

為了能夠將生鮮產品配送車輛配載和路徑優化問題轉換為數學問題進行求解，需要將現實的生鮮產品配送問題進行簡化。假設：

（1）顧客節點的位置、要求的時間窗已知；

（2）顧客節點的需求量已知；

（3）允許顧客節點少量缺貨，但需要按缺貨量補償一定的懲罰；

（4）配送中心的冷藏車數量需保持平衡，車輛服務完顧客節點必須返回；

（5）顧客節點需求不可拆分，不可以服務多次或是由多輛車聯合進行配送；

（6）車輛出發后不能進行中途指派。

2.2 模型參數及變量

（1）相關參數

N={1，2，···，n}為節點集合，配送中心用0表示；

k={1，2，···，m}，m為冷藏車數量上限；

f為使用一輛冷藏車的固定成本；

cmin為冷藏車空載時每小時的運輸成本；

cmax為冷藏車滿載時每小時的運輸成本。

Ce為每小時車輛制冷的成本；

P為單位產品的價值；

λ為運輸過程中產品變質系數；

μ為卸貨過程中產品變質系數；

Li,j為節點i到節點j的距離；

V為冷藏車平均速度；

tk為冷藏車k從節點i到節點j的行駛時間，

i,j

tk為冷藏車k到達顧客節點i的時刻；

wi為顧客節點i的卸貨時間；

Qi為顧客節點i的需求量；

Qz為冷藏車的最大載貨量；

b為車輛晚于顧客節點時間窗到達時每小時每箱貨的懲罰成本；

[tmini，tmaxi]為顧客節點i的時間窗。

（2）決策變量

2.3 生鮮產品變質分析

生鮮產品在運輸過程中存在腐敗變質的問題，其價值隨運輸時間增加而急劇下降，且其變質腐敗速度受溫度、濕度等多方面因素的影響。本文假設在某一恒定溫度前提下，生鮮產品的變質隨時間變化呈指數型降低，見式（1）。

Qt：生鮮產品在t時刻的品質；

Q0：生鮮產品完好時的品質；

ρ：產品變質系數，影響產品變質腐敗速度，與貨種、溫度、濕度等相關。

2.4 目標函數

總成本可分為以下幾個部分：

（1）固定成本。固定成本只與使用的車輛數量有關。固定成本C1見式（2）。

（2）運輸成本。為了方便計算，選擇根據行駛時間和單位時間的運輸成本進行計算，假設車輛行駛速度基本固定，同時考慮各路段上冷藏車的不同實際載重量有不同的單位運輸成本，假設其運輸成本與實際載重量線性相關。運輸成本C2見公式（3）。

（3）貨損成本。在運輸過程中冷藏車內溫度基本保持恒定，但在卸貨過程中，由于需要開門卸貨，冷藏車內溫度會暫時升高，導致產品變質加快，所以運輸過程與卸貨過程中生鮮產品變質速度不同。假設λ是運輸過程中產品變質系數，μ是卸貨過程中產品變質系數（λ＜μ），整個配送過程的貨損成本C3見式（4）。

（4）制冷成本。制冷成本包括運輸過程中、卸貨過程中以及車輛早于時間窗到達時等待過程中車內制冷系統都需要一直運行以保證車內的低溫狀態，制冷成本C4見式（5）。

（5）懲罰成本。由于生鮮產品時間要求極高，為了保證能在規定時間內送達，需要設置遲到懲罰成本。遲到時間越久，貨物越多則懲罰越重，冷藏車遲到的懲罰成本C5見式（6）。

總成本C為以上五項費用之和，目標函數見式（7）。

模型滿足以下約束條件：

式（8）是冷藏車通過兩個連續的顧客節點的時間限制；式（9）表示冷藏車容量限制；式（10）表示配送路線的數量必須小于或等于冷藏車的數量；式（11）、（12）表示顧客節點的需求不可拆分；式（13）-（20）為變量內部約束；式（21）-（23）表示變量必須是0或1。

3 求解算法

城市生鮮產品配送優化問題屬于典型的NP問題，隨著配送節點的增加，計算量呈指數級增長，難以通過精確算法求解[11]。本文采用遺傳算法對該生鮮產品配送路線問題進行了優化。

3.1 編碼

根據優化模型的特點，選擇整數編碼，在編碼和解碼過程中不考慮配送中心0（代碼為n+1），而是選擇對路線中的需求點進行排序，將它們編碼在染色體上，再按順序將其分配到每一輛冷藏車上。

3.2 初始化種群

初始種群規模的選取對求解速度和優化結果的準確性都有巨大影響。初始群體規模越大，遺傳算法的優化性越好，同時能夠有效避免一直陷入局部最優無法正確求解的情況，但是過大的規模將增加計算量難以求解。權衡計算速度和準確性，每一代種群內染色體選取1 600個隨機數列。

3.3 適應度函數

適應度是衡量染色體個體優劣的標準，也是進行選擇算子操作的重要依據，適應度低的染色體個體會通過選擇算子進行淘汰。本文的生鮮產品配送路線優化模型的優化目標是希望綜合成本最小，而適應度是越大越好，因此可選擇綜合成本的倒數作為適應度函數。

3.4 遺傳操作

（1）選擇算子。選擇算子是通過對染色體個體的適應度進行排序來淘汰較差的染色體，只留部分較優的染色體供后續的遺傳操作。本文選用輪盤賭來篩選染色體，同時，為了保證遺傳算法計算過程的收斂，采用精英保留策略，對前一代種群適應度排名前5%的個體無條件保留，替代經過后續遺傳操作后產生的新種群中適應度排名后5%的個體，避免遺傳操作降低種群的優良性。

（2）交叉算子。對于配送問題，鄰域信息的影響要大于位置信息。因此采用次序交叉法交叉算子計算該類問題性能較好[12]。

以一定概率選取需要交叉的染色體，在需要進行交叉操作的兩個染色體上隨機生成兩個交叉的位置，將兩個染色體在這兩個位置之間的片段進行交換。但此時會出現同一染色體基因有重復的情況，導致重復配送，因此需要進行調整，從交換后染色體的交換片段后一個基因開始，將交換前的染色體從第一個基因開始填入，如果需要的基因與交換后染色體前面位置的基因沖突，跳過該基因，選擇下一個基因，這種過程反復進行，直到所有的基因都被選擇一次。

（3）變異算子。通過變異算子能夠增加染色體遺傳過程中的豐富性，減少陷入局部最優的情況。本文中具體操作是逆轉染色體片段，以一定概率選取需要變異的染色體，然后在需要進行變異操作的兩個染色體上隨機生成兩個位置，調轉這兩個節點之間基因的順序。

4 算例分析

為驗證上述模型和算法在實際配送過程中的科學性和可行性，以A企業的配送問題為例進行研究，并采用改進的遺傳算法對該配送優化模型進行編程求解。

4.1 參數設置及分析

在A企業配送案例中，由1個配送中心為10個需求點配送對蝦，最多可使用4輛冷藏車進行配送。各節點的期望需求和時間窗（時間以早上6點作為起始點）見表1。配送中心和需求點之間的相對位置如圖1所示。

表1 A企業配送信息

注：假設使用外尺寸為50cm×36cm×30.5cm的泡沫保溫箱（內尺寸：42cm×28cm×22cm）進行包裝，每箱約放置20kg對蝦。

圖1 配送中心及需求點位置

各節點之間的距離見表2，假設車輛以40km/h的速度勻速行駛，不考慮車輛擁堵的情況，可以根據各節點之間的距離計算節點間的行駛時間。

表2 節點間運輸距離（單位：km）

采用廂長4.1m的冷藏車進行配送（該車型每行駛100km的油耗約11-13L，載重噸不超過1 000kg），假設每次使用一輛車的固定成本為80元，冷藏車容量Qz取50箱，當平均車速V為40km/h，油價為5.6元/L時，假設空載時單位時間運輸成本cmin為25元/h，滿載時單位時間運輸成本cmax為45元/h，單位時間制冷成本為15元/h。假設對蝦價格為50元/kg，則每箱對蝦價格P約為1 000元。同時由于活對蝦采用冷藏保存時一般可存活將近5天，假設對蝦在冷藏車內溫度下每5天價值下降一半，則運輸過程冷鏈品常數λ約為0.000 1/min，假設卸貨時貨損速度加倍，則運輸過程冷鏈品常數μ約為0.000 2/min，假設車輛晚于最遲卸貨時間到達，每箱貨每小時懲罰成本b為80元。

4.2 模型求解

本文用matlab編程計算配送路線，經過200次隨機試驗（如圖2所示），出現了最佳測試結果，見表3和圖3。優化結果的各項成本見表4。

圖2 種群綜合成本變化趨勢

表3 配送路徑優化結果

圖3 配送路徑

表4 最優路徑成本

由于本文選取算例中配送貨物對蝦價值較高，貨損速度較快，因此貨損成本占比最高，是配送路徑決策時主要考慮的一項成本；由于配送節點較少，配送范圍比較小，使用冷藏車的固定成本占比也較高；由于時間窗較寬松，且遲到懲罰成本較高，因此優化結果中的配送路線沒有出現遲到的懲罰成本。

5 結論

優化結果表明，遺傳算法能夠有效地解決具有時間約束條件的生鮮產品配送問題。在考慮配送決策時，由于各點的需求量基本確定，需要使用多少輛冷藏車也基本固定，雖然使用冷藏車固定成本占比較高，但其對于最終配送路線的決策影響并不是太大；由于每個節點的需求和時間窗都是固定的，且懲罰成本較高，所以都是盡量避免出現遲到。值得注意的是，與傳統配送問題相比，由于生鮮產品對于時間要求較高，配送過程中的貨損成本較高，其占比受貨種影響，若是貨物價值較高，貨損成本甚至會超過運輸成本及冷藏成本，因此在配送過程會與傳統配送有所區別，并不一定選擇最短路而是可能有限考慮滿足需求量較大、時間要求較高的節點。

同時，本文建立的模型中忽略了許多影響因素，研究可以進一步擴展，考慮不同產品的不同變質率、需求波動等因素對于配送模型的影響。

[參考文獻]

[1]Tas D,Dellaert N,van Woensel T,et al.Vehicle routing problem with stochastic travel times including soft time windows and service costs[J].Computers&Operations Research,2013,40(1):214-224.

[2]Hsu C I,Hung S F,Li H C.Vehicle routing problem with timewindows for perishable food delivery[J].Journal of Food Engineering,2007,80(2):465-475.

[3]Agustina D,Lee C K M,Piplani R.Vehicle scheduling and routing at a cross docking center for food supply chains[J].International Journal of Production Economics,2014,152(2):29-41.

[4]Le T,Diabat A,Richard J,et al.A column generation-based heuristic algorithm for an inventory routing problem with perishable goods[J].Optimization Letters,2013,7(7):1 481-1 502.

[5]Derigs U,Gottlieb J,Kalkoff J,et al.Vehicle routing with compartments:applications,modelling and heuristics[J].OR Spectrum,2011,33(4):885-914.

[6]李娜.不確定需求和配送時間窗約束下的供應鏈優化[J].計算機仿真,2015,(4):424-428.

[7]王咪,楊孔雨.基于2-Opt免疫遺傳算法的冷鏈配送路徑優化問題研究[J].物流技術,2016,35(7):72-75.

[8]屠丹,周建頻,初良勇.不確定需求條件下生鮮類農產品供應鏈網絡優化設計研究[J].物流科技,2014,37(6):32-35.

[9]曹美容.O2O模式下生鮮冷鏈配送路徑優化研究[J].價值工程,2017,36(23):85-86.

[10]湯齊,張亞麗.基于時間約束的生鮮產品配送路徑優化[J].鐵道運輸與經濟,2016,38(6):40-43.

[11]繆小紅,周新年,林森,等.第3方冷鏈物流配送路徑優化研究[J].運籌與管理,2011,(4):32-38.

[12]Abdoun O,Abouchabaka J.A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem[J].Computer Science,2012,31(11):49-57.