作者簡介：程麗紅（1995-），女，漢族，安徽亳州人，學(xué)生，南京農(nóng)業(yè)大學(xué)，交通運(yùn)輸專業(yè)。

摘要：本文針對由子庫向零售點(diǎn)配送貨物的路徑選擇問題，綜合運(yùn)用節(jié)約矩陣法、貪心算法以及旋轉(zhuǎn)掃描法選擇每輛車需要配送的零售點(diǎn)并安排配送路線，使得總運(yùn)輸距離最短進(jìn)而降低運(yùn)輸費(fèi)用。

關(guān)鍵詞：配送路線；節(jié)約矩陣法；貪心算法；車輛調(diào)度

引言

作為現(xiàn)代物流最重要的部分，運(yùn)輸引起越來越多企業(yè)的關(guān)注。運(yùn)輸距離作為影響運(yùn)輸費(fèi)用的主要因素，如何盡可能縮短運(yùn)輸距離是企業(yè)管理者正在面臨的問題。一個子庫如何配發(fā)車輛選擇合適的路徑配送貨物屬于車輛的路徑優(yōu)化問題（VRP），國內(nèi)外的學(xué)者均對此有所研究，提出了遺傳算法、掃描法、節(jié)約法以及精確算法。由于部分算法的模型復(fù)雜、運(yùn)算量較大難以求解以至于沒能被企業(yè)推廣使用。通過學(xué)習(xí)和查閱資料得知用節(jié)約矩陣算法進(jìn)行物流送貨路線優(yōu)化，可以簡單有效地求得問題的最優(yōu)解或近似最優(yōu)解，本文采用操作簡單便捷的節(jié)約矩陣法優(yōu)化配送路線，在通過軟件實現(xiàn)的過程中由于運(yùn)用節(jié)約矩陣算法進(jìn)行排序的程序代碼出錯較多，選擇用貪心算法來實現(xiàn)給各個客戶送貨的排序問題。由于貪心算法選擇最近的點(diǎn)，個別點(diǎn)會明顯增大總路線長度，因而用旋轉(zhuǎn)掃描法進(jìn)行最終的優(yōu)化。綜合運(yùn)用三個模型看似麻煩實則算法復(fù)雜度及路線優(yōu)化效果均明顯提高，具有較強(qiáng)實用性。

1.問題描述分析

該問題是對從子庫到零售點(diǎn)送貨安排路線優(yōu)化問題的研究，由子庫向50個不同需求的零售點(diǎn)配送貨物，每輛送貨車裝載量上限為160，通過制定合理的送貨線路，快速而經(jīng)濟(jì)地將子庫貨物送達(dá)用戶手中。以總的運(yùn)輸時間最短為目標(biāo)，假設(shè)速度均勻，則可轉(zhuǎn)化為總的路線長度之和最短同時要滿足的約束條件是每輛送貨車的裝載量不超過160，送到每個零售點(diǎn)的貨物不少于各自的需求量。

運(yùn)用節(jié)約矩陣法進(jìn)行送貨線路優(yōu)化時，已知條件為每個零售點(diǎn)的位置坐標(biāo)和訂貨量、子庫的位置坐標(biāo)以及擁有的車輛數(shù)；優(yōu)化目標(biāo)為確定每一個參與送貨的車輛裝載多少貨物，送貨到哪幾個零售點(diǎn)，走什么線路，使得配送距離最短從而使送貨總費(fèi)用最小。

對于網(wǎng)狀結(jié)構(gòu)的運(yùn)輸配送，把子庫和零售點(diǎn)假定成點(diǎn)，把子庫與零售點(diǎn)之間的配送路線假定成線。從而把子庫與零售點(diǎn)之間的配送運(yùn)輸路線優(yōu)化問題轉(zhuǎn)化成尋找由點(diǎn)與線組成的網(wǎng)絡(luò)圖中各點(diǎn)與各線之間的最佳路徑問題。

2.算法原理與求解

節(jié)約矩陣法的基本思想是：如果將運(yùn)輸問題中的兩個回路合并成一個回路，就可縮短配送線路總里程，并減少了一輛車。下圖為合并回路前后總里程優(yōu)化情況：

圖1兩種配送路線圖

設(shè)子庫為O點(diǎn)，位置坐標(biāo)為（xO，yO）；訂貨零售點(diǎn)為1、2、……n，位置坐標(biāo)分別為（x1，y1）、（x2，y2）……（xn，yn）。節(jié)約矩陣分析法的主要求解步驟包括：

（1）確定距離方陣。確認(rèn)距離方陣是要求出配送系統(tǒng)中子庫與各零售點(diǎn)之間的距離，在坐標(biāo)系中兩點(diǎn)之間的距離公式為：

Dist（a，b）=（xa-xb）2+（ya-yb）2（2-1）

式中a，b是0—n之間的任意數(shù)。

（2）確定節(jié)約方陣。節(jié)約方陣是指將兩個零售點(diǎn)的訂貨放在一輛貨車上聯(lián)合運(yùn)送時節(jié)約的累積，本文按照距離建立節(jié)約方陣。用S（A，B）表示由于將o-a-o、o-b-o兩個回路合并成o-a-b-o一個回路而節(jié)約的距離，由圖一可知節(jié)約方陣如下：

（3）確定每輛車配送的零售點(diǎn)。確定每輛車配送的零售點(diǎn)時，目標(biāo)是在滿足每個零售點(diǎn)的訂貨量需求以及保證每輛車不超載的前提下使總的節(jié)約距離最大。方法是首先為各個零售點(diǎn)確定單獨(dú)的配送回路，任意選擇一個零售點(diǎn)為起點(diǎn)，按照節(jié)約距離越大優(yōu)先權(quán)越高的原則優(yōu)先合并各零售點(diǎn)間的配送車輛直至車輛的最大載運(yùn)量。接著開始新的車輛配送點(diǎn)選擇直至所有零售點(diǎn)配送完成。

（4）確定每輛車的配送路線。確定每輛車所需要配送的零售點(diǎn)后需要確定為各個零售點(diǎn)配送訂單的先后順序，由于每輛車所配送的零售點(diǎn)不重疊，各配送路線間不會相互影響，因此目標(biāo)是每輛車的運(yùn)輸行程最短即可，貪心算法可以簡單有效地求得問題的最優(yōu)解或近似最優(yōu)解。

貪心算法步驟如下：（1）從點(diǎn)1出發(fā)計算點(diǎn)1與余下的n-1個點(diǎn)的距離，最短的距離為的d1、2′，相對應(yīng)的點(diǎn)記作2、；（2）計算點(diǎn)2與余下的n-2個點(diǎn)的距離，最短的距離為的d2′，3′，相對應(yīng)的點(diǎn)記作3′；…；（3）計算點(diǎn)j′與余下n-j個點(diǎn)間的距離，最小距離為dj′，（j+1）′，相對應(yīng)的點(diǎn)記作（j+1）′…；（4）最后，計算點(diǎn)（n-1）′與余下的點(diǎn)n′間的距離d（n-i）′，j′，n′，總路程：

L=d12′+∑n-1j=2dj′，（j+1）′+dn′，1′（2，3）

此算法是基于局部最優(yōu)進(jìn)而求得整體解，可能出現(xiàn)線路反復(fù)、最后返回出發(fā)點(diǎn)的距離很大等情況，故求得的整體解不一定最優(yōu)。但可以后期通過畫圖對結(jié)果進(jìn)行直觀的優(yōu)化。

（5）優(yōu)化初始送貨線線。綜合節(jié)約矩陣法和貪心算法得到的配送運(yùn)輸路線后，采用旋轉(zhuǎn)掃描法，對于明顯不合理的客戶節(jié)點(diǎn)進(jìn)一步優(yōu)化，從而得到使運(yùn)輸行程變短或運(yùn)輸成本變小的優(yōu)化送貨線路。

3.算例分析

某公司子庫為50個零售點(diǎn)配送貨物，子庫、零售點(diǎn)坐標(biāo)及訂單量等信息如下表：

4.結(jié)論

伴隨著電子商務(wù)的快速發(fā)展，運(yùn)輸在企業(yè)中發(fā)揮越來越重要的地位。本文提出了綜合節(jié)約矩陣法、貪心算法以及旋轉(zhuǎn)掃描法來解決子庫與零售點(diǎn)間車輛配送路線優(yōu)化問題。經(jīng)過對實例的分析可以驗證方法的便捷實用性，優(yōu)化效果良好，對企業(yè)的配送路線優(yōu)化具有一定的實用價值。（作者單位：南京農(nóng)業(yè)大學(xué)）

參考文獻(xiàn)：

[1]軒華.基于改進(jìn)節(jié)約法的配送路線優(yōu)化問題研究[J].物流技術(shù)，2010，Z2：94-97.

[2]王勇，吳志勇，廖明，張戰(zhàn)峰，趙鵬.物流配送車輛調(diào)度決策支持系統(tǒng)[J].重慶大學(xué)學(xué)報（自然科學(xué)版），2006，09：162-166.

[3]張宇，童瑩.物流業(yè)節(jié)約矩陣法優(yōu)化研究[J].企業(yè)導(dǎo)報，2013，01：116-117.