李存兵，謝林君，楊金欣

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

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

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

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

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

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

根據(jù)目前煙草物流配送體系特點(diǎn)及要求，需優(yōu)化的問題包括：①確定服務(wù)區(qū)域聚類；②確定中轉(zhuǎn)站，在聚類基礎(chǔ)上以配送量的距離作為指標(biāo)，使配送中心與中轉(zhuǎn)站之間以及中轉(zhuǎn)站與對應(yīng)服務(wù)區(qū)域之間綜合期望代價(jià)最小；③服務(wù)區(qū)域再優(yōu)化，以中轉(zhuǎn)站為中心，使服務(wù)區(qū)域之間配送時(shí)間波動最小化，且分布規(guī)模均勻。

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

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

（1）配送量的距離最小化目標(biāo)：

（2）配送時(shí)間的方差最小化目標(biāo)：

式（7）表示所有中轉(zhuǎn)站對應(yīng)服務(wù)區(qū)域的配送時(shí)間相對均衡，其中SjΔt表示中轉(zhuǎn)站i 對應(yīng)服務(wù)區(qū)域配送時(shí)間方差。

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

式中：xik，yik，xjq，yjq分別表示聚類k，q中零售點(diǎn)i，j的坐標(biāo)，k，q=1，2，3，…，m，m 取聚類k，q 中聚類點(diǎn)較少的數(shù)。

（4）綜上，得到總目標(biāo)函數(shù)：

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

2 改進(jìn)的遺傳聚類算法

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

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

2.1 染色體編碼/解碼機(jī)制

本文中設(shè)計(jì)了一種基于聚類中心的三維實(shí)數(shù)編碼方式?；诰垲愔行牡娜旧w編碼就是將p 個聚類中心作為一串染色體的基因，三維編碼實(shí)現(xiàn)了聚類中心對應(yīng)零售點(diǎn)及位置坐標(biāo)的映射，n維樣本需要p個聚類中心，則染色體結(jié)構(gòu)：

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

2.2 種群初始化

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

2.3 適應(yīng)度函數(shù)

聚類問題的實(shí)質(zhì)是找到某種劃分，使不同類之間存在較大差異性，同一類中的樣本具有較高的相似性。根據(jù)擬求解的問題，適應(yīng)度函數(shù)即為總目標(biāo)函數(shù)：

2.4 選擇算子

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

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

2.5 交叉算子

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

2.6 變異算子

為滿足配送時(shí)間波動最小目標(biāo)，設(shè)計(jì)了基于配送時(shí)間方差最小化自適應(yīng)變異算子，即假設(shè)選取的基因?yàn)閤i，變異后的基因?yàn)閤＇i，兩者之間的選擇原則及關(guān)系：

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

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

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

2.7 算法流程

根據(jù)上述分析，得到精英自適應(yīng)遺傳聚類算法流程，見圖3。

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

3 應(yīng)用效果

3.1 應(yīng)用現(xiàn)狀

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

3.2 數(shù)據(jù)分析

3.2.1 空間聚合度分析

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

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

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

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

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

3.2.2 配送優(yōu)化

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

圖6 不同數(shù)量中心轉(zhuǎn)站的聚類效果Fig.6 Clustering effects for different amount transit stations

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

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

表1 無中轉(zhuǎn)站方案配送效果數(shù)據(jù)（p=0）Tab.1 Delivery effect data with no transit station（p=0）

表2 有1個中轉(zhuǎn)站配送方案效果數(shù)據(jù)（p=1）Tab.2 Delivery effect data with one transit station（p=1）

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

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

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

表3 有2個中轉(zhuǎn)站配送方案效果數(shù)據(jù)（p=2）Tab.3 Delivery effect data with two transit stations（p=2）

表4 有3個中轉(zhuǎn)站配送方案效果數(shù)據(jù)（p=3）Tab.4 Delivery effect data with three transit stations（p=3）

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

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

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

4 結(jié)論

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