基于兩階段法的多車型卷煙配送路徑優化研究

趙 峰，王 澤，李 軼 ZHAO Feng,WANG Ze,LI Yi

0 引言

目前的卷煙配送線路安排主要有兩種模式，一種是通過卷煙配送系統安排線路，另一種是根據人工經驗安排線路。據調查，大多數地級市商業性煙草企業在卷煙配送時采取的都是以人工經驗為主、系統為輔的配送模式，由于人工安排的線路中其主觀性較大，不能根據實際情況綜合考慮問題，這對卷煙的配送提出了嚴峻的挑戰，其配送網絡布局和路線規劃的合理與否直接影響到卷煙的配送效率和成本。因此，就如何合理的規劃線路來提高卷煙的配送效率和降低配送成本成為煙草配送急需解決的關鍵問題。

Tu W等[1]利用基于雙層Voronoi圖的元啟發式算法來解決大規模多車場車輛路徑問題（MDVRP）。Wei Td等[2]在針對帶時間窗的大規模車輛路徑問題（VRPTW） 時，提出了基于時空Voronoi圖的啟發式方法，從時空Voronoi圖導出空間—時間Voronoi距離，以在時空搜索上找到近鄰，并提出了一種集成時間扭曲操作的Voronoi距離衰減策略，以加速局部搜索過程。潘國鵬[3]以安陽煙草公司為例，結合安陽煙草公司出現的實際問題，運用先分組后路線的兩階段方法對大規模卷煙配送線路進行優化，先用K-means聚類算法劃分配送區域，后對各區域內運用最大最小蟻群算法優化線路。羅勇等[4]提出了基于序的選擇算子、最小代價樹的交叉算子和隨機點長度控制的變異算子的改進遺傳算法對物流配送路徑進行優化，并通過實例仿真驗證了其有效性。任曉智、賓彬超[5]提出了基于聚類分析的卷煙配送路徑優化，并給出了具體步驟和求解過程。蔣國清等[6]針對物流配送路徑優化問題提出了一種兩階段式的物流配送路徑優化方法，即遺傳—蟻群結合的路徑搜索方法，先通過遺傳算法找到問題的初始解，后通過蟻群算法尋找最優方案，通過實例驗證其在求解時魯棒性更強。王力鋒等[7]針對傳統遺傳算法在物流配送路徑優化中的不足，提出了一種基于蟻群算法的物流運輸快速配送路徑規劃方法。蒲思睿[8]在解決車輛路徑優化問題中引入了GIS，構建了動態的GIS-TSP模型。本文在總結前人的基礎上運用兩階段法對卷煙配送路徑進行優化，先利用K-means聚類算法對區域進行劃分，再考慮工作量均衡的條件下引入遺傳算法對區域調整，最后利用混合遺傳算法對各配送區域進行線路優化。

1 基于K-means聚類算法對配送區域的劃分

本文以Q市雨山、花山兩區周三的送貨線路為例運用兩階段法對其進行分析，在其既定的服務范圍內進行線路優化。由于全市卷煙配送問題具有通性，該區域的優化思路可適當應用到全市。

Q市雨山、花山區周三服務的零售戶共有1 088戶，其分布如圖1所示，其配送路線為11條，其客戶分布如圖2所示（圖中不同顏色的點表示不同的線路上的零售戶）。從圖2可以看出當前劃分的線路間交叉迂回現象較為突出，嚴重影響了卷煙的配送效率和成本，為提高配送效率，急需對原配送路線進行整合重新規劃線路。

圖1 客戶分布圖

圖2 各配送路線上客戶分布圖

（1）K值的確定

由于在卷煙的實際配送中涉及到多種車型，其中涉及到車輛的指派與車型選擇的問題，本文利用文獻[9]中K值的確定方法確定區域的個數，建立數學模型，運用LINGO軟件對模型進行求解，其中v1=5 000，v2=6 000，n1=15，n2=4，Q=42 526，其中最大裝載量為5 000條煙的車和6 000條煙的車百公里耗油量分別為10L和11L，每升油價為6.57元/L，可得每公里單位成本c1=0.657元/km，c2=0.7227元/km，模型求解結果為取最大裝載量為5 000的車4輛，最大裝載量為6 000的車4輛，由此得出q=5 500，即K=8。

（2） 初始聚類結果

利用K-means聚類算法對零售戶進行聚類，初始聚類結果如圖3所示：

根據圖3的聚類結果對聚類后各區域所含的客戶數和總需求量進行統計匯總，如表1所示：

圖3 初始聚類結果圖

表1 聚類后各區域客戶數及需求量統計表

2 考慮工作量均衡的區域劃分調整

傳統的K-means聚類在聚類時僅考慮到客戶間的分布密度，并沒有考慮到聚類后各區域內需求總量和總里程的限制，不能滿足使劃分好的區域間工作量均衡的要求，直接影響到卷煙的配送效率。針對上述缺點，本文在傳統的K-means聚類的基礎上引入遺傳算法，先計算K個聚類中心對應聚類內的零售戶數、卷煙配送總量Qj和各區域內最大配送里程Lj；將每個聚類內的零售戶卷煙配送總量Qj及總配送里程Lj與對應車型的單車最大載貨量Qmax及允許配送的最大里程Lmax進行比較：若Qj≤Qmax且Lj≤Lmax成立，則表示聚類后該區域符合約束條件，即將該客戶點歸入該聚類，否則，將距離該聚類中心最遠的客戶點彈出，將其納入與之最近的聚類中并進行條件判斷；再選擇距該聚類次之的客戶點進行條件判斷，直至所有區域均調整完畢。

根據上述思路對區域做進一步優化調整，其聚類中心的選取收斂圖及各區域的劃分圖如圖4、圖5所示。

圖4 優化調整后聚類中心收斂圖

圖5 優化調整后區域劃分圖

從圖4聚類中心的收斂圖中可以看出約在45代左右算法達到收斂，即各區域內聚類中心達到穩定狀態。圖5為優化調整后的區域劃分圖，將優化后各聚類所含客戶數和總需求進行匯總，如表2所示：

表2 各聚類客戶數及需求表

從表2中可以看出各區域內的客戶數量和總需求量都相對均衡，且車輛利用率較高，區域8有186戶，是因為區域8處于市中心地段，客戶相對集中，區域3中的客戶數為67戶，相對較少，是因為區域3離市區較遠且客戶位置分布較為分散。

3 卷煙配送線路優化模型的建立

（1） 問題描述

煙草物流作為特殊的物流行業，其卷煙的配送路徑問題是一種大規模車輛路徑問題，屬于NP難問題。一般多車輛多服務點的大規模路徑優化問題可以分兩步進行：①對配送區域劃分，②對子區域進行線路優化。故針對多車型的單車輛多服務點配送問題可以描述為：由配送中心針對劃分好的區域對K種不同型號的車輛進行合理的調度，選擇合適的車型對相應區域內的客戶進行服務，各區域內的每個客戶必須且僅能由一輛車進行訪問，有且僅能訪問一次，區域內的客戶需求量和總里程不能超過單車的最大核載能力和行駛能力。其中配送中心和各區域內客戶點位置、需求量已知，完成配送任務后車輛返回配送中心。

（2） 數學模型的構建

通過對Q煙草公司卷煙配送中心的實地調查和根據現實中的實際配送情況對問題進行適當的抽象和簡化，以配送總成本最小為目標建立數學模型。

上述模型中式（1）為卷煙配送路徑優化的目標函數，表示配送總成本最小，其中包括運輸成本和車輛固定使用成本；式（2）和式 （3）表示每個客戶點都由某種車型服務，且僅有一次；式（4）表示所有的配送車輛均從配送中心出發且最終回到該配送中心；式（5）表示一條線路上所有客戶間的里程和不能超過配送車輛的最大行駛里程限制；式（6）表示特定車型所負責配送的客戶卷煙總量不能超過該車的最大裝載量限制；式（7）和式（8）為決策變量的取值范圍。

（3） 模型變量說明

n表示客戶點集合，n=｛1,2 ,…,n｝；m配送車輛車型集合，m=｛1,2 ,…,k｝；uk表示k型車的數量，k∈m；Lk表示k型車的最大行駛距離；fk表示k型車的固定費用，一般包括車雜費、折舊費、修理費等費用；ck表示k型車的單位行駛費用；qi表示每個客戶的需求量，i=｛1,2 ,…,n｝；Qkmax表示k型車的最大裝載量；dij表示客戶i到客戶j間的配送距離，其中，d0j表示配送中心到各客戶的配送距離，i,j=1,2,…,n，xijkl和yikl為0、1決策變量，具體表示如下：

4 基于混合遺傳算法的卷煙配送線路優化

4.1 混合遺傳算法原理

本文提出的遺傳—爬山混合算法是針對遺傳算法在全局搜索能力較強，而局部搜索能力較弱的基礎上嵌入局部搜索能力較強的爬山算法，該算法主要在遺傳—變異算子執行后引入爬山算子，利用爬山操作在每代群體中選擇最優的個體作為迭代種群進一步迭代尋優找出最優解。嵌入爬山操作的遺傳算法能有效地降低其陷入局部最優的缺陷，提高算法的求解性能。

4.2 混合遺傳算法的設計與改進

本文針對遺傳算法容易出現早熟的缺陷，采用局部搜索能力較強的爬山算法與遺傳算法相結合的混合遺傳算法對一般遺傳算法進行改進，并在算法的交叉和變異操作階段設計了自適應交叉、變異概率，且結合爬山算法在遺傳算法的變異操作基礎上引入爬山算子來提高優質的個體被選中的概率，在一定程度上能有效降低遺傳算法早熟的缺陷，提高算法的求解性能，具體設計如下：

（1） 染色體編碼設計

車輛路徑優化問題是一種組合優化問題，本文針對該問題對染色體采用自然數編碼。在經過區域劃分后，本文直接將配送中心和路徑中被訪問的客戶依次編碼成一條染色體，每條染色體對應一條路徑，其編碼方式如（0 7 6 1 9 4 8 2 5 3 0），其具體表述為：配送中心 （0） →客戶 （7） →客戶 （6） →客戶 （1） →客戶 （9） →客戶 （4） →客戶 （8） →客戶 （2） →客戶（5） →客戶 （3） →配送中心 （0）。

（2） 適應度函數

在遺傳算法中適應度的大小是評價個體優劣的重要標志，適應度越大，個體被選中的幾率就越大，適應度函數的選取直接影響遺傳算法的收斂速度以及能否找到最優解。本文需解決的問題是在卷煙配送時使配送總成本最小，即目標函數值最小，故將目標函數轉化為適應度：

式（11）中，Zi表示種群中第i條染色體所對應的的目標函數值，即配送總成本；fi是第i條染色體所對應的適應度，fi越大，被選則的幾率就越大。

（3） 選擇操作

本文采用輪盤賭選擇策略進行選擇，為確保種群的多樣性，在算法的交叉、變異操作階段引入自適應的交叉、變異概率對交叉、變異操作做自適應調整。自適應交叉概率pc和pm變異概率函數引用文獻[10]。

（4） 交叉操作

本文在混合遺傳算法中的交叉操作所采用方法為部分匹配交叉法（PMX）[11]。PMX交叉法與傳統的交叉方式有所不同，以染色體A：123456789，B：987654321為例，先在待交叉的兩個父代上隨機選取兩個交叉位，如A：123|4567|89，B：987|6543|21，然后交換交叉區域，將交叉段放在父體的待交叉的首個基因前，如 A′：6543123456789，B′：4567987654321，再刪去與該交叉段相同的基因，得到最終染色體，如A′′：654312789，B′′：456798321。

PMX交叉法的優點在于在交叉過程中即使有兩個相同的個體存在也同樣能通過交叉操作獲得新的個體，在增加個體多樣性的同時，也在一定程度上降低了早熟現象發生的概率。

（5） 變異操作

為進一步提高種群的多樣性和個體的適應度，本文采用的變異方法為利用倒位變異算子對算法執行變異操作，以染色體A：123456789為例，隨機選取變異位，如A'：123|45678|9，利用上述算子產生的染色體為A''：123876549。

（6） 爬山操作

本文采用基因換位算子來實現遺傳—爬山混合操作，先從父代中隨機選擇兩個基因，交換位置，判斷交換后適應度是否增加，若適應度函數值增加，則用該個體替換原個體，重復爬山操作到預設的次數為止。

（7） 終止準則

本文以迭代次數作為終止準則，若算法搜索達到預設的迭代次數時終止迭代，輸出最優解，否則迭代次數加1繼續迭代，直到滿足預設的迭代次數時算法迭代終止，輸出結果。

4.3 模型求解

本文運用Matlab實現算法，經過大量的試驗不斷的對算法參數進行調整，得出的最佳參數組合為：種群大小：40；最大迭代次數：3 000；最大爬山次數：50；交叉概率：pc1：0.8，pc2：0.5；變異概率：pm1：0.2，pm2：0.002。優化結果如表3所示：

表3 路線優化結果表

從表3中線路優化的結果中可以看出優化后共生成8條路徑方案，各配送區域內的總里程、總需求及客戶數相對均衡，再一次驗證了考慮工作量后對區域劃分的合理性。鑒于篇幅關系文中不一一列出，此處選區域3的配送線路優化結果作為參考，運行后得出的路徑優化圖和迭代圖如圖6、圖7所示：

圖6 區域3車輛運行路線圖

圖7 算法迭代圖

車輛運行路線如下（其中0表示配送中心）：

0→710→772→771→767→746→769→766→768→734→743→742→723→722→721→727→724→726→725→729→730→728→733→752→748→749→750→762→764→770→712→709→708→706→718→717→719→720→735→739→740→744→741→714→761→763→751→760→756→753→757→747→759→758→755→754→765→707→732→731→736→745→716→737→738→713→715→711→0

4.4 優化效果及對比分析

將優化前與優化后的配送進行對比，如表4所示。

表4 優化前與優化后配送對比表

從表4可以看出，優化后的路徑方案比優化前減少3條，配送車輛減少3輛；空載率同比下降25.52%；優化后的配送里程較目前線路同比下降18.71%；優化后配送成本較目前線路成本同比下降25.42%，優化效果明顯。

5 結論

本文以卷煙的配送為背景，針對當下煙草企業卷煙配送存在的問題，運用兩階段法對其配送線路進行優化。文章以Q煙草公司為例，先運用K-means聚類算法對配送區域進行劃分；再在考慮工作量均衡的條件下加入遺傳算法對區域進行調整；最后通過嵌入爬山算法的混合遺傳算法對各配送區域進行線路優化，從配送里程、線路數、總成本、車輛數、空載率等指標上兩階段法的配送效果更優。