樊倩 熊雷鳴 邵曉根 孔亮

摘要：為了響應(yīng)國家低碳經(jīng)濟(jì)的號(hào)召，為了降低物流行業(yè)的成本，提高商品配送的質(zhì)量和效率，該文提出了基于遺傳算法的生鮮配送的路徑優(yōu)化模型，并針對(duì)具體案例進(jìn)行了仿真，初始的行駛距離為：210.76km，優(yōu)化后行駛距離為：80.4964km。該文提出的模型具有較高參考性和可行性，具有實(shí)際應(yīng)用的價(jià)值。

關(guān)鍵詞：遺傳算法;生鮮配送;路徑優(yōu)化

中圖分類號(hào)：0229;F505;0224 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）01-0213-03

1背景

為了響應(yīng)國家低碳經(jīng)濟(jì)的號(hào)召，各行各業(yè)都在最大限度地減少能源的使用。特別是物流行業(yè)，隨著社會(huì)經(jīng)濟(jì)的不斷發(fā)展，物流配送業(yè)務(wù)也隨之提高，但是大量的能源在運(yùn)輸過程中被消耗，運(yùn)輸成本不斷上升。如何能夠在保證配送成本和消耗能源最小的情況下，提高商品配送的質(zhì)量和效率，縮短生鮮在途時(shí)間是本文研究的主要內(nèi)容。

2生鮮配送問題描述

目前生鮮配送主要由自營(yíng)配送和建設(shè)配送網(wǎng)絡(luò)兩種構(gòu)成。自營(yíng)配送會(huì)產(chǎn)生成本的大量投入;建設(shè)配送網(wǎng)絡(luò)容易出現(xiàn)地區(qū)發(fā)展不協(xié)調(diào)的問題。

沒有做到合理的配送計(jì)劃，易造成配送成本得虛高。借助先進(jìn)的物流管理理念、技術(shù)，建立合適的配送路徑優(yōu)化模型是目前配送系統(tǒng)面臨的主要問題。

考慮到這個(gè)問題，本文主要研究如何優(yōu)化現(xiàn)有的同城配送運(yùn)輸網(wǎng)。優(yōu)化運(yùn)輸網(wǎng)，可以縮減成本，以下是該研究問題的示意圖：

3生鮮配送問題的模型的建立

如果要解決生鮮的配送路徑優(yōu)化問題，則該模型描述為：

1）車輛從暫存點(diǎn)出發(fā)，送至客戶點(diǎn)，再返回暫存點(diǎn);

2）滿足路徑上的需求量要求、車輛容載限制的約束;

與以往的車輛路徑問題不同的是，生鮮在配送的過程中，將會(huì)產(chǎn)生制冷成本，本文在研究這個(gè)優(yōu)化問題的時(shí)候需要將其考慮在內(nèi)。

生鮮的配送問題，可以看作是一個(gè)多商旅問題（MTSP），可將其分成M個(gè)商旅問題（TsP）。

3.1模型的假設(shè)

在對(duì)生鮮的配送問題建模的過程中，為了保證模型準(zhǔn)確性，運(yùn)算的簡(jiǎn)便性，本文做出以下幾點(diǎn)假設(shè)：

1）客戶的需求量已知;

2）配送車輛勻速行駛，行駛路徑固定;

3）在運(yùn)輸范圍內(nèi)不考慮生鮮腐壞的問題;

4）配送車輛的載重量一定，且能夠滿足客戶的需要量。

3.2模型的描述

生鮮暫存點(diǎn)，為n個(gè)客戶點(diǎn)提供生鮮配送服務(wù);pi（i=1，2，…n）為第i個(gè)客戶的需求量;運(yùn)送車的規(guī)定載重為O。

3.3模型的目標(biāo)函數(shù)

配送車輛從暫存點(diǎn)出發(fā)，送至多個(gè)客戶點(diǎn)，最后再返回暫存點(diǎn)。

1）配送車輛的運(yùn)輸成本

運(yùn)輸成本主要由以下兩個(gè)方面組成：一方面，固定成本co，這成本與行駛的距離無關(guān);另一方面，變動(dòng)成本c，這成本與行駛的距離有關(guān)：

4基于遺傳算法的生鮮配送問題的模型的求解

車輛路徑問題屬于NP-hard問題，參考文獻(xiàn)，本文選擇遺傳算法對(duì)問題進(jìn)行求解。遺傳算法全局搜索能力強(qiáng)、求解時(shí)間少，避免了逐次逼近算法效率低下的問題，也避免了陷入局部最優(yōu)解。步驟如下：

4.1染色體編碼

編碼采用十進(jìn)制的方式。采用一個(gè)隨機(jī)數(shù)列表示種群中的一個(gè)個(gè)體，作為染色體。

4.2初始種群設(shè)定

采用改良圈算法，解得一個(gè)初始種群。產(chǎn)生M個(gè)染色體（即可行解）。把這些可行解轉(zhuǎn)換成染色體編碼。這個(gè)初始種群規(guī)模應(yīng)適當(dāng)：規(guī)模太大，會(huì)影響搜索效果;規(guī)模太小，會(huì)容易陷入局部最優(yōu)解。

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

適應(yīng)度函數(shù)是一個(gè)有關(guān)目標(biāo)函數(shù)的函數(shù)，其目的是用來判斷個(gè)體的優(yōu)劣：

4.4遺傳操作

4.4.1選擇

在父代、子代種群中選擇適應(yīng)度大的個(gè)體。適應(yīng)度大的個(gè)體，將會(huì)被不斷被選中、進(jìn)化到下一代。

4.4.2交叉

使用單點(diǎn)交叉的方式。在新的種群中隨機(jī)地選擇兩個(gè)個(gè)體，再隨機(jī)地選擇一個(gè)位置，兩者進(jìn)行交叉互換。

4.4.3變異

按照給定的變異率，選擇發(fā)生變異的個(gè)體。隨機(jī)地選取該個(gè)體的一個(gè)基因段，將其隨機(jī)地插入余下的一個(gè)基因段中間，從而產(chǎn)生新的個(gè)體。

4.5終止原則

當(dāng)算法迭代到指定的代數(shù)之后，停止運(yùn)行，并將當(dāng)前的最優(yōu)染色體作為最優(yōu)的解輸出。

5生鮮配送問題的模型的仿真

為了驗(yàn)證本文所提出的算法是有效的，基于江蘇省徐州市的生鮮超市進(jìn)行配送模擬仿真。

stepl：獲取生鮮商店的位置

首先，借助百度地圖的坐標(biāo)拾取器，獲得徐州市130余家售賣生鮮食品的商店的地址及經(jīng)緯度。然后，將獲取的數(shù)據(jù)進(jìn)行篩選，剔除數(shù)據(jù)缺失的項(xiàng)。同時(shí)，根據(jù)商店的實(shí)際經(jīng)營(yíng)情況，選擇需要生鮮配送的大型商店。最終，選取了39家適合商店作為客戶點(diǎn)，其中包括：愛客來、悅客等連鎖便利店。將其繪制在地圖中，如下圖2所示：

step2：經(jīng)緯度轉(zhuǎn)換為距離

將經(jīng)緯度的單位為角度，利用Matlab中distance函數(shù)計(jì)算兩點(diǎn)與地心連線的夾角，再將角度乘以地球半徑6370km，即為徐州市客戶點(diǎn)之間的距離。

step3：對(duì)配送問題進(jìn)行模擬仿真

根據(jù)客戶點(diǎn)地地理位置及城區(qū)規(guī)劃范圍，將MTSP問題轉(zhuǎn)化為3個(gè)TSP問題。求解該遺傳算法問題，將參數(shù)設(shè)定如下，種群的大小為M=19;最大的迭代次數(shù)G=1000;為保證種群能夠充分進(jìn)化，交叉概率pc=1;一般來說，變異發(fā)生的可能性比較小，變異概率pm=0.1。最終，通過建立的模型，經(jīng)過Matlab計(jì)算得到結(jié)果，繪制出配送的初始路徑圖和配送的路徑優(yōu)化圖。

初始時(shí)行駛距離為：210.76km。由結(jié)果圖可以看出優(yōu)化過后的路徑更短，行駛的距離為：80.4964km。

6結(jié)束語

本文所研究的生鮮配送問題，除了考慮到距離最小之外，還考慮了生鮮在配送過程中的制冷所產(chǎn)生的成本，使得問題更加貼近實(shí)際生活。優(yōu)化現(xiàn)有的運(yùn)輸網(wǎng)絡(luò)，降低成本，為企業(yè)的發(fā)展帶來更好的收益。