基于改進遺傳算法的生鮮產(chǎn)品配送路徑優(yōu)化

陳 寧，陳翔宇

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

1 引言

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

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

2 模型構(gòu)建

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

2.1 模型假設

為了能夠?qū)⑸r產(chǎn)品配送車輛配載和路徑優(yōu)化問題轉(zhuǎn)換為數(shù)學問題進行求解，需要將現(xiàn)實的生鮮產(chǎn)品配送問題進行簡化。假設：

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

（2）顧客節(jié)點的需求量已知；

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

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

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

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

2.2 模型參數(shù)及變量

（1）相關參數(shù)

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

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

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

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

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

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

P為單位產(chǎn)品的價值；

λ為運輸過程中產(chǎn)品變質(zhì)系數(shù)；

μ為卸貨過程中產(chǎn)品變質(zhì)系數(shù)；

Li,j為節(jié)點i到節(jié)點j的距離；

V為冷藏車平均速度；

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

i,j

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

wi為顧客節(jié)點i的卸貨時間；

Qi為顧客節(jié)點i的需求量；

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

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

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

（2）決策變量

2.3 生鮮產(chǎn)品變質(zhì)分析

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

Qt：生鮮產(chǎn)品在t時刻的品質(zhì)；

Q0：生鮮產(chǎn)品完好時的品質(zhì)；

ρ：產(chǎn)品變質(zhì)系數(shù)，影響產(chǎn)品變質(zhì)腐敗速度，與貨種、溫度、濕度等相關。

2.4 目標函數(shù)

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

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

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

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

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

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

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

模型滿足以下約束條件：

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

3 求解算法

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

3.1 編碼

根據(jù)優(yōu)化模型的特點，選擇整數(shù)編碼，在編碼和解碼過程中不考慮配送中心0（代碼為n+1），而是選擇對路線中的需求點進行排序，將它們編碼在染色體上，再按順序?qū)⑵浞峙涞矫恳惠v冷藏車上。

3.2 初始化種群

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

3.3 適應度函數(shù)

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

3.4 遺傳操作

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

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

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

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

4 算例分析

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

4.1 參數(shù)設置及分析

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

表1 A企業(yè)配送信息

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

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

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

表2 節(jié)點間運輸距離（單位：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天，假設對蝦在冷藏車內(nèi)溫度下每5天價值下降一半，則運輸過程冷鏈品常數(shù)λ約為0.000 1/min，假設卸貨時貨損速度加倍，則運輸過程冷鏈品常數(shù)μ約為0.000 2/min，假設車輛晚于最遲卸貨時間到達，每箱貨每小時懲罰成本b為80元。

4.2 模型求解

本文用matlab編程計算配送路線，經(jīng)過200次隨機試驗（如圖2所示），出現(xiàn)了最佳測試結(jié)果，見表3和圖3。優(yōu)化結(jié)果的各項成本見表4。

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

表3 配送路徑優(yōu)化結(jié)果

圖3 配送路徑

表4 最優(yōu)路徑成本

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

5 結(jié)論

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

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

[參考文獻]

[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]李娜.不確定需求和配送時間窗約束下的供應鏈優(yōu)化[J].計算機仿真,2015,(4):424-428.

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

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

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

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

[11]繆小紅,周新年,林森,等.第3方冷鏈物流配送路徑優(yōu)化研究[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.