基于遺傳算法的生鮮配送的路徑優(yōu)化問題

樊倩 熊雷鳴 邵曉根 孔亮

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

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

中圖分類號：0229;F505;0224 文獻標識碼：A

文章編號：1009-3044（2020）01-0213-03

1背景

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

2生鮮配送問題描述

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

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

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

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

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

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

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

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

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

3.1模型的假設

在對生鮮的配送問題建模的過程中，為了保證模型準確性，運算的簡便性，本文做出以下幾點假設：

1）客戶的需求量已知;

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

3）在運輸范圍內不考慮生鮮腐壞的問題;

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

3.2模型的描述

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

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

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

1）配送車輛的運輸成本

運輸成本主要由以下兩個方面組成：一方面，固定成本co，這成本與行駛的距離無關;另一方面，變動成本c，這成本與行駛的距離有關：

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

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

4.1染色體編碼

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

4.2初始種群設定

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

4.3適應度函數(shù)

適應度函數(shù)是一個有關目標函數(shù)的函數(shù)，其目的是用來判斷個體的優(yōu)劣：

4.4遺傳操作

4.4.1選擇

在父代、子代種群中選擇適應度大的個體。適應度大的個體，將會被不斷被選中、進化到下一代。

4.4.2交叉

使用單點交叉的方式。在新的種群中隨機地選擇兩個個體，再隨機地選擇一個位置，兩者進行交叉互換。

4.4.3變異

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

4.5終止原則

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

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

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

stepl：獲取生鮮商店的位置

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

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

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

step3：對配送問題進行模擬仿真

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

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

6結束語

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