張 睿（無(wú)錫職業(yè)技術(shù)學(xué)院，江蘇 無(wú)錫 214073）

0 引 言

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

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

1 論文總體思路綜述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

位于客戶點(diǎn)i的第k只螞蟻選擇客戶點(diǎn)j的概率為：

其中：

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

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

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

當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。

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

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

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

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

4 本文的局限與進(jìn)一步研究的方向

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

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

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

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

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

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