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

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

0 引言

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

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

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

本文以Q市雨山、花山兩區(qū)周三的送貨線路為例運(yùn)用兩階段法對其進(jìn)行分析，在其既定的服務(wù)范圍內(nèi)進(jìn)行線路優(yōu)化。由于全市卷煙配送問題具有通性，該區(qū)域的優(yōu)化思路可適當(dāng)應(yīng)用到全市。

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

圖1 客戶分布圖

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

（1）K值的確定

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

（2） 初始聚類結(jié)果

利用K-means聚類算法對零售戶進(jìn)行聚類，初始聚類結(jié)果如圖3所示：

根據(jù)圖3的聚類結(jié)果對聚類后各區(qū)域所含的客戶數(shù)和總需求量進(jìn)行統(tǒng)計(jì)匯總，如表1所示：

圖3 初始聚類結(jié)果圖

表1 聚類后各區(qū)域客戶數(shù)及需求量統(tǒng)計(jì)表

2 考慮工作量均衡的區(qū)域劃分調(diào)整

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

根據(jù)上述思路對區(qū)域做進(jìn)一步優(yōu)化調(diào)整，其聚類中心的選取收斂圖及各區(qū)域的劃分圖如圖4、圖5所示。

圖4 優(yōu)化調(diào)整后聚類中心收斂圖

圖5 優(yōu)化調(diào)整后區(qū)域劃分圖

從圖4聚類中心的收斂圖中可以看出約在45代左右算法達(dá)到收斂，即各區(qū)域內(nèi)聚類中心達(dá)到穩(wěn)定狀態(tài)。圖5為優(yōu)化調(diào)整后的區(qū)域劃分圖，將優(yōu)化后各聚類所含客戶數(shù)和總需求進(jìn)行匯總，如表2所示：

表2 各聚類客戶數(shù)及需求表

從表2中可以看出各區(qū)域內(nèi)的客戶數(shù)量和總需求量都相對均衡，且車輛利用率較高，區(qū)域8有186戶，是因?yàn)閰^(qū)域8處于市中心地段，客戶相對集中，區(qū)域3中的客戶數(shù)為67戶，相對較少，是因?yàn)閰^(qū)域3離市區(qū)較遠(yuǎn)且客戶位置分布較為分散。

3 卷煙配送線路優(yōu)化模型的建立

（1） 問題描述

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

（2） 數(shù)學(xué)模型的構(gòu)建

通過對Q煙草公司卷煙配送中心的實(shí)地調(diào)查和根據(jù)現(xiàn)實(shí)中的實(shí)際配送情況對問題進(jìn)行適當(dāng)?shù)某橄蠛秃喕?，以配送總成本最小為目?biāo)建立數(shù)學(xué)模型。

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

（3） 模型變量說明

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

4 基于混合遺傳算法的卷煙配送線路優(yōu)化

4.1 混合遺傳算法原理

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

4.2 混合遺傳算法的設(shè)計(jì)與改進(jìn)

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

（1） 染色體編碼設(shè)計(jì)

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

（2） 適應(yīng)度函數(shù)

在遺傳算法中適應(yīng)度的大小是評價(jià)個(gè)體優(yōu)劣的重要標(biāo)志，適應(yīng)度越大，個(gè)體被選中的幾率就越大，適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。本文需解決的問題是在卷煙配送時(shí)使配送總成本最小，即目標(biāo)函數(shù)值最小，故將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度：

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

（3） 選擇操作

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

（4） 交叉操作

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

PMX交叉法的優(yōu)點(diǎn)在于在交叉過程中即使有兩個(gè)相同的個(gè)體存在也同樣能通過交叉操作獲得新的個(gè)體，在增加個(gè)體多樣性的同時(shí)，也在一定程度上降低了早熟現(xiàn)象發(fā)生的概率。

（5） 變異操作

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

（6） 爬山操作

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

（7） 終止準(zhǔn)則

本文以迭代次數(shù)作為終止準(zhǔn)則，若算法搜索達(dá)到預(yù)設(shè)的迭代次數(shù)時(shí)終止迭代，輸出最優(yōu)解，否則迭代次數(shù)加1繼續(xù)迭代，直到滿足預(yù)設(shè)的迭代次數(shù)時(shí)算法迭代終止，輸出結(jié)果。

4.3 模型求解

本文運(yùn)用Matlab實(shí)現(xiàn)算法，經(jīng)過大量的試驗(yàn)不斷的對算法參數(shù)進(jìn)行調(diào)整，得出的最佳參數(shù)組合為：種群大?。?0；最大迭代次數(shù)：3 000；最大爬山次數(shù)：50；交叉概率：pc1：0.8，pc2：0.5；變異概率：pm1：0.2，pm2：0.002。優(yōu)化結(jié)果如表3所示：

表3 路線優(yōu)化結(jié)果表

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

圖6 區(qū)域3車輛運(yùn)行路線圖

圖7 算法迭代圖

車輛運(yùn)行路線如下（其中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 優(yōu)化效果及對比分析

將優(yōu)化前與優(yōu)化后的配送進(jìn)行對比，如表4所示。

表4 優(yōu)化前與優(yōu)化后配送對比表

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

5 結(jié)論

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