基于遺傳算法的煙草卷煙共用庫選址優化模型

王 全，陳瑋娟，劉曉飛，張 婷

（甘肅煙草工業有限責任公司，甘肅 蘭州 730050）

1 引言

目前煙草工商公司之間的物流運輸主要采用點對點的直達模式[1]，該模式下工商公司之間物流車輛沒有統籌利用，存在非滿載運送和空車返程的情況，一方面造成了運力資源的浪費，另一方面點對點運輸不利于工業企業對商業企業需求的快速響應。為解決上述問題，可建立一種高效、合理、快速響應的煙草工商公司中轉倉儲和運輸體系。目前，國內對于煙草行業物流運輸的研究主要集中在商業公司零售配送路徑的規劃、卷煙包裝箱回收系統歸集中心的選址和工業公司內部集中庫的選址方面，李家斌等[2]研究了某省實際卷煙包裝箱回收數據，得到了最優歸集中心的選址方案，卻未研究運輸里程因素對于選址的影響。杜運琪[3]研究了新疆煙草物流配送中心的選址問題，但未進行深層次的量化分析。丁一[4]研究了江蘇中煙銷售模式下的物流運輸模式，基于層次分析法的評估模型理論評價了5個集中庫設計方案，方案中考慮了運輸費用和現狀費用等因素，有一定的借鑒意義，但未考慮拼車、車輛往返裝載對于運輸單價的影響。

文章通過分析2020年全國煙草工商公司銷售數據，引入運輸里程、運輸路徑、共用庫位置、拼車、往返裝載等因素，建立卷煙運輸總體費用最低的工商公司卷煙運輸共用庫選址優化模型，為行業物流相關戰略規劃提供參考。

2 選址優化模型建立

2.1 煙草工商公司物流運輸流程及相關假設

卷煙物流運輸包括煙草工業公司、工商共用庫、商業配送中心3個環節。其詳細的運作流程如圖1所示。

圖1 煙草工商公司卷煙物流運輸拓撲圖

在該模型中，工業公司結合往年的銷售計劃和本年度簽訂的銷售協議，提前安排車輛將卷煙發往合適的共用庫。然后，卷煙在各個共用庫之間轉運；最后，按照工業公司的要求，完成向商業公司的卷煙運送。

為方便構建模型，做出以下假設：

a.各工業企業的發貨地點只有1個，即為工業公司所在城市。

b.聯營加工的卷煙視作從委托方發出。

c.商業公司以省級公司為單位，僅有1個收貨地點，為當前省公司的省會城市。

d.共用庫的選址范圍為除臺北之外31個省會城市。

e.單箱卷煙的運輸單價與車輛是否滿載、拼車有關，與地理位置無關。

f.共用庫的固定建設成本不在共用庫選址的考慮因素當中。

g.共用庫的卷煙倉儲保管費用不在共用庫地址的考慮因素當中。

h.共用庫的庫容為理想狀態，可滿足所有工業企業的儲存要求。

i.工業企業在運輸路徑規劃時不考慮共用庫的庫容限制。

2.2 模型建立

主要參數和變量見表1。

表1 目標函數主要參數和變量

模型的其他部分如下：

目標函數：

約束條件：

式（1）表示目標函數，使得某段時間內煙草行業工商公司卷煙總體運輸費用相對最小，由于引入了運輸單價系數，因此最終得到是相對費用，而非真實的運輸費用，該費用包括工業公司至共用庫相對運輸費用、共用庫之間相對運輸費用和共用庫至商業公司相對運輸費用。在該函數中，將問題轉換為通過求解各城市（工業公司、商業公司和共用庫所在城市）之間路徑的相對物流運輸費用之和，每條路徑的物流費用為當前路徑各工業卷煙運輸總量乘以卷煙運輸單價和卷煙運輸單價系數。

式（2）表示卷煙運輸單價系數，該系數表示某時間段內某條路徑上非滿載裝運、空車返回對于運輸單價的影響，當某時間段內該路徑上卷煙運輸的總量越大時，出現非滿載裝運和空車返回的概率越小，運輸單價相應越低。因此，在目標函數中，運輸單價系數取當前路徑運輸總量和總運量的比值，最后得到的最小運輸費用（Fmin）是相對的，不是真實的最低運輸費用。

3 遺傳算法求解

選擇遺傳算法[5]求解共用庫的選址，主要原因包括以下幾點：一是按照前文的假設，共用庫的選址從省會城市產生，目標函數解的定義域是明確的；二是解空間的數量不確定，即達到全局最優的共用庫數量不確定；三是遺傳算法可在不遍歷定義域內解組合的基礎上求解全局范圍內的較優解。

文章提出的遺傳算法步驟如圖2所示，步驟注釋：

圖2 遺傳算法的流程圖

（1）初始化種群：種群數量為Pop.Size=2；

（2）根據目標函數計算種群中個體適應值fitness；

（3）種群內個體之間進行基因交叉、變異和選擇；

（4）判斷種群遺傳代數Generation是否達到上限，如果是，轉步驟（5），否則轉步驟（6）；

（5）種群繁殖1次，轉步驟（2）；

（6）判斷種群個數是否達到上限，如果是，遺傳結束，否則轉步驟7；

7）種群數量增加1個，轉步驟2。

3.1 染色體

在研究模型中，pi,j、ek,h、wk,h、μk,h等與W有直接或間接的聯系，W的任何變化將會導致其他變量發生改變，因此選擇W作為染色體，染色體中基因的編碼為城市的編號二進制表示。在研究中，假設W從省會城市中選擇，共用庫選址編號見表2。

表2 共用庫選址城市編號

3.2 初始化種群

最初的種群是由2個隨機產生的個體組成的，之后評估每個個體的適應度，基于這些個體的適應度對它們進行排序，形成第一代種群。

3.3 個體適應度

個體的適應度是根據目標函數式（1）計算的，計算過程如下：

（1）通過編程從百度地圖開放平臺獲取S中城市之間的距離，初始化矩陣E，城市之間公路里程見表3；

表3 城市之間公路里程 單位：km

（2）根據dijkstra算法[6]獲得工業公司i經當前共用庫集合至商業公司j之間的最短路徑pi,j；

（3）重復（2）中步驟，直到獲得所有工業公司至各家商業公司的最短路徑；

（4）根據目標函數計算個體的目標函數。

3.4 遺傳操作

遺傳算法的主要操作包括交叉、變異和選擇。

（1）交叉：在交叉過程中，選擇單點交叉方式（One Point Crossover）[7]，交叉點固定為個體的第一個基因，即第一個基因后的2個個體的染色體交換后形成新的2個個體，發生交叉的概率為0.75。

（2）變異：在變異的過程中，選擇均勻變異算子（Uniform Mutation）[8]，使用符合基因值范圍內均勻分布的隨機數，發生變異的概率為0.1。

（3）選擇：在種群選擇的過程中，選擇最優保存策略（Elite Selection）[9]，把適應度最好的個體保留到下一代種群中。

4 結果和討論

將2020年煙草工商公司之間銷售數據帶入模型計算，按照遺傳算法求解共用庫個數（即種群數量）為2～31時的最優選址。

4.1 算法求解結果

圖3為算法求解過程中選擇不同共用庫個數時，算法的收斂速度（用繁殖的代數表示）。由于共用庫是從31個省會級城市選址，因此當共用庫個數為31時，算法在第一代就收斂。從圖3可以看出，除共用庫個數為30或31之外，算法取得局部最優解（即限定共用庫個數）時，繁殖的代數分布在15～50。

圖3 遺傳算法收斂速度

從圖4可以看出，相對運輸費用隨共用庫個數的增加呈類拋物線趨勢變化，當共用庫個數為9時，算法在27代時收斂求得全局最優，此時相對運輸費用最低，共用庫選址在天津、銀川、南寧、西寧、西安、昆明、武漢、南昌、合肥等地，每個共用庫的年轉運量如表4所示。

表4 最優選址時的各共用庫轉運量

圖4 相對運輸費用隨共用庫個數變化趨勢

4.2 結果分析

上述可知，相對運輸費用隨共用庫個數的增加呈近似拋物線趨勢變化。在實際卷煙運輸中，運輸費用主要由運輸距離、卷煙數量和運輸單價決定，因為卷煙數量在一段時間內為定值，所以影響因素只有運輸距離、運輸單價2個，由式（1）可知，運輸單價跟當前線路的運量成正比。

當共用庫較少時，卷煙從工業公司經共用庫運至商業公司的平均運輸距離較大，雖然各條線路上的運輸單價較低，但此時起主要作用的是運輸距離，總的運輸費用較高。

隨著共用庫逐漸增加，卷煙從工業公司經共用庫運至商業公司的平均運輸距離有所縮短；另外，由于運輸線路增加，線路上的平均運量有所降低，平均運輸單價有所升高；在共用庫數量增大到某個值時，總的運輸費用達到最低。

當共用庫數量繼續增大時，卷煙從工業公司經共用庫運至商業公司的平均運輸距離繼續縮短，但是由于運輸線路持續增多導致單箱卷煙的平均運輸單價進一步升高，此時起主要作用的是運輸單價，總的運輸費用增加。

當共用庫數量為31時，每個省會級城市均為共用庫選址，工業公司發往商業公司的最短路徑為不經過其他共用庫的直達模式，這與現有的點對點煙草工商運輸模式一樣。從圖4可知，以2020年全國煙草工商企業銷售數據為準，利用文章提出的新煙草物流運輸模型（即共用庫選址在天津、銀川、南寧、西寧、西安、昆明、武漢、南昌、合肥等地），相對于當前工商點對點運輸模式，可節省10.2%的物流費用，同時此模式下工業卷煙可前置于共用庫，對商業需求的響應也更加及時。

5 結論

以煙草行業工商公司總體卷煙運輸費用最低為決策目標構建共用庫選址模型。在構建模型的過程中，除考慮運輸距離之外，還充分考慮了卷煙運輸中非滿載裝運和空車返回對于運輸單價的影響，避免造成結果偏差。最后通過2020年全國煙草工商公司銷售數據驗證了模型的有效性。從研究的結果發現，煙草共用庫選址存在一個解，使得煙草工商公司總體運輸費用最低。

在研究共用庫選址問題時做了一些必要的簡化假設，未來可以從以下幾個方面進行深入研究：一是通過對煙草工商公司歷史銷售數據進行分析，設計精確算法求解以物流運輸費用最低為目標的共用庫庫容；二是優化模型，求解綜合考慮共用庫建設成本、倉儲費用和共用庫庫容等因素的，以物流運輸費用最低為目標的共用庫選址。