基于節(jié)約里程法的物流配送線路優(yōu)化與改進(jìn)研究

張穎敏 （華南師范大學(xué) 增城學(xué)院，廣東 廣州 511363）

·交通運(yùn)輸·

基于節(jié)約里程法的物流配送線路優(yōu)化與改進(jìn)研究

張穎敏 （華南師范大學(xué) 增城學(xué)院，廣東 廣州 511363）

配送線路的優(yōu)化，即在確定的需求下，保證貨物準(zhǔn)時到達(dá)客戶指定地點的條件下，盡可能地減少運(yùn)輸車次和運(yùn)輸?shù)目偫锍蹋慈绾魏侠磉M(jìn)行車輛調(diào)度的問題。配送最佳線路的確定有利于提高配送效率，降低成本。

1 節(jié)約里程法的基本思想

節(jié)約里程法的基本思路是：由一輛車裝載所有客戶的貨物，沿一條優(yōu)選的線路，依次逐一將貨物分送到各個客戶，既保證客戶按時送貨又節(jié)約行駛里程，節(jié)省運(yùn)輸費用。具體實現(xiàn)如圖1所示。圖中，P為配送中心，A、B分別為需要送貨的客戶，原始的配送方案是：派兩輛車從P出發(fā)，分別到達(dá)客戶A、B后原路返回P點，其行駛路程是：2（ a+b）；節(jié)約里程法的思想是派一輛車進(jìn)行沿途分送，即從P出發(fā)到達(dá)A后再到達(dá)B進(jìn)行送貨，最后從B返回到P，其行駛路程是：a+c+b。由此可知兩種方案的里程之差是：△lij=2（ a+b）-（a+c+b）=a+b-c （△lij表示送貨到客戶節(jié)點i、j之間的節(jié)約里程），由三角形的性質(zhì)可知a+b-c必定大于零 （三角形的兩邊之和大于第三邊），即采用分送式的配送方法會產(chǎn)生里程的節(jié)約。

2 節(jié)約里程法在配送線路優(yōu)化中的應(yīng)用步驟

基于節(jié)約里程法的基本思路，在配送網(wǎng)絡(luò)中尋找這樣的三角形的回路：盡可能裝載多的貨物，且節(jié)約盡可能多的行駛里程。具體的步驟如下：

（1）形成初始解。初始解滿足顧客的需求，而且所有的約束條件，如車輛載重量的限制、車輛總數(shù)的限制等也能得到滿足。基本的初始解為直送式配送，即不考慮線路合并的一對一的配送模式，配送中心對每個客戶的送貨點均指派一輛車或多輛車完成配送。

（2）進(jìn)行節(jié)約度的計算。即計算出圖1中的△lAB=lPA+lPB-lAB，即兩個客戶之間的歷程節(jié)約度為這兩個客戶節(jié)點分別到配送中心的里程之和減去客戶節(jié)點之間的距離。

（3）對節(jié)約度從大到小進(jìn)行降序排列。

（4）進(jìn)行回路的合并。從節(jié)約度排序表找出產(chǎn)生該節(jié)約度的兩個客戶節(jié)點i、j，并判斷連接i、j的回路是否存在合并的可能性。如果一個回路以p,（）j開始，一個回路以（i,p ）結(jié)束，則該回路可以合并，并進(jìn)行下面的合并操作：刪除兩個回路中的部分路徑（p,j）和（i,p ），然后引入新的連接 （i,j）， 得到新的回路 （p,…,i,j,…,p ）。

圖1 節(jié)約里程法的基本思想

3 算法的實例驗證

本文以某物流配送中心的數(shù)據(jù)資料作為研究依據(jù)，以進(jìn)一步驗證模型的實用性。某物流配送中心P，擁有9個客戶A～（）

I，構(gòu)成的配送網(wǎng)絡(luò)如圖2所示 （其中，括號里的數(shù)字為需輸送到各地的貨物重量，線上的數(shù)字表示節(jié)點間的距離），該配送中心有最大載重量為2噸和5噸的兩種貨車。以下為節(jié)約里程法的求解過程：

圖2 配送網(wǎng)絡(luò)圖

（1）利用最短路徑法，求出網(wǎng)絡(luò)中各節(jié)點之間的最短距離。計算結(jié)果如表1所示。

表1 網(wǎng)絡(luò)節(jié)點的最短路徑

（2）計算各客戶節(jié)點之間的節(jié)約里程。根據(jù)節(jié)約里程法的基本公式 （△lij=lPj+lPj-lij，式中，P表示配送中心，i,j分別表示客戶i,j），計算各客戶間的節(jié)約里程△lij，如表2所示：

表2 客戶節(jié)點之間的節(jié)約里程數(shù)

（3）對節(jié)約里程按大小順序進(jìn)行降序排列。

（4）確定初始配送方案，即配送中心分別派2噸和5噸的車輛對每個客戶進(jìn)行一次送貨，即產(chǎn)生9條往返的配送線路PA-AP、PB-BP、PC-CP、PD-DP、PE-EP、PF-FP、PG-GP、PH-HP、PI-IP。

（5）按節(jié)約里程的大小，進(jìn)行配送線路的第一次優(yōu)化，即在滿足載重量的條件下連接F-G和F-H。可以看出，當(dāng)連接形成線路P-H-F-G-P時，車輛一次載重量達(dá)到0.3+3.5+0.9=4.7，在連接任何一個客戶節(jié)點都將超過5噸的車輛額定載重量，所以這一條配送線路1可以最終確定下來。對剩余的客戶節(jié)點重復(fù)上述的合并步驟，得到最終優(yōu)化的配送方案，如圖3所示。

圖3 最終優(yōu)化的配送線路

從示例中可以計算出，原始的一對一配送模式下，共需派9輛車，其中2噸的車輛7輛，5噸的車輛2輛，配送總里程為：2 （lPA+lPB+lPC+lPD+lPE+lPF+lPG+lPH+lPI）=2 （5+8+7+5+4+12+9+12+6）=136公里；而采用分送式配送模式經(jīng)過優(yōu)化后的方案，形成3條配送線路：P-H-F-G-P；P-I-A-B-C-P；P-D-E-P，共需派3輛5噸的車輛， 配送總里程為： （12+7+4+9）+（6+3+4+3+7）+（5+3+4 ）=67公里， 比初始一對一配送模式節(jié)省里程共69公里。

4 大型復(fù)雜配送網(wǎng)絡(luò)下的模型改進(jìn)

當(dāng)物流網(wǎng)點錯綜復(fù)雜，特別是大型的配送網(wǎng)絡(luò)下，通過使用節(jié)約里程法優(yōu)化物流配送線路總的計算工作量是非常龐大的，運(yùn)算的復(fù)雜性也隨之增加，為了能更快速地形成優(yōu)化配送線路，可以通過聚類分析法對以上的模型進(jìn)行改進(jìn)。

聚類是一個將數(shù)據(jù)集劃分為若干組或類的過程，并使得同一個組內(nèi)的數(shù)據(jù)對象具有較高的相似度，而不同組內(nèi)的數(shù)據(jù)對象則是不相似的。將聚類用于物流配送網(wǎng)絡(luò)區(qū)域劃分，可以將配送網(wǎng)絡(luò)中的節(jié)點按業(yè)務(wù)需求量或特征模式的相似性劃分為若干區(qū)域，以采取有針對性的配送策略，在市場定位、劃分等方面有廣泛的應(yīng)用。根據(jù)這一思想應(yīng)用于大型復(fù)雜物流網(wǎng)絡(luò)的配送線路優(yōu)化中，可以幫助配送企業(yè)形成其配送區(qū)域，然后再應(yīng)用節(jié)約里程法對某一規(guī)模相對小的區(qū)域進(jìn)行線路優(yōu)化。具體處理步驟如下：

（1）通過對配送企業(yè)的物流網(wǎng)絡(luò)、業(yè)務(wù)數(shù)據(jù)進(jìn)行分析，找出企業(yè)配送中最關(guān)注的指標(biāo)作為某一聚類的劃分標(biāo)準(zhǔn)。常用的指標(biāo)可以是配送業(yè)務(wù)量、貨損率、交貨期等對企業(yè)至關(guān)重要的服務(wù)指標(biāo)。

（2）應(yīng)用具體的聚類分析算法進(jìn)行物流配送區(qū)域的劃分。聚類分析的算法有很多，具體包括系統(tǒng)聚類法、模糊聚類法、K-means算法、有序樣品的聚類、分解法和加入法。其中K-means被廣泛地應(yīng)用于經(jīng)濟(jì)數(shù)據(jù)的分析，其算法簡單、運(yùn)行速度快，特別是對大數(shù)據(jù)集有很好的可伸縮性，效率相對較高，在本文研究的配送線路優(yōu)化改進(jìn)模型中使用具有明顯優(yōu)勢。

（3）對每個聚類使用前述的節(jié)約里程法進(jìn)行各個物流區(qū)域內(nèi)的配送線路進(jìn)行優(yōu)化。

5 小 結(jié)

通過以上分析，節(jié)約里程法與聚類分析法相結(jié)合，相互補(bǔ)充，較好地解決了特別是大型復(fù)雜配送網(wǎng)絡(luò)的線路優(yōu)化問題。

[1] 胡春紅，吳耀華，廖莉.物流配送車輛線路的優(yōu)化及其應(yīng)用[J].山東大學(xué)學(xué)報，2007(4):104-107.

[2] 雷同飛，張宏.物流配送中的車輛路徑優(yōu)化問題[J].商場現(xiàn)代化，2009(2):119-120.

[3] 牟燕妮.物流配送中的路徑優(yōu)化的選擇研究[D].沈陽：沈陽工業(yè)大學(xué) （碩士學(xué)位論文），2006.

[4] 王曉博，李一軍.電子商務(wù)中物流配送路徑優(yōu)化研究[J].計算機(jī)工程，2007(10):202-204.

[5] 劉丹.物流企業(yè)管理[M].北京：科學(xué)出版社，2010.

Research on Routing Optimization of Logistics Distribution Based on Saving Algorithm and its Improvement

ZHANG Ying-min (South China Normal University of Zengcheng College,Guangzhou 511363,China)

配送是物流運(yùn)作中的一個重要環(huán)節(jié)，如何在物流網(wǎng)絡(luò)中綜合考慮各線路的車流量、客戶分布狀況、車輛的載重量以及其它車輛運(yùn)行限制等因素，進(jìn)行配送線路的規(guī)劃，將直接關(guān)系到配送中心運(yùn)作的成本和效率。通過對節(jié)約里程法的研究探討，對物流配送線路進(jìn)行優(yōu)化，并通過一組測試數(shù)據(jù)驗證了算法的可行性，最后提出了復(fù)雜配送網(wǎng)絡(luò)中模型的改進(jìn)方法。

節(jié)約里程法；物流配送線路；線路優(yōu)化；聚類分析

Distribution is an important part of logistics,while routing optimization based on the constrain of car flow,distribution of customers,capacity of carriage and so on is directly influent to the cost and efficiency of distribution center.The paper research on saving algorithm,optimize the distribution route,verify the feasibility of the method,and finally propose the improvement method of this model based on complicated distribution network.

saving algorithm;logistics distribution;route optimization;clustering analysis

F506

A

2010-12-21

張穎敏（1980-），女，廣東新會人，華南師范大學(xué)增城學(xué)院，講師，管理學(xué)碩士，研究方向：電子商務(wù)、物流管理。

1002-3100(2011)04-0113-03