基于精英自適應遺傳聚類算法的煙草物流配送優(yōu)化研究

李存兵，謝林君，楊金欣

1. 浙江省煙草公司寧波市公司，浙江省寧波市高新區(qū)凌云路75 號 315000

2. 浙江工業(yè)大學，杭州市下城區(qū)潮王路18 號 310014

3. 浙江省煙草公司紹興市公司，浙江省紹興市人民東路485 號 312000

煙草物流配送中心選址以及服務區(qū)域規(guī)劃是近年來物流系統(tǒng)建設的一個重點，并逐步向煙草行業(yè)要求的“集約化管理，規(guī)?；洜I，專業(yè)化物流，標準化服務”方向發(fā)展[1]。傳統(tǒng)的配送中心選址問題主要采用整數規(guī)劃、重心法、線性規(guī)劃、圖上作業(yè)等方法，對目標函數要求較高，多約束條件處理困難。隨著現(xiàn)代化物流的發(fā)展，啟發(fā)式（Heuristics）和混合智能算法在選址問題上的應用優(yōu)勢越來越明顯。該算法在搜索域中按一定規(guī)則搜索，搜索效率高且結果相對精確，能夠更好地解決物流優(yōu)化問題。劉鵬程等[2]構建了可動態(tài)適應多個分布式電源投切的開關函數，通過引入多種群遺傳算法，提出了分布式電源配電網故障區(qū)段配送方法，有效提高了故障區(qū)段電源的配送效率；任曉智等[3]采用改進的聚類算法和遺傳算法相結合，對煙草物流中轉站、周期配送區(qū)域及線路進行了優(yōu)化；Smieja 等[4]采用部分監(jiān)督的高斯混合模型（C3L）進行聚類分析，通過控制最大初始分類之間的矛盾產生聚類，并結合專家知識和分布數據進行集群檢測，提高了聚類在工程應用中的有效性；Abualigah 等[5]提出了3 種特征選擇與特征權重方案，用于解決動態(tài)降維算法中的聚類問題，通過動態(tài)降低緯度以減少聚類因子，結合遺傳算法、粒子群算法提升聚類速度和聚類性能。將上述算法應用于煙草物流配送則存在初始類核無法完全聚類或者聚類不均勻、算法收斂速度慢等問題。為此，采用配送物流量的距離、配送時間方差、服務區(qū)之間差異等指標，基于傳統(tǒng)遺傳算法構建了一種精英自適應遺傳聚類算法，對配送服務區(qū)域分布和中轉站數量進行優(yōu)化，以期降低物流成本，提高配送效率。

1 配送問題與優(yōu)化策略設計

1.1 配送優(yōu)化問題

根據目前煙草物流配送體系特點及要求，需優(yōu)化的問題包括：①確定服務區(qū)域聚類；②確定中轉站，在聚類基礎上以配送量的距離作為指標，使配送中心與中轉站之間以及中轉站與對應服務區(qū)域之間綜合期望代價最?。虎鄯諈^(qū)域再優(yōu)化，以中轉站為中心，使服務區(qū)域之間配送時間波動最小化，且分布規(guī)模均勻。

1.2 配送服務區(qū)域與中轉站優(yōu)化

為確定服務區(qū)域聚類和中轉站個數、位置，以配送距離、配送量、客戶數、配送時間等為指標，建立目標函數。

（1）配送量的距離最小化目標：

（2）配送時間的方差最小化目標：

式（7）表示所有中轉站對應服務區(qū)域的配送時間相對均衡，其中SjΔt表示中轉站i 對應服務區(qū)域配送時間方差。

（3）不同服務區(qū)域（聚類）之間的差異最大化目標。區(qū)域劃分問題的實質是聚類問題，采用聚類分析中的歐氏距離可以檢驗不同聚類之間的差異性：

式中：xik，yik，xjq，yjq分別表示聚類k，q中零售點i，j的坐標，k，q=1，2，3，…，m，m 取聚類k，q 中聚類點較少的數。

（4）綜上，得到總目標函數：

式（9）是對式（1）、式（7）和式（8）的加權糅合，α，β，γ的大小可根據物流中心的商業(yè)目標做相應調整。若提高α值，需要建立緊湊型聚類；若提高β，γ值，需要關注聚類內部的平衡以及類與類之間的差異性。

2 改進的遺傳聚類算法

遺傳算法是借鑒生物自然選擇和交叉變異遺傳進化機制建立的一種全局優(yōu)化搜索算法，具有優(yōu)越的全局搜索能力，但局部搜索能力不佳，容易早熟。聚類分析是一種分類學與多元分析相結合的多元統(tǒng)計方法，將分類對象置于一個多維空間，依據相似性對樣本自動分類，具有較強的局部搜索能力。常規(guī)的聚類算法有分割和層次兩類，層次算法是指整個數據集分解成樹狀圖子集，直到每個子集只包含一個數據對象，其構建方法有分裂和合并兩種；分割算法是根據目標數據到聚類中心的距離進行迭代的算法。Barreto等[6]專門對選址和路徑規(guī)劃方法進行了比較分類，見圖1。本文中提出的遺傳聚類分析方法是將改進的遺傳算法應用于聚類分析中，使分類過程既可用于局部范圍搜索，也可在全局范圍搜索分類，提高了聚類速度，且聚類結果可靠。

圖1 聚類方法分類Fig.1 Classification of clustering methods

2.1 染色體編碼/解碼機制

本文中設計了一種基于聚類中心的三維實數編碼方式?；诰垲愔行牡娜旧w編碼就是將p 個聚類中心作為一串染色體的基因，三維編碼實現(xiàn)了聚類中心對應零售點及位置坐標的映射，n維樣本需要p個聚類中心，則染色體結構：

每條染色體的長度為3×p×n，其坐標和需求量向量依附于編號基因，這種編碼方式包含的信息量較大，易于后續(xù)模型求解，也避免了二進制編碼反復編、譯碼的問題。

2.2 種群初始化

種群初始化是隨機產生一個初始種群的過程。在事先確定p 個中轉站的基礎上，首先利用一般聚類算法進行第一次分類，得到p 個初始聚類中心，根據編碼方式構成染色體，作為遺傳聚類的精英初始種群。由于聚類算法每次聚類得到的聚類中心存在差異性，重復此步驟若干次，直至構成初始種群規(guī)模。

2.3 適應度函數

聚類問題的實質是找到某種劃分，使不同類之間存在較大差異性，同一類中的樣本具有較高的相似性。根據擬求解的問題，適應度函數即為總目標函數：

2.4 選擇算子

將精英主義選擇與輪盤賭注方法相結合[7-8]，計算父代染色體適應度，保留并復制適應度最高的染色體后進入下一代，對剩余染色體采用輪盤賭注方法選擇，第i條染色體的選擇概率：

在輪盤賭注方法中，輪盤轉動N次（初始種群的數量），每轉動一次產生一個被比較的個體。該個體的選擇概率與一個隨機產生的0～1之間的實數γ相比較，如果Pi-1＜r＜Pi，則選擇Pi。

2.5 交叉算子

為擴大搜索區(qū)域，使染色體向著適應度高的方向發(fā)展，選用了部分映射交叉法[9-10]，即在隨機的兩條染色體中選取片段確定映射關系，交換雙親中的子串，并利用映射關系使后代合法化，見圖2。

2.6 變異算子

為滿足配送時間波動最小目標，設計了基于配送時間方差最小化自適應變異算子，即假設選取的基因為xi，變異后的基因為x＇i，兩者之間的選擇原則及關系：

式（13）表示選擇聚類（服務區(qū)域）配送時間方差最大的基因（聚類中心）作為變異基因位。式（14）表示變異后的基因表達式，Δ（Tc，X）為變異步長，X 是變異選擇范圍，r 是服從（0，1）均勻分布的隨機數，λ是系統(tǒng)參數。Tc是變異溫度，在本文中定義為：

圖2 映射交叉算法Fig.2 Mapping crossover algorithm

由式（16）可知，配送時間方差越大，表示變異步長越大，染色體產生的變異范圍隨之增大。本文中設計的基于配送時間的自適應變異算子，能夠依據配送時間最大限度地產生新染色體，使之向著適應度高的方向發(fā)展，有效避免早熟現(xiàn)象。

2.7 算法流程

根據上述分析，得到精英自適應遺傳聚類算法流程，見圖3。

圖3 算法流程圖Fig.3 Algorithm flowchart

3 應用效果

3.1 應用現(xiàn)狀

浙江省煙草公司下屬某市公司現(xiàn)有1 個物流配送中心、1個分中心、3個中轉站，承擔全市26 000余零售戶的卷煙配送任務。通過對成本、效率和服務等物流配送指標進行綜合評價，發(fā)現(xiàn)目前配送體系存在物流成本過高、配送效率較低等問題。該公司擬建設新物流配送中心，撤銷現(xiàn)有配送中心和分中心，對中轉站及對應服務區(qū)域進行重新調整和劃分，達到降低物流成本、提高配送效率的目的。

3.2 數據分析

3.2.1 空間聚合度分析

根據Barreto 等[6]的研究結論，從獲得最優(yōu)解的次數看，從下而上的二階段方法性能最好；從求解的平均結果看，自下而上的一階段方法和直接指派方法的效果最好。因此，利用文獻[6]中的聚類算法對煙草配送問題進行求解，并將3種方法與本文中提出的精英自適應遺傳聚類算法的空間聚合度進行對比，結果見圖4。

圖4 傳統(tǒng)算法與精英自適應遺傳聚類算法空間聚合度對比Fig.4 Comparison of spatial aggregation between traditional algorithm and self-adaptive elitist-based genetic clustering algorithm

圖4a可見，從總體上看聚類效果可以接受，但存在兩個問題：①每類的容量規(guī)模分布不平衡，特別是邊遠地區(qū)存在一些小類，影響配送車輛利用率；②少數類之間存在相互交叉重疊現(xiàn)象，對路徑規(guī)劃效率產生不利影響。圖4b可見，最大的幾個類每個都覆蓋了很大一塊區(qū)域，因此需要進行第二階段調整，即對這塊區(qū)域重新聚類。Barreto等使用的最大測試數是318 個零售點，而該地區(qū)有25 956 個零售點。因此，該方法在Barreto等的研究中應用效果較好，但在本文中的大規(guī)模區(qū)域仍存在一定困難。圖4c 可見，從總體上看聚類效果可以接受，但最終類的效果無法與初始類核完全聚合，故不能找到穩(wěn)定的求解結果。圖4d可見，每個類的分布規(guī)模較均勻，空間聚合度也較高，可以對實際問題進行求解。

參數設置：種群數N=100，迭代次數T=100，交叉概率Pc=0.8，變異概率為自適應值，系統(tǒng)參數λ=1。利用Matlab進行計算，本文算法與K-mean聚類算法的計算結果見圖5。可見，本文算法比K-mean 聚類算法收斂速度更快，收斂目標值也更優(yōu)，表明本文算法具有可行性和實效性。

圖5 本文算法與K-mean聚類算法適應度曲線Fig.5 Convergence curves of the designed lgorithm and K-mean clustering algorithm

3.2.2 配送優(yōu)化

將整個配送區(qū)域均分為40×40點陣，共1 600個候選點，相鄰候選點東西間距4 km，南北間距3.6 km，給定中轉站和配送中心數量，以最小總里程為目標，計算最佳選址方案。分別選取中轉站個數p=0，1，2，3，運用本文中提出的算法進行聚類，效果見圖6。

圖6 不同數量中心轉站的聚類效果Fig.6 Clustering effects for different amount transit stations

圖6a 方案無中轉站只有一個配送中心（紅點所示）。由表1可見，配送總里程38 682.04 km，直送率達到100%。

圖6b 方案有1 個中轉站（紅色三角形所示）和1個配送中心（紅點所示）。由表2可見，中轉站安排在區(qū)域A，配送總里程30 729 km，零售戶直送率和按量直送率分別為70.9%和74.9%。

表1 無中轉站方案配送效果數據（p=0）Tab.1 Delivery effect data with no transit station（p=0）

表2 有1個中轉站配送方案效果數據（p=1）Tab.2 Delivery effect data with one transit station（p=1）

圖6c 方案有2 個中轉站（紅色三角形所示）和1個配送中心（紅點所示）。由表3可見，中轉站分別安排在區(qū)域A 和區(qū)域B，配送總里程26 153 km，零售戶直送率和按量直送率分別為51.8%和55.4%。

圖6d 方案有3 個中轉站（紅色三角形所示）和1個配送中心（紅點所示）。由表4可見，中轉站分別安排在區(qū)域A、區(qū)域B 和區(qū)域C，配送總里程24 648 km。方案d 與優(yōu)化前3 個中轉站模式相比，零售戶直送率由27.6%提高至35.0%，按量直送率由38.5%提高至41.4%，總里程由26 000 km 降低至24 648 km，所有中轉站對應的服務區(qū)域分布也更加均衡。

集中配送可以降低配送成本，因此配送中心選址的最優(yōu)位置應在配送最集中的區(qū)域。由圖7可見，該地區(qū)卷煙銷量集中區(qū)域與采用方案d規(guī)劃的配送效果相符合。

表3 有2個中轉站配送方案效果數據（p=2）Tab.3 Delivery effect data with two transit stations（p=2）

表4 有3個中轉站配送方案效果數據（p=3）Tab.4 Delivery effect data with three transit stations（p=3）

以浙江省各市煙草物流成本、分揀、倉庫儲存等指標為對象進行對比，結果見圖8。某市未優(yōu)化前萬支卷煙物流成本遠高于全省平均水平，優(yōu)化后略低于全省平均值；未優(yōu)化前萬支分揀、倉庫費用明顯高于全省平均水平，優(yōu)化后顯著降低，但各指標仍未達到全省最低值，原因在于該市年平均人工費用124 302 元/年，人工成本較高，且該市處于丘陵地帶，擬建設的配送中心所處地理位置也造成物流配送成本較高。

圖7 卷煙銷量集中區(qū)域分布Fig.7 Distribution of major cigarette markets

圖8 優(yōu)化前后物流成本對比Fig.8 Comparison of logistics costs before and after optimization

4 結論

針對配送中心選址以及服務區(qū)域規(guī)劃問題，提出了配送物流量的距離最小化、配送時間的方差最小化、不同服務區(qū)域之間差異最大化的目標，通過加權糅合構建綜合目標模型，并設計了精英自適應遺傳聚類算法進行求解，提高了聚類收斂速度，避免了早熟現(xiàn)象，使聚類的區(qū)域分布更加均衡。以浙江省某市煙草物流配送中心為對象進行測試，結果表明：①利用本文算法實現(xiàn)了對應服務區(qū)域和中轉站的確定以及聚類區(qū)域的優(yōu)化，分別對中轉站個數p=0，1，2，3 進行優(yōu)化分析，其中3 個中轉站模式優(yōu)化后，零售戶直送率提高7.4 百分點，按量直送率提高2.9 百分點，總里程減少1 352 km，所有中轉站對應的服務區(qū)域分布較均衡；②優(yōu)化后萬支卷煙物流成本、分揀和倉庫費用顯著降低，低于浙江省平均水平；③該地區(qū)卷煙銷量集中區(qū)域與采用本文算法規(guī)劃的配送效果相符合。本文算法具有一定的可行性和實用性，有利于降低物流成本，提高物流配送效率。