李惠珠,宋海清

(11廣東工貿(mào)職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系,廣東廣州 510510;21中山大學(xué)嶺南學(xué)院,廣東廣州 510000)

基于GIS的物流配送車輛調(diào)度實(shí)現(xiàn)與應(yīng)用

李惠珠1,宋海清2

(11廣東工貿(mào)職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系,廣東廣州 510510;21中山大學(xué)嶺南學(xué)院,廣東廣州 510000)

本文指出物流配送車輛路徑 (VRP)兩類模型的局限,分析在電子商務(wù)下物流配送車輛路徑充分利用GIS的優(yōu)勢,以克服VRP數(shù)學(xué)模型求解結(jié)果的抽象性,讓車輛路徑優(yōu)化調(diào)度簡單易用,有助于物流配送企業(yè)降低物流運(yùn)輸成本。

物流配送;車輛路徑;GIS應(yīng)用

據(jù)報(bào)道,光棍節(jié)淘寶商城單日交易額9136億。艾瑞咨詢近期最新數(shù)據(jù)顯示:2010年第一季度,國內(nèi)B2C網(wǎng)上商城的銷售額已經(jīng)突破千億,是2009年的2倍多。雖然中國網(wǎng)購用戶數(shù)量已接近2億,但電子商務(wù)的滲透率只有30%,而這個數(shù)字在美國、英國達(dá)到70%以上,可見電子商務(wù)必將帶來的巨大市場和利潤。電子商務(wù)的任何一筆交易,都包含著信息流、商流、資金流和物流活動。其中信息流、商流、資金流三者都可以通過信息網(wǎng)絡(luò)完成,唯獨(dú)物流,作為眾流中最為特殊的一種,是實(shí)物的傳遞,不能通過信息網(wǎng)絡(luò)完成,必須通過把實(shí)物位置轉(zhuǎn)移到購物者中,才算完成,所以物流是完成電子商務(wù)交易過程的一個非常重要的環(huán)節(jié),是實(shí)現(xiàn)電子商務(wù)的保證。電子商務(wù)公司的配送面對的不僅有批發(fā)商和零售商,還直接面對大批的最終消費(fèi)者;同時(shí)電子商務(wù)不受時(shí)間、地域上的限制,較難形成集中的有規(guī)模的配送流量。這些都造成配送任務(wù)復(fù)雜而瑣碎,使物流配送成本居高不下[1]。要降低配送物流成本,優(yōu)化送貨路線是一條降低配送物流成本的重要途徑。

1 車輛優(yōu)化調(diào)度

優(yōu)化送貨路線問題屬于車輛路徑問題[2](Vehicle Routing Problem,VRP)。該問題由Dantzig和Ramser于1959年首次提出,因其廣泛的應(yīng)用性,國內(nèi)外學(xué)者對其進(jìn)行廣泛地理論研究與實(shí)驗(yàn)分析,綜合運(yùn)用運(yùn)籌學(xué)、管理科學(xué)、經(jīng)濟(jì)學(xué)、組合數(shù)學(xué)、計(jì)算機(jī)科學(xué)、圖論等理論知識,通過類比、演繹、推理和綜合的方法,取得一定的成果。研究VRP可以合理使用調(diào)運(yùn)工具,優(yōu)化運(yùn)輸路線,降低企業(yè)物流成本。

圖1 車輛路線問題的網(wǎng)絡(luò)圖形描述

研究車輛路徑問題 (VRP),主要有兩類模型:網(wǎng)絡(luò)圖模型和數(shù)學(xué)模型。

網(wǎng)絡(luò)圖模型 (如圖1)具有直觀性強(qiáng),容易理解而受歡迎,但對參數(shù)的容納能力有限。

數(shù)學(xué)模型[3]:對于VRP問題,一般以成本最小為目標(biāo),尋找滿足一定約束條件的解。下面先給出VRP的一般數(shù)學(xué)模型。

首先對符號說明:

cij表示從點(diǎn)i到點(diǎn)j的運(yùn)輸成本,它的含義可以是距離、費(fèi)用、時(shí)間等,本文中代表距離。

N:配送需求點(diǎn)下標(biāo)集合,即 N={1,2,…,n},其中 n為配送需求點(diǎn)數(shù)。

點(diǎn) o:為配送中心,記 N0=N∪{0}。

V:車輛下標(biāo)集合,即 V={1,2,…,k},其中 k為車輛數(shù)。

Q:每輛車的裝載容量(所有車輛的裝載容量相同)。

di:點(diǎn) i的配送需求量,我們假定

(111)為目標(biāo)函數(shù),使車輛完成配送任務(wù)的行駛總路徑最短;

(112),(113)確保每個配送需求點(diǎn)恰好被車輛訪問一次;

(114)是流守恒條件,即車輛到達(dá)某點(diǎn)后,必須離開該點(diǎn);

(115)是車輛容量限制;

(116)限制車輛路線中不含子回路;

(117)變量約束。

數(shù)學(xué)模型 (一般包含目標(biāo)函數(shù)與約束條件)具有:(i)容量大。該種模型對參數(shù)的容納能力很大,能夠表達(dá)任何大規(guī)模的問題;(ii)靈活性高。隨著實(shí)際應(yīng)用需求的出現(xiàn),數(shù)學(xué)模型的表達(dá)形式會隨著問題條件的變化而發(fā)生一些改變;(iii)通用性強(qiáng)。一旦將路徑規(guī)劃問題抽象成上述的數(shù)學(xué)模型,從模型本身就很難看出原問題所屬的領(lǐng)域,任何可以抽象成該類型模型的其他管理決策問題都可以用這類模型表示。這一特點(diǎn)也使得VRP在抽象成數(shù)學(xué)模型的過程中失去了本身問題的特征。失去了車輛路徑問題 (VRP)的問題特征,求解的結(jié)果要還原成用戶能夠理解的形式,需要尋找建模之初對這些變量所做的假定含義,這樣就造成了模型使用過程的復(fù)雜[4]。

車輛路徑問題(VRP)的網(wǎng)絡(luò)圖模型容納能力的有限性,數(shù)學(xué)模型求解結(jié)果的抽象性,使車輛路徑問題(VRP)在理論領(lǐng)域的研究較多,應(yīng)用于實(shí)際較少。為了克服數(shù)學(xué)模型求解結(jié)果的抽象性,讓求解結(jié)果能直接反映;同時(shí)借助計(jì)算機(jī)技術(shù)的發(fā)展(來計(jì)算最短路徑)與城市路網(wǎng)的成熟;由 GIS來支持車輛路徑問題(VRP)的研究。本文采用了GIS系統(tǒng)作為研究車輛路徑問題(VRP)的界面,下面對GIS系統(tǒng)進(jìn)行簡單的介紹。

2 GIS概述

GIS(Geographic Information System)中文譯名“地理信息系統(tǒng)”,是20世紀(jì)60年代發(fā)展起來的一門新興技術(shù)。它是利用現(xiàn)代計(jì)算機(jī)圖形和數(shù)據(jù)庫技術(shù)來處理地理空間及其相關(guān)數(shù)據(jù)的計(jì)算機(jī)系統(tǒng),是融地理學(xué)、測量學(xué)、幾何學(xué)、計(jì)算機(jī)科學(xué)和應(yīng)用對象為一體的綜合性高新技術(shù)。其最大的特點(diǎn)就在于:它能把地球表面空間事物的地理位置及其特征有機(jī)地結(jié)合在一起,并通過計(jì)算機(jī)屏幕形象、直觀地顯示出來。

GIS是一類獲取、處理、分析、表示并在不同系統(tǒng)、不同地點(diǎn)和不同用戶之間傳輸空間數(shù)據(jù)的計(jì)算機(jī)應(yīng)用系統(tǒng),是由計(jì)算機(jī)技術(shù)與空間數(shù)據(jù)結(jié)合而產(chǎn)生的一種高新技術(shù),它包含了地理信息的各種高級功能。以GIS為理論基礎(chǔ)和軟件開發(fā)平臺,可以實(shí)現(xiàn)交通網(wǎng)絡(luò)數(shù)據(jù)庫設(shè)計(jì)、數(shù)據(jù)輸入預(yù)處理、空間查詢與分析、網(wǎng)絡(luò)圖形和數(shù)據(jù)之間的轉(zhuǎn)換、專題地圖可視化輸出等功能。如果將GIS作為車輛調(diào)度系統(tǒng)的地理信息系統(tǒng)平臺,就可以將車輛調(diào)度的優(yōu)化算法集成到GIS平臺上。這樣,配送軟件將可以自動制訂每次的配送計(jì)劃和選擇最優(yōu)配送路線,并且實(shí)時(shí)地顯示在電子地圖上,克服了車輛優(yōu)化調(diào)度的數(shù)學(xué)模型求解結(jié)果的抽象性,可以提高工作效率和降低運(yùn)輸成本。

用戶根據(jù)自己的需求,可在電子地圖上設(shè)定行車路線,還可以同時(shí)設(shè)定多條行車路線,借助輔助路線決策、最短距離、最短路徑、單行線和禁左等功能由導(dǎo)航軟件來確定其最佳路徑,并建立路線庫,供駕駛員選擇[5]。

因此,把電子地圖與最短路徑求解結(jié)合起來是一種降低物流配送成本的理想方法。

3 問題的描述與算法的介紹

3.1 問題的描述

在實(shí)際配送中,車輛調(diào)度為非滿載的調(diào)度問題,即每個客戶的貨物不夠一整車,每輛車承擔(dān)多個點(diǎn)的運(yùn)輸任務(wù)。貨車需要到指定的幾個地點(diǎn)去卸貨。優(yōu)化的最終目標(biāo)有兩個,一個是使派車的數(shù)量最少;另一個是行駛的路程最短。據(jù)此可以將上述問題劃分為配載和路徑優(yōu)化兩個子問題。

(1)根據(jù)車輛的載重量和容積約束 (有些可能還有特殊約束,如堆碼高度等)計(jì)算最少派車數(shù)量,確定每輛車經(jīng)過的卸貨地點(diǎn)。

(2)對于每輛車單獨(dú)進(jìn)行路徑優(yōu)化,使得每輛車的運(yùn)行路徑最短。優(yōu)化的時(shí)候要根據(jù)后裝先卸的原則,即最先卸載的貨物要裝載在最外面,方便卸貨。

3.2 配送車輛行駛路線優(yōu)化和配裝優(yōu)化

車輛行駛路線的優(yōu)化問題,屬于運(yùn)籌學(xué)中廣為研究的車輛路徑問題 (VRP)。由于車輛路徑問題是NP難問題,精確算法只適用于求解小規(guī)模的問題,不能滿足實(shí)際需要。因此近年來研究人員都把主要精力放在啟發(fā)式算法上。同樣地配裝問題也是NP難問題,本研究只注重載重量和容積約束,不考慮堆碼問題。本系統(tǒng)運(yùn)用聚類算法、插入算法、節(jié)約算法、掃描分組算法這些現(xiàn)代啟發(fā)式算法來設(shè)計(jì)求解車輛行駛路線優(yōu)化問題。目的是為中小型物流企業(yè)通過仿真來尋求最短配送線路及最少派車臺數(shù)。

4 系統(tǒng)的實(shí)現(xiàn)

4.1 使用平臺簡介

筆者使用 (http:∥20211161921246/enjoyvrp/frame1htm)平臺,該平臺是一個輔助進(jìn)行車輛路徑問題研究的公共平臺。該平臺可完成如下幾點(diǎn):(1)自定義VRP問題模型;(2)整合多種高效的VRP求解算法;(3)線路規(guī)劃結(jié)果對比統(tǒng)計(jì);(4)GPS車輛實(shí)時(shí)監(jiān)控與軌跡回放。

圖2 模型設(shè)置主界面

該平臺由三部分基本功能模塊組成:VRP實(shí)驗(yàn)功能模塊、GPS車輛監(jiān)控功能模塊以及基礎(chǔ)數(shù)據(jù)維護(hù)功能模塊。其中,VRP實(shí)驗(yàn)功能模塊是本系統(tǒng)的核心,該模塊包含VRP問題模型的 (需求、車輛等條件)定義、模型瀏覽、模型求解和求解結(jié)果評價(jià)等基本功能。界面如圖2所示。

該模型主界面非常直觀,電子地圖把倉庫及需求點(diǎn)清晰顯示出,同時(shí)相關(guān)需求點(diǎn)的地理位置,需求量 (包括體積、重量及時(shí)間要求)、車輛信息及求解結(jié)果和行駛路徑都能讓人一目了然。

把相關(guān)的內(nèi)容 (需求點(diǎn)位置、需求的重量和體積、車輛信息)輸入,選擇合適的求解算法,通過計(jì)算機(jī)計(jì)算,得出配送方案。方案包括:總體的線路規(guī)劃;總路線規(guī)劃的總距離;各線路的具體距離;各線路的需求點(diǎn)順序及需求量 (包括貨物的體積與重量);具體的行車線路;貨物的重量方差及體積方差;用車的車輛信息;配送路徑還可在圖中直接顯示。在相同的條件下,由于選用的算法不同而有不同的結(jié)果,可以進(jìn)一步優(yōu)化配送路徑。

4.2 實(shí)現(xiàn)與應(yīng)用

圖3 界面顯示了用聚類算法 (編號000170)、插入算法 (編號000169)、節(jié)約算 (編號000168)法、掃描分組算法 (編號000167)對35個規(guī)劃需求點(diǎn)進(jìn)行線路規(guī)劃。左側(cè)顯示了求解結(jié)果,右側(cè)顯示了用聚類算法時(shí)各車的具體行車線路及載重。

通過選用不同的求解編號,可以顯示各種算法得出的各車的具體行車線路及各線路中所有需求點(diǎn)需求的貨物的重量和體積。

圖3 顯示用四種不同算法的計(jì)算結(jié)果及具體規(guī)劃線路

表1顯示用VRP問題的四種算法規(guī)劃線路所得的距離、容積率、載重率以及其他統(tǒng)計(jì)指標(biāo)。

表1 算例的統(tǒng)計(jì)指標(biāo)

從表1可知,本次實(shí)例的虛擬配送路徑該選擇節(jié)約算法或聚類算法推薦的行車線路,它們可達(dá)到路徑總距離較短,載重率高,所用車輛數(shù)量最少;聚類算法的距離方差較小,說明各線路的行駛距離相差不大,平衡了各線路的工作量,而重量方差和體積方差是四種算法中較小,對貨物的裝載較為均衡,有利于行車安全。掃描算法所得的距離最短,但由于多用了一臺車,且無論是載重率或容積率都不是較高的,不會作為推薦的算法,相應(yīng)的線路也不是所選的線路。

進(jìn)一步地,基于GIS的物流配送平臺還可以規(guī)劃配送路徑、提高容積率及載重率。筆者利用 (http:∥20211161921246/enjoyvrp/vrp/frame1htm)平臺展示VRP規(guī)劃的物流配送線路、實(shí)際的行車路線、配送貨物的重量和體積。

圖4顯示了聚類算法中路線4的配送線路、實(shí)際的行車路線、需求點(diǎn)配送貨物的重量和體積。電子地圖中紅色部分為線路R4的路徑,左上方框內(nèi)顯示了線路中各個需求點(diǎn)配送貨物的重量和體積及配送順序。

可見,VRP規(guī)劃的物流配送線路、實(shí)際的行車路線、配送貨物的重量和體積都可用平臺使其可視化,并且清晰具體,易于應(yīng)用。

圖4 聚類算法中路線4的配送線路、實(shí)際的行車路線、配送貨物的重量和體積

5 結(jié)束語

電子商務(wù)的快速發(fā)展,迫切地要求物流配送快速發(fā)展作保證。中國的物流企業(yè)以中小型居多,由于信息化程度不高,效率低,成本高。這些企業(yè)要在電子商務(wù)環(huán)境下有所發(fā)展,對優(yōu)化配送路徑必然要重視,可以通過上述的仿真尋求最佳配送路徑,基于GIS的配送車輛調(diào)度,可顯示化高,求解結(jié)果克服了數(shù)學(xué)模型的抽象性,具有顯示具體,清晰易用,計(jì)算速度快的特點(diǎn)。能夠達(dá)到如下目的:

(1)利用虛擬配送方案為實(shí)際的配送尋找最佳線路,是讓居高不下的物流成本下降的有效途徑。

(2)直觀且具體地顯示配送線路、實(shí)際的行車路線、配送貨物的重量和體積,可操作性強(qiáng)。

(3)通過模型的解中明細(xì)顯示車輛裝配是否均衡,有利于行車安全與貨物裝卸。

(4)軟件易于操作,適合文化知識水平不特別高的物流人員操作,而結(jié)果直觀易見且顯示具體。

綜上所述,隨著物流信息化步伐的加快和電子商務(wù)的發(fā)展,以及全球定位系統(tǒng) (GPS)的廣泛應(yīng)用,基于GIS的配送車輛調(diào)度系統(tǒng)將會有更大的發(fā)展和廣闊的應(yīng)用前景。

[1]李文生.基于電子商務(wù)下的物流配送研究[J].物流科技.2007(3):86-88.

[2]Dantzig G.Ramser J.The truck dispatching problem[J].Management Science,1959,10(6):80-91.

[3]戴錫.車輛路線問題的二階段啟發(fā)式算法及其在現(xiàn)代物流配送中的應(yīng)用[D].上海:復(fù)旦大學(xué),2004.

[4]孫麗君,胡祥培,王征.車輛路徑規(guī)劃問題及其求解方法研究進(jìn)展[J].系統(tǒng)工程,2006(24):34-41.

[5]劉志強(qiáng),丁鵬,盛煥燁.物流配送系統(tǒng)設(shè)計(jì)[M].北京:清華大學(xué)出版社,2004.

The Realization and Application of Logistics Distribution VRP Based on GIS

LI Hui-zhu1,SONG Hai-qing2
(1.Department of Computer Science,Guangdong College of Industry and Commerce,Guangzhou 510510,China;2.Lingnan College,SUN Y AT-SEN University,Guangzhou 510000,China)

In this paper,the limitations of two models of logistics distribution VRP are pointed out.The technology of GIS is analyzed according to the development of electronic commerce.Full use of the advantages of GIS is proposed to solve the problem,because it can overcome the abstractness of solution results of VRP mathematical model.By using GIS,it makes VRP easy and helps logistics distribution companies to reduce transportation costs.

Logistics Distribution;Vehicle Routing Problem(VRP);the Application of GIS

U11612

A

1008-178X(2011)02-0020-05

2011-01-29

中山大學(xué)中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助 (大規(guī)模、多車型、分路段限行的配送路線規(guī)則問題研究)。

李惠珠 (1966-),女,廣東廣州人,廣東工貿(mào)職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系講師,碩士,從事應(yīng)用數(shù)學(xué)研究。