基于聚類分析的煙草物流配送線路優(yōu)化算法的研究與應(yīng)用

任曉智，賓彬超

1.廣西大學(xué)機(jī)械工程學(xué)院，南寧市鄉(xiāng)塘區(qū)大學(xué)路100號(hào) 530004

2.廣西壯族自治區(qū)煙草專賣局，南寧市青秀區(qū)茶花園路25號(hào) 530022

現(xiàn)代物流已經(jīng)越來越受到各國、各行業(yè)、各大型企業(yè)的重視和積極推進(jìn)，配送更是現(xiàn)代物流發(fā)展的重中之重［1］。如何經(jīng)濟(jì)高效地組織配送，保證配送過程的低成本、高效率運(yùn)作，為客戶提供更完善的增值服務(wù)，增強(qiáng)對(duì)零售網(wǎng)點(diǎn)服務(wù)質(zhì)量的監(jiān)控等，是目前物流配送的主要研究對(duì)象，受到國內(nèi)外研究機(jī)構(gòu)的廣泛重視［2］。國外研究人員已取得了許多成果，Higgins［3］針對(duì)配電網(wǎng)合理規(guī)劃設(shè)計(jì)，提出了物流配送模型，對(duì)區(qū)域分布進(jìn)行掃描，完成整體布局的優(yōu)化控制。Tan［4］采用智能啟發(fā)式方法計(jì)算求解車輛路徑問題，從而實(shí)現(xiàn)了減少配送次數(shù)的目的，利用智能路徑計(jì)算完成了對(duì)相關(guān)區(qū)域的有效連接，減少配送過程中的線路冗余。隨著人工智能技術(shù)的發(fā)展，包括模擬退火算法、遺傳算法、BP 神經(jīng)網(wǎng)絡(luò)、聚類分析等都為物流配送線路的優(yōu)化提供了新方法。例如，Cooper［5］在2007年介紹了運(yùn)輸選址的綜合考慮模式，從而可以獲得優(yōu)化的配送路線；潘魯寧等［6］將MAS 應(yīng)用于物流配送，實(shí)現(xiàn)了自組織、動(dòng)態(tài)優(yōu)化配送路線的先進(jìn)模式，解決了分配量變化導(dǎo)致動(dòng)態(tài)差異而產(chǎn)生冗余的問題；Taranrilis 等［7］在2002年設(shè)計(jì)的空間決策支持系統(tǒng)實(shí)現(xiàn)了配送線路優(yōu)化的問題。在我國對(duì)物流配送也有較多研究，如郎茂祥等［8］建立的物流配送路徑優(yōu)化數(shù)學(xué)模型，針對(duì)遺傳算法在局部搜索能力方面的缺點(diǎn)，采用爬山算法構(gòu)造了求解物流配送路徑的混合遺傳算法，可在一定程度上提高局部搜索能力。李金蘋［9］提出在考慮時(shí)間窗的條件下用節(jié)約法解決非滿載運(yùn)輸問題的優(yōu)化算法，并通過實(shí)驗(yàn)測試了配送的效果。陳艷艷等［10］通過將區(qū)域地理信息與遺傳算法的決策相結(jié)合，提出了綜合優(yōu)化決策模型，實(shí)現(xiàn)了配送數(shù)據(jù)的連續(xù)性，利用遺傳算法優(yōu)化決策，使配送成本降低。國內(nèi)在煙草配送方面進(jìn)行的研究有采用GIS 優(yōu)化配送路線、通過各種算法設(shè)計(jì)最短路徑、通過GSM 網(wǎng)絡(luò)提高配送通信等［11-12］。在煙草配送過程中，即使是同一種地形或同一建筑布局，由于地方文化的差異而具有不同的配送風(fēng)格，因此目前大部分文獻(xiàn)所提到的優(yōu)化方案一般僅針對(duì)該地區(qū)的配送優(yōu)化，僅限于對(duì)地形和路線的優(yōu)化，不考慮地區(qū)特點(diǎn)。為此，基于聚類分析算法對(duì)廣西煙草物流配送過程進(jìn)行了優(yōu)化設(shè)計(jì)，針對(duì)的不是地形而是配送行徑路線，即使有地方特色也不影響優(yōu)化結(jié)果，以進(jìn)一步提高煙草行業(yè)物流管理水平，并使之與營銷系統(tǒng)整合，提高企業(yè)的整體競爭力。

1 優(yōu)化策略設(shè)計(jì)

在廣西煙草物流優(yōu)化過程中所要解決的問題是降低全自治區(qū)商業(yè)企業(yè)的物流配送成本、節(jié)省能源消耗、提高客戶的滿意度、實(shí)現(xiàn)低耗綠色和可持續(xù)發(fā)展。這類實(shí)際問題由于其規(guī)模、問題約束條件的復(fù)雜性等，不可能采用精確算法如線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃等方法來解決，所能接受的算法都是基于啟發(fā)式（heuristics）算法，有些要借助于新發(fā)展起來的所謂智能優(yōu)化（metaheuristic）方法以獲得更好的解決方案。在廣西煙草物流優(yōu)化過程中，由于問題規(guī)模大、特性復(fù)雜，采用了解決組合優(yōu)化問題中常用的“分而治之”(divide-and-conquer)的策略，其主要思想是把原來的問題根據(jù)商業(yè)運(yùn)行的特點(diǎn)，分成若干個(gè)相對(duì)獨(dú)立的小問題，然后再利用算法分別解決這些規(guī)模相對(duì)較小的問題。問題自身規(guī)模減小，求解效率可以提高，同時(shí)這些相對(duì)獨(dú)立的問題可以平行處理，在多核的硬件環(huán)境下操作簡單。

根據(jù)對(duì)廣西煙草物流優(yōu)化問題的特性和其商業(yè)運(yùn)作的要求，將整個(gè)問題解決過程分為3 大步驟：①中轉(zhuǎn)站的區(qū)域規(guī)劃。主要是針對(duì)所給定的區(qū)域，包含煙草零售戶和現(xiàn)有的中轉(zhuǎn)站，確定若干個(gè)中轉(zhuǎn)站，使這些中轉(zhuǎn)站所對(duì)應(yīng)服務(wù)的零售戶的期望代價(jià)為最小。②周期配送區(qū)域（片區(qū)時(shí)間區(qū)域）的規(guī)劃。根據(jù)每個(gè)中轉(zhuǎn)站的服務(wù)區(qū)域，即所對(duì)應(yīng)的服務(wù)對(duì)象（零售戶），根據(jù)送貨周期，例如一周5 天或7 天等，確定周期中每天的配送區(qū)域。與步驟①同理，所追求的目標(biāo)是使整個(gè)周期配送的期望代價(jià)為最小，同時(shí)還要考慮每個(gè)配送區(qū)域應(yīng)相對(duì)平衡，避免對(duì)配送資源的需要有大起大落現(xiàn)象，以便于管理。③線路優(yōu)化。對(duì)每天的配送區(qū)域以及零售戶的需求、配送運(yùn)行所能獲得的資源（車輛、駕駛?cè)藛T等）構(gòu)造合理的配送線路。其目標(biāo)是在滿足一定商業(yè)約束條件下使每天配送運(yùn)行成本為最低，提高生產(chǎn)效率（裝車率、每條線路送貨的門店數(shù)等）和客戶的滿意度。

2 中轉(zhuǎn)站的區(qū)域規(guī)劃

2.1 區(qū)域規(guī)劃設(shè)計(jì)

中轉(zhuǎn)站區(qū)域規(guī)劃是利用道路、零售戶、中轉(zhuǎn)站等數(shù)據(jù)，從現(xiàn)有的中轉(zhuǎn)站中選出p 個(gè)中轉(zhuǎn)站（p≤中轉(zhuǎn)站個(gè)數(shù)），其目的是降低服務(wù)代價(jià)（運(yùn)輸成本等）。本研究采用運(yùn)籌學(xué)中著名的p-中位（p-median）方法進(jìn)行區(qū)域規(guī)劃設(shè)計(jì)，其對(duì)應(yīng)數(shù)學(xué)模型可表達(dá)為：給定一組可以被用來設(shè)立p 個(gè)中轉(zhuǎn)站的點(diǎn)的集合I={1,...,n},一組客戶點(diǎn)J={1,...,m},以及一個(gè)n×m 維的矩陣，gij表示從中轉(zhuǎn)站去服務(wù)客戶的費(fèi)用，那么p-中位問題所要解決的就是從I 中找出p 個(gè)中轉(zhuǎn)站的總服務(wù)費(fèi)用或加權(quán)費(fèi)用（客戶的需求乘以到中轉(zhuǎn)站的距離）為最低。如果所有的客戶都需要得到服務(wù)，其目標(biāo)函數(shù)可表達(dá)為：

由式(1)可知，當(dāng)問題的規(guī)模達(dá)到一定程度時(shí)，無法用精確算法在給定計(jì)算時(shí)間內(nèi)獲得求解。而結(jié)合聚類問題分析方法，則可以在不精確計(jì)算的條件下獲得最優(yōu)解。

2.2 區(qū)域規(guī)劃算法步驟及結(jié)果

本研究采用的是一種啟發(fā)式算法。由于啟發(fā)式算法存在容易陷入局部最優(yōu)的缺陷，所以還輔助采用了一些智能化策略，以盡量避免局部最優(yōu)而達(dá)不到全局最優(yōu)的效果。算法的具體求解過程是：①數(shù)據(jù)準(zhǔn)備工作。計(jì)算出每個(gè)零售戶到所有可能中轉(zhuǎn)站的最短距離（行駛時(shí)間或行駛距離），并計(jì)算出相應(yīng)的加權(quán)費(fèi)用（距離乘以需求）。②產(chǎn)生初始解集合。先生成一個(gè)空的初始解集合，然后執(zhí)行以下步驟q 次，q 值可根據(jù)問題的規(guī)模和所給定參數(shù)確定。③改進(jìn)解集合中的每個(gè)解。對(duì)解集合中的各個(gè)初始解分別進(jìn)行改進(jìn)，以取得更好的結(jié)果。④對(duì)解集合進(jìn)行總體改進(jìn)并產(chǎn)生最終結(jié)果。合并2 個(gè)或多個(gè)解，它們的結(jié)合有可能把整個(gè)求解的方向引導(dǎo)到一個(gè)全新的搜索方向，從而產(chǎn)生另一個(gè)全新的解。

優(yōu)化結(jié)果如圖1 所示，原有中轉(zhuǎn)站10 個(gè)，優(yōu)化后為7 個(gè)。其中對(duì)西南區(qū)域和東北區(qū)域的中轉(zhuǎn)站進(jìn)行了調(diào)整，包括站點(diǎn)位置和覆蓋區(qū)域。優(yōu)化后減少了中轉(zhuǎn)站和總配送點(diǎn)個(gè)數(shù)，節(jié)省了中轉(zhuǎn)站的調(diào)配費(fèi)用，簡化了配送結(jié)構(gòu)。由于在優(yōu)化過程中調(diào)整了配送路線，圖1（a）中的路線較密集，而圖1（b）中的路線較寬松，在外圍的路線設(shè)置中注重區(qū)域的統(tǒng)一，不再為單點(diǎn)產(chǎn)生多余的路線，總體的配送網(wǎng)絡(luò)連接則能覆蓋整個(gè)區(qū)域。區(qū)域規(guī)劃的設(shè)置采用隨距離變化的聚類分析算法，將距離、行進(jìn)路線相近的劃分為一類，再將每個(gè)小區(qū)域構(gòu)成一個(gè)類，最后對(duì)每類的最優(yōu)連接進(jìn)行分析，從而得到配送點(diǎn)位置。

圖1 廣西崇左市轄區(qū)優(yōu)化前后中轉(zhuǎn)站位置及分布

3 片區(qū)時(shí)間區(qū)域的規(guī)劃

3.1 片區(qū)時(shí)間規(guī)劃設(shè)計(jì)

中轉(zhuǎn)站確定后，需要對(duì)每個(gè)中轉(zhuǎn)站配送的片區(qū)時(shí)間進(jìn)行規(guī)劃。根據(jù)每個(gè)中轉(zhuǎn)站不同的商業(yè)運(yùn)營模式，在一個(gè)配送周期（以一周為例）中配送的天數(shù)不同，因此需要為每個(gè)中轉(zhuǎn)站所服務(wù)的區(qū)域建立配送時(shí)間區(qū)域，每個(gè)時(shí)間區(qū)域?qū)⒃谀骋惶毂环?wù)。該類問題被稱為聚類（clustering）問題，其中心思想是產(chǎn)生若干個(gè)點(diǎn)的聚類，任何一對(duì)節(jié)點(diǎn)在同類之間所期望的運(yùn)行（行駛）成本相對(duì)于不同類而言為最小。系統(tǒng)對(duì)應(yīng)的目標(biāo)函數(shù)值：

式中：xi和yi是各個(gè)零售戶的坐標(biāo)，Xk和Yk是聚類k的中心坐標(biāo)。

聚類分析算法適合解決不同類型的聚類問題，但并不適合解決本研究所涉及的時(shí)間區(qū)域規(guī)劃問題，這是因?yàn)槌诵旭偩嚯x或時(shí)間外，還需要考慮各時(shí)間區(qū)域的平衡，保證各時(shí)間區(qū)域不沖突，否則就會(huì)出現(xiàn)一個(gè)零售戶的隔壁周一送了貨，而他本身要等到周五才能得到貨（即周一的區(qū)域和周五的區(qū)域有相交）。為解決該問題，不僅要對(duì)地形進(jìn)行分析優(yōu)化，而且需兼顧行駛時(shí)間（距離）和各區(qū)域平衡，使優(yōu)化因子包括地區(qū)特點(diǎn)等因素對(duì)配送路線的影響，并使得目標(biāo)函數(shù)值f 為最?。?/p>

其中，Dist 是總距離之和（聚類中心到任何一個(gè)屬于此聚類的節(jié)點(diǎn)的行駛距離或時(shí)間），Dev 是各聚類需求的方差之和，如果把所有的需求疊加起來并除以節(jié)點(diǎn)數(shù)，可以獲得平均的需求量q’。如果用m 表示在一個(gè)聚類中的節(jié)點(diǎn)數(shù)，那么希望該聚類的需求總和要盡量趨近于m×q’；如果所有節(jié)點(diǎn)的需求量都為1，在為相同需求量的節(jié)點(diǎn)提供配送時(shí)，其所要達(dá)到的目標(biāo)h（配送中心）中所含的節(jié)點(diǎn)個(gè)數(shù)應(yīng)基本相同。該數(shù)據(jù)可以通過配送總量和中心節(jié)點(diǎn)個(gè)數(shù)計(jì)算出來，并得到該聚類需求量的方差值。在目標(biāo)函數(shù)（3）中a1和a2分別是距離和需求量方差的權(quán)重，根據(jù)不同的商業(yè)需求可以進(jìn)行調(diào)整。如果a1的值高，表明需要建立緊湊的聚類；如果a2的值高，表明更需要注重與聚類的平衡問題。

3.2 片區(qū)時(shí)間規(guī)劃算法步驟及結(jié)果

在給出定義之后，假設(shè)要建立k 個(gè)時(shí)間片區(qū)，具體的聚類算法步驟如下：

（1）初始步驟。計(jì)算每對(duì)節(jié)點(diǎn)之間的行駛距離或行駛時(shí)間，包括中轉(zhuǎn)站與零售戶節(jié)點(diǎn)間的行駛時(shí)間和距離。構(gòu)造初始的聚類，如果有給定的種子點(diǎn)，此時(shí)每個(gè)初始聚類只包含對(duì)應(yīng)的種子點(diǎn)。如果種子點(diǎn)沒有給定，可以隨機(jī)選取k 個(gè)節(jié)點(diǎn)（區(qū)域內(nèi)的配送節(jié)點(diǎn)）作為種子點(diǎn)，構(gòu)造初始聚類，并確定每個(gè)聚類的中心點(diǎn)。

（2）聚類的構(gòu)造。如果所有的節(jié)點(diǎn)（零售戶）都已分配到相應(yīng)的聚類，轉(zhuǎn)入步驟3。對(duì)于沒有分配的節(jié)點(diǎn)，針對(duì)每個(gè)聚類計(jì)算其加入該聚類可能產(chǎn)生的費(fèi)用，即目標(biāo)函數(shù)（3）的增量。在未被分配的節(jié)點(diǎn)中選擇具有最小加入費(fèi)用的節(jié)點(diǎn)，加入到對(duì)應(yīng)聚類中，并更新此聚類的中心點(diǎn)，重復(fù)步驟2。

（3）聚類的改進(jìn)。從全局的角度出發(fā)，對(duì)步驟2 中產(chǎn)生的聚類進(jìn)行改進(jìn)，主要是通過節(jié)點(diǎn)的轉(zhuǎn)移從一個(gè)聚類轉(zhuǎn)移到另一個(gè)聚類，或節(jié)點(diǎn)互換，即節(jié)點(diǎn)所對(duì)應(yīng)的聚類互換，其目的都是改進(jìn)目標(biāo)函數(shù)（3）的值。在該步驟中還要考慮轉(zhuǎn)移和互換操作的可行性，也就是“鄰居點(diǎn)”的關(guān)系不能被破壞。

在步驟2 和步驟3 中，每次計(jì)算目標(biāo)函數(shù)（3）的值或其增量非常耗時(shí)。為提高計(jì)算效率，與選址問題的算法類似，可以采用GRASP（General Resource Allocation and Scheduling Program）策略。在此基礎(chǔ)上獲得的種子點(diǎn)的聚類結(jié)果見圖2。圖中各點(diǎn)表示在該行政區(qū)域中每個(gè)需要配送的銷售網(wǎng)點(diǎn)，而黑色三角標(biāo)號(hào)表示不同行政區(qū)域的中轉(zhuǎn)交換點(diǎn)。每個(gè)中轉(zhuǎn)交換點(diǎn)以最大的銷售網(wǎng)點(diǎn)聚合，且在該區(qū)域的主干交通線上，可保障其不受交通的影響。

4 線路優(yōu)化

當(dāng)配送片區(qū)設(shè)計(jì)規(guī)劃好每個(gè)中轉(zhuǎn)站后，可根據(jù)每個(gè)片區(qū)中客戶的需求、中轉(zhuǎn)站所能提供的配送資源、執(zhí)行配送人員的作息時(shí)間、中轉(zhuǎn)站的開發(fā)和關(guān)閉時(shí)間、客戶對(duì)配送的特殊要求（送貨的時(shí)間窗、車輛到達(dá)后的卸貨等），確定車輛的配送路線。從數(shù)學(xué)模型上而言，需要解決帶有時(shí)間窗的車輛線路優(yōu)化問題。

線路優(yōu)化問題是針對(duì)給定的一組需要服務(wù)的客戶點(diǎn)、中轉(zhuǎn)站或配送中心，所能利用的配送資源，根據(jù)客戶的需要和資源等約束條件構(gòu)造的一組配送線路，確定哪些客戶由哪輛車服務(wù)以及配送順序，其目標(biāo)是使配送或服務(wù)成本為最低。

5 結(jié)語

基于聚類分析的線路優(yōu)化方式，給出了優(yōu)化算法模型及步驟，并對(duì)廣西煙草物流配送線路區(qū)域進(jìn)行了規(guī)劃設(shè)計(jì)，不但考慮了配送成本和時(shí)間，還兼顧到地方區(qū)域的接收能力及特點(diǎn)，實(shí)現(xiàn)了煙草物流配送線路的優(yōu)化，從而為各煙草接收網(wǎng)點(diǎn)提供了快速、高效的配送服務(wù)。優(yōu)化后中轉(zhuǎn)站數(shù)量由10 個(gè)減少為7 個(gè)，總配送路線減少30%，配送節(jié)點(diǎn)更集中，有效節(jié)省了配送費(fèi)用和配送時(shí)間，提高了運(yùn)營效率，提升了煙草行業(yè)物流管理水平。

［1］張曉靜，秦存永，朱風(fēng)鵬.國內(nèi)10 省區(qū)煙葉中重金屬含量的差異與聚類分析［J］.煙草科技，2012（10）：53-57.

［2］王能如，何寬信，黎茶根.江西烤煙主要化學(xué)特性的適宜性評(píng)價(jià)和聚類分析［J］.煙草科技，2012（8）：52-56.

［3］Higgins J C.On the merits of simple models in distribution planning［J］.International Journal of Physical Distribution，2006，1（2）：144-148.

［4］Tan K C.Artificial intelligence heuristics in solving vehicle routing problems with time window constraints ［J］.Engineering Applications of Artificial Intelligence，2001，1（14）：825-837.

［5］Cooper L.The transportation-location problem［J］.Operations Research，2007，1（20）：94-108.

［6］潘魯寧，趙林度.基于MAS 的物流運(yùn)輸路徑動(dòng)態(tài)規(guī)劃［J］.物流技術(shù)，2003（12）：64-66.

［7］Tarankilis C D，Kiranondis C T.Using a spatial decision support system for solving the vehicle routing problem［J］.Information ＆ Management，2004，1（39）：359-375.

［8］郎茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究［J］.中國管理科學(xué).2002（5）：52-57.

［9］李金蘋.現(xiàn)代物流配送系統(tǒng)的運(yùn)輸優(yōu)化調(diào)度方案［J］.物流技術(shù)，2002（5）：9-11.

［10］陳艷艷，宋健民.基于地理信息系統(tǒng)及遺傳算法的道路規(guī)劃［J］.計(jì)算機(jī)工程與應(yīng)用，2002（3）：21-22.

［11］丁一，林國龍.煙草配送中心多階段物流系統(tǒng)分析及應(yīng)用［J］.煙草科技，2012（10）：18-22.

［12］汪壽陽，趙秋紅，夏國平.集成物流管理系統(tǒng)中的定位運(yùn)輸線路安排問題的研究［J］.管理科學(xué)學(xué)報(bào)，2004，3（2）：69-75.