張 睿（無錫職業(yè)技術學院，江蘇 無錫 214073）

0 引 言

流通領域中，許多物流配送企業(yè)借助外部經(jīng)濟的發(fā)展，實現(xiàn)了規(guī)模擴張與快速發(fā)展，但對如何控制成本，提高運營效率的迫切性并不強?，F(xiàn)在隨著經(jīng)營環(huán)境的變化，物流需求量更大，客戶、網(wǎng)絡更復雜，對服務的要求更多樣化。但面臨的競爭更加激烈，不管是從事跨區(qū)域配送還是城市配送，首先需要考慮顧客服務水平，贏得客戶的認可，然后考慮配送運營的成本問題，因而如何創(chuàng)新物流服務，提高運營效率和控制日常運營成本成為每個配送企業(yè)需要時刻思考的問題。

傳統(tǒng)的基于經(jīng)驗的方法，在企業(yè)規(guī)模有限，客戶數(shù)量不是非常多，配送網(wǎng)絡相對簡單的情況下，只要員工和管理者技能過關，執(zhí)行力好，都應該能夠較好地完成配送任務，獲得企業(yè)的發(fā)展。但是隨著銷售區(qū)域擴大，客戶數(shù)量的不斷增加，客戶需求持續(xù)增長，配送業(yè)務量大增，配送周期縮短，配送線路更復雜，并且需求的隨機性、變動性加大，光憑經(jīng)驗和手工安排，已無法做到配送計劃的優(yōu)化，必須借助于統(tǒng)計分析、利用數(shù)學模型和智能算法，才能獲得較好的配送計劃，節(jié)省時間，提高效率。本文就是針對這些問題，從企業(yè)應用的角度，提出先合理劃分配送區(qū)域，再優(yōu)化配送路線的方法，從而達到降低成本，提高競爭力的目標。

1 論文總體思路綜述

排單和車輛調(diào)度是整個配送計劃和作業(yè)實施的核心，是配送任務和客戶服務按時完成的有力保證。

傳統(tǒng)的訂單排單和車輛調(diào)度、路線安排都是由公司里業(yè)務能手來完成，送貨區(qū)域大了，客戶多了，這項工作的效率和完成工作的成本控制都會不理想，現(xiàn)在常用的智能優(yōu)化方法，把它作為一個典型的VSP問題，建立數(shù)學模型，利用智能化的算法，求解可行的配送路徑規(guī)劃，作為理論研究，這樣的做法是有意義的。但是有兩個問題：（1）這個模型數(shù)據(jù)的收集整理工作量特別大，計算過程也較長，因而成本不會低。（2）模型本身一定要適合實際的作業(yè)過程，這就需要有一個不斷測試和優(yōu)化的過程，并且還要適應每天的動態(tài)變化，否則反而會影響到日常的作業(yè)過程。許多研究理論完備、精深，但是在適應產(chǎn)業(yè)化運營時，工程上的可實現(xiàn)性還有待提高和完善。因而影響了這些很有價值的研究在企業(yè)實際中的運用。

本文的研究并不針對配送路徑規(guī)劃做理論上的深究，而是立足實際應用，在可接受的范圍內(nèi)，利用較簡易實用的智能優(yōu)化方法，在較短的時間內(nèi)，以較低的成本獲得相對優(yōu)化的配送路徑規(guī)劃方案。不求最佳，但求有效。為今后電子排單和送貨線路優(yōu)化軟件的開發(fā)和應用作必要的鋪墊。

具體設想：第一步，利用聚類分析法對配送區(qū)域進行合理分區(qū)，先把復雜問題簡單化。第二步，每個分區(qū)內(nèi)就是個典型的TSP問題，有很成熟的解決辦法。在平衡好各分區(qū)工作時間安排后，就能很快獲得較理想的配送方案。

重點是第一步，分區(qū)時一定要考慮到客戶位置、需求量、車輛載重、作業(yè)時間均衡限制等因素，需要花費好多功夫。

2 配送區(qū)域動態(tài)優(yōu)化及其方法

2.1 配送區(qū)域的初始劃分方法。配送區(qū)域優(yōu)化方法對最終優(yōu)化的結果有很大的影響，因而合理的劃分方法的選擇十分重要，目前常用的劃分方法有掃描法和聚類算法，在配送客戶有限、區(qū)域較小時運用掃描法就可以了，但是當客戶數(shù)量很多，區(qū)域較大，又要考慮約束條件時，聚類算法就是我們必然的選擇了，聚類算法中K-means比較成熟，操作簡單，原理是：把大量d維（二維）數(shù)據(jù)對象n個聚集成k個聚類（k＜n），使同一聚類內(nèi)的對象相似性最大，不同聚類內(nèi)的對象相似性盡量的小。利用聚類算法分區(qū)可以使配送區(qū)域的劃分比較緊密并且實用。

在運用聚類分析法時有幾個問題要注意：第一，k的選擇，以一天送貨總量/單車載重量，也可以放寬一些，到：一天送貨總量/單車載重量+1。第二，k個聚類內(nèi)的密度，分區(qū)密度大，效率高，成本低。第三，每個分區(qū)內(nèi)工作時間大體相當，這樣便于運行的穩(wěn)定，進行成本控制和人員、車輛的考核。第四，每個聚類間不重合。做到這樣分區(qū)效果會比較好。

傳統(tǒng)的K-means聚類法，k個聚類區(qū)內(nèi)，初始點是隨機產(chǎn)生的，運行時間長，收斂效果差?；诰饣紤]，在配送對象分布不均勻時，用密度法效果較好，初始中心點以密度來定義，運用兩點間歐氏距離方法，求解所有對象間的相互距離，并求平均數(shù)，用mean（D）表示，確定領域半徑n是對象數(shù)目，coefR是半徑調(diào)節(jié)系數(shù)，0＜coefR＜1，經(jīng)驗表明，coefR=0.13時，效果最好。如果使用平均歐氏距離還不理想，可增加距離長度，甚至用最大距離選擇法，收斂速度比較快。

在配送對象分布較均勻時，可考慮用網(wǎng)格法，效果較好，整個配送區(qū)域劃分用k=Q/q，k為初始點個數(shù)，假設k=mn，將地圖劃分成m行n列，以每格中心點為初始點，通過網(wǎng)格內(nèi)的反復聚類運算，達到收斂，獲得網(wǎng)格穩(wěn)定的聚類中心。

2.2 分區(qū)內(nèi)配送工作量的均衡。這樣就完成了配送區(qū)域的初步劃分，但是沒有考慮各個分區(qū)內(nèi)工作量的均衡問題，如果工作量不均衡，對于客戶服務水平的保證，成本的控制，作業(yè)的安排，人員、車輛的考核都存在問題。

在實際的物流企業(yè)配送作業(yè)過程中，一般一輛車一天也就送貨10多家或20來家，多余的時間要用于收款，與公司財務部門交賬，核算出車相關費用，所以不考慮同一車同一天出車多次的情況，多次出車待以后深入探討。那么就意味著每個分區(qū)就是一輛車一條線路，把問題大大簡化了，需要說明的是：這種方法對于配送規(guī)模不是特別大的單個城市配送是適用的，也具有廣泛性。

各分區(qū)內(nèi)的每日配送工作量是以配送作業(yè)耗用時間來衡量的，耗用時間有兩部分構成：（1）車輛行駛時間；（2）客戶服務時間。由于配送分區(qū)有限，每個分區(qū)內(nèi)的客戶數(shù)量不是很多，可以采用實地測時的方式，把每條線路的配送時間統(tǒng)計出來，這是一種手工辦法，但比較符合實際，各線路時間分別為T1,T2,T3,T4,…,Tk，從中選出最大值Tmax，最小值Tmin，用經(jīng)驗法確定允許的差值，然后來調(diào)整超過差值的分區(qū)內(nèi)的客戶，從而使得各區(qū)作業(yè)時間基本均衡。

如果客戶數(shù)量眾多，分區(qū)也較復雜，就需要借助統(tǒng)計學方法，通過對樣本線路車輛行駛時間以及服務時間，擬合出分區(qū)作業(yè)時間函數(shù)，然后，計算出所有線路作業(yè)時間，即使分區(qū)重新調(diào)整，線路重新組合，仍可以很快計算出線路作業(yè)時間。本文不在這個方面進行深入探討。

2.3 重新組合客戶，確定最終區(qū)域劃分。觀察各線路作業(yè)時間超過允許差值的部分，由大到小來調(diào)整，將離聚類中心最遠的數(shù)據(jù)點彈出，使本區(qū)T值下降，直至在差值以內(nèi)，將彈出點加入到臨近的不足均衡作業(yè)時間的分區(qū)內(nèi)，如果臨近分區(qū)作業(yè)時間超過允許差值，這個點就不能彈出，只能彈出另外的次遠數(shù)據(jù)點，以此類推，任何一個數(shù)據(jù)點只能彈出一次，直到所有數(shù)據(jù)點和分區(qū)調(diào)整完畢。

這樣最終確定的分區(qū)，既能做到區(qū)域劃分緊密，效率、成本更低，又能做到各區(qū)作業(yè)時間均衡，便于工作指派，車輛、人員核算。

以上是本文的第一部分工作，也是最有意義的工作，確定好合理的區(qū)域劃分，不僅是配送作業(yè)合理化的重要步驟，也是業(yè)務人員訪銷工作和客戶服務的重要依據(jù)。

3 基于改進蟻群算法的分區(qū)線路優(yōu)化方法

分區(qū)內(nèi)線路安排，就是一輛送貨車由DC出發(fā)，依次經(jīng)過分區(qū)內(nèi)每一個客戶點，完成送貨后返回DC，求出近似最優(yōu)的行車順序，這是個典型的旅行商問題（Traveling Salesman Problem，TSP），TSP是NP完全問題，解法很多，有精確算法，也有啟發(fā)式算法，目前許多智能算法就屬于啟發(fā)式算法，可以解決較復雜的線路優(yōu)化問題，對于一般線路優(yōu)化也能做得更準確，這里介紹蟻群算法解決實際問題。原因是蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有較強的魯棒性和搜索較好解的能力，是一種分布式的并行算法，一種正反饋算法，易于與其它方法結合?？朔舅惴ㄈ秉c，改善算法性能。

3.1 蟻群算法簡介。蟻群算法（Ant Colony Algorithm,ACA）是由意大利學者M.Dorigo等人于20世紀90年代初提出的一種新的模擬進化算法，其真實地模擬了自然界螞蟻群體的覓食行為。M.Dorigo等人將其用于解決旅行商問題TSP，并取得了較好的實驗結果。

蟻群算法用于解決優(yōu)化問題的基本思路是：用螞蟻的行走路徑表示待優(yōu)化問題的可行解，整個螞蟻群體的所有路徑構成待優(yōu)化問題的解空間。路徑較短的螞蟻釋放的信息素數(shù)量較多，隨時間推移，較短路徑上積累的信息素濃度逐步增高，選擇該路線的螞蟻數(shù)量也越來越多，最終整個螞蟻會在正反饋的作用下集中到最佳線路上，這個路線就是最有解。

3.2 用蟻群算法解決分區(qū)線路優(yōu)化問題。以下用數(shù)學語言描述蟻群算法的整個過程：設螞蟻數(shù)量為m，分區(qū)內(nèi)客戶數(shù)量為n，m≤n，客戶點i與客戶點j之間距離用dij（i,j=1,2,3,…,n）表示，t時刻i與j連接路徑上的信息素濃度為τij（t）。初始時刻各路徑上的信息素濃度相同。

位于客戶點i的第k只螞蟻選擇客戶點j的概率為：

其中：

τ（i,j）表示邊（i,j）上的信息素濃度；

η（i,j）是啟發(fā)信息，d是客戶點i和j之間的距離；α和β反映了信息素與啟發(fā)信息的相對重要性；

tabuk表示螞蟻k已經(jīng)訪問過的城市列表。

當所有螞蟻完成周游后，按以下公式進行信息素更新。

其中：ρ為小于1的常數(shù)，表示信息的持久性。

其中：Q為常數(shù)；lk表示第k只螞蟻在本次迭代中走過的路徑，Lk為路徑長度。

蟻群算法解決TSP問題具體步驟：（1）基本參數(shù)設置：包括螞蟻數(shù)m，信息素重要程度因子0≤α≤5，啟發(fā)函數(shù)重要因子1≤β≤5，信息素消逝參數(shù)0.1≤ρ≤0.99，信息素釋放總量10≤Q≤10 000，最大迭代次數(shù)iter_max，迭代次數(shù)初值iter=1。用試驗方法確定α、β、ρ、Q值，以獲得較優(yōu)的組合，有助于改進基本蟻群算法，提高整體優(yōu)化效果，并縮短運算時間。（2）初始解的求解：利用最近鄰算法，以縮短算法運算時間，并以此算法產(chǎn)生初始解的路徑長度作為產(chǎn)生初始信息素的基礎。（3）構建解空間：將各個螞蟻隨機地置于不同出發(fā)點，對每個螞蟻，按公式（1）計算其下一個待訪問的網(wǎng)點，直到所有螞蟻訪問完區(qū)域內(nèi)所有網(wǎng)點。（4）更新信息素：計算各個螞蟻經(jīng)過的路徑長度Lk（k=1,2,…,m），記錄當前迭代次數(shù)中的最優(yōu)解。同時，根據(jù)（2）式和（3）式對各個網(wǎng)點連接路徑上的信息素濃度進行更新。（5）判斷是否終止：若iter＜iter_max，則令iter=iter+1，清空螞蟻經(jīng)過路徑的記錄表，并返回步驟2，否則終止計算，輸出最優(yōu)解。

蟻群算法如結合其他啟發(fā)式算法，建立混合算法，能夠解決許多現(xiàn)實問題，達到較好運算效果，結合具體問題，可以深入研究。

4 本文的局限與進一步研究的方向

本文的研究更多地從實際運用和操作的便利角度出發(fā)，因而力求方法簡便，運算效率較高，然而實際問題遠比設想復雜，物流系統(tǒng)的優(yōu)化應該是整體性的優(yōu)化。本文只是做了配送區(qū)域的合理劃分，在此基礎上，對區(qū)域內(nèi)配送路徑進行優(yōu)化，只是送貨過程的優(yōu)化，完整的過程還包括客戶服務水平，合理的庫存水平，以及配送中心選址，服務地點（卸貨點）的設置等，只有這些因素都考慮到了，才能真正實現(xiàn)配送系統(tǒng)的優(yōu)化。另外，還有靜態(tài)分析和動態(tài)分析的區(qū)別，大區(qū)域劃分保持相對靜態(tài)，區(qū)域間根據(jù)每日具體的業(yè)務需求做必要的動態(tài)調(diào)整，這部分可借助人工安排，也可參考軟件，保持一定的靈活性。整個配送系統(tǒng)的研究千頭萬緒，在進一步的研究中，首先需要把銷售系統(tǒng)的優(yōu)化結合進來，客戶前端的需求和庫存決定著后面的訂單以及配送，業(yè)務員對零售網(wǎng)點的訪銷，一方面對接客戶服務，體現(xiàn)公司的客戶服務水平，另一方面，對接訂單的處理以及最終的配送工作，業(yè)務人員訪銷作業(yè)的系統(tǒng)性安排，以及客戶、配送中心信息的一體化都有賴于業(yè)務訪銷與配送作業(yè)的綜合優(yōu)化。

因而，配送區(qū)域合理劃分、送貨線路優(yōu)化以至于整個物流系統(tǒng)，銷售系統(tǒng)、供應系統(tǒng)的不斷優(yōu)化，對于物流企業(yè)、社會物流以及整個經(jīng)濟運行系統(tǒng)是非常有意義的，對于眾多轉(zhuǎn)型中，缺乏專業(yè)知識和技術的中小物流企業(yè)，有著普遍意義，值得重視。

[1] 陳子俠,等.杭煙物流與送貨路線優(yōu)化[J].物流技術，2003(8):38-40.

[2] 王勇，池吉.物流配送路線及配送時間的優(yōu)化分析[J].重慶交通大學學報，2008(4):647-650.

[3] 楊弋，顧幸生.物流車輛優(yōu)化調(diào)度的綜述[J].東南大學學報，2003（增刊）:105-111.

[4] 陳文，鄭少鋒.基于蟻群算法的配送路徑規(guī)劃研究[J].物流科技，2013(7):45-47.