基于節(jié)約矩陣法的配送中心送貨路線優(yōu)化問(wèn)題研究

1、基于節(jié)約矩陣法的配送中心送貨路線優(yōu)化問(wèn)題研究摘要針對(duì)物流配送中心送貨路線優(yōu)化問(wèn)題的各種算法，本文選擇適合我國(guó)物流業(yè)發(fā)展現(xiàn)狀的節(jié)約矩陣法，從而為客戶提供個(gè)性化服務(wù)。然后，詳細(xì)介紹節(jié)約矩陣法的基本思路及求解步驟，并將其用于一個(gè)現(xiàn)實(shí)問(wèn)題的求解。求解結(jié)果表明節(jié)約矩陣法可以簡(jiǎn)單有效的對(duì)我國(guó)物流企業(yè)送貨路線進(jìn)行優(yōu)化。關(guān)鍵詞送貨路線；節(jié)約矩陣法；優(yōu)化；最遠(yuǎn)插入法study of the optimization of distribution routing problem based on the economy-matrix methodabstract：based on various algorit

2、hms for logistics distribution center delivery route optimization problem, this paper chooses the saving matrix method suitable for the current development of chinas logistics industry , thus providing customers with personalized service. then this paper gives basic principle and solution steps of t

3、his method in details and used it to solve a real problem. the results showed that this method can be a simple and effective way to optimize delivery routes for chinas logistics enterpriseskeywords： distribution routing; saving-matrix method; optimization; furthest insert method1 引言物流配送是指按照用戶訂貨要求，在配

4、送中心進(jìn)行分貨和配貨，然后將貨物及時(shí)送交收貨人，其當(dāng)前趨勢(shì)是朝著小批量、多品種、多批次的即時(shí)送貨方向發(fā)展，及時(shí)滿足客戶的個(gè)性化需求1。影響物流配送體系的因素眾多，其中送貨線路的規(guī)劃是非常重要的運(yùn)營(yíng)決策，其對(duì)加快配送速度、提高物流服務(wù)質(zhì)量和降低配送成本有重要影響。然而，由于我國(guó)物流業(yè)起步晚，發(fā)展速度慢、物流行業(yè)基礎(chǔ)設(shè)施不足且技術(shù)落后，當(dāng)前我國(guó)物流企業(yè)基本處于小、少、弱、散的狀況2。此外，目前我國(guó)大部分自營(yíng)物流配送中心的運(yùn)營(yíng)現(xiàn)狀是：送貨業(yè)務(wù)量小且終端客戶多；缺乏合理的送貨規(guī)劃；缺乏送貨線路優(yōu)化軟件；物流規(guī)劃專業(yè)人才缺乏等。由于這些問(wèn)題的存在，我國(guó)物流企業(yè)尤其是中小物流企業(yè)送貨成本較高。考慮到中小物

5、流企業(yè)是構(gòu)成我國(guó)物流行業(yè)的主體，且今后較長(zhǎng)時(shí)間內(nèi)我國(guó)物流業(yè)仍將以中小物流企業(yè)為主體，因而我國(guó)物流行業(yè)迫切需要降低送貨成本，因而找到一種適合我國(guó)物流發(fā)展現(xiàn)狀而且簡(jiǎn)單實(shí)用的送貨線路優(yōu)化方法具有重要的現(xiàn)實(shí)意義。本文主要關(guān)注從物流配送中心調(diào)用多輛車滿足向各零售點(diǎn)的送貨服務(wù)，即通過(guò)為多輛車分配客戶并分別制定各輛車的合理行駛線路的多車輛路徑問(wèn)題vrp（vehicle routing problem）優(yōu)化算法的實(shí)現(xiàn)，從而快速且經(jīng)濟(jì)的將貨物送達(dá)用戶。關(guān)于多車輛路徑問(wèn)題算法的研究，國(guó)內(nèi)外學(xué)者提出了很多方法，如遺傳算法、禁忌搜索算法、模擬退火算法等3。這些算法能夠解決復(fù)雜的配送路線優(yōu)化問(wèn)題，但存在模型復(fù)雜、求解難

6、、運(yùn)算量大的缺點(diǎn)，由此限制了它們?cè)谖覈?guó)物流企業(yè)中的推廣應(yīng)用4。本文提出的節(jié)約矩陣法，已知條件較少、操作方法簡(jiǎn)單、優(yōu)化效果良好，而且可以很容易的根據(jù)送貨時(shí)間限制和其他限制進(jìn)行修改。采用節(jié)約矩陣法決定哪些貨車為哪些客戶送貨，以及確定每輛貨車的最優(yōu)送貨路線，適用于我國(guó)現(xiàn)有的中、小型物流企業(yè)5。本文運(yùn)用節(jié)約矩陣法進(jìn)行送貨線路優(yōu)化時(shí)，優(yōu)化目標(biāo)為：確定每一個(gè)參與送貨的車輛該運(yùn)多少貨物，走什么線路，送貨到哪幾個(gè)零售點(diǎn)），從而使送貨總費(fèi)用最小6。已知條件為：配送中心的位置坐標(biāo)以及擁有的車輛數(shù)；每個(gè)客戶的位置坐標(biāo)和訂貨量。限制條件為：車輛的載重能力約束；每個(gè)客戶點(diǎn)只能被一輛車訪問(wèn)。實(shí)際中可能還存在客戶對(duì)送貨時(shí)間

7、的約束，即時(shí)間窗問(wèn)題），本文暫且不涉及該約束。2 節(jié)約矩陣法由于交通運(yùn)輸是一個(gè)網(wǎng)狀結(jié)構(gòu)，因此可以把分布于這個(gè)網(wǎng)狀結(jié)構(gòu)中的配送中心和用戶假定成一個(gè)個(gè)數(shù)學(xué)上的點(diǎn)，把配送中心與用戶以及用戶與用戶之間的運(yùn)輸線路假定成一條條的線。那么，送貨線路優(yōu)化問(wèn)題就可轉(zhuǎn)化為在一個(gè)以許多“點(diǎn)”和“線”組成的“圖”中尋找各點(diǎn)與點(diǎn)間的最佳路徑問(wèn)題。設(shè)配送中心為o點(diǎn)，位置坐標(biāo)為（xo，yo）；訂貨客戶為a、b、n，位置坐標(biāo)分別為（xa，ya）、（xb，yb）（xn，yn）。節(jié)約矩陣法主要步驟如下：（1）確認(rèn)距離方陣1確認(rèn)距離方陣是要確認(rèn)任何將要經(jīng)過(guò)的兩個(gè)地點(diǎn)之間的距離。坐標(biāo)系中任意兩點(diǎn)之間的距離公式，見(jiàn)式1。 （1）式中，

8、k、m都可以取o和an之間的任意點(diǎn)。這樣，就構(gòu)造出一個(gè)n1階的距離方陣。由于兩點(diǎn)之間距離的對(duì)等關(guān)系，亦即dist(k，m)= dist(m，k)，因而該距離方陣是一個(gè)對(duì)稱陣。因此可以將其簡(jiǎn)化為上三角或下三角陣。（2）確認(rèn)節(jié)約方陣1節(jié)約方陣是指將兩個(gè)客戶的訂貨放在一輛貨車上聯(lián)合運(yùn)送時(shí)節(jié)約的累積。節(jié)約可以按照距離、時(shí)間或者貨幣來(lái)計(jì)量，本文按照距離建立節(jié)約矩陣。運(yùn)輸工具的行程依其所經(jīng)過(guò)地點(diǎn)的順序不同來(lái)確認(rèn)。oko這一行程表示始于配送中心，送貨給客戶后返回到配送中心。節(jié)約s(k，m)表示將兩個(gè)行程oko、 omo合成為一個(gè)行程okmo后而節(jié)約的距離，節(jié)約距離的計(jì)算（其中k，m的取值范圍同式1）公式，見(jiàn)

9、式2，節(jié)約方陣表見(jiàn)表1。 （2） 表1節(jié)約方陣表 客戶a客戶b客戶i客戶n客戶as(a，a)客戶bs(b，a)s(b，b)客戶is(i，a)s(i，b)s(i，i)客戶ns(n，a)s(n，b)s(n，i)s(n，n)（3）將客戶劃歸不同運(yùn)輸車輛 1將客戶劃歸到不同運(yùn)輸線路的運(yùn)輸車輛，其目標(biāo)是在完成送貨任務(wù)的同時(shí)使總的節(jié)約最大化。劃分步驟：先把每一客戶劃分到各自獨(dú)立的運(yùn)輸線路中，然后不斷把已有線路與剩下的某點(diǎn)進(jìn)行合并。合并優(yōu)先權(quán)按照兩條線路的節(jié)約距離大小加以確定，即節(jié)約越大，優(yōu)先權(quán)越高。合并可行性規(guī)則是指兩條運(yùn)輸線路上的運(yùn)輸總量不超過(guò)貨車的最大載重量。每一輛車的合并過(guò)程持續(xù)到合并不可行為止（即

10、合并運(yùn)貨量超過(guò)車輛的最大載重量），然后進(jìn)行另一輛車的合并，直到所有的客戶訂貨量都被劃歸到相應(yīng)的運(yùn)輸車輛中。（4）排定車輛的初始送貨線路 1排定送貨線路就是確定每一輛車為客戶送貨的先后順序，使車輛的以運(yùn)輸行程代表的運(yùn)輸成本最小化，排定車輛的初始送貨線路方法主要有三種：最遠(yuǎn)插入法、最近插入法和最近鄰居法。本文采用最遠(yuǎn)插入法，其基本原理為：以配送中心為運(yùn)輸線路初始點(diǎn)，以規(guī)劃到同一車輛的尚未納入運(yùn)輸線路的客戶點(diǎn)為集合，分別測(cè)算出集合中的每一點(diǎn)插入到已有線路的任何位置（起始點(diǎn)除外）后得到的線路長(zhǎng)度的增加值，從中選出最小值，即求得該點(diǎn)插入后對(duì)已有線路原有長(zhǎng)度的最小增加值；然后把集合里所有點(diǎn)的最小增加值進(jìn)行

11、比較，選取其中的最大值，并將該值對(duì)應(yīng)的客戶點(diǎn)納入已有線路，得到一個(gè)新的行程。重復(fù)進(jìn)行這一過(guò)程，直到所有屬于該線路的客戶點(diǎn)全部被納入為止。因?yàn)榫嚯x當(dāng)前線路最遠(yuǎn)的客戶被一一納入，因此這種方法被稱為最遠(yuǎn)插入法。（5）優(yōu)化初始送貨線路 在運(yùn)用最遠(yuǎn)插入法、最近插入法或最近鄰居法得到某種初始送貨線路后，可以運(yùn)用二分法或三分法對(duì)其進(jìn)行改進(jìn)，從而使運(yùn)輸行程變短，即運(yùn)輸成本變小。實(shí)際上，使用最遠(yuǎn)插入法和最近插入法（與最遠(yuǎn)插入法相反，總是把距離當(dāng)前線路最近的客戶納入）得到的初始送貨線路無(wú)需再進(jìn)行路線改進(jìn)，因?yàn)椴捎眠@兩種方法得到的送貨路線已經(jīng)是最優(yōu)路線1。但是，如果采用最近鄰居法，則需要采用二分法或三分法改進(jìn)得到最

12、優(yōu)送貨路線。3 實(shí)例某公司配送中心（dc）于某天上午收到來(lái)自12個(gè)不同客戶的訂單。配送中心及每個(gè)客戶的位置坐標(biāo)和訂貨量，見(jiàn)表2。該中心共有4輛卡車，每輛卡車的最大載重量是225單位（1單位0.1噸），采用節(jié)約矩陣法確定每輛卡車的送貨客戶及送貨線路。 表2 客戶坐標(biāo)及訂貨量 x坐標(biāo)y坐標(biāo)訂貨量配送中心-12074顧客1-5655顧客2-15768顧客3-129109顧客4-31581顧客502041顧客621774顧客74752顧客86180顧客961540顧客10720103顧客119775顧客12-12074解：運(yùn)用式1確定的距離方陣，見(jiàn)表3。表3 距離方陣dc123456789101112

13、dc0112028903178100415984051517914110620231520166071722132016540881791916111410096181222201720166010162314221998481401121281826221176131950121122142421141612579130運(yùn)用式2確定的節(jié)約方陣，見(jiàn)表4。 表4 節(jié)約方陣 12345678910111210211032115041815280510141819069131719290771214162733083761212141509021146780105101112212829168011

14、5111214253432168330121545121516141018190將客戶劃歸不同運(yùn)輸車輛。由表4可知，最大的節(jié)約來(lái)自客戶6和11，節(jié)約量為34，兩者總運(yùn)量為144，小于225，因此將6和11合并。與6或11相關(guān)的下一個(gè)最大的節(jié)約是6和7，節(jié)約量為33，三者總運(yùn)量為218，小于貨車的最大載重量225，因此將11、7、6合并。與11、7、6相關(guān)的最大節(jié)約為10和11，節(jié)約量為33，四者總運(yùn)量為287，大于225，合并不可行，停止本次合并，從而將客戶6、7和11劃歸到第一條線路。排除客戶11、6、7。接下來(lái)最大的節(jié)約來(lái)自3和4，節(jié)約量為28，兩者總運(yùn)量為177，小于貨車的最大載重量22

15、5，因此將3和4合并。與3和4相關(guān)的最大節(jié)約來(lái)自3和1，節(jié)約量為21，三者總運(yùn)量為251，大于225，合并不可行。與3和4相關(guān)的最大節(jié)約來(lái)自4和5，節(jié)約量為19，三者總運(yùn)量為258，大于225，合并不可行。與3和4相關(guān)的最大節(jié)約來(lái)自2和3，節(jié)約量為15，三者總運(yùn)量為232，大于225，合并不可行。與3和4相關(guān)的最大節(jié)約來(lái)自4和10，節(jié)約量為12，三者總運(yùn)量為246，大于225，合并不可行。與3和4相關(guān)的最大節(jié)約來(lái)自4和8，節(jié)約量為12，三者總運(yùn)量為229，大于225，合并不可行，從而將客戶3和7劃歸到第二條線路。排除客戶3、4。接下來(lái)最大的節(jié)約來(lái)自5和10，節(jié)約量為21，兩者總運(yùn)量為150，小

16、于貨車的最大載重量225，因此5和10合并。與5和10相關(guān)的最大節(jié)約來(lái)自10和12，節(jié)約量為18，三者總運(yùn)量為225，恰好為貨車的最大載重量，合并可行，從而將客戶5、10和12劃歸到第三條線路。排除客戶5、10和12。接下來(lái)最大的節(jié)約來(lái)自1和2，節(jié)約量為11，兩者總運(yùn)量為129，小于貨車的最大載重量225，因此1和2合并。剩下客戶8和9，加入客戶8，三者總運(yùn)量為181，合并可行。加入客戶9，四者總運(yùn)量為221，合并可行，從而將客戶1、2、8和9劃歸到第四條線路。排定每輛貨車的最優(yōu)送貨線路。本例采用最遠(yuǎn)插入法排定初始送貨線路，因而排定的初始送貨線路也是最優(yōu)線路。對(duì)于第一組6，7，11，最初的行程

17、只包括配送中心，長(zhǎng)度為0。納入客戶11，長(zhǎng)度增加了42；納入客戶6，長(zhǎng)度增加了40；納入客戶7，長(zhǎng)度增加了34；運(yùn)用最遠(yuǎn)插入法，首先納入客戶11得到一條新的線路（配送中、客戶11、配送中心），長(zhǎng)度為42。下一步再納入客戶6，使行程長(zhǎng)度增加至48；納入客戶7，使行程長(zhǎng)度增加至44。因此，納入客戶6，得到了長(zhǎng)度為48的一條新線路（配送中心、客戶11、客戶6、配送中心）。現(xiàn)在還剩下客戶7，因此把客戶7放在客戶6之后。因此第一條線路的優(yōu)化結(jié)果為配送中心、客戶11、客戶6、客戶7、配送中心，線路長(zhǎng)度為49，卡車載重量為218。采用同樣的方法（步驟略）可以確定出其余3條線路的最優(yōu)送貨線路，則該公司配送中心每輛卡車的線路安排，見(jiàn)表5。表5送貨行程安排 貨車送貨線路線路長(zhǎng)度每輛貨車載重量1dc1167dc492182dc34dc401773dc10512dc502254dc1829dc562214 結(jié)束語(yǔ)本文針對(duì)我國(guó)目前物流配送業(yè)務(wù)中存在的問(wèn)題，提出用節(jié)約矩陣法對(duì)我國(guó)物流企業(yè)尤其是中小物流企業(yè)的配送中心送貨線路進(jìn)行優(yōu)化，從而使以總運(yùn)輸距離最短為代表的運(yùn)輸成本最小化。通過(guò)對(duì)一個(gè)實(shí)際應(yīng)用問(wèn)題的求解，可以看出節(jié)約矩陣法操作簡(jiǎn)單且優(yōu)化效果良好，可以幫助我國(guó)物流企業(yè)降低送貨成本，對(duì)我國(guó)物流企業(yè)送貨線路的優(yōu)化與決策具有一定的實(shí)用價(jià)值。參考文獻(xiàn)1 sunil chopra，peter meindl供應(yīng)鏈管理