基于服務區域劃分優化的配送路徑規劃問題研究

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

0 引 言

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

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

1 論文總體思路綜述

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

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

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

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

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

2 配送區域動態優化及其方法

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

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

傳統的K-means聚類法，k個聚類區內，初始點是隨機產生的，運行時間長，收斂效果差。基于均衡化考慮，在配送對象分布不均勻時，用密度法效果較好，初始中心點以密度來定義，運用兩點間歐氏距離方法，求解所有對象間的相互距離，并求平均數，用mean（D）表示，確定領域半徑n是對象數目，coefR是半徑調節系數，0＜coefR＜1，經驗表明，coefR=0.13時，效果最好。如果使用平均歐氏距離還不理想，可增加距離長度，甚至用最大距離選擇法，收斂速度比較快。

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

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

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

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

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

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

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

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

3 基于改進蟻群算法的分區線路優化方法

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

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

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

3.2 用蟻群算法解決分區線路優化問題。以下用數學語言描述蟻群算法的整個過程：設螞蟻數量為m，分區內客戶數量為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）是啟發信息，d是客戶點i和j之間的距離；α和β反映了信息素與啟發信息的相對重要性；

tabuk表示螞蟻k已經訪問過的城市列表。

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

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

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

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

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

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

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

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

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

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

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

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