薛大維，黃宏陽，劉玉偉，王凱忠

(黑龍江工程學(xué)院 汽車與交通工程學(xué)院，黑龍江 哈爾濱 150050)

?

GIS在綏化城區(qū)煙草物流配送路線優(yōu)化中的應(yīng)用

薛大維，黃宏陽，劉玉偉，王凱忠

(黑龍江工程學(xué)院 汽車與交通工程學(xué)院，黑龍江 哈爾濱 150050)

摘要：根據(jù)綏化市煙草配送和設(shè)計(jì)要求，結(jié)合當(dāng)?shù)氐穆肪W(wǎng)情況，對(duì)黑龍江省綏化市煙草配送初步設(shè)計(jì)，從而達(dá)到加快配送時(shí)間，降低成本的目的。運(yùn)用GIS軟件對(duì)綏化市煙草配送進(jìn)行配送現(xiàn)狀分析、配送區(qū)域重構(gòu)、配送方案優(yōu)化、優(yōu)化方案分析。對(duì)單配送中心和多個(gè)配送點(diǎn)的物流配送線路選擇問題進(jìn)行深入研究，并用綏化市實(shí)例驗(yàn)證此方法簡單可行，對(duì)提高企業(yè)配送效率具有重要的意義，整個(gè)物流成本中，運(yùn)輸成本占比很大，本設(shè)計(jì)內(nèi)容針對(duì)綏化市市區(qū)內(nèi)煙草配送現(xiàn)狀，實(shí)現(xiàn)配送節(jié)點(diǎn)的矢量化標(biāo)注，分析存在的問題與不足，整合配送資源，完善研究區(qū)域路網(wǎng)，合理劃分線路配送區(qū)域，提高配送能力，給出合理配送方案。

關(guān)鍵詞：GIS；煙草物流配送；配送路線優(yōu)化；配送成本

1綏化城區(qū)配送現(xiàn)狀分析

根據(jù)綏化市城區(qū)需求總量匯總表及各區(qū)域的配送里程柱狀圖，可以看出城區(qū)各區(qū)域的配送里程情況，如圖1所示。

圖1　2013年綏化市煙草需求總量

從圖1可以看出，配送區(qū)域劃分為5個(gè)區(qū)。在劃分區(qū)域中，城一、城五區(qū)明顯配送量高于其他幾個(gè)區(qū)，而城三區(qū)則配送量較少，這是綏化市城區(qū)煙草配送所出現(xiàn)的問題之一。配送區(qū)域劃分不夠合理，車輛配送可能就存在貨多車少、貨少車多的問題，因此，本文首先將綏化市北林城區(qū)進(jìn)行區(qū)域重構(gòu)，從而實(shí)現(xiàn)合理的配送安排，在合理的區(qū)域重構(gòu)情況下減少配送車輛，提高企業(yè)配送效率。

根據(jù)綏化市城區(qū)配送里程匯總表及各區(qū)域的配送里程柱狀圖和時(shí)間柱狀圖，可以看出城區(qū)各區(qū)域配送里程情況和配送時(shí)間現(xiàn)狀，如圖2、圖3所示。

圖2　2013年城區(qū)煙草配送里程現(xiàn)狀

圖3　2013年綏化市城區(qū)配送時(shí)間

通過綏化市城區(qū)配送里程與時(shí)間，可以分析出2013年綏化市煙草配送現(xiàn)狀，由圖3可見綏化市配送區(qū)域劃分為5個(gè)區(qū)域，每個(gè)區(qū)域?yàn)?條路線，從里程上可以看出從配送中心抵達(dá)城五區(qū)的配送距離較遠(yuǎn)，導(dǎo)致所需時(shí)間較長，配送總量最大，在里程、需求都較大的情況下，應(yīng)加強(qiáng)對(duì)城五區(qū)路線的安排，從而節(jié)省時(shí)間，提高使用效率。而減少城三區(qū)的配送路徑，從2013年配送現(xiàn)狀可以看出，城三區(qū)需求量、里程都較低，而配送車輛卻與需求量較高城區(qū)相同，因而本次設(shè)計(jì)對(duì)這種情況進(jìn)行了優(yōu)化。

2車輛路徑算法原理

2.1最短路徑算法

算法具體的形式包括：

1)確定起點(diǎn)的最短路徑問題：即已知起始結(jié)點(diǎn)，求最短路徑的問題。

2)確定終點(diǎn)的最短路徑問題：與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)地確定問題起點(diǎn)。

3)確定起點(diǎn)終點(diǎn)的最短路徑問題：即已知起終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。

4)全局最短路徑問題：求圖中所有的最短路徑[1-2]。

用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時(shí)被簡稱作“路徑算法”。最常用的路徑算法有：迪克斯特拉 (Dijkstra)算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法[3-5]。

2.2Dijkstra算法

Dijkstra算法是典型最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直至終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。

Dijkstra算法思想為：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合(用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 ，就將 加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了)。第二組為其余未確定最短路徑的頂點(diǎn)集合(用U表示)，按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中，保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)距離就是從v到此頂點(diǎn)的最短路徑長度，U中頂點(diǎn)的距離是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度[6-7]。

2.3Dijkstra步驟

1)初始時(shí)，S只包含源點(diǎn)，即S=v的距離為0。U包含除v外的其他頂點(diǎn)，U中頂點(diǎn)u距離為邊上的權(quán)(若v與u有邊)或u不是v的出邊鄰接點(diǎn)。

2)從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k加入S中(該選定的距離就是v到k的最短路徑長度)。

3)以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u(u U)的距離(經(jīng)過頂點(diǎn)k)比原來距離(不經(jīng)過頂點(diǎn)k)短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。

4)重復(fù)步驟2)和3)直到所有頂點(diǎn)都包含在S中。如圖4所示，設(shè)點(diǎn)A為源點(diǎn)，求點(diǎn)A到其他各頂點(diǎn)(B，C，D，E，F(xiàn))的最短路徑。線上所標(biāo)注為相鄰線段之間的距離，即權(quán)值(此圖為隨意所畫，相鄰頂點(diǎn)間的距離與圖中目視長度不能一一對(duì)等)[7-8]。

圖4　Dijkstra無向圖

3GIS在綏化城區(qū)煙草物流配送系統(tǒng)線路優(yōu)化中的應(yīng)用

GIS的技術(shù)路線及使用流程如下：

1)整個(gè)項(xiàng)目開展過程前，會(huì)對(duì)所有工作人員進(jìn)行GPS培訓(xùn)，熟悉后進(jìn)行點(diǎn)數(shù)據(jù)的采集工作，對(duì)送煙工作人員進(jìn)行GPS現(xiàn)場(chǎng)定位，對(duì)路網(wǎng)交叉點(diǎn)、配送點(diǎn)等進(jìn)行一一采集，采集工作結(jié)束后會(huì)通過GIS軟件將GPS采集到的點(diǎn)數(shù)據(jù)傳輸?shù)诫娔X軟件中，形成網(wǎng)上具體數(shù)據(jù)[9]。

2)圖層的建立以及描點(diǎn)工作的開展。在GIS軟件內(nèi)導(dǎo)入綏化城區(qū)電子地圖，構(gòu)建相關(guān)的道路圖層、商店圖層等，如圖5所示。在相關(guān)帶有圖層的電子地圖上顯示出相關(guān)的線數(shù)據(jù)、當(dāng)?shù)氐牡缆纷邉?shì)，同時(shí)進(jìn)行相關(guān)描點(diǎn)工作，如圖6所示，并輸入各個(gè)賣煙地點(diǎn)的相關(guān)信息，包括客戶編碼、店名、負(fù)責(zé)人、銷量完成?？奎c(diǎn)的圖層。

圖5　電子地圖

圖6　描點(diǎn)圖

3)配送區(qū)域的重構(gòu)，得出優(yōu)化路線。如圖7所示，將所有描點(diǎn)圖進(jìn)行分區(qū)處理，將城區(qū)分為20個(gè)配送區(qū)域，配送網(wǎng)點(diǎn)的分區(qū)處理按照一定的原則進(jìn)行人工分區(qū)，此處為人工互換實(shí)現(xiàn)，人為按照分區(qū)原則，各個(gè)區(qū)之間總量必須均勻；相關(guān)地域的地理地貌也在考慮范圍之內(nèi)；各區(qū)之間配送里程要有一個(gè)均勻值；配送網(wǎng)點(diǎn)要盡量分布均勻，通過這樣的人為分區(qū)能夠保證送貨時(shí)間、工作量大致相同。

4)對(duì)各個(gè)區(qū)域選擇不同的顏色加以區(qū)分，這樣就能得到每個(gè)城區(qū)區(qū)域的所有網(wǎng)點(diǎn)匯總，同時(shí)要求每一個(gè)區(qū)要確保配送網(wǎng)點(diǎn)在10個(gè)左右，使得配送過程中配送運(yùn)量、配送滿載率都相差較小。通過新建車輛路徑求解得出一個(gè)相對(duì)合理的配送網(wǎng)點(diǎn)配送方案，但在實(shí)際操作中還存在一些問題，所以要手動(dòng)進(jìn)行調(diào)整，依次將網(wǎng)點(diǎn)在Network Analyst窗口中提前，從而實(shí)現(xiàn)更改順序。最后，將綏化市區(qū)20條線路依次按順序?qū)氲貓D并通過Network Analyst 新建路徑方式計(jì)算出每個(gè)區(qū)域相應(yīng)配送路徑，這是通過GIS軟件自身即能夠根據(jù)相應(yīng)條件在已有的算法下實(shí)現(xiàn)的，最后得出相關(guān)路徑[10-12]。

圖7　重新分區(qū)及優(yōu)化路徑

4配送優(yōu)化后分析

圖8是綏化市城區(qū)優(yōu)化后的配送里程表柱狀圖，從圖中可以看出優(yōu)化后城區(qū)送貨路徑為20條，配送區(qū)域都是相對(duì)平均的，并且配送里程最高的城六區(qū)與最低的城一區(qū)只相差15 km，這樣可以使配送時(shí)間保持相對(duì)一致，配送里程相比較優(yōu)化前配送現(xiàn)狀已經(jīng)有了很大改善，最大與最小配送里程在縮小，而且已經(jīng)趨于穩(wěn)定。

圖9為綏化市城區(qū)優(yōu)化后配送時(shí)間表柱狀圖，由于司機(jī)不可連續(xù)工作6 h以上,但優(yōu)化前可以清楚地看出大部分工作時(shí)間為4 h以內(nèi)，這樣大量浪費(fèi)人力資源，給企業(yè)產(chǎn)生不必要的開支，員工應(yīng)該保持在4～6 h的工作時(shí)間才會(huì)不浪費(fèi)人力資源，而優(yōu)化之后配送時(shí)間幾乎保持在4 h以上，從而降低成本，同時(shí)各區(qū)域配送時(shí)間趨于穩(wěn)定，與優(yōu)化前有了很大的改善，更好地解決了車輛配送時(shí)間存在較大差異的不公平現(xiàn)象。

圖10為綏化市優(yōu)化后配送總需求量柱狀圖，可以看出優(yōu)化后每個(gè)區(qū)域安排一輛配送車輛，不僅大大減少配送中所存在的誤差，同時(shí)使優(yōu)化后的車輛配送量穩(wěn)定，車輛的滿載率得到了提升，減少了企業(yè)運(yùn)營成本的投入。

圖8　優(yōu)化后城區(qū)配送里程

圖9　優(yōu)化后配送時(shí)間

圖10　優(yōu)化后城區(qū)配送需求量

5優(yōu)化方案評(píng)價(jià)

1)配送網(wǎng)點(diǎn)覆蓋率100%。根據(jù)優(yōu)化前后的數(shù)據(jù)分析，所有的用戶都在優(yōu)化路線上，包含所有配送網(wǎng)點(diǎn)，同時(shí)沒有出現(xiàn)配送錯(cuò)誤，因此，達(dá)到了配送要求以及配送目標(biāo)，網(wǎng)點(diǎn)的覆蓋率達(dá)到100%。

2)配送總里程節(jié)約20%以上?；诔菂^(qū)優(yōu)化前和優(yōu)化后的數(shù)據(jù)分析，可以得到優(yōu)化前的車輛總配送里程為891.1 km，優(yōu)化后的車輛總配送里程為411.3 km，配送總里程節(jié)約53.8%，滿足配送總里程節(jié)約20%以上。

3)配送車輛數(shù)減少20%及以上。根據(jù)綏化城區(qū)優(yōu)化前的線路數(shù)為25條，優(yōu)化后的線路數(shù)為20條。所以配送車輛數(shù)減少20%，滿足配送車輛數(shù)減少20%及以上的要求。

6結(jié)束語

現(xiàn)有的研究成果是假設(shè)每天各區(qū)的配送量不變的情況下進(jìn)行的，并且本文的結(jié)果是經(jīng)過實(shí)際驗(yàn)證的。隨著煙草物流配送市場(chǎng)的壯大，為了提高企業(yè)的市場(chǎng)競(jìng)爭力，GIS軟件應(yīng)運(yùn)而生，其靈活、適用性強(qiáng)的車輛優(yōu)化方法得到了越來越多配送企業(yè)的青睞，尤其是隨著配送市場(chǎng)的擴(kuò)大，配送網(wǎng)點(diǎn)的數(shù)目不斷增加，各配送網(wǎng)點(diǎn)的需求情況存在越來越大的差異性，且地理分布不集中，因此，通過GIS軟件中的車輛配送功能模塊，新建車輛配送以及路徑，設(shè)計(jì)出經(jīng)濟(jì)合理的車輛配送方案，從而減少煙草配送企業(yè)運(yùn)營成本的投入[13-15]?；贕IS軟件在配送流程中的應(yīng)用，給配送企業(yè)創(chuàng)造了一個(gè)可視化的信息平臺(tái),為企業(yè)做出相關(guān)的決策與分析提供基本依據(jù),并為企業(yè)提供了良好的管理信息模塊。

參考文獻(xiàn)

[1]金江軍.第三方物流發(fā)展?fàn)顩r分析[M].北京：中國物資出版社,2013：25-30.

[2]王子平.現(xiàn)代物流煙草業(yè)獲取利潤的新亮點(diǎn)[M].北京：中國煙草出版社，2013:23-24.

[3]陳繼冶.賀州煙草優(yōu)化訪銷配送模式提高服務(wù)質(zhì)量[N].中華合作時(shí)報(bào)，2010-6-12.

[4]趙剛,張永鋒.冷鏈物流配送路徑優(yōu)化研究[C].[出版者不詳],2011：30-45.

[5]黃阿醒,李志勇.淺析GIS在物流配送的運(yùn)用[J].漳州職業(yè)技術(shù)學(xué)院學(xué)報(bào),2009,15(3)：20-26.

[6]王變利.GIS在物流配送系統(tǒng)中的應(yīng)用研究[D].焦作：河南理工大學(xué),2010.

[7]STUDLAR D T.Tobacco control: comparative politics in the United States and Canada[J].Broadview Press Ltd,2012,120(9):411-425.

[8]TEUNTER R.Lot-sizing for inventory systems with product recovery[J].Computes and Industrial Engineering,2012,120(46):431-441.

[9]白竹，金曉紅.出租車GPS數(shù)據(jù)的應(yīng)用研究[J].黑龍江工程學(xué)院學(xué)報(bào)，2014，19(4)：27-30.

[10] 張文宏.GIS在物流配送中的運(yùn)用[D].成都：西南交通大學(xué),2012.

[11] 符卓,陳斯衛(wèi).車輛路徑問題的研究現(xiàn)狀與發(fā)展趨勢(shì)[C].香港：Global-Link Publishing Company,2010:15-30.

[12] 金真,王小麗.物流信息管理[M].北京:北京電子工業(yè)出版社,2008:15-25.

[13] 鄧濤,陳瑤.基于專家系統(tǒng)的物流配送智能仿真系統(tǒng)探析[J].西南農(nóng)業(yè)大學(xué)學(xué)報(bào),2012,15(52):19-28.

[14] 莫韋嶙,譚勇,張寶華.煙草配送系統(tǒng)中路徑優(yōu)化問題[M].北京：中國物資出版社，2009：26-31.

[15] 王煥,蘭洪杰,張凱.企業(yè)配送線路的優(yōu)化分析[C].北京：中國鐵道出版社，2011：35-40.

[責(zé)任編輯：郝麗英]

Application of GIS to tobacco logistics distribution route optimization in Suihua City

XUE Dawei，HUANG Hongyang，LIU Yuwei ，WANG Kaizhong

(College of Automobile and Traffic Engineering，Heilongjiang Institute of Technology，Harbin 150050，China)

Abstract：In this paper,tobacco distribution in Suihua City,Heilongjiang Province,is preliminarily designed according to the local tobacco distribution and design requirements,and combined with the local road network,so as to speed up the time of distribution and reduce the cost of the purpose.By using GIS (Geographic Information System)software,the distribution status analysis,distribution area reconstruction,distribution scheme optimization and optimization scheme analysis are carried on for the tobacco distribution in Suihua City.The problems of single distribution center and distribution route selection of multiple distribution points are in-depth study,and one example in Suihua City is used to verify that the method is simple and feasible,which has a important significance in improving the efficiency of enterprise distribution so that the quality of service can be improved.In the whole logistics,transportation costs account for a large part of the cost of logistics.The design aims at tobacco distribution situation in Suihua City to achieve the distribution nodes vector tagging,analyze the existing problems and shortcomings,integrate the distribution resources,perfect the regional road network and arrange the distribution line region,in order to improve the ability of distribution and give a reasonable delivery scheme.

Key words：geographic information system; logistics and distribution of tobacco; delivery route optimization; distribution costs；delivery status

DOI:10.19352/j.cnki.issn1671-4679.2016.03.010

收稿日期：2015-12-17

基金項(xiàng)目：黑龍江工程學(xué)院大學(xué)生創(chuàng)新項(xiàng)目(201411802055)

作者簡介：薛大維(1972-)，男，副教授，研究方向：物流配送.

中圖分類號(hào)：P208

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1671-4679(2016)03-0037-06