作者簡介：程麗紅（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è)管理者正在面臨的問題。一個(gè)子庫如何配發(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)化配送路線，在通過軟件實(shí)現(xiàn)的過程中由于運(yùn)用節(jié)約矩陣算法進(jìn)行排序的程序代碼出錯(cuò)較多，選擇用貪心算法來實(shí)現(xiàn)給各個(gè)客戶送貨的排序問題。由于貪心算法選擇最近的點(diǎn)，個(gè)別點(diǎn)會明顯增大總路線長度，因而用旋轉(zhuǎn)掃描法進(jìn)行最終的優(yōu)化。綜合運(yùn)用三個(gè)模型看似麻煩實(shí)則算法復(fù)雜度及路線優(yōu)化效果均明顯提高，具有較強(qiáng)實(shí)用性。

1.問題描述分析

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

運(yùn)用節(jié)約矩陣法進(jìn)行送貨線路優(yōu)化時(shí)，已知條件為每個(gè)零售點(diǎn)的位置坐標(biāo)和訂貨量、子庫的位置坐標(biāo)以及擁有的車輛數(shù)；優(yōu)化目標(biāo)為確定每一個(gè)參與送貨的車輛裝載多少貨物，送貨到哪幾個(gè)零售點(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)輸問題中的兩個(gè)回路合并成一個(gè)回路，就可縮短配送線路總里程，并減少了一輛車。下圖為合并回路前后總里程優(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é)約方陣是指將兩個(gè)零售點(diǎn)的訂貨放在一輛貨車上聯(lián)合運(yùn)送時(shí)節(jié)約的累積，本文按照距離建立節(jié)約方陣。用S（A，B）表示由于將o-a-o、o-b-o兩個(gè)回路合并成o-a-b-o一個(gè)回路而節(jié)約的距離，由圖一可知節(jié)約方陣如下：

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

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

貪心算法步驟如下：（1）從點(diǎn)1出發(fā)計(jì)算點(diǎn)1與余下的n-1個(gè)點(diǎn)的距離，最短的距離為的d1、2′，相對應(yīng)的點(diǎn)記作2、；（2）計(jì)算點(diǎn)2與余下的n-2個(gè)點(diǎn)的距離，最短的距離為的d2′，3′，相對應(yīng)的點(diǎn)記作3′；…；（3）計(jì)算點(diǎn)j′與余下n-j個(gè)點(diǎn)間的距離，最小距離為dj′，（j+1）′，相對應(yīng)的點(diǎn)記作（j+1）′…；（4）最后，計(jì)算點(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個(gè)零售點(diǎn)配送貨物，子庫、零售點(diǎn)坐標(biāo)及訂單量等信息如下表：

4.結(jié)論

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

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