任曉智，賓彬超

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

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

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

1 優(yōu)化策略設計

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

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

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

2.1 區(qū)域規(guī)劃設計

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

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

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

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

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

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

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

3.1 片區(qū)時間規(guī)劃設計

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

式中：xi和yi是各個零售戶的坐標，Xk和Yk是聚類k的中心坐標。

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

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

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

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

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

（2）聚類的構造。如果所有的節(jié)點（零售戶）都已分配到相應的聚類，轉入步驟3。對于沒有分配的節(jié)點，針對每個聚類計算其加入該聚類可能產生的費用，即目標函數(shù)（3）的增量。在未被分配的節(jié)點中選擇具有最小加入費用的節(jié)點，加入到對應聚類中，并更新此聚類的中心點，重復步驟2。

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

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

4 線路優(yōu)化

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

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

5 結語

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

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

［2］王能如，何寬信，黎茶根.江西烤煙主要化學特性的適宜性評價和聚類分析［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 的物流運輸路徑動態(tài)規(guī)劃［J］.物流技術，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］.中國管理科學.2002（5）：52-57.

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

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

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

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