李致遠 王璐 張磊 王晉冰 張杰 林輝輪

摘 要：本文提出了解決卷煙配送問題的差分進化算法。在繼承了傳統(tǒng)的遺傳算法解決路徑優(yōu)化問題的諸多算法優(yōu)點基礎上，差分進化算法具有更強的魯棒性，并且逼近效果更加顯著。由于卷煙配送問題有時間、精確度需求，因此，運用差分進化算法解決該問題具有顯著優(yōu)勢。

關鍵詞：卷煙配送;路徑優(yōu)化;差分進化算法

中圖分類號：TP18 文獻標識碼：A

0 引言

我國煙草公司客戶數(shù)量眾多、分布不均勻且客戶訂單大小有差異。因此煙草公司在進行卷煙配送時，如果事先沒有合理的卷煙配送路徑安排，就會導致運輸頻次過高以及資源浪費。因此，如何合理優(yōu)化卷煙配送路徑，具有很大的現(xiàn)實意義。本文以貴州省煙草公司貴陽市公司為例，對其卷煙配送路徑選擇系統(tǒng)進行了優(yōu)化，建立了精度、效率更高的卷煙配送路徑選擇模型，并采用差分進化算法進行模型求解。

1 卷煙配送路徑優(yōu)化問題描述及數(shù)學模型

1.1 問題描述

VRP配送問題為大規(guī)模組合優(yōu)化問題，而且隨著問題求解規(guī)模擴大而呈指數(shù)式增長。一般情況下，卷煙配送問題涉及幾千個配送節(jié)點，配送網(wǎng)絡路徑組合更是復雜，因此，采用經(jīng)典VRP算法直接求解相當困難?？紤]到卷煙配送問題的規(guī)律性和區(qū)域特點，對卷煙配送問題采用基于區(qū)域劃分的差分進化算法，將復雜的卷煙配送問題轉(zhuǎn)化為簡單的VRP問題求解。

1.2 數(shù)學模型

1.2.1 模型轉(zhuǎn)化

第一步：建立配送點區(qū)域單元集合，在同一區(qū)域單元，各配送點之間路徑距離相近，一般以相鄰多個街道作為一個區(qū)域單元，區(qū)域單元范圍以區(qū)域范圍內(nèi)包含配送點的數(shù)量和統(tǒng)計配送量的多少來確定。區(qū)域單元集合的構(gòu)建可以通過對現(xiàn)有配送方案進行聚類，構(gòu)建初始區(qū)域單元集合，然后通過人工調(diào)整得到合理的區(qū)域單元集合。其中，采用正半矢公式進行兩配送點之間距離計算。

式中，和表示兩點的緯度，和表示兩點的經(jīng)度，r表示地球半徑。

用該原則將貴陽市公司客戶進行區(qū)域劃分，結(jié)果如圖1所示。

第二步：針對每個區(qū)域，采用聚類算法將距離相近的客戶“打包”為一個配送域，并計算出每個配送域的中心位置及訂單總量。

以已劃分的花溪區(qū)為例，將該區(qū)域內(nèi)相鄰的顧客劃分為不同的配送域，結(jié)果如圖2所示。

將每個配送域看作一個訂單，采用相關路徑規(guī)劃啟發(fā)式算法確定配送車輛及配送路線。針對每個配送域再次進行路徑規(guī)劃，最終求得整個區(qū)域所有客戶的具體配送方案。

1.2.2 傳統(tǒng)VRP模型

該模型中，目標函數(shù)（2）表示最小化車輛行駛路程，公式（3）表示所有配送域必須被訪問，且每個配送域只能訪問一次;公式（4，5，6）表示所有車輛都從起始點出發(fā)并最終回到起始點;公式（7）表示每輛車訪問的配送域訂單貨物總量不得超過車輛荷載量（若某個配送域的訂單貨物超出載荷量，可在第二階段的路徑規(guī)劃中安排多輛車進行配送）;公式（7）定義所有車輛實際運送卷煙量不得超過其規(guī)定載重;公式（8）定義決策變量為0-1整數(shù)變量。

2 模型求解

由于構(gòu)建的模型對應的決策變量很多，若用傳統(tǒng)的遺傳算法對該實例中構(gòu)建的VRP模型進行求解，則需要花費大量時間，且求出的結(jié)果精度較低。因此，本文提出了使用差分進化算法進行模型求解。通過進化個體編碼與解碼、初始種群產(chǎn)生、變異和交叉得出最優(yōu)路徑。

3 實驗結(jié)果與分析

3.1 實驗結(jié)果

本文采用貴州省煙草公司貴陽分公司的數(shù)據(jù)，并結(jié)合提出的差分進化算法，對該公司卷煙配送路徑選擇模型進行求解，并將求解得出的配送路徑與現(xiàn)有配送路徑進行對比。

首先采用差分進化算法對各個配送域之間的配送路徑進行求解，所得結(jié)果如圖3所示。接著可采用同樣的方法對每個配送域中的客戶進行具體的路徑規(guī)劃，從而最終得到所有客戶的具體配送線路，所得結(jié)果如圖4所示。

最后用同樣算法算出每個區(qū)域的具體卷煙配送路徑（如圖5），并與原有的卷煙配送路徑進行比較（如圖6）。

3.2 結(jié)果分析

模擬仿真實驗結(jié)果表明，本研究所規(guī)劃的配送路線遠優(yōu)于現(xiàn)有固定配送線路，并且更加靈活，節(jié)約了大量運輸成本，具有一定的應用潛力。

本文研究不足在于：目前本研究中計算客戶兩兩之間的距離是根據(jù)經(jīng)緯度計算出兩點之間的直線距離，與實際的路網(wǎng)行駛距離會存在一定偏差。同時所采用的聚類算法是根據(jù)客戶位置進行自動劃分，未考慮道路實際情況，如采用人工標注將會更加準確。

參考文獻：

[1]齊佳婷.城市農(nóng)產(chǎn)品冷鏈物流配送車輛路徑問題研究[D].浙江理工大學，2016.

[2]周輝仁，唐萬生，王海龍.基于差分進化算法的多旅行商問題優(yōu)化[J].系統(tǒng)工程理論與實踐，2010，30（08）：1471-1476.

[3]王小平，曹立明.遺傳算法理論、應用軟件實現(xiàn)[M].西安交通大學出版社，2002.

[4]鄧欣.基于遺傳算法的多車場車輛路徑間題研究[D].重慶大學，2007.

[5]胡紅春.煙草物流配送車輛線路優(yōu)化研究與應用[J].物流技術，2012，31（21）：214-217.

[6]付依良，李萌，程強，等.煙草物流配送網(wǎng)絡綜合優(yōu)化模型與方法[J]中外企家，2013，30（30）：205-215.