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

·交通運(yùn)輸·

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

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

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

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

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

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

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

（1）形成初始解。初始解滿足顧客的需求，而且所有的約束條件，如車(chē)輛載重量的限制、車(chē)輛總數(shù)的限制等也能得到滿足?；镜某跏冀鉃橹彼褪脚渌?，即不考慮線路合并的一對(duì)一的配送模式，配送中心對(duì)每個(gè)客戶的送貨點(diǎn)均指派一輛車(chē)或多輛車(chē)完成配送。

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

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

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

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

3 算法的實(shí)例驗(yàn)證

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

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

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

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

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

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

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

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

（4）確定初始配送方案，即配送中心分別派2噸和5噸的車(chē)輛對(duì)每個(gè)客戶進(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時(shí)，車(chē)輛一次載重量達(dá)到0.3+3.5+0.9=4.7，在連接任何一個(gè)客戶節(jié)點(diǎn)都將超過(guò)5噸的車(chē)輛額定載重量，所以這一條配送線路1可以最終確定下來(lái)。對(duì)剩余的客戶節(jié)點(diǎn)重復(fù)上述的合并步驟，得到最終優(yōu)化的配送方案，如圖3所示。

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

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

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

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

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

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

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

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

5 小 結(jié)

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

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

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

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

[4] 王曉博，李一軍.電子商務(wù)中物流配送路徑優(yōu)化研究[J].計(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)作中的一個(gè)重要環(huán)節(jié)，如何在物流網(wǎng)絡(luò)中綜合考慮各線路的車(chē)流量、客戶分布狀況、車(chē)輛的載重量以及其它車(chē)輛運(yùn)行限制等因素，進(jìn)行配送線路的規(guī)劃，將直接關(guān)系到配送中心運(yùn)作的成本和效率。通過(guò)對(duì)節(jié)約里程法的研究探討，對(duì)物流配送線路進(jìn)行優(yōu)化，并通過(guò)一組測(cè)試數(shù)據(jù)驗(yàn)證了算法的可行性，最后提出了復(fù)雜配送網(wǎng)絡(luò)中模型的改進(jìn)方法。

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

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-），女，廣東新會(huì)人，華南師范大學(xué)增城學(xué)院，講師，管理學(xué)碩士，研究方向：電子商務(wù)、物流管理。

1002-3100(2011)04-0113-03