陳 寧，陳翔宇

（武漢理工大學(xué) 交通學(xué)院，湖北 武漢 430063）

1 引言

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

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

2 模型構(gòu)建

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

2.1 模型假設(shè)

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

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

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

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

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

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

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

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

（1）相關(guān)參數(shù)

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

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

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

cmin為冷藏車空載時(shí)每小時(shí)的運(yùn)輸成本；

cmax為冷藏車滿載時(shí)每小時(shí)的運(yùn)輸成本。

Ce為每小時(shí)車輛制冷的成本；

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

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

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

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

V為冷藏車平均速度；

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

i,j

tk為冷藏車k到達(dá)顧客節(jié)點(diǎn)i的時(shí)刻；

wi為顧客節(jié)點(diǎn)i的卸貨時(shí)間；

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

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

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

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

（2）決策變量

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

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

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

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

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

2.4 目標(biāo)函數(shù)

總成本可分為以下幾個(gè)部分：

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

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

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

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

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

總成本C為以上五項(xiàng)費(fèi)用之和，目標(biāo)函數(shù)見式（7）。

模型滿足以下約束條件：

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

3 求解算法

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

3.1 編碼

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

3.2 初始化種群

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

3.3 適應(yīng)度函數(shù)

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

3.4 遺傳操作

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

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

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

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

4 算例分析

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

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

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

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

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

圖1 配送中心及需求點(diǎn)位置

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

表2 節(jié)點(diǎn)間運(yùn)輸距離（單位：km）

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

4.2 模型求解

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

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

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

圖3 配送路徑

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

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

5 結(jié)論

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

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

[參考文獻(xiàn)]

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

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

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

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

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

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